CrewCTF 2024 4ES Write-Up: Meet-in-the-Middle Attack

Difficulty Level: Easy

Introduction Link to heading

The meet-in-the-middle attack is a powerful cryptanalytic technique used to break encryption schemes by exploiting the structure of multiple encryption layers. This attack is particularly effective when both the plaintext and its corresponding ciphertext are known. In this write-up, we will demonstrate how the meet-in-the-middle attack can be used to break a 4-layer AES encryption scheme encountered in CrewCTF 2024. The victim encryptor script encrypts a plaintext using four layers of AES encryption, each with a different key derived from 3-byte values. The final goal is to decrypt the encrypted flag by breaking this encryption scheme. It is important to note that without knowledge of both the plaintext and the corresponding ciphertext, the meet-in-the-middle attack would not be feasible.

Understanding the Victim Encryptor Link to heading

The provided victim encryptor script, 4ES.py, performs the encryption of a given plaintext using four layers of AES encryption with different keys.

Code Breakdown Link to heading

#!/usr/bin/env python3

import Crypto
from hashlib import sha256
from random import choices
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()

chars = b'crew_AES*4=$!?'
L = 3

w, x, y, z = (
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
)

k1 = sha256(w).digest()
k2 = sha256(x).digest()
k3 = sha256(y).digest()
k4 = sha256(z).digest()

print(w.decode(), x.decode(), y.decode(), z.decode())

pt = b'AES_AES_AES_AES!'
ct = AES.new(k4, AES.MODE_ECB).encrypt(
         AES.new(k3, AES.MODE_ECB).encrypt(
             AES.new(k2, AES.MODE_ECB).encrypt(
                 AES.new(k1, AES.MODE_ECB).encrypt(
                     pt
                 )
             )
         )
     )

key = sha256(w + x + y + z).digest()
enc_flag = AES.new(key, AES.MODE_ECB).encrypt(pad(FLAG, AES.block_size))

with open('output.txt', 'w') as f:
    f.write(f'pt = {pt.hex()}\nct = {ct.hex()}\nenc_flag = {enc_flag.hex()}')

Encryption Process Link to heading

Key Generation:
- Four random 3-byte values (w, x, y, z) are chosen from a predefined character set.
- Each of these values is hashed using SHA-256 to derive the AES keys (k1, k2, k3, k4).
Layered Encryption:
- The plaintext pt is encrypted using k1.
- The resulting ciphertext is then encrypted using k2.
- This process is repeated for k3 and k4 to produce the final ciphertext ct.
Flag Encryption:
- A single key derived from the concatenation of w, x, y, z is used to encrypt the flag.

Character Set and Key Length Link to heading

Character Set: crew_AES*4=$!?
Key Length: 3 characters

Brute-Force Attack Analysis Link to heading

Total possible keys (4 keys): 56,693,912,375,296

Meet-in-the-Middle Attack Link to heading

The meet-in-the-middle attack is an efficient cryptanalytic technique used against encryption schemes that use multiple layers of encryption. It works by dividing the encryption process into two parts and finding a common intermediate value that matches between the two halves.

Implementation Link to heading

The attack involves the following steps:

Generate all possible combinations of the 3-byte keys from the given character set.
Encrypt the plaintext using all possible combinations of the first two keys.
Decrypt the ciphertext using all possible combinations of the last two keys.
Find matching intermediate values between the encrypted and decrypted results to identify the correct keys.
Use the identified keys to decrypt the encrypted flag.

Phase 1: Key Space Generation Link to heading

The character set and length of the keys are defined. All possible combinations of the 3-byte keys are generated using the itertools.product function.

Phase 2: Encryption and Decryption Link to heading

Encryption Phase Link to heading

For each possible combination of the first two keys:

Encrypt the plaintext using the first key.
Encrypt the result using the second key.
Store the intermediate encrypted value in a dictionary.

Decryption Phase Link to heading

For each possible combination of the last two keys:

Decrypt the ciphertext using the last key.
Decrypt the result using the third key.
Store the intermediate decrypted value in a dictionary.

Phase 3: Finding Matching Values Link to heading

The intermediate values from the encryption and decryption phases are compared. When a match is found, it indicates that the correct keys have been identified.

