4ES

This challenge was made by me for CrewCTF 2024 as a member of thehackerscrew. We are provided with the Python source code to encrypt the 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()}')  

We also have the output output.txt:

pt = 4145535f4145535f4145535f41455321
ct = edb43249be0d7a4620b9b876315eb430
enc_flag = e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b  

Source code analysis

The script encrypts the flag 4 times with AES. The 4 AES keys are SHA256 hashes of 3-letter choices from a given alphabet: crew_AES*4=$!?. We are also given a plaintext AES_AES_AES_AES! and its ciphertext.

In brief, we have 3-letter keys from a 14-letter alphabet that are hashed and 4 encryptions. A naïve brute force attack would take up to $(14^3)^4 = 14^{12}$ possibilities, that is $2^{45} \lt 14^{12} \lt 2^{46}$, which is not affordable.

Meet-in-the-middle attack

Instead, we can use a meet-in-the-middle (MITM) attack. That is, instead of computing 4 forward encryptions, we can compute 2 forward encryptions, save them in a look-up table and then perform 2 backward decryptions until we find a match. The complexity of this approach will be $2 \cdot (14^3)^2 = 2 \cdot 14^6$ possibilities, which is affordable because $2^{23} \lt 2 \cdot 14^6 \lt 2^{24}$.

So, we will have a map:

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

And we test $\mathrm{DEC}_{k_4}(\mathrm{DEC}_{k_3}(\mathrm{ct}))$ until we find a match with $\mathrm{ENC}_{k_1}(\mathrm{ENC}_{k_2}(\mathrm{pt}))$. At that point, we will have $(k_1, k_2, k_3, k_4)$ so that

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

and

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

Flag

The solvers are single-threaded and not optimized. One of them is programmed in Go, which takes around 10 seconds to run; whereas the Python solver takes around 2 minutes:

$ 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  

The full scripts can be found in here: solve.go and solve.py.