[Easy] Iced Tea

Iced Tea

5$^{th}$ February 2024 / Document No. D24.102.28

Prepared By: aris

Challenge Author(s): aris

Difficulty: Easy

Classification: Official

Synopsis

• In this challenge, the player has to determine that the provided block cipher is known as the TEA cipher by researching online for cryptographic constants. Then they can implement their own decrypt function or use Wikipedia's to decrypt the flag using TEA in ECB mode.

Description

• Locked within a cabin crafted entirely from ice, you're enveloped in a chilling silence. Your eyes land upon an old notebook, its pages adorned with thousands of cryptic mathematical symbols. Tasked with deciphering these enigmatic glyphs to secure your escape, you set to work, your fingers tracing each intricate curve and line with determination. As you delve deeper into the mysterious symbols, you notice that patterns appear in several pages and a glimmer of hope begins to emerge. Time is flying and the temperature is dropping, will you make it before you become one with the cabin?

Skills Required

• Basic Python source code analysis.
• Basic research skills.
• Know how to identify cryptographic algorithms.
• Familiar with bitwise operations.

Skills Learned

• Learn to research for cryptographic constants for cryptosystem identification.
• Understand how to perform TEA-ECB decryption.

Enumeration

In this challenge, we are provided with two files:

• source.py : This is the main script that encrypts the flag.
• output.txt : This is the output file that contains the encryption key and the encrypted flag, both in hex format.

Analyzing the source code

Let us first inspect how the flag is encrypted. The main function of the source script is straight forward to follow.

if __name__ == '__main__':
    KEY = os.urandom(16)
    cipher = Cipher(KEY)
    ct = cipher.encrypt(FLAG)
    with open('output.txt', 'w') as f:
        f.write(f'Key : {KEY.hex()}\nCiphertext : {ct.hex()}')

First, a random 16-byte key is generated which is used as the encryption key for the provided cipher. Then the flag is encrypted and finally both the encryption key and the encrypted flag are written to the output file. Let us take a closer look at the Cipher class.

from enum import Enum

class Mode(Enum):
    ECB = 0x01
    CBC = 0x02

class Cipher:
    def __init__(self, key, iv=None):
        self.BLOCK_SIZE = 64
        self.KEY = [b2l(key[i:i+self.BLOCK_SIZE//16]) for i in range(0, len(key), self.BLOCK_SIZE//16)]
        self.DELTA = 0x9e3779b9
        self.IV = iv
        if self.IV:
            self.mode = Mode.CBC
        else:
            self.mode = Mode.ECB
    
    def _xor(self, a, b):
        # ...

    def encrypt(self, msg):
        # ...

    def encrypt_block(self, msg):
        # ...

At first glance, we can derive the following information:

1. From the naming used in this class, we can conclude that the cipher is a block cipher where each block is 64 bits.
2. The cipher supports two modes, ECB and CBC. In case an IV is provided, the mode is automatically set to CBC.
3. The key is splitted in $\dfrac{64}{16}=4$ dwords (i.e. four quadratuples of bytes).

Since in this challenge, there is no IV provided. We know that the flag is encrypted with the cipher in ECB mode so let us take a look how ECB is implemented and how each block is encrypted.

def encrypt(self, msg):
    msg = pad(msg, self.BLOCK_SIZE//8)
    blocks = [msg[i:i+self.BLOCK_SIZE//8] for i in range(0, len(msg), self.BLOCK_SIZE//8)]

    ct = b''
    if self.mode == Mode.ECB:
        for pt in blocks:
            ct += self.encrypt_block(pt)
    elif self.mode == Mode.CBC:
    		# ...
        
		return ct

The ECB mode implementation is trivial. Each plaintext block is encrypted and concatenated to the ciphertext as it is.

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)

As the encryption key is provided to us there is no need to break the cipher. All we have to do is figure out how to perform the reverse operations and decrypt each ciphertext block. At first glance, this might seem a complicated task to do as there are several bitwise operations involved. At this point, the player can move on by doing any of the following.

1. Ask ChatGPT or any other similar tool to write them a decrypt_block function, which is something we do not recommend.
2. Write their own decrypt_block function by reversing the operations. This might take some time but will eventually work and the player will become familiar with bitwise operations.
3. Realize that this is an easy challenge so there should already exist a decrypt_block function somewhere.

We will showcase the third option. Before moving on, let us write a function that loads the encryption key and the encrypted flag from output.txt.

def load_data():
    with open('output.txt') as f:
        key = bytes.fromhex(f.readline().split(' : ')[1])
        enc_flag = bytes.fromhex(f.readline().split(' : ')[1])
		return key, enc_flag

Solution

Finding the vulnerability

As aforementioned, the key is already provided so we do not really have to exploit any vulnerability of the cipher. However, we do need a starting point when it comes to researching for ciphers online. Something that stands out in the cipher implementation and could be considered unique is the utilization of the DELTA constant 0x9e3779b9.

Indeed, if, for example, we research this constant online along with the key words "block cipher", we will stumble upon a known block cipher known as the TEA (Tiny Encryption Algorithm) block cipher. By inspecting the corresponding Wikipedia, we can see that the encryption routine matches the one provided in this challenge. This is a strong sign that we have successfully identified the provided cipher.

Exploitation

Wikipedia also provides us with the decrypt function which can be used as it is to decrypt the flag. One can use the C language to decrypt it or reimplement it in Python which is what we are going to do.

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

    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)

Now, we can implement the equivalent TEA-ECB decryption routine and obtain the flag.

def tea_ecb_decrypt(key, enc_flag):
    key = [b2l(key[i:i+4]) for i in range(0, len(key), 4)]
    blocks = [enc_flag[i:i+8] for i in range(0, len(enc_flag), 8)]
    flag = b''

    for ct in blocks:
        flag += decrypt_block(key, ct)
    
    return flag

Getting the flag

A final summary of all that was said above:

1. Notice that the provided cipher is a block cipher with a block size of 64 bits.
2. The block cipher encrypts the flag in ECB mode as no IV is provided.
3. Notice the cryptographic constant 0x9e3779b9 and research online with the proper keywords to find out the TEA cipher.
4. Take Wikipedia's implementation of the decrypt function or implement it from scratch and decrypt the flag by running TEA in ECB mode.

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

def pwn():
    key, enc_flag = load_data()
    flag = tea_ecb_decrypt(key, enc_flag)
    print(flag)

if __name__ == '__main__':
		pwn()