BkPCTF 2013 - randy (200)
The randy binary should be the next target of interest. As it has no file name extension, we assume that it’s an executable binary for Linux. A quick lookup confirms this:
$> file randy
randy: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=0x0bb2fcccb38b0191ba3512735541461e5ffb468a, not stripped
So let’s once more give in to the temptation and just run it:
$> ./randy
Password: pass
:(
Okay. It asks for a password and then quits on my (obviously) wrong input. Let’s ask IDA to show what is going on inside. The boring part is done by the tool:
Nothing too exciting here. These lines basically read a string from stdin and compare if its length equals 0x1c. If this is the case, the keygen function is invoked and upon the return value we get either a happy or (as in my case) a sorry smiley.
So all the magic seems to happen within the keygen function. The first and only parameter of the function is a pointer to the input string in the $rdi register. Let’s investigate a little bit more:
.text:0000000000400A20 public keygen
.text:0000000000400A20 keygen proc near ; CODE XREF: main+155p
.text:0000000000400A20 mov r12, 0
.text:0000000000400A2A mov r13, rdi
.text:0000000000400A2D
.text:0000000000400A2D do_1:
.text:0000000000400A2D mov rax, [r13+r12*4+0]
.text:0000000000400A32 mov rdi, rax ; seed
.text:0000000000400A35 call _srandom
.text:0000000000400A3A call _random
.text:0000000000400A3F cmp rax, 7358837Ah
.text:0000000000400A45 jnz bad
.text:0000000000400A4B call _random
.text:0000000000400A50 cmp rax, 6E1B2658h
.text:0000000000400A56 jnz bad
.text:0000000000400A5C call _random
.text:0000000000400A61 cmp rax, 3C00C5FFh
.text:0000000000400A67 jnz bad
.text:0000000000400A6D call _random
.text:0000000000400A72 cmp rax, 8C0D4AAh
.text:0000000000400A78 jnz bad
.text:0000000000400A7E inc r12
Okay. We see the pointer being moved to the r13 register and an offset in r12 being initialized to zero. Then the first four bytes of the input string are taken and used as the first and only parameter of the srand function. Afterwards, a chain of calls to random is made and the respective outputs are compared to several fixed values.
This instantly makes clear why the challenge is called randy: We have to supply an input string whose bytes are used as initializers for the random function. As random behaves completely deterministic for a fixed srand input, it should be easy to recover the needed inputs via a brute-force search over all possible 4 byte blocks.
But first let’s obtain the respective values that need to be matched:
.text:0000000000400A20 mov r12, 0
.text:0000000000400A2A mov r13, rdi
.text:0000000000400A2D
.text:0000000000400A2D do_1:
.text:0000000000400A2D mov rax, [r13+r12*4+0]
.text:0000000000400A32 mov rdi, rax ; seed
.text:0000000000400A35 call _srandom
.text:0000000000400A3A call _random
.text:0000000000400A3F cmp rax, 7358837Ah
.text:0000000000400A45 jnz bad
--- <% snip ---
.text:0000000000400A7E inc r12
.text:0000000000400A81
.text:0000000000400A81 do_2:
.text:0000000000400A81 mov rax, [r13+r12*4+0]
.text:0000000000400A86 mov rdi, rax ; seed
.text:0000000000400A89 call _srandom
.text:0000000000400A8E call _random
.text:0000000000400A93 cmp rax, 34D8C3B5h
--- <% snip ---
.text:0000000000400AD2 inc r12
.text:0000000000400AD5
.text:0000000000400AD5 do_3:
.text:0000000000400AD5 mov rax, [r13+r12*4+0]
.text:0000000000400ADA mov rdi, rax ; seed
.text:0000000000400ADD call _srandom
.text:0000000000400AE2 call _random
.text:0000000000400AE7 cmp rax, 1F49456Ch
.text:0000000000400AED jnz bad
--- <% snip ---
.text:0000000000400B26 inc r12
.text:0000000000400B29
.text:0000000000400B29 do_4:
.text:0000000000400B29 mov rax, [r13+r12*4+0]
.text:0000000000400B2E mov rdi, rax ; seed
.text:0000000000400B31 call _srandom
.text:0000000000400B36 call _random
.text:0000000000400B3B cmp rax, 1FEA6614h
.text:0000000000400B41 jnz bad
--- <% snip ---
.text:0000000000400B7A inc r12
.text:0000000000400B7D
.text:0000000000400B7D do_5:
.text:0000000000400B7D mov rax, [r13+r12*4+0]
.text:0000000000400B82 mov rdi, rax ; seed
.text:0000000000400B85 call _srandom
.text:0000000000400B8A call _random
.text:0000000000400B8F cmp rax, 4E81ABC7h
.text:0000000000400B95 jnz bad
--- <% snip ---
.text:0000000000400BCE inc r12
.text:0000000000400BD1
.text:0000000000400BD1 do_6:
.text:0000000000400BD1 mov rax, [r13+r12*4+0]
.text:0000000000400BD6 mov rdi, rax ; seed
.text:0000000000400BD9 call _srandom
.text:0000000000400BDE call _random
.text:0000000000400BE3 cmp rax, 683D3F5Dh
.text:0000000000400BE9 jnz short bad
--- <% snip ---
.text:0000000000400C12 inc r12
.text:0000000000400C15
.text:0000000000400C15 do_7:
.text:0000000000400C15 mov rax, [r13+r12*4+0]
.text:0000000000400C1A mov rdi, rax ; seed
.text:0000000000400C1D call _srandom
.text:0000000000400C22 call _random
.text:0000000000400C27 cmp rax, 28C9A8FEh
.text:0000000000400C2D jnz short bad
--- <% snip ---
The values of the respective first compare instructions of the chains are:
0x7358837A 0x34D8C3B5 0x1F49456C 0x1FEA6614 0x4E81ABC7 0x683D3F5D 0x28C9A8FE
Now we have enough information to write a simple brute force exploit that recovers the original (printable) values:
#include <stdio.h>
#include <unistd.h>
unsigned int keys[7] =
{ 0x7358837A, 0x34D8C3B5, 0x1F49456C, 0x1FEA6614, 0x4E81ABC7, 0x683D3F5D, 0x28C9A8FE};
#define START 0x20
#define END 0x7f
int main() {
puts(solution);
int i,j,k,l,m;
int r = 0;
int seed = 0;
for (i = START; i < END; i++) {
for (j = START; j < END; j++) {
for (k = START; k < END; k++) {
for (l = START; l < END; l++) {
seed = i << 24 | j << 16 | k << 8 | l;
srand(seed);
r = rand();
for (m = 0; m < 7; m++) {
if (r == keys[m]) printf("0x%08x -> 0x%08x\n", keys[m], seed);
}
}
}
}
}
}
Let’s run it:
$> gcc -O2 -o derand derand.c && ./derand
0x7358837a -> 0x2074306e
0x28c9a8fe -> 0x21212121
0x1f49456c -> 0x30646e34
0x683d3f5d -> 0x31316120
0x1fea6614 -> 0x3420306d
0x34d8c3b5 -> 0x72203073
0x4e81abc7 -> 0x72337466
Nice! If we now rearrange the values of the right column such that the keys in the first column appear in the same order as they appear in the binary we get:
#include <stdio.h>
char *solution =
"\x6e\x30\x74\x20"
"\x73\x30\x20\x72"
"\x34\x6e\x64\x30"
"\x6d\x30\x20\x34"
"\x66\x74\x33\x72"
"\x20\x61\x31\x31"
"\x21\x21\x21\x21";
int main() {
puts(solution);
};
Running it yields:
$> gcc -O2 -o printsolution printsolution.c && ./printsolution
n0t s0 r4nd0m0 4ft3r a11!!!!
And indeed:
$> ./randy
Password: n0t s0 r4nd0m0 4ft3r a11!!!!
:)
Flag captured.