Bitbanging challenge

The binary

$ file bin
bin: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/, for GNU/Linux 2.6.32, BuildID[sha1]=917a8066affea23dc0c37a01c9004f8efa4e4c25, not stripped

We’ve got an unstripped x64 binary. Let’s see how it behaves upon running:

$ ./bin   
Usage: ./bin [key]

We need to provide a key!

$ ./bin asdf  
The key has to be a number!

So we’ve got some more information about the needed input now.

$ ./bin 111111
Wrong length!

We even get feedback about the length, we could bruteforce the length by providing any number from length 1 to n. Let’s take a look at the disassembly instead.

Binary download
Binary BinaryNinja file download


Okay so we need to provide a number of length 4.
If only one input is accepted that leaves us with a 1 in 10^4 probability. Let’s dig some further into the disassembly.

	gdb-peda$ disassemble main
	Dump of assembler code for function main:
	   0x00000000004005f6 <+0>:	push   rbp
	   0x00000000004005f7 <+1>:	mov    rbp,rsp
	=> 0x00000000004005fa <+4>:	sub    rsp,0x20
	   0x00000000004005fe <+8>:	mov    DWORD PTR [rbp-0x14],edi
	   0x0000000000400601 <+11>:	mov    QWORD PTR [rbp-0x20],rsi
	   0x0000000000400605 <+15>:	cmp    DWORD PTR [rbp-0x14],0x2
	   0x0000000000400609 <+19>:	je     0x40062e <main+56>             ; continue if input was provided
	   0x000000000040060b <+21>:	mov    rax,QWORD PTR [rbp-0x20]
	   0x000000000040060f <+25>:	mov    rax,QWORD PTR [rax]
	   0x0000000000400612 <+28>:	mov    rsi,rax
	   0x0000000000400615 <+31>:	mov    edi,0x400854                   ; otherwise load Usage: ... string
	   0x000000000040061a <+36>:	mov    eax,0x0
	   0x000000000040061f <+41>:	call   0x4004c0 <[email protected]>          ; print Usage: ... string
	   0x0000000000400624 <+46>:	mov    edi,0x1
	   0x0000000000400629 <+51>:	call   0x4004e0 <[email protected]>            ; exit binary
	   0x000000000040062e <+56>:	mov    rax,QWORD PTR [rbp-0x20]       ; continue execution here if input was provided
	   0x0000000000400632 <+60>:	add    rax,0x8
	   0x0000000000400636 <+64>:	mov    rax,QWORD PTR [rax]            ; load input into RAX
	   0x0000000000400639 <+67>:	mov    rdi,rax                        ; mov input into RDI as calling argument (check x64 ABI!)
	   0x000000000040063c <+70>:	call   0x4004b0 <[email protected]>          ; call string_length() on our input
	   0x0000000000400641 <+75>:	cmp    rax,0x4                        ; check if it has length 4
	   0x0000000000400645 <+79>:	je     0x40065b <main+101>            ; if yes continue execution
	   0x0000000000400647 <+81>:	mov    edi,0x400865                   ; otherwise load "Wrongth length!" into EDI
	   0x000000000040064c <+86>:	call   0x4004a0 <[email protected]>            ; print that string
	   0x0000000000400651 <+91>:	mov    edi,0x1
	   0x0000000000400656 <+96>:	call   0x4004e0 <[email protected]>            ; end program afterwards
	   0x000000000040065b <+101>:	mov    DWORD PTR [rbp-0x4],0x0        ; set RBP-0x4 to 0
	   0x0000000000400662 <+108>:	jmp    0x400690 <main+154>            ; continue execution at main+154
	   0x0000000000400664 <+110>:	mov    rax,QWORD PTR [rbp-0x20]       ; main+110 is here
	   0x0000000000400668 <+114>:	add    rax,0x8                        ; pointer to our input
	   0x000000000040066c <+118>:	mov    rdx,QWORD PTR [rax]
	   0x000000000040066f <+121>:	mov    eax,DWORD PTR [rbp-0x4]        ; sets EAX to current loop iteration
	   0x0000000000400672 <+124>:	cdqe   
	   0x0000000000400674 <+126>:	add    rax,rdx
	   0x0000000000400677 <+129>:	movzx  eax,BYTE PTR [rax]             ; move first byte of input into RAX (higgest bit)
	   0x000000000040067a <+132>:	movsx  eax,al
	   0x000000000040067d <+135>:	lea    edx,[rax-0x30]                 ; loads input into edx
	   0x0000000000400680 <+138>:	mov    eax,DWORD PTR [rbp-0x4]
	   0x0000000000400683 <+141>:	cdqe                                  ; expands it to a quad word (4bytes to 8bytes)
	   0x0000000000400685 <+143>:	mov    DWORD PTR [rax*4+0x601060],edx ; inserts input into an array (see below for visualization)
	   0x000000000040068c <+150>:	add    DWORD PTR [rbp-0x4],0x1
	   0x0000000000400690 <+154>:	cmp    DWORD PTR [rbp-0x4],0x3        ; main+154 is here!, use RBP-0x4 as loop condition
	   0x0000000000400694 <+158>:	jle    0x400664 <main+110>            ; if it is <=3 jmp to main+110
	   0x0000000000400696 <+160>:	mov    DWORD PTR [rbp-0x4],0x0        ; ontinue execution here after array is filled in first loop!
	   0x000000000040069d <+167>:	jmp    0x4006d8 <main+226>            ; directly jump to main+226
	   0x000000000040069f <+169>:	mov    eax,DWORD PTR [rbp-0x4]        ; main+169 is here.
	   0x00000000004006a2 <+172>:	cdqe   
	   0x00000000004006a4 <+174>:	mov    eax,DWORD PTR [rax*4+0x601060] ; load an input byte depending on loop iteration into EAX
	   0x00000000004006ab <+181>:	test   eax,eax
	   0x00000000004006ad <+183>:	js     0x4006c0 <main+202>            ; pre emptive loop exit if test input_byte,input_byte fails
	   0x00000000004006af <+185>:	mov    eax,DWORD PTR [rbp-0x4]        ; otherwise load loop counter into EAXeax
	   0x00000000004006b2 <+188>:	cdqe   
	   0x00000000004006b4 <+190>:	mov    eax,DWORD PTR [rax*4+0x601060] ; load current input_byte into EAX again
	   0x00000000004006bb <+197>:	cmp    eax,0x9                        ; compare if it to 9
	   0x00000000004006be <+200>:	jle    0x4006d4 <main+222>            ; if it is <= 9 (meaning it is a number!) continue loop
	   0x00000000004006c0 <+202>:	mov    edi,0x400873                   ; otherwise move "The key has to be a number!" into edo
	   0x00000000004006c5 <+207>:	call   0x4004a0 <[email protected]>            ; print that string
	   0x00000000004006ca <+212>:	mov    edi,0x1
	   0x00000000004006cf <+217>:	call   0x4004e0 <[email protected]>            ; and exit the binary
	   0x00000000004006d4 <+222>:	add    DWORD PTR [rbp-0x4],0x1        ; add +1 to loop counter and continue loop at main+226
	   0x00000000004006d8 <+226>:	cmp    DWORD PTR [rbp-0x4],0x3        ; main+226 is here another loop condition check with 3 iterations
	   0x00000000004006dc <+230>:	jle    0x40069f <main+169>            ; if iteration <= 3 jump to main+168
	   0x00000000004006de <+232>:	mov    eax,DWORD PTR [rip+0x20097c]   ; 0x601060 <array>; if all 4 bytes are verified as numbers MSB is loaded into EAX
	   0x00000000004006e4 <+238>:	cmp    eax,0x5                        ; and compared to 0x5
	   0x00000000004006e7 <+241>:	jne    0x4007b6 <main+448>            ; if its not equal to 0x5 we jump to main+448, meaning our first digit should be a 5!
	   0x00000000004006ed <+247>:	mov    eax,DWORD PTR [rip+0x200971]   ; 0x601064 <array+4>; # load second input byte into EAX
	   0x00000000004006f3 <+253>:	neg    eax                            ; negate EAX, meaning: 0 - EAX and put the result into EAX
	   0x00000000004006f5 <+255>:	mov    edx,eax                        ; move that value into EDX
	   0x00000000004006f7 <+257>:	mov    eax,DWORD PTR [rip+0x200967]   ; 0x601064 <array+4>; load 2nd input byte into EAX again
	   0x00000000004006fd <+263>:	add    eax,0x1                        ; add 1 on our 2nd input byte
	   0x0000000000400700 <+266>:	and    eax,edx                        ; to a bitwise AND with the negative of our 2nd input byte and our 2nd input byte+1 (check below!)
	   0x0000000000400702 <+268>:	and    eax,0x4                        ; do another bitewise and of the prior result with 0x4
	   0x0000000000400705 <+271>:	test   eax,eax						
	   0x0000000000400707 <+273>:	je     0x4007a2 <main+428>            ; jumps if TEST EAX, EAX results in a set zero flag
	   0x000000000040070d <+279>:	mov    eax,DWORD PTR [rip+0x200955]   ; 0x601068 <array+8>; load 3rd input byte
	   0x0000000000400713 <+285>:	cmp    eax,0x6                        ; compare it to 6
	   0x0000000000400716 <+288>:	je     0x40078e <main+408>            ; if is equal to 6 goto a bad exit, so 3rd input has to be !=6
	   0x0000000000400718 <+290>:	mov    eax,DWORD PTR [rip+0x20094a]   ; 0x601068 <array+8>; load 3rd input byte again
	   0x000000000040071e <+296>:	cmp    eax,0x5                        ; check against 5
	   0x0000000000400721 <+299>:	je     0x40078e <main+408>            ; if its equal to 5 goto a bad exit again, so it has to be !=5 too!
	   0x0000000000400723 <+301>:	mov    eax,DWORD PTR [rip+0x20093f]   ;0x601068 <array+8>; load 3rd input byte
	   0x0000000000400729 <+307>:	neg    eax                            ; oh its the same routine as above!
	   0x000000000040072b <+309>:	mov    edx,eax
	   0x000000000040072d <+311>:	mov    eax,DWORD PTR [rip+0x200935]   ; 0x601068 <array+8>
	   0x0000000000400733 <+317>:	add    eax,0x1
	   0x0000000000400736 <+320>:	and    eax,edx
	   0x0000000000400738 <+322>:	and    eax,0x2                        ; just this time we need to make sure it passes the and eax, 0x2 followed by a test
	   0x000000000040073b <+325>:	test   eax,eax
	   0x000000000040073d <+327>:	je     0x40078e <main+408>
	   0x000000000040073f <+329>:	mov    eax,DWORD PTR [rip+0x200927]   ; 0x60106c <array+12>; load 4th input byte
	   0x0000000000400745 <+335>:	cmp    eax,0x8                        ; compare it to 8
	   0x0000000000400748 <+338>:	je     0x40077a <main+388>            ; bad exit if it is 8, so it has to be !=8
	   0x000000000040074a <+340>:	mov    eax,DWORD PTR [rip+0x20091c]   ; 0x60106c <array+12>	# and to make it more annoying another check for the 4th byte
	   0x0000000000400750 <+346>:	neg    eax                            ; again the same routine
	   0x0000000000400752 <+348>:	mov    edx,eax
	   0x0000000000400754 <+350>:	mov    eax,DWORD PTR [rip+0x200912]   ; 0x60106c <array+12>
	   0x000000000040075a <+356>:	add    eax,0x1
	   0x000000000040075d <+359>:	and    eax,edx
	   0x000000000040075f <+361>:	and    eax,0x8                        ; just another test condition again
	   0x0000000000400762 <+364>:	test   eax,eax
	   0x0000000000400764 <+366>:	je     0x40077a <main+388>
	   0x0000000000400766 <+368>:	mov    edi,0x40088f                   ; This one is the congrats message and the desired exit
	   0x000000000040076b <+373>:	call   0x4004a0 <[email protected]>
	   0x0000000000400770 <+378>:	mov    edi,0x0
	   0x0000000000400775 <+383>:	call   0x4004e0 <[email protected]>            ; until here
	   0x000000000040077a <+388>:	mov    edi,0x40089d                   ; Everything from here and below are "bad exits" we want to avoid!
	   0x000000000040077f <+393>:	call   0x4004a0 <[email protected]>
	   0x0000000000400784 <+398>:	mov    edi,0x1
	   0x0000000000400789 <+403>:	call   0x4004e0 <[email protected]>
	   0x000000000040078e <+408>:	mov    edi,0x4008ab
	   0x0000000000400793 <+413>:	call   0x4004a0 <[email protected]>
	   0x0000000000400798 <+418>:	mov    edi,0x1
	   0x000000000040079d <+423>:	call   0x4004e0 <[email protected]>
	   0x00000000004007a2 <+428>:	mov    edi,0x4008ab
	   0x00000000004007a7 <+433>:	call   0x4004a0 <[email protected]>
	   0x00000000004007ac <+438>:	mov    edi,0x1
	   0x00000000004007b1 <+443>:	call   0x4004e0 <[email protected]>
	   0x00000000004007b6 <+448>:	mov    edi,0x4008ab						
	   0x00000000004007bb <+453>:	call   0x4004a0 <[email protected]>				
	   0x00000000004007c0 <+458>:	mov    edi,0x1
	   0x00000000004007c5 <+463>:	call   0x4004e0 <[email protected]>				
	End of assembler dump.

