Tridea is VolgaCTF 2024 Quals task, category reverse.

Task files:

  1. tridea

  2. flag.png.enc

Solution files:

  1. tridea_solution.zip

Summary

Tridea, as in "Triple IDEA", is a utility that encrypts / decrypts input data in ECB mode with three keys in encrypt-decrypt-encrypt fashion:

\[C = E_{K_3}(D_{K_2}(E_{K_1}(P))).\]

The key derivation function is exceptionally bad: it decreases the total key length to \(48\) bits, \(16\) bits per each of the \(K_1\), \(K_2\), and \(K_3\).

As triple encryption is used, we can further reduce the workload applying a MITM attack to achieve complexity about \(O(2^{32})\).

1. Reversing

1.1 Anti-reverse and self-ptrace ing

Opening the task binary tridea in any disassembler (e.g. IDA) we can notice that some functions are not being disassembled correctly. The reason is a technique colloquially called disassembly desynchronization [1, Ch. 21].

Also, trying to debug tridea binary causes it to exit immediately, which resembles anti-debugging technique called self-ptrace ing [2]. The core of this technique is to call ptrace system call, and there are several ways to do it: calling ptrace() library wrapper, dynamically loading libc.so and manually locating the wrapper function, calling the system call directly using syscall instruction.

If we check binary’s imports table we won’t see ptrace() being imported:

$ readelf --dyn-syms tridea | grep ptrace

However, searching for syscall instruction within .text we get a hit:

$ ROPgadget --binary ./tridea | grep syscall
0x0000000000001363 : add byte ptr [rax], al ; mov rax, 0x65 ; syscall
0x000000000000136a : add byte ptr [rax], al ; syscall
0x0000000000001366 : mov eax, 0x65 ; syscall
0x0000000000001365 : mov rax, 0x65 ; syscall
0x000000000000136c : syscall

We see syscall is indeed used, and 0x65 is ptrace system call number [3]

As to how syscall invocation is arranged for, typically it’s done in a constructor function (check .init_array).

Anyway, these are minor obstacles and can be easily combated by nop ing.

1.2 Locating the functions of interest

That’s the most daunting part of the challenge for sure.

The logic of the binary is obvious - it encrypts and decrypts input files (take a look at its usage message).

Essentially, we need to find out:

  1. location of the block encryption and decryption functions (that process a single block of data)

  2. location of the wrappers that encrypt / decrypt the given buffer

  3. location of the key schedule and / or key derivation functions - to understand exactly how the input passphrase is transformed to the key.

Identifying the cipher also might be a huge help.

We won’t go into detail here, but give the necessary functions offsets along with the original names and their brief descriptions:

  • 0x2409 (pass_phrase_to_keys) - turns user-supplied pass phrase into three \(128\)-bit keys, treated as uint16_t key[8]

  • 0x1a10 (key_sched) - key schedule for encryption, turns \(128\)-bit key into an array of round keys, uint16_t K[52]

  • 0x1bd6 (key_sched_rev) - key schedule for decryption, sim.

  • 0x2642 (encrypt) - encrypts input data

  • 0x27e7 (decrypt) - decrypts input data

  • 0x22c9 (encrypt_block) - encrypts an \(8\)-byte block with a set of round keys

  • 0x230a (decrypt_block) - decrypts an \(8\)-byte block with a set of round keys

  • 0x2337 (pad) - pads input data

  • 0x23c7 (unpad) - removes the padding.

1.3 Finding the vulnerability

Examining the functions encrypt_block and decrypt_block we can find that they scream Lai-Massey scheme [4], and IDEA is one of the most prominent ciphers of this type. To verify we can try to encrypt IDEA’s test vectors.

Anyway, the true identity is irrelevant as the actual vulnerability is the function 0x2409 (pass_phrase_to_keys).

In a series of rather pointless manipulations pass_phrase_to_keys reduces the user’s input to three uint16_t values - \(48\) bits total. These values are used to generate three \(128\)-bit keys via a deterministic operation that in the source code looks like this:

uint16_t pkey1, pkey2, pkey3;  // the three keys
...
for (int i = 0; i < 8; i++) {
key1[i] = (PBOX1[(pkey1 + i) & 0xFF] << 8) | PBOX2[((pkey1 >> 8) + i) & 0xFF];
key2[i] = (PBOX3[(pkey2 + i) & 0xFF] << 8) | PBOX4[((pkey2 >> 8) + i) & 0xFF];
key3[i] = (PBOX5[(pkey3 + i) & 0xFF] << 8) | PBOX6[((pkey3 >> 8) + i) & 0xFF];
}

The PBOX es are permutations of length \(256\).

Therefore, the effective keyspace is \(2^{48}\) values.

2. MITM attack

We’re given an encrypted file flag.png.enc and we know it’s a PNG, so it starts with values:

00000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452  .PNG........IHDR

So we have a known plaintext-ciphertext pair \((P, C)\) and therefore can:

  • bruteforce \(48\) bits of the keys (doable, but doubtful)

  • split the \(E_{K_3}(D_{K_2}(E_{K_1}(P)))\) operation and apply meet-in-the-middle attack [6].

The basic idea is as follows:

  1. bruteforce \(16\)-bit key \(K_3\) (\(2^{16}\) values total), for each calculate \(B = D_{K_3}(C)\) and store these \((K_3, B)\) in a hash map

  2. then bruteforce \(2^{32}\) \((K_1, K_2)\) pairs, calculate \(R = D_{K_2}(E_{K_1}(P))\) and search for \(R\) in the map.

At some point we get a hit and the corresponding \(K_1\), \(K_2\), \(K_3\) are the keys we’re looking for. Using these we then decrypt flag.png.enc.

It’s also possible to store pairs of keys \((K_1,K_2)\) in the hash map (total of \(2^{32}\) pairs) and make only up to \(2^{16}\) searches, which is faster, but requires significantly more memory - that’s your run-of-the-mill time-memory tradeoff.

2.1 Implementing the attack and decrypting the flag

There are multiple ways the outlined attack can be implemented. As the core IDEA implementation functions are compiled to x86-64, they are fast enough, so we can use them as is, and they won’t slow down the attack.

This reusing is achieved by the means of LIEF framework [7]. Task’s binary tridea is effectively turned into a library (shared object) libtridea.so that exports the following core functions:

  • key_sched

  • key_sched_rev

  • encrypt_block

  • decrypt_block

The attack implementation files can be found in tridea_solution.zip. The main file is solution.cpp, and make_libtridea.py prepares the binary.

We also need to reverse-engineer a fairly straightforward fragment of code (0x24f4-0x261d) that turns three \(16\)-bit keys into the full \(128\)-bit IDEA keys. This function uses six statically defined PBOXes that can be extracted with the help of the auxiliary script export_pboxes.py.

Finally, although solution.cpp implements decryption function and decrypts the flag image itself, having successfully executed MITM attack we can use the three found \(16\)-bit keys to decrypt the flag with auxiliary script decrypt.py.

Using this auxiliary script decrypt.py allows us to skip reversing function decrypt, see the comments preceding its declaration in solution.cpp.

Both auxiliary scripts use Qiling DBI framework [8].

To perform the attack:

$ unzip tridea_solution.zip
$ OMP_NUM_THREADS=`nproc` docker compose up
$ sudo chown -R $USER flag.decrypted.png
$ xdg-open flag.decrypted.png

Opening the decrypted image we get the flag: VolgaCTF{91f74d6b27a851db0f2c33c8eab460ce}.

References