Wednesday, May 21, 2014

Of Binary Bombs (part 2)

In part 1 I worked out the setup of the binary bomb and walked through the solution to the first phase of the riddle. This post continues from there to examine phase 2.

After defusing phase 1 the program reads the next line from the user (sym.read_line) and calls sym.phase_2. In my first post I glazed over the sym.read_line with some hand-waving so I'd like to revisit that here with a little more attention. As a reminder, in radare2 you can search for a symbol while in visual mode with s (s sym.read_line).

The first thing that happens in sym.read_line (after managing the pointers and local variables) is a call to sym.skip. sym.skip has a little more to it than just this but basically determines which input line is to be read by looking at the global variable sym.num_input_strings and using that as an index into sym.input_strings (a global holding each input string in an 80-byte char array). It returns the string read in eax.

Once a line is read from the input stream the following instructions check the return value of sym.skip.

    test eax, eax
    jne 0x804925f

Only if the return value of sym.skip is zero (when null is returned) does execution not jump to 0x0804925f. I will cover later what happens in the null return case. For now, non-null returns follow this explanation.

    mov eax, [sym.num_input_strings]

At this point, we have entered 2 strings but the global counter sym.num_input_strings has only been updated once so contains the value 1.

    lea eax, [eax+eax*4]
    shl eax, 0x4
    lea edi, [eax+sym.input_strings]

The above sets eax to eax * 5, multiplies the result by 16, and loads the string at sym.input_strings+eax into edi. In this case (sym.num_input_strings == 1) this yields the second index in the sym.input_strings array (recall that each entry there is 80 bytes).

The next set of instructions calculate the length of the input string by decrementing a counter for each non-null byte in the string. The calculation uses some shortcuts for efficiency so is not directly mapped to traditional C-like counting (google 'asm string length' for details).

    mov al, 0x0
    mov ecx, 0xffffffff 
    repne scasb
    mov eax, ecx
    not eax
    lea edi, [eax-0x1]

Our input strings must fit within the 80-byte array so checking that the string (less newline) is less than 0x4f (79) bytes is done next

    cmp edi, 0x4f

Finally, the newline is replaced with a zero byte

    mov byte [edi+eax+0x804b67f], 0x0

the input string is placed in eax and the global sym.num_input_strings is incremented by 1.

At this point eax contains the input string and I can resume with the second phase of the bomb.

After the prologue and setting aside 32 bytes of local space the input string is copied to edx and the local buffer address is loaded into eax. These two arguments are pushed onto the stack and sym.read_six_numbers is invoked. To avoid making this post too long I'll skip over the detail of sym.read_six_numbers and just mention that the numbers in the input string are read into the local array via sscanf with a format string of "%d %d %d %d %d %d" (Hint #1). 

The following check verifies that the first entry in the local array has the value 1 and is the second hint to solving this phase.

    cmp dword [ebp-0x18], 0x1                

The next section of code is the meat of phase 2 and how we determine what numbers to include in our string.

    mov ebx, 0x1
    lea esi, [ebp-0x18] 
    lea eax, [ebx+0x1]  ; target of jump below (0x8048b76)
    imul eax, [esi+ebx*4-0x4] 
    cmp [esi+ebx*4], eax   
    je 0x8048b88 
    call sym.explode_bomb
    inc ebx             ; target of jump above (0x8048b88)
    cmp ebx, 0x5  
    jle 0x8048b76 

This is a loop from 1 to 5 using ebx as the counter. The initialization sets ebx to 1 and esi to the beginning of the array of converted numbers (the local array). On each iteration of the loop eax is set to ebx + 1 then multiplied by the nth entry of the local array (n is ebx - 1). The result of that is compared to the next entry in the array. In C parlance this might look like:

    int xs[] = {...}; 
    for (i = 0; i < 5; ++i)
        if ((i+1) * xs[i] != xs[i+1]) 

If we know that xs[0] must be 1 we can now use the above to calculate the remainder of the array.

    x[1] = 2 * x[0] => 2
    x[2] = 3 * x[1] => 6 
    x[3] = 4 * x[2] => 24

Ultimately, our input requirements become: 1 2 6 24 120 720. This works as expected and phase 2 is now solved.

On to phase 3.

No comments :

Post a Comment