Crackme: In Memory Bruteforce
The hardest crackme from the NVISO Cyber Security Challenge 2015 qualifications was a really interesting challenge and forced me to come up with a creative solution. You can download the crackme below:
As with any crackme, you have to provide a password in order to obtain the flag. If you start reverse engineering the crackme you will quickly understand that the password checking function is far from trivial and that the flag is generated from that password. The only way to obtain the flag is to reverse the password checking algorithm.
Instead of spending a lot of precious time on reversing all that assembly code, I decided to try instrumentation based techniques. Unfortunately, instruction counting using intel Pin and breakpoint counting using gdb both failed because of the algorithm specifics. So we have to learn more about that algorithm.
Here is what the password checking algorithm does:
- the main function (0x400809) only accepts 20 characters long passwords
- each character of the password is split in individual bits to form a 160 integers array of 0’s and 1’s (functions 0x40074a and 0x4006bd)
- a loop (0x400924) load 12 different ranges of different sizes of the integer array in a single integer by reassembling the bits (function 0x4007ac)
- those 12 integers are checked by 11 (one is used twice) different functions through a call table (function 0x4009f0)
- each of those functions is different and non trivial (some of them even use sprintf …)
The instruction counting and breakpoint counting could not work because the checksum ranges are not byte aligned and sometimes cover more than 4 characters. Thus any guided bruteforce of the password would have been slow and tricky to implement.
But I still did not want to reverse those checksum functions.
What if we could bruteforce those checksum functions directly? We would obtain the correct values and could then reassemble the bit array and obtain the password. The biggest range is 31 bits long which should not take long to bruteforce.
What is the easiest way to instrument those functions for the bruteforce? An old time reverser best friend: LD_PRELOAD of course. Our code will be loaded with the crackme and we can bruteforce those checksum functions in the init function of our preloaded library.
As we can see, more than one values are validated by some checksum functions. However, because the result needs to be a printable password, the largest values are a safe bet. We can now reassemble the bits and obtain the flag.
The flag is simply the base64 decoding of the password (function 0x400e9c).
Reverse engineering is not only about static analysis and debugging, binary instrumentation can be a real time saver. Know your tools. Learn how to use Intel Pin and Valgrind, how to write LD_PRELOAD libraries and automate GDB.
As a side note: this password also validates but gives the wrong flag ;)