Input to array

The array insertion in the first loop looks like the following with the input 1234 :

gdb-peda$ x/8x 0x601060
0x601060 <array>:	0x0000000200000001	0x0000000400000003
0x601070 <array+16>:	0x0000000000000000	0x0000000000000000

Each byte of the input was inserted into the array, starting with the most significant bit from the input (1) at the lowest array position. Each byte has a full 8 byte if space in the array.

Calculating the 2nd input byte!

	   0x00000000004006ed <+247>:	mov    eax,DWORD PTR [rip+0x200971]   ; 0x601064 <array+4>
	   0x00000000004006f3 <+253>:	neg    eax
	   0x00000000004006f5 <+255>:	mov    edx,eax
	   0x00000000004006f7 <+257>:	mov    eax,DWORD PTR [rip+0x200967]   ; 0x601064 <array+4>
	   0x00000000004006fd <+263>:	add    eax,0x1
	   0x0000000000400700 <+266>:	and    eax,edx
	   0x0000000000400702 <+268>:	and    eax,0x4
	   0x0000000000400705 <+271>:	test   eax,eax
	   0x0000000000400707 <+273>:	je     0x4007a2 <main+428>

This snipped from the above code block is used to calculate the 2nd input byte. So First we load our 2nd provided digit into EAX. Next up we negate that number in a 0 - EAX manner and put the result into EDX. Then we load our original 2nd input byte again and add 1 to it.

