j3r3mias

Random site.

14 July 2022

Google CTF 2022 - Segfault Labyrinth

by Jeremias Gomes

Table of Contents

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

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:

stdin
[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:

stdin
[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:

stdin
[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:

Core idea of a representation of the labyrinth.

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.

Execution in pwndbg sending multiples `0xcc` as a payload.

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:

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
nop

In 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:

Visualization of how the strategy works.

And running the solution (check writeup-solver-01.py at the end of this article) this is the output:

stdin
[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{c0ngratulat1│
    00000010  6f 6e 73 5f  6f 4e 5f 6d  34 6b 31 6e  47 5f 31 74  │ons_oN_m4k1nG_1t│
    00000020  5f 74 68 72  30 75 47 68  5f 74 68 33  5f 6c 34 42  │_thr0uGh_th3_l4B│
    00000030  79 72 31 6e  74 68 7d 0a  00 00 00 00  00 00 00 00  │yr1nth}·········│
    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
nop

Not the most beautiful one but flag is flag! ¯\_(ツ)_/¯

Check the output:

stdin
[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.

Codes

01 - Exploit 01 - Explore the Labyrinth

02 - Exploit 02 - Rage Against the Random

03 - Exploit 03 - Lazy CTF Player (Bonus)

04 - IDA Disassembly of the Binary

References

  1. Google Capture the Flag

  2. Google Capture the Flag 2022 - Segfault Labyrinth files

  3. pwntools (checksec)

  4. IDA Decompiler/Disassembler

  5. Secure Computing Mode (Seccomp)

  6. seccomp-tools

  7. stat(2) — Linux manual page

  8. write(2) — Linux manual page

  9. ISO C Random Number Functions

  10. libc(7) — Linux manual page

  11. Proof of Work

  12. V8

tags: ctf - google-ctf - reversing - reverse-engineering - writeup