Welcome to part 3 of 3 of this RE walkthrough. If you’ve somehow jumped straight in here, go look up the first 2 parts to catch up.
I’ll start this write-up with the debugger paused at the first instruction within the phase_4 function.
At first glance, this looks like its a lot simpler than the previous phase but I’m sure that won’t be the case.
The first hurdle in this phase is using the sscanf function again. This time its expecting a single number. If successful it will avoid jumping to a boom command.
It then checks to make sure that the number is greater than 0.
Once these checks are complete, it will retrieve the input you gave it and pass it to a new function named func4. The output of this function is compared to 0x37 to avoid the bomb so that must be the number we’re aiming for but I doubt it will be that easy this far on.
Looking at func4, I can see that this is a custom function. I can also see that the function has 2 calls which both call to itself so there is going to be some recursive execution involved in this one, which means it won’t be as simple as passing it 0x37 and moving on.
The first step is to take the input and compare it to 1. If it is 1 it will jump all iterations of the function and return 1 to the phase_4 function. To me this says that if i <= 1 return i else do something. As we already know the ouput will be compared to 0x37, so we know this is not what we want.
Looking closer at the else path it looks like there are two main iterations in the function that feed into each other.
The first cycle compares the input to 1 and continues to subtract 1 from it until it passes the jump, where the function will return 1, which is passed to the second function. This function will subtract 2 and will feed back into the first. This will be continued for an unknown amount of times.
I could see that this was more than likely an advanced mathematical equation, which almost certainly was using bracket notation to control execution. I could see from the function that it resembled something like x = (x-1)+(x-2) but the recursive nature of this made it difficult to determine accurately.
I decided to attempt feeding the function 55 (0x37) to see how it reacted to it, so I restarted the execution and tried it. After some time I realised that the function was hanging. This led me to believe that it was not writen to ingest large numbers in this instance. This narrowed it down slightly but only left me with 2 options. Either attempt feeding it different values or try and gather some information with OS research. I went with OS research.
A quick search of the web for (x-1)+(x-2) = 55 recursive function found that the famous Fibonacci sequence has the formula F(n-1) + F(n-2) which is not far off my estimate. This mathematical equation generates a sequence of numbers of which the sum of the two previous numbers result in the next number in the list eg. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … The ninth number in this iteration is 55 which is the number we’re looking for so I tried giving it 9.
It worked! So on to phase 5.
After setting a bp and feeding a dummy value, you should be paused within phase_5. The first hurdle for this is checking the length of the string input.
Its looking for exactly 6 characters so go back and change your input if needed.
The next part of this phase is a loop which is going to increment edx and compare it to 5. The xor edx, edx instruction is a common method of clearing a register, which is used here to ensure edx is 0 before initiating the loop.
So basically, this is going to loop six times and as we have six characters in our string, I’m guessing that this is going to be comparing each character to something.
The value above is moved into esi prior to the loop so this could be the string that contains the real input. The part of the loop shown below is how it selects the characters from the string.
The top mov is used to move through each character in our input string based off the counter in edx. The and instruction is using masking to omit the unused binary bits before moving it back into eax. It then uses this number to select a character from the string stored in esi before pushing the character onto the stack. It will repeat this until it has six characters selected from the string.
Directly after the loop, there is a call to strings_not_equal which we have seen before. This takes two strings and compare them.
It looks like the string its looking for is giants so we just have to figure out how to manipulate the previous loop to output the string we need.
So we know that there are 16 characters within the string and we know its using masking to generate a number using the first 4 bits of the input which gives 16 possible options. So this would look something like this.
If you cross reference this to the first 4 bits of the equivalent character in a conversion table it would result in the string Opukma.
A site I like to refer to when I want do quick conversions of short strings is:
Correct! On to phase 6.
Even at first glance its obvious that this phase is by far the biggest and most complex of all the phases. The tactic of splitting the code down isn’t going to work this time as there are nested loops throughout.
Before we get into to this mind melter we can deal with the call to <read_six_numbers> which we know is expecting 6 integer inputs. Go ahead and set a breakpoint at the instruction immediately after the function call and give it a 6 number input.
In essence, this whole chunk is designed to check that each of the 6 inputs are below 6 and that they are all unique. So we can assume from this that it is expecting the numbers 1,2,3,4,5 and 6 in an unknown order. For now, give it any combination and step through it until you come to the xor instruction immediately after the last jump.
The complexity continues to increase from here. I chose to go with 1, 2, 3, 4, 5 and 6 for my input. I first mapped out the flow of execution plotting each cmp and jmp instruction so I could see the paths it could take then I began stepping through to get an understanding of how it was using the inputs.
There are 3 main stages in the remainder of this phase. It gets tricky here as it processes all the inputs and conducts multiple actions before it fails unlike the previous challenges which would fail at each input.
The first stage is a series of nested loops which is designed to, first check that each number is not 0. It then pulls a value from a list based on the current input and finally pushes the value onto the stack, iterating by 8 bits each time.
The second stage re-pushes the values back onto the stack (I’m not certain as to why it does this).
The final stage takes the values in the new list and compares them with the next value in the list. If the value is less than the previous value, the bomb goes off. So I had a look at the values in the new list.
As you can see, each value in the list is hex. So going off what we already know, we need to try and get this list in order, largest to smallest. So that would look something like this.
- node 4 = 0x3e5
- node 2 = 0x2d5
- node 6 = 0x1b0
- node 3 = 0x12d
- node 1 = 0xfd
- node 5 = 0xd4
So I restarted and added this to the list of inputs…
Overall, a very challenging binary to reverse but very well put together. It gets progressively more challenging at a steady pace which I like. A great intro for beginners or if you’re like me, a good refresher on AT&T if its been a while.
I had one last look through the code before I shut the book on this and I noticed that within the phase_defused function which is called at the end of every phase, there is a secret function which I have not covered and will look into in the future if I get a chance.
Thanks for reading.