[Hard] Tsayaki

Tea Collisions

6^th February 2024 / Document No. D24.102.32

Prepared By: aris

Challenge Author(s): aris

Difficulty: Hard

Classification: Official

Synopsis

• In this challenge the player is called to recover the IV from a TEA-CBC encryption oracle. Having IV, they must find four distinct keys such that they all encrypt to the same ciphertext. The goal is to implement the "TEA equivalent keys attack" which reduces the efficient keyspace of TEA from 128 bits to 126 bits.

Description

• You find yourself in the middle of a deadly ancient maze. The maze sprawls before you, its secrets veiled in shadows, its gates locked tight against intruders. With thousands of keys shimmering under the harsh light, you steel yourself for the daunting challenge ahead. Each chamber of the maze presents a new puzzle to unravel, each gate a barrier to overcome. Armed with determination and resolve, you set forth into the labyrinth's depths, knowing that your survival hinges on unlocking the path forward by finding the proper key. With each new chamber you enter, you are greeted with a cup of tea—a brief respite from the perilous journey that lies ahead. But the tea is not the only gift bestowed upon you in these chambers. With each cup, you receive a hint that will guide you on how to move on.

Skills Required

• Familiar with Python source code auditing.
• Familiar with finding the correct keywords to research for a problem online.
• Good knowledge of how the TEA cipher works.
• Familiar with bitwise operations.

Skills Learned

• Learn about the equivalent keys attack in TEA cipher.
• Become more familiar with translating a problem into keywords to search online.
• Low-level understanding of how addition and the bitwise XOR operation work.

Enumeration

In this challenge, we are provided with two files:

• server.py : This is the main script that runs when we connect to the challenge instance.
• tea.py : This is the same file that was also provided in the challenge Iced Tea. It is an implementation of the TEA cipher in ECB and CBC mode.

Analyzing the source code

Let us analyze the main flow of the server script.

from tea import Cipher as TEA
from secret import IV, FLAG
import os

server_message = os.urandom(20)
print(f'Here is my special message: {server_message.hex()}')

used_keys = []
ciphertexts = []
for i in range(ROUNDS):
    print(f'Round {i+1}/10')
    try:
        ct = bytes.fromhex(input('Enter your target ciphertext (in hex) : '))
        assert ct not in ciphertexts

        for j in range(4):
            key = bytes.fromhex(input(f'[{i+1}/{j+1}] Enter your encryption key (in hex) : '))
            assert len(key) == 16 and key not in used_keys
            used_keys.append(key)
            cipher = TEA(key, IV)
            enc = cipher.encrypt(my_message)
            if enc != ct:
                print(f'Hmm ... close enough, but {enc.hex()} does not look like {ct.hex()} at all! Bye...')
                exit()
    except:
        print('Nope.')
        exit()

    ciphertexts.append(ct)

print(f'Wait, really? {FLAG}')

Notation

Let us denote the encryption key as $K$ and the TEA encryption as the function $E$. Then, $E_K$ denotes the TEA cipher running with $K$ as the key. The function $E$ receives two parameters.

• $M$, which is the message to be encrypted. This parameter is required in both ECB and CBC modes.
• $IV$, which is the IV that will be used by the cipher. This parameter is used only in CBC mode.

Analyzing the core flow

To get the flag, we must successfully complete a specific task 10 times in a row. The task is explained below:

1. The server generates a random global message $M$ that will be reused for each round.
2. First we are asked to submit our target ciphertext $ct$ in hexadecimal format.
3. Then, we have to provide four distinct 16-byte encryption keys $k_0, k_1, k_2, k_3$.
4. For each $k_i$, the server computes $C_i = E_{k_i}(M, IV)$. If any $C_i$ is not equal to $ct$, the script is terminated.

Last but not least, it should be noted that in case $C_i \neq ct$, the server outputs both $C_i$ and $ct$ to the screen to prove us that they do not match indeed and then it exits.

Steps 2-4 are repeated 10 times and if we pass all the tests, we get the flag.

At this point, it is safe to assume that the task is to find four distinct keys $k_i$ such that all result in the same ciphertext. However, there are some additional parameters that make the problem relate not only to the encryption keys.

• We do not know the IV used by the server to encrypt $M$.

• We are not permitted to submit the same ciphertext more than once, due to the assertion check:

  assert ct not in ciphertexts
  

To be able to produce the same ciphertext as the server, we need to know the IV so that should be our first step before figuring out how to send $k_i$.

Solution

Finding the vulnerability

Recovering the IV

