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)
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 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 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) 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 😀