30
Apr
2012

Plaid CTF 2012 – Simple

Our lead scientist was really close to cracking this problem before a robot assassin took his life and stole all his work. All that was left was a posted saying ‘simple’.

The file provided is a 32-bit ELF executable for Linux. Disassembling the executable code gives a ‘simple’ interpreter:

   0x31341:	cmp    ebp,esp
   0x31343:	jg     0x3139e
   0x31345:	pop    eax
   0x31346:	pop    ebx
   0x31347:	pop    ecx
   0x31348:	test   eax,eax
   0x3134a:	jl     0x3137b
   0x3134c:	test   ebx,ebx
   0x3134e:	jl     0x31364
   0x31350:	lea    eax,[ebp+eax*4+0x0]
   0x31354:	mov    eax,DWORD PTR [eax]
   0x31356:	lea    ebx,[ebp+ebx*4+0x0]
   0x3135a:	sub    DWORD PTR [ebx],eax
   0x3135c:	jg     0x31341
   0x3135e:	lea    esp,[ebp+ecx*4+0x0]
   0x31362:	jmp    0x31341

There is only one instruction in the machine which can actually be used to do a conditional branch and that is the jg at 0x3135c.
We decided to create a gdb script which logs the values of [ebx] and eax at the point of the compare.

set height 0
b *0x0003135A
commands 1
silent
printf "%08x %08x\n", *$ebx, $eax
c
end

This script can be used to generate a trace as follows:

gdb ./simple -x script <<< 'r <<< AAAAAAAAAAAAA' > output-A

Comparing the output for AAAAAAAAAAAAA and BBBBBBBBBBBBB shows some interesting differences where a value dependent on the input is compared to a static value. If they are equal some extra instructions are exectued.

For example in the input with all A’s the following compare takes place:
00000060 0000008b
While in the input with all B’s the compare is:
00000061 0000008b

So it seems that there is a compare for input+x to a constant. We created a python script to find such compares and calculate the input which would make the comparison be true:

import sys
f1 = open(sys.argv[1])
for line in open(sys.argv[1]):
        if line.find('0000') == 0: # Only look at lines starting with 0000
                (v1,v2) = map(lambda x: int(x,16),line.split())
                if v2 != 0xa and v1 > 0x41 and v2 > 0x41 and v1 < 0xff and v2 < 0xff and v1 != v2:
                        sys.stdout.write(chr(v2-v1+ord('A')))
print
$ python find_key.py output-A
l3ss_1s_m0r3!

{One Response to “Plaid CTF 2012 – Simple”}

  1. Nice! gdb’s “silent” would’ve saved us a lot of pythonging :O

    Dan