Phase 4: Decrypting the Flag Link to heading

The identified keys are used to derive the final encryption key for the flag. This key is then used to decrypt the encrypted flag.

Final Script with Logging Link to heading

import itertools
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

# Given plaintext and ciphertext in hexadecimal format
pt = bytes.fromhex("4145535f4145535f4145535f41455321")
ct = bytes.fromhex("edb43249be0d7a4620b9b876315eb430")
enc_flag = bytes.fromhex("e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b")

# Character set and length of keys
chars = b'crew_AES*4=$!?'
L = 3

def generate_possible_keys(chars, length):
    return [bytes(comb) for comb in itertools.product(chars, repeat=length)]

def encrypt_with_key(plain_text, key):
    return AES.new(key, AES.MODE_ECB).encrypt(plain_text)

def decrypt_with_key(cipher_text, key):
    return AES.new(key, AES.MODE_ECB).decrypt(cipher_text)

def meet_in_the_middle_attack(pt, ct, possible_keys):
    encrypt_dict = {}
    decrypt_dict = {}

    total_keys = len(possible_keys)
    print("Starting encryption phase")
    count = 0
    for w, x in itertools.product(possible_keys, repeat=2):
        count += 1
        if count % 1000 == 0:
            print(f"Encryption phase progress: {count}/{total_keys**2} combinations")
        k1 = sha256(w).digest()
        k2 = sha256(x).digest()
        intermediate_enc = encrypt_with_key(encrypt_with_key(pt, k1), k2)
        encrypt_dict[intermediate_enc] = (w, x)

    print("Starting decryption phase")
    count = 0
    for y, z in itertools.product(possible_keys, repeat=2):
        count += 1
        if count % 1000 == 0:
            print(f"Decryption phase progress: {count}/{total_keys**2} combinations")
        k3 = sha256(y).digest()
        k4 = sha256(z).digest()
        intermediate_dec = decrypt_with_key(decrypt_with_key(ct, k4), k3)
        decrypt_dict[intermediate_dec] = (y, z)

    print("Finding matching intermediate values")
    for intermediate_value in encrypt_dict:
        if intermediate_value in decrypt_dict:
            w, x = encrypt_dict[intermediate_value]
            y, z = decrypt_dict[intermediate_value]
            return w, x, y, z

    return None, None, None, None

def decrypt_flag(enc_flag, w, x, y, z):
    key = sha256(w + x + y + z).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    return unpad(cipher.decrypt(enc_flag), AES.block_size)

# Example usage
if __name__ == "__main__":
    possible_keys = generate_possible_keys(chars, L)
    w, x, y, z = meet_in_the_middle_attack(pt, ct, possible_keys)

    if w and x and y and z:
        print(f"Using found keys: w: {w}, x: {x}, y: {y}, z: {z}")
        flag = decrypt_flag(enc_flag, w, x, y, z)
        print(f"Decrypted FLAG: {flag.decode()}")
    else:
        print("No matching keys found.")

Execution Results Link to heading

Upon running the script, the following output was obtained, indicating a total break and the successful decryption of the flag:

...
Finding matching intermediate values
Using found keys: w: b'_c*', x: b'A?S', y: b'c=e', z: b'A_*'
Decrypted FLAG: crew{m1tm_at74cK_1s_g0lD_4nd_py7h0n_i5_sl0w!!}

Performance Considerations Link to heading

Meet-in-the-Middle (MITM) Attack:

Total possible keys per key: 2,744
Encryption operations (2 keys): 7,529,536
Decryption operations (2 keys): 7,529,536
Total possible keys: 15,059,072

Conclusion Link to heading

The meet-in-the-middle attack successfully decrypted the 4-layer AES encryption scheme by efficiently narrowing down the possible key combinations through intermediate value matching. This demonstrates the vulnerability of multi-layer encryption schemes to such attacks and the importance of using encryption methods that mitigate these risks.

By implementing the meet-in-the-middle attack, we highlighted the efficiency gains over brute-force methods, making it clear why such cryptographic techniques are crucial in practical scenarios. The successful decryption of the flag further solidifies the effectiveness of this attack approach.