Writeups – Hastad, Triptych (UIUCTF)

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.

Hastad

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.

Triptych

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.

About Norman

Sometimes, I write code. Occasionally, it even works.
This entry was posted in Bards, Computers, Jesting. Bookmark the permalink.

5 Responses to Writeups – Hastad, Triptych (UIUCTF)

  1. Hi, excellent write-up, I just have few follow up questions.
    1. In the Triptych challenge, how did you figure out that it was self-modifying code just by looking at the assembly (you mentioned that after first screenshot “Right, self-modifying code it is”)? I just getting started with RE so I would like to know how to make sense out of the assembly. I get stuck every time when I look at the assembly. Can you please point me in the right direction. Thank you!

    • Norman says:

      Hello! I inferred this by the presence of the mprotect call:

      .text:0000000000400B18 mov [rbp+addr], offset unk_400000
      .text:0000000000400B20 mov rax, [rbp+addr]
      .text:0000000000400B24 mov edx, 7 ; prot
      .text:0000000000400B29 mov esi, 1000h ; len
      .text:0000000000400B2E mov rdi, rax ; addr
      .text:0000000000400B31 call _mpro

      We can see that mprotect is called to change the memory protection from 400000, such that it is writeable and executable. This is generally required for self-modifying code (which edits itself in memory, then executes its modified code), therefore, we can infer that this is related to the challenge.

  2. taybrown90 says:

    Is there a way to dump or create a copy of the executable with GDB after the_second or the_third functions have been decrypted dynamically, so you have a permanent copy to analyze? This was my first time attempting to reverse a self-modifying binary.

    • taybrown90 says:

      I was using Binary Ninja with the Binjatron plugin for what it’s worth. I had GDB running alongside it, and could see the bytes being written to the_second’s location in memory, but was scratching my head on the best way to get to “update” the binary with the new code

      • Norman says:

        Hello! I’m not aware of a single, pre-packaged way to do it, but I achieved it by dumping the memory from the process for the_second, the_third and validate, and then using a hex editor to simply edit the corresponding code on disk (as well as the corresponding call to main, to skip decryption loops).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.