The next instruction is the “gimmick” of this binary ! Let’s see what we can do here. We have to provide a number, between 1 and 9 to pass all prior checks!

If we negate any possible number our 2nd input byte maps to following (only least significant bit is important):

  • 1 -> f -> 1111
  • 2 -> e -> 1110
  • 3 -> d -> 1101
  • 4 -> c -> 1110
  • 5 -> b -> 1011
  • 6 -> a -> 1010
  • 7 -> 9 -> 1001
  • 8 -> 8 -> 1000
  • 9 -> 7 -> 0111

So if we provide a 1 as our 2nd input byte we get an f in this step and so on..

So next up our 2nd input is pulled back into EAX again and 1 is added. This corresponds to the following possible mapping:

  • 1 -> 2 -> 0010
  • 2 -> 3 -> 0011
  • 3 -> 4 -> 0100
  • 4 -> 5 -> 0101
  • 5 -> 6 -> 0110
  • 6 -> 7 -> 0111
  • 7 -> 8 -> 1000
  • 8 -> 9 -> 1001
  • 9 -> a -> 1010

Then the 2nd input byte +1 is compared bitwise to the negative version of our 2nd input byte. The result of that comparison resides in EAX.

Directly following is another AND eax, 0x4 and the result from this is self tested against with TEST eax, eax.

