- 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
).
- Four random 3-byte values (
-
Layered Encryption:
- The plaintext
pt
is encrypted usingk1
. - The resulting ciphertext is then encrypted using
k2
. - This process is repeated for
k3
andk4
to produce the final ciphertextct
.
- The plaintext
-
Flag Encryption:
- A single key derived from the concatenation of
w
,x
,y
,z
is used to encrypt the flag.
- A single key derived from the concatenation of
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.
Further Readings Link to heading
For those interested in exploring more about the topics discussed in this write-up, here are some valuable resources:
-
Space-Time Tradeoff: Learn more about the concept of trading off space for time in algorithms and cryptographic attacks.
-
Meet-in-the-Middle Attack: Understand the detailed mechanics and history of the meet-in-the-middle attack, along with other applications and examples.
-
Advanced Encryption Standard (AES): Dive deeper into the Advanced Encryption Standard, its development, and its use in securing data worldwide.
These resources will provide a deeper understanding of the cryptographic concepts and techniques discussed in this write-up.