This weekend, I participated in the UIU CTF. This was a challenging but well-crafted CTF with a good range of challenges: disappointingly, I was only able to solve two challenges in the time allocated. Without further ado, writeups.
This challenge was presented as two text files, with a note which mentions that “e=3”. This is a dead give-away that this is some twist on Hastad’s broadcast attack, where you can recover a plaintext if the same message is sent with 3 or more keys, and ‘e’ is small.
I had a look for public implementations of this attack, and many existed – but all of them needed a number of ciphertexts and a number of public key moduli – we had 3 moduli, but a large number of ciphertexts.
A few moments of brute force, courtesy if Python’s excellent itertools, and we have our solution.
This challenge was presented as an ELF executable, which you can download here.
Opening this up in IDA pro, we are greeted with our first sign of the type of trolling to be inflicted in this challenge:
Right, self-modifying code it is. If we follow the code down a bit further, we can see the self-decrypting code in the_first:
Following this a bit further, we can see the mangled original code in the_second:
This looks like it’d be a hassle to decrypt manually, but it doesn’t take any input from the user or the environment – so it’s a safe bet to simply let the program run, breakpoint at this instruction, and decrypt, breaking at 0x400ACD (the call to the_second, instead of the_second: if gdb implements breakpoints by placing 0xCC in the broken function, a decryption loop will erase the breakpoint).
This yields our decrypted version:
We can see that this is likely a repeat of the first function. We can use IDA’s “Load Additional Binary” feature to patch the application and create a new disassembly of the_second:
This repeats an additional time, until we call validate at 0x4006A6. At this time, I thought it would be a good idea to dump a patched executable and solve it with angr: I attempted to patch the call at 0x400B40 (in main) to directly call a decrypted validate at 0x4006A6, and use “Apply patches to input file” (Edit -> Patch Program) to write a new executable which directly called validate with no funny business, but I discovered that the decrypted functions, loaded via “Load Additional Binary”, didn’t count as patches, and therefore, weren’t written to disk.
At this point, I reviewed the validate function in IDA. At a high level, it looked like a three-layer character substitution cipher, something like the following:
The simple solve for this is to create a lookup table. We can do this by breakpointing the character compare function at 0x4007CE: we pass in a string of “a-z”, and we see what it comes out with. We should be able to determine what ciphertext corresponds to each character, and using this, derive the original key the validate function is checking for.
You can find the solution here.
As always, thankyou to the UIU CTF organisers for putting together this event. While it’s disappointing that I was only able to solve so few challenges, it is only through being humbled that we continue to grow.
For those of you attending BSides, see you all at BSides next week. For everyone else, see you in WPI CTF.