Security Fest CTF *-bit challenges, organizer writeup

by klondike

I wrote the 128-bit, 512-bit and 1024-bit challenges for the Security Fest CTF, this year’s topic was Swordfish so the challenges follow the idea of the quotes being used in the movie regarding 128-bit, 512-bit and 1024-bit ciphers. Sadly, neither of the challenges were solved despite my best attempts. In this post I’ll explain how I expected participants to solve them.

The three challenges provide a binary using a clearly broken encryption, the idea was that once you had figured out the insides you should be able to crack the cipher yourself (128-bit) or ask the cryptography expert in your team for help (512-bit and 1024-bit). In order to prove they worked as expected, a simple python code to solve the challenges was written too.

If you want to test, these challenges are available online.

128-bit

This was intended to be the easiest one of the three challenges. The inner workings are as follows:

  1. The RSA modulus n=0xc92b337654ec925bd5e0de72479522c5 is loaded
  2. A 128-bit random integer is generated (using getrandom). This is repeated until the integer is bigger than 2^64 and smaller than n.
  3. A 64-bit random IV is generated.
  4. The flag is read from stdin and padded using PKCS#7
  5. A 3-DES key is generated from the 128-bit integer for this for each of the 192 bytes of the key, the lowest 7 bits of the integer are used to generate the 8-bit key by shifting them one position to the left and calculating the right parity bit (remember that a bit on each DES key byte is parity), then the 128-bit integer is rotated 7 bits to the left.
  6. The flag is encrypted using 3-DES-EDE in CBC mode with the provided IV and the resulting key.
  7. The 128-bit integer is encrypted using RSA with modulus n=0xc92b337654ec925bd5e0de72479522c5 and g=3.
  8. The encrypted integer is written to stdout.
  9. The iv is written to stdout.
  10. The encrypted flag is written to stdout.

The vulnerability in this one is that the modulus is so small that it can be easily factorized with your favorite tool in really little time, once factorized, calculating the RSA inverse to decrypt the 128-bit integer and use it to generate the 3-DES key is quite trivial.

As to why did I choose DES over AES? Well if you see the DOD screen you’ll read “DES 128 Bit Encrypted Security”. Hence the choice of parameters 😉

512-bit

This is a bit more complicated, as we are given a P2P UDP daemon that tries to ping the others (as was the case in the movie). The inner workings here are as follows:

  1. The binary loads the provided configuration from the program parameters, a network key read from a file, an integer being the node identifier, a listen address and the address of the other nodes in the network.
  2. A UDP socket is created using the listen address.
  3. An alarm handler is set up so the node will periodically ping other nodes.
  4. A random IV is generated along with a counter
  5. The main loop is the executed

The main loop basically waits for packets until either one comes or an alarm is produced (interrupting the recv call).

The packet format is something similar to this: node_id||message_counter||iv||CHACHA*(message||SHA512(node_id||message_counter||iv||message)).

Here || means concatenation, CHACHA* is a broken version of the CHACHA function and SHA512 is the 512-bit SHA-2 function as defined by NIST. Message can be either the strings PING or PONG.

CHACHA* uses the following data as key: “expand 32-byte k”||key||node_id||iv||counter

On the counter the last 8 bits are 0 and are increased for larger messages.

When a packet is received and decoded correctly, the daemon will reply with a PONG message to the sending node if the message was a PING or show that a PONG was received from the remote node. Once the timeout expires, the daemon will send a ping to all the nodes in the network.

The cryptographic vulnerability is in the way in which the CHACHA function was implemented, in particular, the final add with the data used as key was removed making the function reversible, this meant that given a known plain-text (for example the first message sent which is always a ping) it’s possible to reverse the block function and obtain the encryption key, this is why the sha512 hash is encrypted so that at least a full block of CHACHA* stream is available on the packet. This is why a pcap file with some packets was also provided.

1024-bit

Here I didn’t use ANY library functions at all to make reversing harder, instead I used systemcalls directly. This program used an static version of libtomcrypto to perform a 1024-bit DH exchange with the following parameters:

p=0xc749a06459e733e1774155ceb4fc5b505d79332e89a3c244d6d9467126b63ee4b26b244aeea2e97578df370c01340b663cc4a52dae14115b82d829856cc4ac2fdc5b5ab8b7f6f72c1393fc0526b63011bcfc4d1b9eb5dbce6e3e3a39271665a12f443d4f99efe52f4decdf645dda02186e0c01758f8425693282d6e978f6ebfb
B=0x71f1c59b591eb383700602392e1c3acdb1908524cd684b1692f9d0766f23c79d97b3a3d13aea67fe3f9c045ad2775b3b053e1fd48275dfe5573a7f2c63ec891f382ff59fe9adb360a1c06e32fd3b877abf3d1b6b74ecf124d0b73c176e27e51df12240af731c6b8dded0b5ee8e842f7bcf16f9c795f04d0a36bfc63d2a381d99

The program will then use the shared 1024-bit secret as an RC4 key, write to stdout the public key and then proceed to encrypt with RC4 the input it reads.

Cryptographically this approach is unbreakable as it was implemented (well you could try to break the 1024-bit DH exchange but still unlikely you’d do so in the ca 24 hours the CTF lasted). The flaw is in how the private key used in the DH exchange was generated. For this, the current clock was read in little endian and then for the next bytes of the key, the byte 4 positions before was xored with that one position before to generate the key, these numbers where chosen as they provided the largest pattern without repeating and being simple enough. The solution was as simple as checking the modification time of the file in the provided tar file and use that to generate the private key, the DH exchange and the RC4 key to decrypt the flag.

Conclusion

To be sincere I’m quite sad that nobody could solve any of the three challenges, as can be seen, except for maybe 512-bit the cryptography isn’t particularly hard and I didn’t use strong obfuscation techniques either (at most manual calling of syscalls in 1024-bit). Maybe the problem was the time limits of the CTF, eitherway I’d like to hear about how I can make the upcoming challenges better for next time.

I also do have the sources for the different challenges if anybody is interested, although I don’t see much value in them.