01
May
2012

Plaid CTF 2012 – SIMD

After examining some code retrieved by our operative we are unsure whether it was written by an evil genius or a google employee. We will let you decide.
Title: SIMD (250)
Category: Pirating

For this challenge we had to reverse engineer the password from a 64-bit binary using SSE/AVX instructions.

Disassembling the SIMD binary we noticed it does the following:
– Checks whether argv[1] is 31 characters
– If it is the argv is ran through a function called ‘frob’ which calculates a result based on the input using either an SSE or AVX function depending on what the CPU is capable of.
– After the function is finished the output is compared to a fixed value to see if it was correct.

We had a quick look at the SSE2 code, but it seemded quite complex. So we decided first to see if we might be able to ‘black-box’ reverse what the code did.

Looking at the disassembly for the main function we see the following, after the check whether argv[1] is 31 bytes:

   0x000000000040070d <+61>:	callq  0x4007d0 <frob>
   0x0000000000400712 <+66>:	mov    0x2021e7(%rip),%rdi        # 0x602900 <expected>
   0x0000000000400719 <+73>:	mov    $0x20,%ecx
   0x000000000040071e <+78>:	mov    %rsp,%rsi
   0x0000000000400721 <+81>:	repz cmpsb %es:(%rdi),%ds:(%rsi)
   0x0000000000400723 <+83>:	je     0x400748 <main+120>

So it compares the values at [$rdi] = fixed to those at [$rsi].

We can put a breakpoint in gdb at *0x400721 to see what the calculated output is for some fixed inputs:

The desired output:
gdb$ x/32bx $rdi
0x402458 <__dso_handle+48>:	0x02	0xee	0x5b	0xc5	0x9f	0x0a	0x49	0x34
0x402460 <__dso_handle+56>:	0x37	0xb0	0x1a	0x8c	0x37	0x30	0x18	0x10
0x402468 <__dso_handle+64>:	0xbc	0x9f	0xe7	0x5f	0x31	0xb4	0xa0	0xeb
0x402470 <__dso_handle+72>:	0x93	0x04	0x71	0x95	0xc5	0x8b	0xd1	0x3b

Input AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA:
gdb$ x/32bx $rsi
0x7fffffffe490:	0x77	0xdd	0x74	0xf0	0x81	0x3d	0x3b	0x16
0x7fffffffe498:	0x02	0xc1	0x29	0x92	0x47	0x1f	0x2a	0x25
0x7fffffffe4a0:	0x8f	0xab	0xc5	0x6a	0x41	0xc5	0x8f	0xd9
0x7fffffffe4a8:	0x8d	0x26	0x00	0xe4	0xe8	0xf5	0xb1	0x3b

Input BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA:
gdb$ x/32bx $rsi
0x7fffffffe490:	0x74	0xdd	0x74	0xf0	0x81	0x3d	0x3b	0x16
0x7fffffffe498:	0x02	0xc1	0x29	0x92	0x47	0x1f	0x2a	0x25
0x7fffffffe4a0:	0x8f	0xab	0xc5	0x6a	0x41	0xc5	0x8f	0xd9
0x7fffffffe4a8:	0x8d	0x26	0x00	0xe4	0xe8	0xf5	0xb1	0x3b

We noticed that the output only chances in the first byte if change the first byte of the input. Without analyzing or thinking any further we implemented a script which manipulates the input byte for byte to find the key.

We implement a simple GDB script to log the output to a file:

b *0x400721
commands
silent
printf "Got\n"
x/32bx $rsi
c
end

And run a letter for letter guesser

import string,os,re
want = '02ee5bc59f0a493437b01a8c37301810bc9fe75f31b4a0eb93047195c58bd13b'.decode('hex')
def getbytes(s):
        allb = ''
        s = s.split('\n')
        for l in s:
                if '0x7ffff' in l:
                        bytes = l.split(':',2)[1]
                        allb += bytes.replace('0x','').replace(' ','').replace('\t','')
        return allb.decode('hex')

found = ''
while True:
        good = False
        for g in string.printable:
                if g == '"': continue
                guess = found + g
                guess += "A"*(31-len(guess))
                out = os.popen('gdb ./simd -x script <<< "r %s"' % guess).read()
                out = getbytes(out)
                if len(out) < 32: continue
                if out[len(found)] == want[len(found)]:
                        print "Found %s" % guess
                        found += g
                        break

After keeping this running for a few minutes we get the key: 4rnt_v3ct0r_1nstruct10ns_c00l?!

Ofcourse afterwards, when writing the write-up you realize it could have been done much simpler… For example if we also look at the output for all B’s we see it is very similar to the output for all A’s. Almost looks like a simple XOR…

Let’s try that

def string_xor(a,key):
        return ''.join(chr(ord(a[i]) ^ ord(key[i%len(key)])) for i in range(len(a)))

a = '77dd74f0813d3b1602c12992471f2a258fabc56a41c58fd98d2600e4e8f5b13b'.decode('hex')
w = '02ee5bc59f0a493437b01a8c37301810bc9fe75f31b4a0eb93047195c58bd13b'.decode('hex')
key = string_xor(a,'A'*31 + '\x00')
print string_xor(w,key)

Yields the same result in much less code and much quicker… good reminder that thinking is faster than guessing πŸ˜€

Comments are closed.