4ES

Este es un reto que diseñé para CrewCTF 2024 como miembro de thehackerscrew. Se nos proporciona el código fuente en Python para cifrar la flag:

#!/usr/bin/env python3

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()}')  

También tenemos la salida output.txt:

pt = 4145535f4145535f4145535f41455321
ct = edb43249be0d7a4620b9b876315eb430
enc_flag = e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b  

Análisis del código fuente

El script cifra la flag 4 veces con AES. Las 4 claves AES son los hashes SHA256 de palabras de 3 letras aleatorias de un alfabeto dado: crew_AES*4=$!?. También se nos proporciona un texto claro AES_AES_AES_AES! y su texto cifrado.

En resumen, tenemos claves que son el hash de 3 letras de un alfabeto de 14 letras, y 4 cifrados. Un ataque de fuerza bruta llevaría $(14^3)^4 = 14^{12}$ posibilidades, que es $2^{45} \lt 14^{12} \lt 2^{46}$, por lo que no es asequible.

Ataque meet-in-the-middle

En cambio, podemos usar un ataque de meet-in-the-middle (MITM). Es decir, en lugar de calcular 4 cifrados hacia adelante, podemos calcular 2 cifrados hacia adelante, guardarlas en una tabla de búsqueda y luego realizar 2 descifrados hacia atrás hasta que encontremos una coincidencia. La complejidad de este enfoque será de $2 \cdot (14^3)^2 = 2 \cdot 14^6$ posibilidades, que sí es asequible porque $2^{23} \lt 2 \cdot 14^6 \lt 2^{24}$.

Entonces, tendremos un mapa:

$$ \mathrm{ENC}_{k_1}(\mathrm{ENC}_{k_2}(\mathrm{pt})) \longrightarrow (k_1, k_2) $$

Y probamos $\mathrm{DEC}_{k_4}(\mathrm{DEC}_{k_3}(\mathrm{ct}))$ hasta que encontremos una coincidencia con $\mathrm{ENC}_{k_1}(\mathrm{ENC}_{k_2}(\mathrm{pt}))$. En ese momento, tendremos $(k_1, k_2, k_3, k_4)$ tal que

$$ \mathrm{ct} = \mathrm{ENC}_{k_1}(\mathrm{ENC}_{k_2}(\mathrm{ENC}_{k_3}(\mathrm{ENC}_{k_4}(\mathrm{pt})))) $$

y que

$$ \mathrm{pt} = \mathrm{DEC}_{k_4}(\mathrm{DEC}_{k_3}(\mathrm{DEC}_{k_2}(\mathrm{DEC}_{k_1}(\mathrm{ct})))) $$

Flag

Los scripts son de un solo hilo y no están optimizados. Uno de ellos está programado en Go, que tarda alrededor de 10 segundos en ejecutarse; mientras que el otro está escrito en Python y toma cerca de 2 minutos:

$ time go run solve.go
crew{m1tm_at74cK_1s_g0lD_4nd_py7h0n_i5_sl0w!!}
go run solve.go  18,50s user 0,63s system 201% cpu 9,475 total

$ time python3 solve.py
crew{m1tm_at74cK_1s_g0lD_4nd_py7h0n_i5_sl0w!!}
python3 solve.py  94,24s user 0,33s system 99% cpu 1:35,16 total  

Los scripts completos se pueden encontrar aquí: solve.go y solve.py.