So we need to find an appropriate input, which can pass this testing chain resulting in the TEST eax, eax not setting the zero flag so the jump equal can take place!

This can only be the case if the 2nd input is 3 OR 4! Let’s see why.

Let’s visualize this with the 2nd input being 3:

0x3 gets negated to 0xfffffffd, from which only the LSB is relevant so 0xd. 0xd corresponds to 1101 in binary. If we do the first and operation now we have:

        1101 (0xd)
AND	0100 (0x3 +1)
	0100 (0x4)

So the result for that is 0100. Next up follows and eax, 0x4. We can rewrite this as and 0x4, 0x4. Why? Because the EAX there is the result of bitwise and operation with the negated 2nd input and the 2nd input +1. Hence and 0x4, 0x4 obviously results in 0x4 again, which let’s us pass the following TEST EAX, EAX check.

The same math can be done if our input for the 2nd byte is 4. Check it yourselfs :) !

Calculating the 3th input byte!

The calculation is the same procedure as in the 2nd input byte. Also we have an additional restriction/hint that the number cannot be an 5 or 6.

For this 3rd input byte

  • 1 -> f -> 1111
  • 2 -> e -> 1110
  • 9 -> 7 -> 0111

When we do the bitwise and between the negative input value and with input+1 we get:

1+1 =   0010   	           2+1 =    0011  		9+1 = 	 1010
    AND 1111       		AND 1110     		     AND 0111
  	________     		    ______      		______
   	0010        	 	    0010        		 0010

All these inputs result in an EAX of 0x2, which let’s us pass the following and eax, 0x2 and test eax, eax check.

Calculating the 4th input byte!

Once again the same calculation routine as two times before. I’ll cut it short this time. an input of 7 let’s us pass the following check

MISC notes

A few notes for the assembly above:

Note: TEST sets the zero flag ZF, when the result of the bitwise AND operation is zero. If two operands are equal their bitwise AND is zero only when both are zero… TEST also sets the sign flag SF, when the most significant bit is set in the result and the parity flag PF, when the number of set bits is even.

In the case here we do TEST EAX,EAX on our input bytes, the result will never be 0, except we enter a 0 of course. The following Jump Sign (JS) will just take place if the most significant bit is set after the TEST operation, meaning the result of that is negative.

Jump if Equals (JE) tests the zero flag and jumps if the flag is set. JE is an alias of JZ [Jump if Zero] so the disassembler cannot select one based on the opcode. JE is named such because the zero flag is set if the arguments to CMP are equal.



$ ./bin 5317
Congrats man!