What's a bitbang?

Note: This is a re-upload of an old write-up.

This is another write-up from an interesting little challenge. The original forum post about it can be found here.

To get your hands on the challenge I've prepared the base64 text representation of it once again below so you can try it yourself.

base64 -d < bin.b64 | gunzip > bin

H4sIADY2B18AA+1Zb2wcRxWfvfP5T+ycL6lTHNsiGxoLN9SXc7CN06rNnf/E68ixjWM3KsVZn31r
3zX3x9zuBdsiIeA66skkNQKkIFEJgYCgghpAqgIf6guBhHxBjtRGSCBhEKmcJqUpTYMFqY+Z2Td7
u3N7JHzhU+Z09/b95r03b968mZuZ/XJX7z6HICBWHOgZRDmXn/J+wBdrDBGMtaEy/LsN1aFiImqS
8yO/ha6BaUZLQc6Jv0X42+bQ+TaH30LrQI5RwURdyFz8FnqrDFkoQqKhR3z1uHXU4x61UD/4EXZY
9Ryg1wB6DSDP6DI4tsz1rwi+Q2BvCPrFaCfIdZrkSRm4roXIcwYMZUr9FtoMcs2c3mexXjF68OIB
OgjtFYrLbegXo2wcdkUjY63Nu6KhxmgknppunG5rbWxt9qoJ727qkwdku/uGqTyLowg+VyE9B0j9
12dPTLy2/r2nMxdnhSuo//S/+nrrBdDPZeaD92uzDV5XAN9SAH+sAN6CWGZYS3kBeYTjNE7C0oqU
6YiGplKaiqaSkbg2gVQtGVXiSJaJjKxqwaQmx4IRgkzGEnFAZNTd29PeIe/27vaS1h3w0WMq0E9u
PFM1kTJSw/JqrXKUUjZPWan26HgJssZYNOEOE95gwp0m3GfCi0x4mwk356U0d6tUWnAdKxeRNJ/R
XKtHKPib0ot6fbYliauy9Rr+rdzmx0+ED5OqGytZXOpfIDxx+cYy5ccIT1y9kaH85whPXLxxjvKD
hCeu3fgu5R2Yn1hk/jS925O+elhK/1Wa+9vtgaGeyxk/nmnS5QvLJYRcvovXwdUfYb07E5XbcFDP
H8IdG5YaBzCR5tbcUvr60drztGe4O5tGlkhFdgULv0jtj1wkvZjwMv6NAar/lb9TAxfWndiAlL4t
XVjdKwmXpKvr2hbDWjmzVrkN29HbP/H0tzeIeJg3DWPF1Th2bOSS6ySGhA9oS0uimzi2F6VcN7+B
9Qxj7xOF7PLIjVmsQ57xSIjpY7ekdGpl7tgth/aYtNC1Ii0gKX1paQjHgGqufmc9m10i0V79OX6i
InOZUip2eTVBoLm1Iq1qScEaq/2G8Dx+utx1j5i4+UROy7PQdU86IwnLla+jyjcypwaWKZCumh/F
HZ3ruifMHbvnPP57prqHVi8U0er5zPQmMz+3Vna8akklDV/7iDVcgRs27FxYcH2pTMSCrsr5K7h2
wfUFzP7zD+lfL7gmSUVG2L48t1I0n6l88Vu0fpiKF2tHF1z7dU3tyIJrr6HVktNy4KD2L7g+ScVK
Nd+Cq84Q25wTK8ViVUsvEy99xEsa1Qny9ArB6gzPB8nTqwQrNbBnDOzOPYbtNLAVA3sUY3p+BA4F
ng2ks4HhwFDvqXpvsYiT7VQjoQd70nd70m/1Pn6dzsELHzlXE9iANP+uJjb9keVnb/qd3vTdTmwh
W/Unae6iIO25mXqHTNDnRwKfD4wEDgfki4u5fP7gIsxpmMICXjWG1eCk8qRYr4rPH1FmRjagQ8lE
fFLEa92kFt6OhsKKiHExHFRFLSGOKWJQjKdiY0pyO+rAgsmgpoqxYHw7CkRjCVUTtbCSVLajvoQm
qglRCaozuFrDCGmv1vkU+S8ka9vyv7PZE5j6cbcGMG3FUTmLqQdn/O8wPYGpBxa7Kpj/wuwgEqY9
Qm1FSemiUOIhOPmvWMW2dprWLXt5hHaAvITl6Yrn9uxzV++vLP9i6Qm0t+apnZ/e8QkEMmRNPol9
e5P4EHB7Tjo6NrK1kdSFiO84fxUCtLs9Lzva3dWnnV1u8VRRu7vhay7J7TtZLLnb5koOuP1Jd1vA
7Qu4G9rdIpbD8u3uUurnT/A3jO2Y1++H5WF5WB6W+5VlOPedA8qKwNEKoFNFutxG4DvhnLIVeHaO
qAWenY/YcbIa6uu4+g/XswlCzzh0e2zvOurUebZunof6DcAPAC1n9oFuQdZi7GFhn8rWymmgbL0v
AfoxoGvQPsNXgGd+s/bKOB4vx7Q/GZDPAs/ieRv4c1D//yrsHMuXH8K4vg70EtBrQN8Gypfujo4n
xYbhsVRcS4kt3mavr7E1Rbmm402tXl+zt/lxHRd3+5pafa2+Pff10YmjxO4FrLjDOE9bcSfSbPEi
I5+suMvIIytebOSbFS+xHScnzoKMLV5m5IkV32DkkxUvN+aVFa9Ai7b4RnTbFncb9zhWvNKYp1bc
gwZs8U3G/YMV34zWbPFHjHlvxauM+W7FtyDRFn/UNj+deDayc60VrzbmsxXfivy2eA0asMVr8zAy
T4vQ+1ker6B1+f6T9c+B4+/j4l8L+BSHewHn191Oaj/nJ1svDtLn/HjOgp1lzs5JKp8/Lj8o0K9C
/X2V1m1Gq2VW+79E9nFABez8lv4+kuf/NWonf9z/DPK8//+gv/n56RKInfx8qBXIPY0b+UGerfuf
EuzvdV6jeH7+dAv29z3PCcSbGjQK8ux/RBbIHc3WvHyrp3by5+NEAfuzBfDTBfCfQru8/78q0N8r
xH/HViRx8tdov3LrA7vruQ7xJNclpCiAX0Wk3Ro0zdn5BcizdYmdsT4UdHk+PoJDl78L8m/CBCh2
2Ptf47CPwxMOvV+8/bYCdt6jftqsw+NJTdVSExPecSTL+zsG5d6eg0OyjEL4jDoZUTUlKWsxeTya
iCsqlggl5MloYiwYlUNaIqnKwdQ0Gk/EpqKKpoS8n2lpa7EXkici8YgcTCaDM7IS15IzaCIZjCly
KBWLzWAVEydjSc0iOhbRqHv7BgMHuuSuvk7sn+4se7aohJDc+Vxf4EBPh7WG3j9iqLtvWO6SwJrU
OYjk7t7+9kCv3L9v38GuIXko0N7bJbN7zHE1RZ1Hcs/QATkXlqEDHSQoQ8GxqEKvQf1+88UmbRLJ
SiioBeFm1CqgX5pasbyrU76aWDP6YblUxXVqQg4H4yHsjtzTjytCkbicUpWQuSckHJgfU1Uwo1/Q
7j8qD0K/OqJBVcVjTa53+eZxn1nISTBsQ4G86kxMC45hqiV1GmZPuMdKcgp54wlN8Qbaexq14CRw
k/GUdywViYYaIyFEuXBQDSNvaCaO7elUS+o1R5WkGknELYyM65JKNEgE4WkqqpEmcYfJo3cygR80
ZRr/0vH0JhN0cLxKGNIvHErmOF1VTx1dgz2/MJ6k/gRjkXFEzOot6cZwZJEXz4gYTl2befi/FvL/
SpYItq7n3ivpfB0nz79fIPf+5rvv3HsbnRc5+SKOb+L02T5UA2DHffTJ//1dfBZg+my/eobzn52H
SpG19CH97MP02b72PABnASfnJwHln1ueRfrZiOmz/e8oHJjY+YoVPn6HkX62Yfpsn3wO9N2c/w6O
ktcB6yZ9tp/OgL5YwH9WyP6nyGSP7btXQJ/1k48fw18E/Xbg2f58DfTZ+dAFOrz+aZR710gK+/+Y
goE2vUalhR//NKfP9vuLIDjKyXs4+k1On50LboM+Hy+ef4XTN84PELB2p1XeY2XR9zl9tq/phIbK
OHm+/z9G1vnL9hsDoB+7j/7POP3c+1Odb+bkef0lTp+db9ZA/w4nz8ePvGYgOc7ClHufai/P82/h
b6VJn+2Pqx9Q/y/gP9Nn+3HxAfXfRvrYMf3c+26dZ++52fgyfZYHZ7j22TltrfK/t8/oe5y+sX+H
Bvz30V/j9Nm+1++x+snrs7IOGNNn+8UBUGzg5Hl7TkFv38fhTJ/PP/5ebZOpbXP5KlyoVXALLr/+
mnPXXF6C9s/CwH0cf3ch+3sru/Z9cAE2yBnn38//B0gMFoZQIgAA

