hxp


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:

randy

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.