Tools used: exeinfo, IDA Pro
Codes & Binaries: https://github.com/jmprsp/labyrenth/tree/master/Window-Challenge-4
Description: This challenge is written in C and compiled as a 64 bit binary. It is a modified version of the Water pouring puzzle. To solve this challenge, you would need to find the shortest number of steps required to get to the specified end state.
The challenge is expecting an input from the user. Ahhh typical serial cracker challenge? Let’s check if it is packed via exeinfo and IDA Pro.From the figures below, we can conclude that the binary isn’t packed. =D
Let’s start analzying… Back Tracing from the string as highlighted in the above figure, we will come across the following function @ 0x0140001280.
If you were to analyze the function, you will come across a strlen check.
From the above figure, we know that the input string must be 32 character long. Further down, we will come across a check to ensure that the input characters must be >= 0x31 && it must also be <= 33.
To check it manually, suppose we enter 0, which is equivalent to 0x30. Adding 0x30 to 0xFFFFFFCF will give us 0xFFFFFFFF which is above 2 therefore failing the check test.
If we were to enter the value 4, the summation will give us 0x100000003. Now eax takes only the last 4 bytes and therefore we are comparing 3 to 2. As 3 is larger than 2, we fail the test again.
The only values that will pass this test is between 1 and 3.
If we manage to clear all the validation test, we would then reach the address 0x14000151C in which a function(0x140001750) is called. If this function returns 0, we would get a “try again” message. So it seems like we would need to ensure that this function returns a 1.
Zooming into the function @ 0x140001750, we can see that it set a variable initial state into 0x0, 0x0, 0xD, 0x7.
Further down the function, we will come across the end state that we wanted 0x??, 0xA, 0xA, 0x??. With that the code will set eax to 1!
What can be observed is that with the given inputs, the state of the variable changes accordingly. In other words we must give the correct input such that the end state of the variable become 0x??, 0xA, 0xA, 0x?? from 0x0, 0x0, 0xD, 0x7.
We know that the input is expecting 32 characters which equates to 16 combinations based on the puzzle. Each combination can be in the form of 0x11, 0x12, 0x13, 0x21, 0x22, 0x23, 0x31, 0x32, 0x33. However the state wont change if the input values are 0x11,0x22,0x33. This reduces out possible inputs to only 0x12, 0x13, 0x21, 0x23, 0x31, 0x32.
6^16 == forever…. thus bruteforcing might not be a wise choice.
SMT Solver would do the job…. but let’s try the easier approach of manual processing first =D. I reversed the code in 0x140001750 into a php script. You may find the script in the github link provided. Now let’s do some observation.
The above figure shows something interesting. We tested 6 different possible combination for the first input and we end up with only 3 distinct outcome. The first outcome is being back to the initial state. Which leaves us with only 2 distinct outcome. From the figure below, we would just need to either go down the path from 21????? or 31?????.
Hypothesis ==> if we only go down unique paths, we could potentially reach the end state without taking forever!