Google CTF 2022 - Segfault Labyrinth
by Jeremias Gomes
Table of Contents
- Introduction
- Summary Information
- Overview
- Strategies and Solutions
- Final Considerations
- Codes
- References
Introduction
In this write-up I will describe the journey to finish one of the challenges from
Google CTF 2022 called Segfault Labyrinth in the reversing engineering
miscellaneous category. The idea of this write-up is to cover mainly how to
approach and understand a striped binary.
Summary Information
-
Name: Segfault Labyrinth
-
Author: Calle “Zeta Two” Svensson
-
Category: misc
-
Description: Be careful! One wrong turn and the whole thing comes crashing down
-
Host: segfault-labyrinth.2022.ctfcompetition.com
-
Port: 1337
Overview
In-Depth Analysis
The challenge provides a binary called challenge that is a stripped ELF
64-bit. A stripped binary is a program without any debugging symbols. It is
normally used to reduce the size of the files and make the life of reversing
engineers a living hell more difficult (and also responsible for most part
of my headaches). First things first, checking the security settings using
checksec, it returns the following:
[19144] j3r3mias@serenity:misc-segfault-labyrinth > checksec --file challenge [*] '/CTF/2022-google-ctf/misc-segfault-labyrinth/challenge' Arch: amd64-64-little RELRO: Partial RELRO Stack: No canary found NX: NX disabled PIE: PIE enabled RWX: Has RWX segments
In this output a big thing to pay attention is that the binary has writable
segments meaning that probably mmap is being called to create pages with
permissions that allow us to write and execute code. Besides that it also has
executable stack (NX disabled) and no presence of canary, what is a good thing
in a challenge with “segfault” in the name. Trying to execute the binary, this
is the output:
[19654] j3r3mias@serenity:misc-segfault-labyrinth > ./challenge Welcome to the Segfault Labyrinth AAAA ^C ✘ [19655] j3r3mias@serenity:misc-segfault-labyrinth >
There is a message of welcome and the binary hangs waiting for an input and
nothing more. Then it’s morbin reversing time! I chose to use IDA that has
a very useful disassembly feature. Because the binary is stripped and has no
symbols to provide any help, I renamed a lot of variables in the decompiled
code creating a context that helped me to understand better what is what. I will
show some snippets and you can read the full
code at the end of this article.
The first thing the program does is to open /dev/urandom, and then it creates
a page with 0x1000 bytes that is allowed to read and write content (third
parameter).
urandom_fd = fopen("/dev/urandom", "r");
if ( urandom_fd )
{
corridor = 10LL;
labyrinth = mmap(0LL, 0x1000uLL, 3, 34, -1, 0LL);
labyrinth_p = labyrinth;I renamed this variable to labyrinth because this pointer is the entry point
for us to the challenge. The second variable (with value 10) I called corridor
that represents the number of corridors the labyrinth will have after the
construction. From this point ahead all snippets are part of a big while loop
that when some condition do not holds, the program ends the execution. If you
check the original
code
from the creator of the challenge, the code organization is very different
(modular functions, constants, etc) but we need to fight with the weapons we
have.
The next part read a byte from urandom and limit the value from 0 to 15,
saving the value in ptr[0] (I could not decide a better name to this variable).
v6 = fread(ptr, 1uLL, 1uLL, urandom_fd);
random_value_0_15 = ptr[0] & 0xF; // restrict random
LOBYTE(ptr[0]) &= 0xFu;
if ( v6 != 1 )
break;
for ( i = 0LL; i != 16; ++i )
{
v9 = random_value_0_15 == i;
rand_var = rand(); // ! srand not found in the code (?)
door = mmap((void *)(((__int64)rand_var << 12) + 0x10000), 0x1000uLL, 3 * v9, 34, -1, 0LL);
labyrinth_p[i] = door;
if ( !door)
{
fwrite("Error: failed to allocate memory.\n", 1uLL, 0x22uLL, stderr);
goto LABYRINTH_FAIL;
}
random_value_0_15 = ptr[0]; // useless?
}
labyrinth_p = (_QWORD *)labyrinth_p[LOBYTE(ptr[0])];
if ( !labyrinth_p )
goto LABYRINTH_FAIL;
if ( !--corridor )
{
... After that, it starts a loop of 16 iterations (using i as the counter) where
it checks if the value of i is the same as the picked value in
random_value_0_15 and save the result in v9 (consider this a boolean (0 or
1)). Then it picks a value from rand and save it in rand_var. The BIG
observation here is that rand was not seeded (remember this for
later). Thereafter a page is created (called
here door) where the starting address is calculated using rand_var with the
bits “left-shifted” 12 positions. Also the protections of this page uses v9 * 3
and if this result is 1, then the protection will be the value 3 that is
PROT_READ and PROT_WRITE, and if the value is 0, the protection is
PROT_NONE (pages cannot be accessed) (again, check the
original
to see how different a decompiled code can be probably (but not only) because of
flag optimizations).
Outside the loop, the only door with writable attributes is set in
labyrinth_p. This is the access point to the next corridor. Also, after
that, it checks if corridor is zero. While not, the loop starts again creating
a new corridor (using the current access point as a reference) with new 16 doors
where only a single door will have writable attributes again. This pattern
continues until the last corridor (0) when the if finally branch in.
if ( !--corridor )
{
fclose(urandom_fd);
flag_fd = fopen("flag.txt", "r");
flag_fd_p = flag_fd;
if ( flag_fd )
{
if ( fread(labyrinth_p, 1uLL, 0x1000uLL, flag_fd) )
{
fclose(flag_fd_p);
shellcode = (void (__fastcall *)(_QWORD))mmap(0LL, 0x1000uLL, 7, 34, -1, 0LL);
shellcode_p = shellcode;
if ( shellcode )
{
clear_registers_size = &clear_registers_end - (_UNKNOWN *)clear_registers;
memcpy(shellcode, clear_registers, &clear_registers_end - (_UNKNOWN *)clear_registers);
puts("Welcome to the Segfault Labyrinth");Now, after the last corridor, the flag is written to the last writable door.
Then the code allocates a page to receive our shellcode right after a part that
clears all “useful” registers of the program, except for RDI. This
clear_registers were found in .data and renamed properly.
.data:0000000000004088 ; =============== S U B R O U T I N E ==============
.data:0000000000004088
.data:0000000000004088 clear_registers proc near
.data:0000000000004088 xor rax, rax
.data:000000000000408B xor rcx, rcx
.data:000000000000408E xor rdx, rdx
.data:0000000000004091 xor rbx, rbx
.data:0000000000004094 xor rsi, rsi
.data:0000000000004097 xor rsp, rsp
.data:000000000000409A xor rbp, rbp
.data:000000000000409D xor r8, r8
.data:00000000000040A0 xor r9, r9
.data:00000000000040A3 xor r10, r10
.data:00000000000040A6 xor r11, r11
.data:00000000000040A9 xor r12, r12
.data:00000000000040AC xor r13, r13
.data:00000000000040AF xor r14, r14
.data:00000000000040B2 xor r15, r15
.data:00000000000040B2 clear_registers endp
Finally the program send the first output that is the welcome message.
puts("Welcome to the Segfault Labyrinth");
ptr[6] = 0xE701000015LL;
ptr[0] = 0x400000020LL;
...
v22 = 23;
v23 = ptr;
if ( prctl(38, 1LL, 0LL, 0LL, 0LL) )
{
perror("prctl(NO_NEW_PRIVS)");
}
else if ( prctl(22, 2LL, &v22) )
{
perror("prctl(PR_SET_SECCOMP)");
}After the message, there are a lot of constant numbers set in ptr. I did not
dug further what is each number. What I did was use one of the tools the CTF
provided to help us that is Google. Throwing some
number there, it returned values used in
seccomp (it provides a secure state of
the calling process dealing with system calls). Then I used seccomp-tools to
collect the rules seccomp is applying to the program. This is the output:
[19703] j3r3mias@serenity:misc-segfault-labyrinth > seccomp-tools dump ./challenge Welcome to the Segfault Labyrinth line CODE JT JF K ================================= 0000: 0x20 0x00 0x00 0x00000004 A = arch 0001: 0x15 0x01 0x00 0xc000003e if (A == ARCH_X86_64) goto 0003 0002: 0x06 0x00 0x00 0x00000000 return KILL 0003: 0x20 0x00 0x00 0x00000000 A = sys_number 0004: 0x15 0x00 0x01 0x0000000f if (A != rt_sigreturn) goto 0006 0005: 0x06 0x00 0x00 0x7fff0000 return ALLOW 0006: 0x15 0x00 0x01 0x000000e7 if (A != exit_group) goto 0008 0007: 0x06 0x00 0x00 0x7fff0000 return ALLOW 0008: 0x15 0x00 0x01 0x0000003c if (A != exit) goto 0010 0009: 0x06 0x00 0x00 0x7fff0000 return ALLOW 0010: 0x15 0x00 0x01 0x00000000 if (A != read) goto 0012 0011: 0x06 0x00 0x00 0x7fff0000 return ALLOW 0012: 0x15 0x00 0x01 0x00000009 if (A != mmap) goto 0014 0013: 0x06 0x00 0x00 0x7fff0000 return ALLOW 0014: 0x15 0x00 0x01 0x0000000b if (A != munmap) goto 0016 0015: 0x06 0x00 0x00 0x7fff0000 return ALLOW 0016: 0x15 0x00 0x01 0x00000005 if (A != fstat) goto 0018 0017: 0x06 0x00 0x00 0x7fff0000 return ALLOW 0018: 0x15 0x00 0x01 0x00000004 if (A != stat) goto 0020 0019: 0x06 0x00 0x00 0x7fff0000 return ALLOW 0020: 0x15 0x00 0x01 0x00000001 if (A != write) goto 0022 0021: 0x06 0x00 0x00 0x7fff0000 return ALLOW 0022: 0x06 0x00 0x00 0x00000000 return KILL [19704] j3r3mias@serenity:misc-segfault-labyrinth >
The process has its syscalls restricted to rt_sigreturn, exit_group,
exit, read, mmap, munmap, fstat, stat and write. The next part of
the program read a value to ptr that is the length of our payload.
for ( j = 0LL; j <= 7; j += read(0, ptr, 8 - j) )
;
if ( j == 8 )
{
ptr[0] %= (unsigned __int64)(4096 - clear_registers_size);
v18 = ptr[0];
if ( !ptr[0] )
goto RUN_SHELLCODE_LABEL;
do
corridor += read(0, (char *)shellcode_p + clear_registers_size, v18 - corridor);
while ( v18 > corridor );
if ( ptr[0] != corridor )
{
fwrite("Error: failed to read code. Exiting.\n", 1uLL, 0x25uLL, stderr);
return_code = -1;
}
else
{
RUN_SHELLCODE_LABEL:
shellcode_p(labyrinth);
}
}Then our payload is written to the first position after clear_registers and if
everything is OK the shellcode is called.
Summarizing
The main idea of the program is create a labyrinth of corridors where a single
door Dn in a corridor Cm (where n is a random number and m is the number
of the corridor) points to the beginning of the next corridor and continues so
on until it reaches the flag. The following image illustrate this behavior:
And also the program receive a payload as input that is restricted to a few syscalls.
Strategies and Solutions
Once we get the core idea of the binary, there are two approachable strategies to the challenge, that I believe follows what the creator intended to do: (01) Explore the Labyrinth and (02) Rage Against the Random. As a bonus, there will be a third one that I called the (03) Lazy CTF Player.
01 - Explore the Labyrinth
For me, this is the clear one. When you run the program, the payload will be
combined with clear_registers that let us with only a single address in the
register RDI. This address is the entry point of the labyrinth. To check this
statement, the image below shows an execution where the payload have multiple
INT3 (\xcc) instruction which throws a
SIGTRAP in the debugger.
Now the target is clear, we need a payload that travels through the doors in a
corridor until we find the one that has writable permissions. To test if a
memory location is writable, we need to use one of the syscalls available to
us. There are two promising ones (stat and write). In short:
-
stat- Return information about a file, in the buffer pointed to bystatbuf. -
write- Writes upNbytes from the buffer starting at a position in the file referred to by the file descriptorfd.
In both cases, when the address is not accessible, it returns an EFAULT.
EFAULT is when you try to access or write in a bad address or an outside of
your accessible address space. To this solution, I choose to use stat. The
payload has three parts: Check Doors, Explore Every Corridor and Read the
Flag.
Check Doors
Given a corridor, check each door (address) trying to find which one is writable. Since every corridor has only one door that give access to the next corridor, I used an infinite loop that breaks when the correct one is found.
; Use r15 as the reference to explore
mov r15, rdi
; while (1)
doors_loop:
mov rdi, [r15]
; Use a position after our payload
lea rsi, [rip + 0x300]
mov rax, 4
syscall
; compare the return with EFAULT (-14)
cmp rax, -14
jne doors_end_loop
add r15, 8
jmp doors_loop
doors_end_loop:The code uses R15 as a reference to explore, copy the address to be checked to
RDI and call stat (value 4 in RAX). After that, check if the returned
value is equal to EFAULT (-14) and ends the loop when the writable address is
found.
Explore Every Corridor
We also know that with this approach, all corridors need to be traveled. Then
this part of the code is basically a for loop from 10 to 0, using EBX as a
counter.
mov ebx, 10
corridors_loop:
cmp ebx, 0
je end_corridor_exit_labyrinth
dec ebx
; SAME CODE SHOWED IN CHECK DOORS
doors_end_loop:
mov r15, [r15]
jmp corridors_loop
end_corridor_exit_labyrinth:After Check Doors, we know that the address in R15 has the writable
address of that corridor, then we can de-reference R15 that will point to
the next corridor, and continue this procedure until the last one that points to
the flag.
Read the Flag
In the last part of the code, RDI contains the address to our desired flag,
then we use the syscall write reading 0x100 bytes to stdout and finish
the payload calling exit with success.
end_corridor_exit_labyrinth:
mov rsi, rdi
mov rdi, 1
mov rdx, 0x100
mov rax, 1
syscall
mov rax, 0x3c
xor rdi, rdi
syscall
nop
nop
nop
nopIn the end of the code, there are some NOPs (no operation) just because if the
page where payload got copied has some garbage, then the last instruction could
be messed somehow.
Execution
Getting all the code together, the following image shows how this approach should works:
And running the solution (check
writeup-solver-01.py at the end of
this article) this is the output:
[19996] j3r3mias@serenity:misc-segfault-labyrinth > python writeup-solver-01.py REMOTE DEBUG [*] '/CTF/2022-google-ctf/misc-segfault-labyrinth/challenge' Arch: amd64-64-little RELRO: Partial RELRO Stack: No canary found NX: NX disabled PIE: PIE enabled RWX: Has RWX segments [DEBUG] cpp -C -nostdinc -undef -P -I/home/j3r3mias/.local/lib/python3.10/site-packages/pwnlib/data/includes /dev/stdin [DEBUG] Assembling .section .shellcode,"awx" .global _start .global __start .p2align 2 _start: __start: .intel_syntax noprefix // for (ebx = 10; ebx > 0; ebx--) nop mov ebx, 10 corridors_loop: cmp ebx, 0 je end_corridor_exit_labyrinth dec ebx // Use r15 as the reference to explore mov r15, rdi // while (1) doors_loop: // Use a position after our payload mov rdi, [r15] lea rsi, [rip + 0x300] mov rax, 4 syscall // compare return with EFAULT (-14) cmp rax, -14 jne doors_end_loop add r15, 8 jmp doors_loop doors_end_loop: mov r15, [r15] jmp corridors_loop end_corridor_exit_labyrinth: mov rsi, rdi mov rdi, 1 mov rdx, 0x100 mov rax, 1 syscall mov rax, 0x3c xor rdi, rdi syscall nop nop nop nop [DEBUG] /usr/bin/x86_64-linux-gnu-as -64 -o /tmp/pwn-asm-tjt5j4r1/step2 /tmp/pwn-asm-tjt5j4r1/step1 [DEBUG] /usr/bin/x86_64-linux-gnu-objcopy -j .shellcode -Obinary /tmp/pwn-asm-tjt5j4r1/step3 /tmp/pwn-asm-tjt5j4r1/step4 [+] Opening connection to segfault-labyrinth.2022.ctfcompetition.com on port 1337: Done [DEBUG] Received 0x1e bytes: b'== proof-of-work: disabled ==\n' [DEBUG] Received 0x22 bytes: b'Welcome to the Segfault Labyrinth\n' [*] Payload length: 94 [DEBUG] Sent 0x9 bytes: 00000000 5e 00 00 00 00 00 00 00 0a │^···│····│·│ 00000009 [DEBUG] Sent 0x5f bytes: 00000000 90 bb 0a 00 00 00 83 fb 00 74 29 ff cb 49 89 ff │····│····│·t)·│·I··│ 00000010 49 8b 3f 48 8d 35 00 03 00 00 48 c7 c0 04 00 00 │I·?H│·5··│··H·│····│ 00000020 00 0f 05 48 83 f8 f2 75 06 49 83 c7 08 eb e1 4d │···H│···u│·I··│···M│ 00000030 8b 3f eb d2 48 89 fe 48 c7 c7 01 00 00 00 48 c7 │·?··│H··H│····│··H·│ 00000040 c2 00 01 00 00 48 c7 c0 01 00 00 00 0f 05 48 c7 │····│·H··│····│··H·│ 00000050 c0 3c 00 00 00 48 31 ff 0f 05 90 90 90 90 0a │·<··│·H1·│····│···│ 0000005f [+] Receiving all data: Done (257B) [DEBUG] Received 0x100 bytes: 00000000 43 54 46 7b 63 30 6e 67 72 61 74 75 6c 61 74 31 │CTF{│c0ng│ratu│lat1│ 00000010 6f 6e 73 5f 6f 4e 5f 6d 34 6b 31 6e 47 5f 31 74 │ons_│oN_m│4k1n│G_1t│ 00000020 5f 74 68 72 30 75 47 68 5f 74 68 33 5f 6c 34 42 │_thr│0uGh│_th3│_l4B│ 00000030 79 72 31 6e 74 68 7d 0a 00 00 00 00 00 00 00 00 │yr1n│th}·│····│····│ 00000040 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 │····│····│····│····│ * 00000100 [*] Closed connection to segfault-labyrinth.2022.ctfcompetition.com port 1337 [*] Output: b'\nCTF{c0ngratulat1ons_oN_m4k1nG_1t_thr0uGh_th3_l4Byr1nth}\n' [19997] j3r3mias@serenity:misc-segfault-labyrinth >
02 - Rage Against the Random
Like I previous mentioned in the overview, rand_var uses the function
rand(), an implementation of a Pseudorandom Number Generator (PRNG), that is
not properly seeded in the code. The
documentation
states that “If you call rand before a seed has been established with srand,
it uses the value 1 as a default seed.”. Because of that the same door will
always have the same starting address in every execution. The only difference
between different runs is because the writable doors are chosen using
/dev/urandom.
To take advantage of that we can use the
libc to calculate the
starting address of all 160 doors (10 corridors * 16 doors per each). The
following snippet build a list with all starting addresses:
import ctypes
libc = ctypes.cdll.LoadLibrary('libc.so.6')
doors = []
for i in range(10 * 16):
address = (libc.rand() << 12) + 0x10000
doors.append(hex(address))Now we do not need to follow the rules of the labyrinth, and in one of the most
naive approaches we could just test every address using stat or write and
print the content every time the address is writable. This would requires a huge
payload but we can improve this strategy testing only the doors of the last
corridor where only one door has writable permissions. Then using the generated
list of doors, the construction of the payload (using python) is the following:
for addr in doors[-16:]: # Last 16 doors
door_code = f'''
mov rdi, {addr}
lea rsi, [rip + 950]
mov rax, 4
syscall
// compare return with EFAULT (-14)
cmp rax, -14
jne print_flag
'''
payload += door_code
payload += '''
print_flag:
// write content
mov rsi, rdi
mov rdi, 1
mov rdx, 0x100
mov rax, 1
syscall
// exit
mov rax, 0x3c
xor rdi, rdi
syscall
nop
nop
nop
nop
'''The loop in the code just creates a block of code that test each one of the
last 16 doors appending it to payload. When the right one is found, the
program jumps to the label print_flag, write the flag to stdout and exit
successfully. The full solution
can be checked at the end of this article.
03 - Bonus: Lazy CTF Player
This is one of that solutions you are ashamed to be proud of yourself during
CTFs, but it works. Using some consolidation of the previous two solutions, this
one just guess one of the last 16 doors and repeatedly connects to the server
trying always to read the same picked address again and again until that one is
picked from the server as the one to have the flag. Since we only need to pick
an address between 16 doors, 6.25% of chances to hit the jackpot is very
doable even if the contest uses some kind of
PoW (Proof of Work), which it did
not. Now the payload is reduced (22 bytes) to:
mov rsi, ADDRESS_GUESS
mov edi, 1
mov dl, 0x40
inc eax
syscall
nopNot the most beautiful one but flag
is flag! ¯\_(ツ)_/¯
Check the output:
[20891] j3r3mias@serenity:misc-segfault-labyrinth > python writeup-solver-03.py REMOTE DEBUG [*] '/CTF/2022-google-ctf/misc-segfault-labyrinth/challenge' Arch: amd64-64-little RELRO: Partial RELRO Stack: No canary found NX: NX disabled PIE: PIE enabled RWX: Has RWX segments [*] Lucky address guess: 0x68eb2f73000 [DEBUG] cpp -C -nostdinc -undef -P -I/home/j3r3mias/.local/lib/python3.10/site-packages/pwnlib/data/includes /dev/stdin [DEBUG] Assembling .section .shellcode,"awx" .global _start .global __start .p2align 2 _start: __start: .intel_syntax noprefix mov rsi, 0x68eb2f73000 mov edi, 1 mov dl, 0x40 inc eax syscall nop [DEBUG] /usr/bin/x86_64-linux-gnu-as -64 -o /tmp/pwn-asm-8t8ji1n0/step2 /tmp/pwn-asm-8t8ji1n0/step1 [DEBUG] /usr/bin/x86_64-linux-gnu-objcopy -j .shellcode -Obinary /tmp/pwn-asm-8t8ji1n0/step3 /tmp/pwn-asm-8t8ji1n0/step4 [*] Payload length using 0x68eb2f73000: 22 [*] Attempt: 01 [!] Fail [*] Attempt: 02 [!] Fail [*] Attempt: 03 [!] Fail [*] Attempt: 04 [!] Fail [*] Attempt: 05 [!] Fail [*] Attempt: 06 [+] Output: CTF{c0ngratulat1ons_oN_m4k1nG_1t_thr0uGh_th3_l4Byr1nth} [20892] j3r3mias@serenity:misc-segfault-labyrinth >
Final Considerations
This challenges was really a journey to reverse engineering with a lot of
opportunities to suffer learn, review concepts and practice more
understanding of other peoples code. Every year Google CTF delivers a variety of
good challenges and this year was not different.
P.S.: After I finished to write this article, I saw that LiveOverflow and PwnFuncTtion recently published two excellent videos about random and seeds. The first one approaching the creation of worlds in Minecraft and the last one about how random works in V8 (Google’s open source high-performance JavaScript and WebAssembly engine). Both videos are a good examples of how solving challenges like Segfault Labyrinth is a good practice to understand how a lot of projects work and what to do when you face its usage like we did it.