30
Apr
2012

Plaid CTF 2012 – Supercomputer #1

For the “supercomputer” series of challenges you were supposed to optimize a bunch of routines inside a 64bit ELF executable in order to speed up exection so it would eventually give you “keys” based on four different algorithms. Unfortunately, due to time/profit constraints we only solved supercomputer #1.. but, here’s the writeup!

The input for every algorithm is 4 quadwords (64bit), the original initialisation values look like: 0xe63f, 0x6302, 0x0e46, 0xa9c0 .. after an algorithm has run it will verify whether the outcome is correct (not by checking for the actual key ofcourse, that would be too obviouso to snoop then).

First of all, there seem to be some *artificial* slowdowns based on sleep() calls, so let’s get rid of them.

we find:

400d75:     bf 01 00 00 00          mov    $0x1,%edi
401578:     e8 cb ef ff ff          callq  400548 <sleep@plt>

we patch the call with “90 90 90 90 90” to nuke the sleep. After we run the program again the first part of the first stage seems to happen a bit quicker, but it’s still slowing down a bit later, time to dig deeper. using valgrind and kcachegrind we figure out the routine at 0x400c6d is very time consuming during a sample run.

Time to reverse this routine and optimize it! It turns out to be fairly simple, one argument determines the number of iterations, and the innerloop simply increments the output value by one every iteration. Naturally, we can optimize this to a single add instruction. πŸ™‚

Original code:

<   400cae:     eb 35                   jmp    400ce5 <fflush@plt+0x76d>
<   400cb0:     48 8b 45 10             mov    0x10(%rbp),%rax
<   400cb4:     48 83 c0 01             add    $0x1,%rax
<   400cb8:     48 89 45 10             mov    %rax,0x10(%rbp)
<   400cbc:     48 8b 45 18             mov    0x18(%rbp),%rax
<   400cc0:     48 83 c0 01             add    $0x1,%rax
<   400ccc:     48 83 c0 01             add    $0x1,%rax
<   400cd0:     48 89 45 20             mov    %rax,0x20(%rbp)
<   400cd4:     48 8b 45 28             mov    0x28(%rbp),%rax
<   400cd8:     48 83 c0 01             add    $0x1,%rax
<   400cdc:     48 89 45 28             mov    %rax,0x28(%rbp)
<   400ce0:     48 83 45 f8 01          addq   $0x1,-0x8(%rbp)
<   400ce5:     48 8b 45 f8             mov    -0x8(%rbp),%rax
<   400ce9:     48 3b 45 e0             cmp    -0x20(%rbp),%rax
<   400ced:     75 c1                   jne    400cb0 <fflush@plt+0x738>

Our patch:

>   400cae:     48 8b 55 e0             mov    -0x20(%rbp),%rdx
>   400cb2:     48 8b 45 10             mov    0x10(%rbp),%rax
>   400cb6:     48 01 d0                add    %rdx,%rax
>   400cb9:     48 89 45 10             mov    %rax,0x10(%rbp)
>   400cbd:     48 8b 45 18             mov    0x18(%rbp),%rax
>   400cc1:     48 01 d0                add    %rdx,%rax
>   400ccc:     48 01 d0                add    %rdx,%rax
>   400ccf:     48 89 45 20             mov    %rax,0x20(%rbp)
>   400cd3:     48 8b 45 28             mov    0x28(%rbp),%rax
>   400cd7:     48 01 d0                add    %rdx,%rax
>   400cda:     48 89 45 28             mov    %rax,0x28(%rbp)
>   400cde:     90                      nop
>   400cdf:     90                      nop
>   400ce0:     90                      nop
>   400ce1:     90                      nop
>   400ce2:     90                      nop
>   400ce3:     90                      nop
>   400ce4:     90                      nop
>   400ce5:     90                      nop
>   400ce6:     90                      nop
>   400ce7:     90                      nop
>   400ce8:     90                      nop
>   400ce9:     90                      nop
>   400cea:     90                      nop
>   400ceb:     90                      nop
>   400cec:     90                      nop
>   400ced:     90                      nop
>   400cee:     90                      nop

Let’s take it for a spin:

$ ./supercomputer.patched 
Calculating the first key......This could take long..........Too long..... *snip* 
Yay! The first key is 414e0d423f5fcd195a579f95f1ff6525

Success!

Comments are closed.