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
$ 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 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 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
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!
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.