CTFs | HeroCTF2024 | Crypto | Paranoia

Paranoia

In this challenge, we are given the following code.

from cryptography.hazmat.primitives.ciphers.algorithms import AES, SM4
from cryptography.hazmat.primitives.ciphers import Cipher, modes
import os

class Paranoia:
def __init__(self, keys):
	self.keys = keys
	
def __pad(self, data: bytes, bs: int) -> bytes:
	return data + (chr(bs - len(data) % bs) * (bs - len(data) % bs)).encode()
	
def __encrypt(self, algorithm, data: bytes, key: bytes):
	cipher = Cipher(algorithm(key), modes.ECB())
	encryptor = cipher.encryptor()
	return encryptor.update(data) + encryptor.finalize()

def encrypt(self, data: bytes):
	"""
	🇨🇳 encryption to protect against the 🇺🇸 backdoor and
	🇺🇸 encryption to protect against the 🇨🇳 backdoor
	
	I'm a genius !
	"""
	
	data = self.__pad(data, 16)
	data = self.__encrypt(AES, data, self.keys[0])
	data = self.__encrypt(SM4, data, self.keys[1])
	return data

with open("flag.txt", "rb") as f:
	flag = f.read()

keys = [os.urandom(16) for _ in range(2)]
paranoia = Paranoia(keys)

banner = b"I don't trust governments, thankfully I've found smart a way to keep my data secure."

print("pt_banner =", banner)
print("ct_banner =", paranoia.encrypt(banner))
print("enc_flag =", paranoia.encrypt(flag))

# To comply with cryptography export regulations,
# 6 bytes = 2**48 bits, should be bruteforce-proof anyway
for n, k in enumerate(keys):
	print(f"k{n} = {k[3:]}")

We are also given the following output:

pt_banner = b"I don't trust governments, thankfully I've found smart a way to keep my data secure."
ct_banner = b"\xd5\xae\x14\x9de\x86\x15\x88\xe0\xdc\xc7\x88{\xcfy\x81\x91\xbaH\xb6\x06\x02\xbey_0\xa5\x8a\xf6\x8b?\x9c\xc9\x92\xac\xdeb=@\x9bI\xeeY\xa0\x8d/o\xfa%)\xfb\xa2j\xd9N\xf7\xfd\xf6\xc2\x0b\xc3\xd2\xfc\te\x99\x9aIG\x01_\xb3\xf4\x0fG\xfb\x9f\xab\\\xe0\xcc\x92\xf5\xaf\xa2\xe6\xb0h\x7f}\x92O\xa6\x04\x92\x88"
enc_flag = b"\xaf\xe0\xb8h=_\xb0\xfbJ0\xe6l\x8c\xf2\xad\x14\xee\xccw\xe9\xff\xaa\xb2\xe9c\xa4\xa0\x95\x81\xb8\x03\x93\x7fg\x00v\xde\xba\xfe\xb92\x04\xed\xc4\xc7\x08\x8c\x96C\x97\x07\x1b\xe8~':\x91\x08\xcf\x9e\x81\x0b\x9b\x15"
k0 = b'C\xb0\xc0f\xf3\xa8\n\xff\x8e\x96g\x03"'
k1 = b"Q\x95\x8b@\xfbf\xba_\x9e\x84\xba\x1a7"

In the Paranoia challenge, we are presented with a python script that encrypts using a combination of two encryption algorithms: AES and SM4.

Understanding the Challenge

The script generates two random 16-bytes keys.

keys = [os.urandom(16) for _ in range(2)]

Here is the encryption process:

• The data is padded to a 16-bytes multiple.
• The data is encrypted using AES and the first key (keys[0]).
• The data is then encrypted using SM4 and the second key (keys[1]).

def encrypt(self, data: bytes):
	"""
	🇨🇳 encryption to protect against the 🇺🇸 backdoor and
	🇺🇸 encryption to protect against the 🇨🇳 backdoor
	
	I'm a genius !
	"""
	
	data = self.__pad(data, 16)
	data = self.__encrypt(AES, data, self.keys[0])
	data = self.__encrypt(SM4, data, self.keys[1])
	return data

We have the banner plaintext and ciphertext. We have the flag encrypted and the 13 last bytes of each key.

Solution

Brute forcing 6 bytes is 256⁶ = 2.8*10**14 that is too much. However we have the plaintext and ciphertext of the banner and the encryption process is made of two algorithms. We can use that to our advantage.

We can calculate intermediary results. So we have to encrypt the banner using AES and the the first key. We store all the intermediary results. We have 256**3=16777216 results. Brute-force is feasible.

Then we decrypt the banner ciphertext using SM4 and the second key. . We have 256**3=16777216 results.

Then we compare the intermediary results to find a correlation.

So by calculating 2*256**3=33554432, we can brute force the keys.

Then we just have to decrypt the flag.

Here is the full script:

from cryptography.hazmat.primitives.ciphers.algorithms import AES, SM4
from cryptography.hazmat.primitives.ciphers import Cipher, modes
import itertools
from tqdm import tqdm

