Shuffled Love (you need to register) was one of the Linux 64bits reverse challenges available to be solved during the recent 0x00Sec CTF Winter 2017 edition. This challenge was intended to be easy and at the end 42 persons were able to solve it.
Before continuing, I’d like to say that there are many different ways to solve a reverse engineering challenge. I will try to follow a teaching way, in the sense that I would try to maximise the amount of concepts in the write-up against the more efficient solution. I think this post will be useful for those of you that didn’t even know how to attack the challenge… but OK, this is up to you guys to judge.
Said that, if any of you have solved Shuffled Love in a really cool way that deserves to be shared, please go ahead with an extra write-up or let us know in the comments!
Analysing the Binary
Let’s start, with a quick recon phase running the usual tools on the binary:
$ file ./c1
./c1: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=6f2afca4b092b19c4e03e228917c7d496876b619, stripped
$ strings -d c1
(...)
Shuffled Love
by p1c0
My PIN is %d
Your PIN:
You read my mind!!!. We are twin souls
--> 0x00CTF{Y0uR_th3_0n3_%x} <--
Oh. You are not the one :(.
;*3$"
$ readelf -a c1
(...)
Note: There is nothing special in the readelf output for this binary.
So we’ve got a 64bits dynamically linked stripped GNU/Linux binary. It looks like all the strings used in the program are easy to find (no string obfuscation), which is in general useful, as we will see, won’t help much in this case.
Assuming that this was one of the easy challenges, we can also suppose that the string 0x00CTF{Y0uR_th3_0n3_%x} is the actual flag. We can see a %x towards the end. That is the printf format string to print the hexadecimal representation of a number… So we have to find a number, calculate its hex representation and add it to the partial flag we have just found.
We have got quite some information just using pretty simple and standard tools :).
Finding the main function
Stripped binaries does not keep symbols so the first thing to do is to find the main function. In case you use some reversing tool like radare2, the tool will find main for you. However, for those that are learning I will briefly explain you how to find the main function on a standard GNU/Linux binary, that is, plain C code compiled with gcc without hackish modifications.
Any binary starts its execution at a certain memory address once it has been loaded in memory. That address is known as entry point. You can find the entry point of a binary using different tools. These are some examples:
Using readelf.
$ readelf -h c1 | Entry
Entry point address: 0x400590
Using gdb
$ gdb -q c1
(...)
(gdb) info file
Symbols from "/tmp/c1".
Local exec file:
`/tmp/c1', file type elf64-x86-64.
Entry point: 0x400590
Fine, but what does this entry point code do?. Good question :). The entry point for a standard binary basically contains a call to the libc function __libc_start_main whose prototype is like this:
int __libc_start_main(int *(main) (int, char * *, char * *), int argc, char * * ubp_av, void (*init) (void), void (*fini) (void), void (*rtld_fini) (void), void (* stack_end));
As you can see the first parameter that this function receives is actually the main function. Knowing this, let’s take a look to the code in the entry_point of our binary.
Using objdump:
$ objdump -d /tmp/c1 | grep -A 10 400590
0000000000400590 <.text>:
400590: 31 ed xor %ebp,%ebp
400592: 49 89 d1 mov %rdx,%r9
400595: 5e pop %rsi
400596: 48 89 e2 mov %rsp,%rdx
400599: 48 83 e4 f0 and $0xfffffffffffffff0,%rsp
40059d: 50 push %rax
40059e: 54 push %rsp
40059f: 49 c7 c0 00 09 40 00 mov $0x400900,%r8
4005a6: 48 c7 c1 90 08 40 00 mov $0x400890,%rcx
4005ad: 48 c7 c7 cc 07 40 00 mov $0x4007cc,%rdi
4005b4: e8 a7 ff ff ff callq 400560 <__libc_start_main@plt>
Or using gdb
gdb-peda$ x/12i 0x400590
0x400590: xor ebp,ebp
0x400592: mov r9,rdx
0x400595: pop rsi
0x400596: mov rdx,rsp
0x400599: and rsp,0xfffffffffffffff0
0x40059d: push rax
0x40059e: push rsp
0x40059f: mov r8,0x400900
0x4005a6: mov rcx,0x400890
0x4005ad: mov rdi,0x4007cc
0x4005b4: call 0x400560 <__libc_start_main@plt>
0x4005b9: hlt
Now, in order to continue, what you need to know is some details of the Linux 64bits ABI (Application Binary Interface). This interface covers, among other things, how to pass parameters to a function. For Linux 64bits, parameters are passed in the registers RDI, RSI, RDX and RCX respectively. Reality is actually a bit more complex but for reversing this binary we do not really need to know more. Those of you that want to know all details about this, just Google Linux ABI.
Therefore, looking to the code on the entry point, we can see that the first parameter (that is passed on register RDI is actually the address 0x4007cc. Or in other words, our main function is located at address 0x4007cc.
Looking at main
Now we can take a look to the main function.
$ objdump -d /tmp/c1 | grep -A 50 "4007cc:"
(...)
gdb-peda$ x/50i 0x4007cc
0x4007cc: push rbp
0x4007cd: mov rbp,rsp
0x4007d0: sub rsp,0x20
0x4007d4: mov rax,QWORD PTR fs:0x28
0x4007dd: mov QWORD PTR [rbp-0x8],rax
0x4007e1: xor eax,eax
0x4007e3: mov DWORD PTR [rbp-0x10],0x0
0x4007ea: mov DWORD PTR [rbp-0x14],0x0
0x4007f1: mov DWORD PTR [rbp-0xc],0x0
0x4007f8: mov edi,0x400918
0x4007fd: call 0x400530 <puts@plt>
0x400802: mov edi,0x400926
0x400807: call 0x400530 <puts@plt>
0x40080c: mov DWORD PTR [rbp-0x10],0x5a9e5
0x400813: mov eax,DWORD PTR [rbp-0x10]
0x400816: mov esi,eax
0x400818: mov edi,0x40092f
0x40081d: mov eax,0x0
0x400822: call 0x400550 <printf@plt>
0x400827: lea rax,[rbp-0x14]
0x40082b: mov rsi,rax
0x40082e: mov edi,0x400946
0x400833: mov eax,0x0
0x400838: call 0x400570 <__isoc99_scanf@plt>
0x40083d: mov edx,DWORD PTR [rbp-0x14]
0x400840: mov eax,DWORD PTR [rbp-0x10]
0x400843: mov esi,edx
0x400845: mov edi,eax
0x400847: call 0x400686
0x40084c: mov DWORD PTR [rbp-0xc],eax
0x40084f: cmp DWORD PTR [rbp-0xc],0x0
0x400853: jne 0x40086b
0x400855: mov eax,DWORD PTR [rbp-0x14]
0x400858: mov esi,eax
0x40085a: mov edi,0x400950
0x40085f: mov eax,0x0
0x400864: call 0x400550 <printf@plt>
0x400869: jmp 0x400875
0x40086b: mov edi,0x40099a
0x400870: call 0x400530 <puts@plt>
0x400875: mov eax,0x0
0x40087a: mov rcx,QWORD PTR [rbp-0x8]
0x40087e: xor rcx,QWORD PTR fs:0x28
0x400887: je 0x40088e
0x400889: call 0x400540 <__stack_chk_fail@plt>
0x40088e: leave
0x40088f: ret
We have got the code!. Unfortunately, gdb or objdump does not show pointers content so the code they dump are a bit hard to follow. For instance, take a look to this piece of code:
0x4007f8: mov edi,0x400918
0x4007fd: call 0x400530 <puts@plt>
You should know by now that this is a call to puts (a function that prints a string to stdout) that receives as first parameter(RDI) a pointer to 0x400918. If you check the content of that address in gdb the string will be unveiled.
gdb-peda$ x/s 0x400918
0x400918: "Shuffled Love"
Compare this to the output you get with radare2 or other advanced reversing tools (sorry guys radare2 is the only one I have, I couldn’t participate and win the binary ninja one 
).
$ r2 -AA c1
[x] Analyze all flags starting with sym. and entry0 (aa)
[x] Analyze len bytes of instructions for references (aar)
[x] Analyze function calls (aac)
[x] Emulate code to find computed references (aae)
[x] Analyze consecutive function (aat)
[x] Constructing a function name for fcn.* and sym.func.* functions (aan)
[x] Type matching analysis for all functions (afta)
-- 255 shades of (truecolor) grey
[0x00400590]> pdf @main
┌ (fcn) main 196
│ main ();
│ ; var int local_14h @ rbp-0x14
│ ; var int local_10h @ rbp-0x10
│ ; var int local_ch @ rbp-0xc
│ ; var int local_8h @ rbp-0x8
│ ; DATA XREF from 0x004005ad (entry0)
│ 0x004007cc 55 push rbp
│ 0x004007cd 4889e5 mov rbp, rsp
│ 0x004007d0 4883ec20 sub rsp, 0x20
│ 0x004007d4 64488b042528. mov rax, qword fs:[0x28] ; [0x28:8]=-1 ; '(' ; 40
│ 0x004007dd 488945f8 mov qword [local_8h], rax
│ 0x004007e1 31c0 xor eax, eax
│ 0x004007e3 c745f0000000. mov dword [local_10h], 0
│ 0x004007ea c745ec000000. mov dword [local_14h], 0
│ 0x004007f1 c745f4000000. mov dword [local_ch], 0
│ 0x004007f8 bf18094000 mov edi, str.Shuffled_Love ; 0x400918 ; "Shuffled Love" ; const char * s
│ 0x004007fd e82efdffff call sym.imp.puts ; int puts(const char *s)
│ 0x00400802 bf26094000 mov edi, str.by_p1c0_n ; 0x400926 ; "by p1c0\n" ; const char * s
│ 0x00400807 e824fdffff call sym.imp.puts ; int puts(const char *s)
As you can see, radare2 has already found main (probably in the same way we did, but automatically) and also resolves pointers to strings, show us the prototype of some standard function and therefore we can get, immediately, a pretty good snapshot of what main function does. Anyway, we are learning here so knowing how these tools works is a valuable asset… specially when somebody is trying to fiddle with those tools.
Finding the relevant function
So, now, you can use the tool you prefer to analyse main. I presume you had run the binary at least once so you know what the program does: shows some message, tells you its pin, ask for yours and shows a success/fail message. Knowing this, it is pretty easy to figure out that, the function we are interested on is:
0x400847: call 0x400686
0x40084c: mov DWORD PTR [rbp-0xc],eax
0x40084f: cmp DWORD PTR [rbp-0xc],0x0
0x400853: jne 0x40086b
And checking the calls to printf afterwards we can also easily figure out that this function returns 0 when we enter the right PIN.
Note: for Linux binaries, function return values in register
RAX
Now, the reversing task starts:
The PIN checking function
The PIN checking function is a bit long, so we will be analysing it in pieces. Let’s start with the first part of the function:
gdb-peda$ x/100i 0x00400686
0x400686: push rbp
0x400687: mov rbp,rsp
0x40068a: sub rsp,0x40
0x40068e: mov DWORD PTR [rbp-0x34],edi
0x400691: mov DWORD PTR [rbp-0x38],esi
0x400694: mov rax,QWORD PTR fs:0x28
0x40069d: mov QWORD PTR [rbp-0x8],rax
0x4006a1: xor eax,eax
0x4006a3: mov DWORD PTR [rbp-0x28],0x186a0
0x4006aa: mov DWORD PTR [rbp-0x24],0x0
0x4006b1: mov DWORD PTR [rbp-0x2c],0x0
0x4006b8: jmp 0x4006ff
This is a standard function initialisation (the so-called function prologue). You will find those 3 instructions very often when analysing binaries. These instructions just allocate space in the stack for the function local variables effectively creating the stack frame for this function. In this case the function is allocating 0x40 bytes for its local variables.
Then we see how the first (RDI) and the second (RSI) parameters received by the function are stored in the stack. in other words, in local variables. You can also see how the function stores the stack canary from fs:0x28 in order to detect buffer overflows. So it is time to name our local variables:
[rbp-0x8] -> Canary [rbp-0x24] -> Var2 = 0x0 [rbp-0x28] -> Var1 = 0x186a0 (1000000) [rbp-0x2c] -> Var3 = 0x00 [rbp-0x34] -> Par1 (PIN) - check the function call from main [rbp-0x38] -> Par2 (PASS) - check the function call from main
In this post, we are doing this manually for the shake of our own education. Most modern tools allows you to easily rename local variables in your functions and see the updated assembly using those names you provided. Knowing how to do this manually will help you understand those functions in any tool immediately.
After this initialisation we find a jump instruction to a fixed address. In general, this means that we have found a loop. That is not always the case, but compilers usually generate loops like this for C programs. So, lets start analysing the loop… yes, I can tell you right now that it is a loop :).
First Loop
This is the body of the first loop we have found in the function we are analysing.
0x4006b8: jmp 0x4006ff
0x4006ba: mov eax,DWORD PTR [rbp-0x34]
0x4006bd: cdq
0x4006be: idiv DWORD PTR [rbp-0x28]
0x4006c1: mov edx,eax
0x4006c3: mov eax,DWORD PTR [rbp-0x2c]
0x4006c6: cdqe
0x4006c8: mov BYTE PTR [rbp+rax*1-0x20],dl
0x4006cc: mov eax,DWORD PTR [rbp-0x2c]
0x4006cf: cdqe
0x4006d1: movzx eax,BYTE PTR [rbp+rax*1-0x20]
0x4006d6: movsx eax,al
0x4006d9: imul eax,DWORD PTR [rbp-0x28]
0x4006dd: sub DWORD PTR [rbp-0x34],eax
0x4006e0: mov ecx,DWORD PTR [rbp-0x28]
0x4006e3: mov edx,0x66666667
0x4006e8: mov eax,ecx
0x4006ea: imul edx
0x4006ec: sar edx,0x2
0x4006ef: mov eax,ecx
0x4006f1: sar eax,0x1f
0x4006f4: sub edx,eax
0x4006f6: mov eax,edx
0x4006f8: mov DWORD PTR [rbp-0x28],eax
0x4006fb: add DWORD PTR [rbp-0x2c],0x1
0x4006ff: cmp DWORD PTR [rbp-0x2c],0x5
0x400703: jle 0x4006ba
The loop starts with a jump to 0x4006ff as we had already mentioned, and at that address we find a comparison followed by a conditional jump. We can also see how one of our local variables is incremented just before the comparison. Let’s update our local variables list and name [rbp-0x2c] as i a loop index:
[rbp-0x8] -> Canary [rbp-0x24] -> Var2 = 0x0 [rbp-0x28] -> Var1 = 0x186a0 (1000000) [rbp-0x2c] -> i = 0x00 [rbp-0x34] -> Par1 (PIN) [rbp-0x38] -> Par2 (PASS)
Now we incorporate this information in the loop and let’s see what else we can figure out.
0x4006b8: jmp 0x4006ff
0x4006ba: mov eax,DWORD PTR [rbp-0x34] ; EAX=PIN
0x4006bd: cdq
0x4006be: idiv DWORD PTR [rbp-0x28] ; EAX/ Var1
0x4006c1: mov edx,eax
0x4006c3: mov eax,DWORD PTR [rbp-0x2c] ; EAX = i
0x4006c6: cdqe
0x4006c8: mov BYTE PTR [rbp+rax*1-0x20],dl
0x4006cc: mov eax,DWORD PTR [rbp-0x2c] ; EAX = i
0x4006cf: cdqe
0x4006d1: movzx eax,BYTE PTR [rbp+rax*1-0x20]
0x4006d6: movsx eax,al
0x4006d9: imul eax,DWORD PTR [rbp-0x28] ; EAX *= Var1
0x4006dd: sub DWORD PTR [rbp-0x34],eax ; Par1 -= EAX
0x4006e0: mov ecx,DWORD PTR [rbp-0x28] ; ECX = Var1
0x4006e3: mov edx,0x66666667
0x4006e8: mov eax,ecx
0x4006ea: imul edx
0x4006ec: sar edx,0x2
0x4006ef: mov eax,ecx
0x4006f1: sar eax,0x1f
0x4006f4: sub edx,eax
0x4006f6: mov eax,edx
0x4006f8: mov DWORD PTR [rbp-0x28],eax ; Var1 = EAX
0x4006fb: add DWORD PTR [rbp-0x2c],0x1 ; i++
0x4006ff: cmp DWORD PTR [rbp-0x2c],0x5 ; i > 5
0x400703: jle 0x4006ba
From the code above we can infer that there is another local variable that has not been used yet, and that it is actually an array. Look at this instruction:
mov BYTE PTR [rbp+rax*1-0x20],dl
Let’s reorder the expression in brackets:
mov BYTE PTR [rbp - 0x20 + rax*1],dl
This means that we are storing in dl 1 byte of an array located at rbp-0x20 indexed by RAX. So, let’s update our local variables list once again:
[rbp-0x8] -> Canary [rbp-0x20] -> data[] [rbp-0x24] -> Var2 = 0x0 [rbp-0x28] -> Var1 = 0x186a0 (1000000) [rbp-0x2c] -> i = 0x00 [rbp-0x34] -> Par1 (PIN) [rbp-0x38] -> Par2 (PASS)
Let’s look in more detail the first part of the loop:
0x4006b8: jmp 0x4006ff ; Loop Start
0x4006ba: mov eax,DWORD PTR [rbp-0x34] ; EAX=PIN
0x4006bd: cdq
0x4006be: idiv DWORD PTR [rbp-0x28] ; PIN / Var1
0x4006c1: mov edx,eax ; EDX = PIN / Var1
0x4006c3: mov eax,DWORD PTR [rbp-0x2c] ; EAX = i
0x4006c6: cdqe
0x4006c8: mov BYTE PTR [rbp+rax*1-0x20],dl ; data[i] = BYTE(PIN/Var1)
0x4006cc: mov eax,DWORD PTR [rbp-0x2c] ; EAX = i
0x4006cf: cdqe
0x4006d1: movzx eax,BYTE PTR [rbp+rax*1-0x20] ; EAX = data[i]
0x4006d6: movsx eax,al
0x4006d9: imul eax,DWORD PTR [rbp-0x28] ; EAX = data[i] * Var1
0x4006dd: sub DWORD PTR [rbp-0x34],eax ; Par1 = PIN - data[i] * Var1
The code above can be transcribed to:
data[i] = PIN / Var1
PIN = PIN - data[i] * Var1
This is pretty straightforward. Now let’s look to the rest of the loop that may look a little bit more weird.
0x4006e0: mov ecx,DWORD PTR [rbp-0x28] ; ECX = Var1
0x4006e3: mov edx,0x66666667 ; EDX = 0x6666667
0x4006e8: mov eax,ecx ; EAX = Var1
0x4006ea: imul edx ; EDX:EAX = EAX * EDX
0x4006ec: sar edx,0x2 ; EDX >>= 2 (34 shift of EDX:EAX !)
0x4006ef: mov eax,ecx ; EAX = Var1
0x4006f1: sar eax,0x1f ; EAX >>= 0x1f
0x4006f4: sub edx,eax ; EDX - EAX
0x4006f6: mov eax,edx ; EAX = EDX
So, believe it or no, this code divides by 10 the value of Var1. Without going into all the details, what it does is to substitute the division by a multiplication by the denominator reciprocal. The maths are not that difficult, but I will not go into that. If you are really interest, start reading this link.
In this case, we are multiplying the value of Var1 by 0x66666667 and dividing it by 0x400000000 (which is the result if shifting 1 34 positions). The last part of the code does not have effect in this case. I haven’t fully analysed it but in this case that code will always be zero. All this lead us to this code:
for (i = 0; i <=5; i++) {
data[i] = PIN / Var1;
PIN = PIN - data[i] * Var1;
Var1 = Var1 / 10;
}
In other words, we are storing in an array the decimal digits of the system generated PIN… In this case, just using the debugger to see what the loop produces may be enough for some reverse engineer to keep going and solve the challenge, but I think it is nice to look at the code compilers generate… it’s a pretty interesting exercise.
The Second Loop
The second loop is a bit longer so let’s analyse it again in pieces, for the sake of the readability.
0x400705: mov edi,0xa
0x40070a: call 0x400520 <putchar@plt>
This just prints a new line (and it is not part of the loop 
). Let’s continue.
0x40070f: mov DWORD PTR [rbp-0x28],0x1 ; Var1 = 1
0x400716: mov DWORD PTR [rbp-0x2c],0x0 ; i =0;
0x40071d: jmp 0x4007a3 ; Loop?
Some initialisation and a potential loop again. If you check the code at 0x4007a3, you will identify again a loop to 5. Now there is a big code section, that does some operations. Let’s look at them.
0x400722: mov eax,DWORD PTR [rbp-0x2c] ; EAX = i
0x400725: cdqe
0x400727: movzx esi,BYTE PTR [rbp+rax*1-0x20] ; ESI = data[i]
0x40072c: mov eax,DWORD PTR [rbp-0x2c] ; EAX = i
0x40072f: lea ecx,[rax+0x2] ; ECX = i + 2
0x400732: mov edx,0x2aaaaaab ; EDX = 0x2aaaaaab
0x400737: mov eax,ecx ; EAX = i + 2
0x400739: imul edx ; EDX:EAX = (i + 2) * 0x2aaaaaab
0x40073b: mov eax,ecx ; EAX = i +2
0x40073d: sar eax,0x1f ; EAX >>= 0x1f (This will always be 0)
0x400740: sub edx,eax ; EDX = (i+2) * 0x2aaaaaab / (2^32) => (i+2)/6
0x400742: mov eax,edx ; EAX = EDX = (i + 2) / 6
0x400744: add eax,eax ; EAX += EAX => EAX = EAX * 2
0x400746: add eax,edx ; EAX += EDX => EAX =EAX *EDX = EAX * 3
0x400748: add eax,eax ; EAX += EAX => EAX = EAX * 2 = ((i+2)/6) * 6
0x40074a: sub ecx,eax ; ECX = ECX - EAX = (i + 2) - (((i+2)/6) * 6) = (i+2) % 6
0x40074c: mov edx,ecx ; EDX = (i + 2) % 6
All this code may look pretty confusing. If you follow the comments I added at the right of each instruction, you will figure out how this instructions are actually implementing a modulus operator, which is what we get at the end of the block. Note that this part of the program is using again the reciprocal to perform a division. So, the code above calculates the module as the remainder of an integer division. Let’s see this with an example. Imagine that our index i is 6, so i + 2 is 8 and therefore it falls out of the array boundaries. The code above is calculating the following.
8 - (8/6 * 6) = 8 - (6) = 2
where the division is an integer division.
The rest of the code is simpler and straightforward to reverse.
0x40074e: movsxd rax,edx ; RAX = EDX
0x400751: movzx eax,BYTE PTR [rbp+rax*1-0x20] ; EAX = data[(i+2) % 6]
0x400756: mov ecx,eax ; ECX = EAX = data[(i+2) % 6]
0x400758: mov eax,DWORD PTR [rbp-0x2c] ; EAX = i;
0x40075b: add eax,0x3 ; EAX = i + 3
0x40075e: xor eax,0x6 ; EAX = (i+3) ^ 6
0x400761: cdqe
0x400763: movzx edx,BYTE PTR [rax+0x601058] ; EDX = global[RAX] = global [(i+3) ^ 6]
0x40076a: mov eax,ecx ; EAX = ECX
0x40076c: imul eax,edx ; EAX = EAX * EDX
0x40076f: xor esi,eax ; ESI = ESI ^ EAX = data[i] ^ (global[(i+3) ^ 6] * data[(i+2) % 6)
0x400771: mov edx,esi ; EDX = ESI
0x400773: mov eax,DWORD PTR [rbp-0x2c] ; EAX = i
0x400776: cdqe
0x400778: mov BYTE PTR [rbp+rax*1-0x10],dl ; data2[rax] = dl = data[i] ^ (global[(i+3) ^ 6] * data[(i+2) % 6)
There are a couple of comments we have to do with regards to this piece of code. The first one is that we use a global variable. Actually an array:
0x400763: movzx edx,BYTE PTR [rax+0x601058]
If you check the address 0x601058 you will find out that it is located in the data segment and it contains some predefined data. Depending on the tool you are using, you can extract the contents on different ways. On the command-line you can use the all- mighty objdump:
$ objdump -sj .data /tmp/c1
/tmp/c1: file format elf64-x86-64
Contents of section .data:
601048 00000000 00000000 00000000 00000000 ................
601058 01020103 0205 ......
Or with gdb
gdb-peda$ x/8b 0x601058
0x601058: 0x01 0x02 0x01 0x03 0x02 0x05 0x00 0x00
In any case we can conclude that the global array contains values {1,2,1,3,2,5}.
The other thing we have to mention is that we have found a new local variable. Let’s update once again our local variables table:
[rbp-0x8] -> Canary [rbp-0x10] -> data2[] [rbp-0x20] -> data[] [rbp-0x24] -> Var2 = 0x0 [rbp-0x28] -> Var1 = 0x186a0 (1000000) [rbp-0x2c] -> i = 0x00 [rbp-0x34] -> Par1 (PIN) [rbp-0x38] -> Par2 (PASS)
Now it is time to finish the analysis of this loop.
0x40077c: mov eax,DWORD PTR [rbp-0x2c] ; EAX = i;
0x40077f: cdqe
0x400781: movzx eax,BYTE PTR [rbp+rax*1-0x10] ; EAX = data2[i]
0x400786: movsx eax,al
0x400789: imul eax,DWORD PTR [rbp-0x28] ; EAX *= Var1
0x40078d: add DWORD PTR [rbp-0x24],eax ; Var2 += EAX {data2[i] * Var1)
0x400790: mov edx,DWORD PTR [rbp-0x28] ; EDX = Var1
0x400793: mov eax,edx ; EAX = EDX = Var1
0x400795: shl eax,0x2 ; EAX >>= 2 -> EAX = Var1 * 4
0x400798: add eax,edx ; EAX += EDX -> EAX = Var1 * 4 + Var1 = 5Var1
0x40079a: add eax,eax ; EAX += EAX => EAX = 2 * (5 * Var1)= 10 * Var1
0x40079c: mov DWORD PTR [rbp-0x28],eax ; Var1 = EAX = Var1 * 10
0x40079f: add DWORD PTR [rbp-0x2c],0x1 ; i++
0x4007a3: cmp DWORD PTR [rbp-0x2c],0x5 ; Loop to 5
0x4007a7: jle 0x400722
Here we’ve just found an interesting way to multiply by 10. Everything else is pretty straightforward. Our analysis concludes that this second loop can be represented by the following C code:
for (i = 0 i <=5; i++) {
data2[i] = data[i] ^ (global[(i+3) ^ 6] * data[(i+2) % 6)
Var2 += data2[i] * Var1;
Var1 *= 10;
}
Well, we are almost done. Let’s look at the final part of the code
0x4007ad: mov eax,DWORD PTR [rbp-0x38] ; EAX = Par2 = PASS
0x4007b0: xor DWORD PTR [rbp-0x24],eax ; Var2 ^ PASS
0x4007b3: mov eax,DWORD PTR [rbp-0x24] ; EAX = Var2 ^PASS -> return Value
0x4007b6: mov rdi,QWORD PTR [rbp-0x8] ; Check canary and return
0x4007ba: xor rdi,QWORD PTR fs:0x28
0x4007c3: je 0x4007ca
0x4007c5: call 0x400540 <__stack_chk_fail@plt>
0x4007ca: leave
0x4007cb: ret
Here we can see how the user provided password (actually an integer) is just xored against the value the function has calculated.
Solving the challenge
Now that we know how the program works we have to work this backwards in order to find the PIN that will make the function that we have just analysed, return a zero, Let’s look at the code we have got from our analysis:
char global[] = {1, 2, 1, 3, 2, 5};
int
func (int PIN, int PASS)
{
char data[], data2[];
int Var1, Var2, i, c= 100000;
for (i = 0; i <=5; i++) {
data[i] = PIN / Var1;
PIN = PIN - data[i] * Var1;
Var1 = Var1 / 10;
}
Var1 = 1;
for (i = 0 i <=5; i++) {
data2[i] = data[i] ^ (global[(i+3) ^ 6] * data[(i+2) % 6)
Var2 += data2[i] * Var1;
Var1 *= 10;
}
return Var2 ^ PASS;
}
Fortunately, the function uses static information for all its calculations (the program generated PIN that is fixed). The result of all the code above is always the same, independently of the PIN entered by the user (actually the PASS parameter). This will allow us to calculate Var2 that will be actually the PIN we are looking for. I will just leave this to the reader. Sorry guys, if at this point you can not generate the PIN and the flag, then you need to go one step back and learn some programming .
Note:You may be wondering why I have gone through all this process when there is a easy way to solve this (just keep reading if you haven’t spotted it yet). The main reason is that, this challenge was initially conceived as a keygen and not a CTF challenge. I had to modify it for the CTF so I thought that it would be also interesting to go through the whole reversing process.
How to solve this the ninja way
Well, you just need to go quickly through the check function and you will notice that the user password is only used at the very end. Therefore, just start the program in your preferred debugger, add a breakpoint just before the final xor and check the value of Var2 (rbp-0x24). That will be you the PIN.
The experienced reverser would had noted this just quickly browsing the code. Even the non experienced one will notice that the value calculated by the function is always the same, independently of the value entered by the user. What all this means is that you do not need to fully reverse all the function to solve this challenge. You should have notice that full reversing is a long process, specially if you do not use special tools. I have done it here, because, in order to be able to quickly identify this situations you should have some practice or in other words, you should completely reverse some programs to become familiar with certain patterns and idioms that will give you the experience and knowledge to easily identify situations like this.
Well, this is it for Shuffled Love. In case some of you had solved this in a different way (neither full reversing nor using the debugger) and want to share the techniques, please let us know in the comments. Also do not hesitate to share any doubt you may have or any mistake you may have spotted (I wrote this very quickly).
Many thanks to everybody that participated in the 0x00CTF 2017 event and also to all of you that have read this write-up
Stay tuned for the next one… but I can tell you that it may take a while until it is released.
.