Initial analysis

$ file bin
bin: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, 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 brute force the length by providing any number from length 1 to n. Let's take a look at the disassembly instead. First we can directly see the correct user input length being 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. After validating the key size all four values are stored byte by byte into an array:

The loop iterates (0 <= loop counter <= 3) and accesses the argv[1] string based on the loop counter. Each element is then stored into the array. We can notice the array access with a fixed offset of 4 (array[rax*4]), which indicates the field width of each array element. 4 bytes corresponds to an int even on 64-bit.

When checking the length is done another loop construct verifies that each input byte is <= 9, meaning it double checks that the user only inputs numbers. If that's not the case we go to the bad exit and get notified with "The key has the be a number!". Once we pass that check we reach this part:

Here the first array element of our user input is compared against the integer value 5. If there is no match control flow is redirected to another early exit. So we know for sure that the flag starts with a "5".!

Current flag: 5XXX

Afterwards the second input byte is looked at! 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 backtrack a bit. 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 result of this addition and the negation of our 2nd input byte is thrown into the and instruction. This and happens on bit level and each bit is flipped to the classic boolean logic. The result of that operation resides in eax. Directly following is another and eax, 0x4 and the result is set thrown into test eax, eax to set the ZERO flag accordingly. With a set ZERO flag we're out!

So to summarize: 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 control flow follows the desired good path! This can achieved in the case of our 2nd input being a 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 bit-wise 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 (as test is just a fancy way of using and) check. The same math can be done if our input for the 2nd byte is 4. Check it yourself :)!

Current flag: 5[3/4]XX

Following this we can directly see that the 3rd input byte cannot be equal to 6 or 5 as it would lead to yet another bad exit. This leaves us with 8 possibilities. However the calculation of the correct input is the same procedure as for the 2nd input byte, with the exception being that the and operation is done with 2 instead of 4.

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

When we do the bit-wise 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.

Current flag: 5[3/4][1/2/9]X

For the last input byte we follow the same checking routine for a third time with the only modification being the and operation yet again. 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.

Current flag: 5[3/4][1/2/9]7

$ ./bin 5317
Congrats man!

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.