# Données et clés partielles connues
pt_banner = b"I don't trust governments, thankfully I've found smart a way to keep my data secure."
ct_banner = b"\xd5\xae\x14\x9de\x86\x15\x88\xe0\xdc\xc7\x88{\xcfy\x81\x91\xbaH\xb6\x06\x02\xbey_0\xa5\x8a\xf6\x8b?\x9c\xc9\x92\xac\xdeb=@\x9bI\xeeY\xa0\x8d/o\xfa%)\xfb\xa2j\xd9N\xf7\xfd\xf6\xc2\x0b\xc3\xd2\xfc\te\x99\x9aIG\x01_\xb3\xf4\x0fG\xfb\x9f\xab\\\xe0\xcc\x92\xf5\xaf\xa2\xe6\xb0h\x7f}\x92O\xa6\x04\x92\x88"
k0_partial = b'C\xb0\xc0f\xf3\xa8\n\xff\x8e\x96g\x03"'
k1_partial = b"Q\x95\x8b@\xfbf\xba_\x9e\x84\xba\x1a7"
enc_flag = b"\xaf\xe0\xb8h=_\xb0\xfbJ0\xe6l\x8c\xf2\xad\x14\xee\xccw\xe9\xff\xaa\xb2\xe9c\xa4\xa0\x95\x81\xb8\x03\x93\x7fg\x00v\xde\xba\xfe\xb92\x04\xed\xc4\xc7\x08\x8c\x96C\x97\x07\x1b\xe8~':\x91\x08\xcf\x9e\x81\x0b\x9b\x15"

# Fonction de déchiffrement SM4
def decrypt_sm4(data, key):
	cipher_sm4 = Cipher(SM4(key), modes.ECB())
	decryptor_sm4 = cipher_sm4.decryptor()
	return decryptor_sm4.update(data) + decryptor_sm4.finalize()

# Fonction de chiffrement AES
def encrypt_aes(data, key):
	cipher_aes = Cipher(AES(key), modes.ECB())
	encryptor_aes = cipher_aes.encryptor()
	return encryptor_aes.update(data) + encryptor_aes.finalize()

# Fonction de déchiffrement AES
def decrypt_aes(data, key):
	cipher_aes = Cipher(AES(key), modes.ECB())
	decryptor_aes = cipher_aes.decryptor()
	return decryptor_aes.update(data) + decryptor_aes.finalize()

# Étape 1 : Génération d’une table intermédiaire avec AES et texte clair connu
def generate_intermediate_map():
	intermediate_map = {}
	total_combinations_k0 = 256 ** 3
		with tqdm(total=total_combinations_k0, desc="Génération de la table intermédiaire avec AES") as pbar:
		for missing_bytes_k0 in itertools.product(range(256), repeat=3):
			k0_full = bytes(missing_bytes_k0) + k0_partial
			encrypted_pt = encrypt_aes(pt_banner[:16], k0_full) # Chiffrement du premier bloc
			intermediate_map[encrypted_pt] = k0_full # Associe le résultat intermédiaire avec la clé AES
			pbar.update(1) # Mise à jour de la barre de progression
	return intermediate_map

# Étape 2 : Recherche des clés avec la correspondance sur `ct_banner`
def find_keys(intermediate_map):
	total_combinations_k1 = 256 ** 3
	with tqdm(total=total_combinations_k1, desc="Brute-forcing SM4 keys") as pbar:
		for missing_bytes_k1 in itertools.product(range(256), repeat=3):
			k1_full = bytes(missing_bytes_k1) + k1_partial
			decrypted_ct = decrypt_sm4(ct_banner[:16], k1_full) # Déchiffre le premier bloc
			if decrypted_ct in intermediate_map: # Correspondance trouvée
				k0_full = intermediate_map[decrypted_ct]
				print("Clés trouvées !")
				print("Clé complète k0:", k0_full)
				print("Clé complète k1:", k1_full)
				return k0_full, k1_full
			pbar.update(1) # Mise à jour de la barre de progression
	return None, None

# Étape 3 : Vérification du flag en utilisant les clés trouvées
def decrypt_flag(k0_full, k1_full):
	# Déchiffrement du flag entier
	decrypted_intermediate = decrypt_sm4(enc_flag, k1_full) # Première étape avec SM4
	decrypted_flag = decrypt_aes(decrypted_intermediate, k0_full) # Deuxième étape avec AES
	return decrypted_flag


# Exécution de l'attaque en deux étapes
print("Étape 1 : Génération de la table intermédiaire avec AES...")
intermediate_map = generate_intermediate_map()

print("Étape 2 : Recherche des clés avec SM4...")
k0_full, k1_full = find_keys(intermediate_map)

if k0_full and k1_full:
	# Si les clés sont trouvées, déchiffrement du flag
	flag = decrypt_flag(k0_full, k1_full)
	print("Flag déchiffré :", flag.decode())
else:
	print("Les clés n'ont pas été trouvées.")

We get the flag!

python decrypt.py

Étape 1 : Génération de la table intermédiaire avec AES...
Génération de la table intermédiaire avec AES: 100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████| 16777216/16777216 [01:01<00:00, 272715.55it/s]
Étape 2 : Recherche des clés avec SM4...
Brute-forcing SM4 keys:  58%|██████████████████████████████████████████████████████████████████████████████▎                                                        | 9733744/16777216 [00:35<00:26, 268108.19it/s]Clés trouvées !
Clé complète k0: b'If-C\xb0\xc0f\xf3\xa8\n\xff\x8e\x96g\x03"'
Clé complète k1: b'\x94\xcb\x92Q\x95\x8b@\xfbf\xba_\x9e\x84\xba\x1a7'
Brute-forcing SM4 keys:  58%|██████████████████████████████████████████████████████████████████████████████▍                                                        | 9751442/16777216 [00:35<00:25, 270978.30it/s]
Flag déchiffré : Hero{p4r4n014_p4r4n014_3v3ryb0dy_5_c0m1n6_70_637_m3!}