[0x00CTF] Shuffled Love Write-Up

(pico) #1

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 :(.
$ 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 <[email protected]>

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 <[email protected]>
   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 <[email protected]>
   0x400802:	mov    edi,0x400926
   0x400807:	call   0x400530 <[email protected]>
   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 <[email protected]>
   0x400827:	lea    rax,[rbp-0x14]
   0x40082b:	mov    rsi,rax
   0x40082e:	mov    edi,0x400946
   0x400833:	mov    eax,0x0
   0x400838:	call   0x400570 <[email protected]>
   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 <[email protected]>
   0x400869:	jmp    0x400875
   0x40086b:	mov    edi,0x40099a
   0x400870:	call   0x400530 <[email protected]>
   0x400875:	mov    eax,0x0
   0x40087a:	mov    rcx,QWORD PTR [rbp-0x8]
   0x40087e:	xor    rcx,QWORD PTR fs:0x28
   0x400887:	je     0x40088e
   0x400889:	call   0x400540 <[email protected]>
   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 <[email protected]>

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 :stuck_out_tongue: ).

$ 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 <[email protected]>

This just prints a new line (and it is not part of the loop :slight_smile: ). 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 <[email protected]>
   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};

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 :slight_smile: .

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.



Very neat and detailed writeup @0x00pf . Good job on this.
I love it for a beginner/entry challenge, since it’s not just plain reversing on easy mode, but essentially teaches you to understand and especially read the code carefully.
If you can do this you can easily spot the ninja way :slight_smile: .
If not you at least can brush up your asm skills.



Thanks for the writeup @0x00pf!
The challenge was quite fun and easy to solve after spotting the ninja way :smiley:
Can’t wait for the next writeups!