Reversing little puzzles
This little puzzle was part of a CTF I didn't participate in. I attempted to solve it a couple days after it ended.
The 'flag' had to be forced out of a binary (on a Linux box), no clues given at all. First naive attempt? strings ./binary, which revealed only two strings, "you have to try harder to get the secret message!" and "THE SECRET MESSAGE IS:". Not much. After running the binary a few times, with various arguments, I decided to fire up gdb, while brute-forcing a numeric first argument in another shell..
Disassembling main() led to the following:
# 0x000000000040069c main: push rbp mov rbp,rsp push rbx sub rsp,0x68 mov DWORD PTR [rbp-0x64],edi mov QWORD PTR [rbp-0x70],rsi mov BYTE PTR [rbp-0x60],0xee mov BYTE PTR [rbp-0x5f],0x67 mov BYTE PTR [rbp-0x5e],0x76 mov BYTE PTR [rbp-0x5d],0x67 mov BYTE PTR [rbp-0x5c],0xdf mov BYTE PTR [rbp-0x5b],0x69 mov BYTE PTR [rbp-0x5a],0x6c mov BYTE PTR [rbp-0x59],0x75 mov BYTE PTR [rbp-0x58],0xc1 mov BYTE PTR [rbp-0x57],0x69 mov BYTE PTR [rbp-0x56],0x6c mov BYTE PTR [rbp-0x55],0x69 mov BYTE PTR [rbp-0x54],0xc2 mov BYTE PTR [rbp-0x53],0x66 mov BYTE PTR [rbp-0x52],0x6b mov BYTE PTR [rbp-0x51],0x21 mov BYTE PTR [rbp-0x50],0x8d mov BYTE PTR [rbp-0x4f],0x51 mov BYTE PTR [rbp-0x4e],0x77 mov BYTE PTR [rbp-0x4d],0x75 mov BYTE PTR [rbp-0x4c],0xdf mov BYTE PTR [rbp-0x4b],0x28 mov BYTE PTR [rbp-0x4a],0x6c mov BYTE PTR [rbp-0x49],0x65 mov BYTE PTR [rbp-0x48],0xcc mov BYTE PTR [rbp-0x47],0x65 mov BYTE PTR [rbp-0x46],0x38 mov BYTE PTR [rbp-0x45],0x68 mov BYTE PTR [rbp-0x44],0xcc mov BYTE PTR [rbp-0x43],0x7b mov BYTE PTR [rbp-0x42],0x38 mov BYTE PTR [rbp-0x41],0x77 mov BYTE PTR [rbp-0x40],0xc2 mov BYTE PTR [rbp-0x3f],0x66 mov BYTE PTR [rbp-0x3e],0x38 mov BYTE PTR [rbp-0x3d],0x74 mov BYTE PTR [rbp-0x3c],0xc5 mov BYTE PTR [rbp-0x3b],0x6d mov BYTE PTR [rbp-0x3a],0x38 mov BYTE PTR [rbp-0x39],0x50 mov BYTE PTR [rbp-0x38],0xcc mov BYTE PTR [rbp-0x37],0x66 mov BYTE PTR [rbp-0x36],0x77 mov BYTE PTR [rbp-0x35],0x70 mov BYTE PTR [rbp-0x34],0xd9 mov BYTE PTR [rbp-0x33],0x61 mov BYTE PTR [rbp-0x32],0x6b mov BYTE PTR [rbp-0x31],0x20 mov BYTE PTR [rbp-0x30],0x9f mov BYTE PTR [rbp-0x2f],0x38 mov BYTE PTR [rbp-0x2e],0x29 mov BYTE PTR [rbp-0x2d],0x31 mov BYTE PTR [rbp-0x2c],0x8d mov BYTE PTR [rbp-0x2b],0x4b mov BYTE PTR [rbp-0x2a],0x4c mov BYTE PTR [rbp-0x29],0x46 mov BYTE PTR [rbp-0x28],0x8c mov BYTE PTR [rbp-0x27],0x28 mov BYTE PTR [rbp-0x26],0x38 mov BYTE PTR [rbp-0x25],0xa mov BYTE PTR [rbp-0x24],0x0 cmp DWORD PTR [rbp-0x64],0x2 je 4007b0 <main+0x114> mov eax,0x0 call 400614 <gracefull_exit> mov rax,QWORD PTR [rbp-0x70] add rax,0x8 mov rax,QWORD PTR [rax] mov rdi,rax call 400508 <atoi@plt> mov DWORD PTR [rbp-0x18],eax cmp DWORD PTR [rbp-0x18],0x0 jg 4007d6 <main+0x13a> mov eax,0x0 call 400614 <gracefull_exit> mov ecx,DWORD PTR [rbp-0x18] mov edx,0x29665e1f mov eax,ecx imul edx sar edx,0x8 mov eax,ecx sar eax,0x1f mov ebx,edx sub ebx,eax mov eax,ebx imul eax,eax,0x62f mov edx,ecx sub edx,eax mov eax,edx test eax,eax je 40080a <main+0x16e> mov eax,0x0 call 400614 <gracefull_exit> mov ecx,DWORD PTR [rbp-0x18] mov edx,0x10776183 mov eax,ecx imul edx sar edx,0x6 mov eax,ecx sar eax,0x1f mov ebx,edx sub ebx,eax mov eax,ebx imul eax,eax,0x3e3 mov edx,ecx sub edx,eax mov eax,edx test eax,eax je 40083e <main+0x1a2> mov eax,0x0 call 400614 <gracefull_exit> mov edx,DWORD PTR [rbp-0x18] lea rax,[rbp-0x60] mov esi,0x3c mov rdi,rax call 400646 <a52> mov DWORD PTR [rbp-0x14],eax cmp DWORD PTR [rbp-0x14],0xf8b83a03 je 400868 <main+0x1cc> mov eax,0x0 call 400614 <gracefull_exit> mov eax,0x4009b3 lea rdx,[rbp-0x60] mov rsi,rdx mov rdi,rax mov eax,0x0 call 4004d8 <printf@plt> mov eax,0x0 add rsp,0x68 pop rbx leave ret nop nop nop
So, what do we see? Two functions, gracefull_exit (full of grace, I assume) and a52; we can probably already guess what the former does, and the latter will have to be more closely examined. We also see a large buffer filled byte-by-byte with mostly unprintable characters, apparently to evade strings. To satisfy our curiosity, we disassemble those functions too:
# 0x0000000000400614 gracefull_exit: push rbp mov rbp,rsp mov rax,QWORD PTR [rip+0x2006c9] mov rdx,rax mov eax,0x400980 mov rcx,rdx mov edx,0x32 mov esi,0x1 mov rdi,rax call 400518 <fwrite@plt> mov edi,0x1 call 4004e8 <exit@plt> # 0x0000000000400646 a52: push rbp mov rbp,rsp mov QWORD PTR [rbp-0x18],rdi mov DWORD PTR [rbp-0x1c],esi mov DWORD PTR [rbp-0x20],edx mov DWORD PTR [rbp-0x4],0x0 mov rax,QWORD PTR [rbp-0x18] mov QWORD PTR [rbp-0x10],rax jmp 400684 <a52+0x3e> mov rax,QWORD PTR [rbp-0x10] mov eax,DWORD PTR [rax] mov edx,eax xor edx,DWORD PTR [rbp-0x20] mov rax,QWORD PTR [rbp-0x10] mov DWORD PTR [rax],edx mov rax,QWORD PTR [rbp-0x10] mov eax,DWORD PTR [rax] add DWORD PTR [rbp-0x4],eax add QWORD PTR [rbp-0x10],0x4 mov rdx,QWORD PTR [rbp-0x18] mov eax,DWORD PTR [rbp-0x1c] cdqe lea rax,[rdx+rax*1] cmp rax,QWORD PTR [rbp-0x10] ja 400665 <a52+0x1f> mov eax,DWORD PTR [rbp-0x4] leave ret
gracefull_exit calls fwrite to print a message and exits. a52 seems to loop over a buffer and performing a xor with a value stored in [$rbp-0x20], so it's probably some decryption routine. Let's not deal with that just yet, and figure out the flow and how to manipulate it.
We start with a buffer in 0x7fffffffe0e0 (not important, just where my gdb put it. that's rbp-0x60 in the context of main()) ; it's being filled with what seems like garbage, and there's a good chance it will be decoded later by a52. Then, atoi() is called on the first command-line parameter and the result is checked for being positive. If so, we continue into this first (and only) interesting part:
mov edx,0x29665e1f mov eax,ecx imul edx sar edx,0x8 mov eax,ecx sar eax,0x1f mov ebx,edx sub ebx,eax mov eax,ebx imul eax,eax,0x62f mov edx,ecx sub edx,eax mov eax,edx test eax,eax je 40080a <main+0x16e>
What is happening here? If you try and symbolically map the operations made on the result of atoi() (some people call this "math"), you'll end up with an identity function. Weird, right? This 5-instruction part:
mov eax,ecx sar eax,0x1f mov ebx,edx sub ebx,eax mov eax,ebx
which is nothing more than a fancy way of saying mov eax, edx, is followed by a multiplication with 0x62f (decimal 1583) and it must equal the initial result from atoi(). The only magic, if you will, is contained in the first 5 instructions of our snippet which must seem pretty weird if you're not familiar with them. To better understand it, I suggest reading an excellent series of posts by ridiculousfish on the subject of division, starting here. The gist of it is that to optimize division, some smart people have figured out that division can be expressed as a multiplication with a magic constant and an arithmetic right shift.
Putting all those together, this snippet is the equivalent of (in C):
if(!((param / 0x62f) * 0x62f == param)) { gracefull_exit(); }
which seems kind of crazy all by itself. [edit] As @dfunc has pointed out, this is not the whole deal; indeed, think about the above snippet for a second. It's a straightforward, hexrays-like, disassembly. If all we do is look at it, we'll state something preposterous like "it's true for all numbers!". But take a minute to think before you read the next sentence; what does it actually do? It verifies param is divided exactly by 0x62f (zero modulus) and exits if it isn't. Essentially, that:
if(param % 0x62f) { gracefull_exit(); }
The next snippet, respectively, performs the exact same operation for the constant 0x3e3 (decimal 995). Now it makes a little sense; the supplied parameter to the binary must fulfil those two conditions. Then, if successful, the code calls a52() with 3 arguments: the atoi() result, the address of the buffer and the buffer's length (0x3c). The return value from a52() is then compared for equality to 0xf8b83a03 and then the flag (I assume) is printed.
Alright, so we have a good starting point. Unfortunately, it's near the end. If we calculate the parameter value we need to direct flow into a52(), we get 0x1808ad (the product of 1583 and 995). By running the executable with that parameter, though, we get to the end of the line. The flag is printed and our work is done. Nothing too difficult, right? Turns out the return value of a52(), in case you care, is the result of a 32-bit accumulation of the xored words of the message; you can see it happening in add DWORD PTR [rbp-0x4],eax. The key for XOR in a52() is also the result from atoi().
A fun hour spent. I promise to post more challenging stuff whenever I get the time. :-)
PS. By the time I figured this one out, brute-forcing the parameter had already finished. ;-)