Since we know both the message to encrypt, the corresponding ciphertext and we get to choose the symmetric key, recovering the IV of the cipher is an easy task to do. Let us recall how the CBC encryption works. The ciphertext is computed as follows: $$ C_i = \left{ \begin{array}{ll} E_K(M_i \oplus IV) & , & i = 0\ E_K(M_i \oplus C_{i-1}) & , & i>0 \end{array} \right. $$ Similarly, decryption is algebraically defined as: $$ M_i = \left{ \begin{array}{ll} D_K(C_i) \oplus IV & , & i = 0\ D_K(C_i) \oplus C_{i-1}) & , & i>0 \end{array} \right. $$ The IV is included only in the first block of the entire message. Looking at the decryption routine, we can solve for the $IV$ as: $$ IV = M_0 \oplus D_K(C_0) $$ Therefore we can solve for the $IV$ by XORing the first block of $M$ and the first decrypted ciphertext block $C_0$. As we are provided with the server message, we know $M_0$ but a small step is required to obtain $C_0$. We cannot compute $C_0$​ locally as we do not possess the IV. However, we can take advantage of the validation check done by the server and the message that is printed in case the validation fails.

cipher = TEA(key, IV)
enc = cipher.encrypt(my_message)
if enc != ct:
    print(f'Hmm ... close enough, but {enc.hex()} does not look like {ct.hex()} at all! Bye...')
    exit()

The server encrypts its target message with CBC mode and this print message reveals the corresponding ciphertext. Therefore we obtain the encrypted message and use the first block as $C_0$ to compute the IV.

The idea is:

• Pick a 16-byte encryption key full of null bytes.
• Take the server's message and encrypt it using this key. Since we do not have the IV, we will encrypt it using ECB mode.
• Send the ciphertext to the server.
• The server will check whether our ciphertext matches its own. However, it will encrypt its message using the secret IV in CBC mode. As we do not have access to the IV, the verification check is guaranteed to fail but due to the printed message, we obtain the CBC ciphertext.
• We can use the first block of the CBC ciphertext as $C_0$ to compute the $IV$.

Note that this method works because the $IV$​ is static and reused in every connection.

Let us write a function that implements these steps and recovers the server IV.

def recover_iv():
  	io = remote(HOST, PORT)
    io.recvuntil(b'message: ')
    server_message = bytes.fromhex(io.recvline().decode())
    key = b'\x00'*16
    ct = TEA(key).encrypt(server_message)  														# encrypt with ECB
    io.sendlineafter(b'(in hex) : ', ct.hex().encode())
    io.sendlineafter(b'(in hex) : ', key.hex().encode())
    io.recvuntil(b'but ')
    enc_server_msg = bytes.fromhex(io.recv(48).decode())  	# get CBC ciphertext
    dec_msg = decrypt_block(key, enc_server_msg[:8])				# compute D_K(C_0)
    iv = xor(server_message[:8], dec_msg[:8])								# iv = M_0 XOR D_K(C_0)
    return iv

The function decrypt_block is exactly the same as in the Iced Tea challenge:

from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b

def decrypt_block(key, ct):
    m0 = b2l(ct[:4])
    m1 = b2l(ct[4:])
    msk = (1 << 32) - 1
		DELTA = 0x9e3779b9
    s = 0xc6ef3720
    for i in range(32):
        m1 -= ((m0 << 4) + key[2]) ^ (m0 + s) ^ ((m0 >> 5) + key[3])
        m1 &= msk
        m0 -= ((m1 << 4) + key[0]) ^ (m1 + s) ^ ((m1 >> 5) + key[1])
        m0 &= msk
        s -= DELTA
    m = ((m0 << 32) + m1) & ((1 << 64) - 1)
    return l2b(m)

Finding keys that cause collisions

Having recovered the IV successfully, we move on to the next stage of the challenge. We have to submit four distinct keys $k_0, k_1, k_2, k_3$ such that: $$ ct = E_{k_0}(M) = E_{k_1}(M) = E_{k_2}(M) = E_{k_3}(M) $$ For some more experienced cryptographers this might seem a trivial task to do but in reality it is not that obvious at first sight. Let us take a look at the TEA block encrypt function:

def encrypt_block(self, msg):
    m0 = b2l(msg[:4])
    m1 = b2l(msg[4:])
    K = self.KEY
    msk = (1 << (self.BLOCK_SIZE//2)) - 1

    s = 0
    for i in range(32):
        s += self.DELTA
        m0 += ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
        m0 &= msk
        m1 += ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
        m1 &= msk
    m = ((m0 << (self.BLOCK_SIZE//2)) + m1) & ((1 << self.BLOCK_SIZE) - 1) # m = m0 || m1
    return l2b(m)

Recall that $K[0], K[1], K[2], K[3]$ are dwords; or in other words 32 bits each, so as $m_0, m_1$. Let us step out from the challenge for a while and see an example. Let the following: $$ K_0 &= 11011110101011011011111011101111\ K_1 &= 11001010111111101011101010111110\ m &= 10000000000000000000000000000000 &= 2^{31} $$ Compute $K_0 \oplus K_1$. $$ K_0 \oplus K_1 = 00010100010100110000010001010001 $$ Now, compute $K_0 \oplus m$ and $K_1 \oplus m$. $$ K_0 \oplus m = 01011110101011011011111011101111\ K_1 \oplus m = 01001010111111101011101010111110 $$ We see that the MSB of both $K_0$ and $K_1$ are flipped from a 1 to 0. This is the normal behaviour of the XOR operation.

Let $K'_0 = K_0 \oplus m$ an $K'_1 = K_1 \oplus m$. Then: $$ K'_0 \oplus K'_1 = 00010100010100110000010001010001 = K_0 \oplus K_1 $$ We see that even though we changed the MSB of $K_0, K_1$. Their XOR remained unchanged and that is because this MSB cancelled itself. So eventually $1 \oplus 1 = 0 \oplus 0 = 0$.

While this helps, getting back to our challenge, we see that there is addition as well. That is:

((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])

It turns out that the MSB flipping propagates through both addition and XOR. Note that we keep only the last 32 bits of the following additions. $$ (K_0 + m) \pmod {2^{32}} = 01011110101011011011111011101111\ (K_1 + m) \pmod {2^{32}} = 01001010111111101011101010111110 $$ Therefore, we can get the same result for the two distinct pairs $[K_0, K_1]$ and $[K'_0, K'_1]$. The same holds for $K_2$ and $K_3$, we can form $K'_2, K'_3$ in a similar way such that: $$ K'_2 \oplus K'_3 = K_2 \oplus K_3 $$ Hence, we can form four distinct keys which evaluate to the same TEA ciphertext. $$ {center} \begin{aligned} & \begin{array}{ccccc} Key[0] = & K_0 & K_1 & K_2 & K_3\ Key[1] = & (K_0 \oplus 2^{31}) & (K_1 \oplus 2^{31}) & K_2 & K_3\ Key[2] = & K_0 & K_1 & (K_2 \oplus 2^{31}) & (K_3 \oplus 2^{31})\ Key[3] = & (K_0 \oplus 2^{31}) & (K_1 \oplus 2^{31}) & (K_2 \oplus 2^{31}) & (K_3 \oplus 2^{31})\ \end{array} \end{aligned} $$ Instead of having to figure out this attack, one could read from the Wikipedia page the following line:

TEA has a few weaknesses. Most notably, it suffers from equivalent keys—each key is equivalent to three others, which means that the effective key size is only 126 bits.

The article has a reference to this paper which explains this attack in Chapter 2.5. Officially, this attack is known as the TEA equivalent keys attack. Alternatively, one could find this Master thesis that also describes this attack in Chapter 3.5.

Let us write a function that takes a single key as an argument and produces four equivalent keys that do not affect the TEA encryption process.

from pwn import xor

def get_equivalent_keys(key):
    m = l2b(1 << 31)
    k0, k1, k2, k3 = [key[i:i+4] for i in range(0, len(key), 4)]

    key0 = k0 + k1 + k2 + k3
    key1 = k0 + k1 + xor(k2, m) + xor(k3, m)
    key2 = xor(k0, m) + xor(k1, m) + k2 + k3
    key3 = xor(k0, m) + xor(k1, m) + xor(k2, m) + xor(k3, m)

    return [key0, key1, key2, key3]

Exploitation

Sending the equivalent keys

All that is left to do is connect to the server and solve the task 10 times in a row to get the flag. Let us write a function that solves a single task first.

import os
from tea import Cipher as TEA

def solve_task(server_message, iv):
  	key = os.urandom(16)
    keys = get_equivalent_keys(key)
    ct = TEA(key, iv).encrypt(server_message)
    assert all([ct == TEA(k, iv).encrypt(server_message) for k in keys]), 'Something went wrong'
    io.sendlineafter(b'(in hex) : ', ct.hex().encode())
    for j in range(4):
        io.sendlineafter(b'(in hex) : ', keys[j].hex().encode())
    return True

Now let us write a function that receives the server message and solves the task 10 times.

def get_flag(iv):
  	io = remote(HOST, PORT)
    io.recvuntil(b'message: ')
		server_msg = bytes.fromhex(io.recvline().decode())
		for i in range(10):
    		assert solve_task(server_msg, iv)
    flag = io.recvline().decode()
    return flag

Getting the flag

A final summary of all that was said above:

1. Notice that to get the flag, we have to solve a task 10 times in a row.
2. The task is to submit four distinct keys $k_0, k_1, k_2, k_3$ and a ciphertext $ct$ such that $ct = E_{k_0}(M) = E_{k_1}(M) = E_{k_2}(M) = E_{k_3}(M)$.
3. However the IV is unknown to us so we probably have to recover it.
4. Recover the IV by sending a ciphertext that is guaranteed to fail and extract the server's CBC ciphertext from the outputted error message. Then simply solve for the IV using XOR.
5. Find out about the equivalent keys attack on the TEA cipher, either manually or by researching and apply it to solve the task 10 times.

This recap can be represented by code with the pwn() function:

HOST = 'localhost'
PORT = 1337

def pwn():
		iv = recover_iv()
    flag = get_flag(iv)
    print(flag)
 
if __name__ == '__main__':
		pwn()