crewCTF 4ES writeup

Given:

4ES.py

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

each key is of size 3 e.g w = ‘cre’ x = ‘AES’ and so on

output.txt

pt = 4145535f4145535f4145535f41455321
ct = edb43249be0d7a4620b9b876315eb430
enc_flag = e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b

This is a typical example to what a Meet-in-the-Middle attack looks like we are given both the ciphertext and the plaintext and how it is encrypted

the goal is to find the correct key (w,x,y,z)

part of each key is selected randomly, and using the single key we encrypt recursively

MITM

we have both pt and the ct, to perform meet-in-the-middle, from the ciphertext we decrypt it by first creating every possible 3 size combination of the chars = b'crew_AES*4=$!?'

import itertools

characters = "crew_AES*4=$!?'"
combinations = itertools.product(characters, repeat=3)

then we the encrypt of the plaintext AES_AES_AES_AES!

intermediate = {}

for combo in combinations:
    w = bytes(''.join(combo).encode())
    k1 = sha256(w).digest()
    enc = AES.new(k1, AES.MODE_ECB).encrypt(pt)
    intermediate[enc] = w

so we create a dictionary with key:value pair, which is essentially a hashmap that stores the encrypted value and the key it was encrypted with

then we again encrypt each value in the dictionary

combinations = itertools.product(characters, repeat=3)

intermediate2 = {}
for combo in combinations:
    for enc, w in intermediate.items():
        x = bytes(''.join(combo).encode())
        k2 = sha256(x).digest()
        enc2 = AES.new(k2, AES.MODE_ECB).encrypt(enc)
        intermediate2[enc2] = w + x

this is the middle part

now we perform the decryption using the ciphertext

dec_intermediate = {}

combinations = itertools.product(characters, repeat=3)
for combo in combinations:
    z = bytes(''.join(combo).encode())
    k4 = sha256(z).digest()
    dec = AES.new(k4, AES.MODE_ECB).decrypt(ct)
    dec_intermediate[dec] = z

combinations = itertools.product(characters, repeat=3) 
dec_intermediate2 = {}
for combo in combinations:
    for dec, z in dec_intermediate.items():
        y = bytes(''.join(combo).encode())
        k3 = sha256(y).digest()
        dec2 = AES.new(k3, AES.MODE_ECB).decrypt(dec)
        dec_intermediate2[dec2] = z + y
        if dec2 in intermediate2:
            print(intermediate2[dec2] + y + z)

in the second loop we decrypt the decrypted and compare the value in the dictionary where the 2nd part of encryption is done

in a nut shell pt->encryption->some_text->encryption->’AAAA’ ct->decryption->some_text->decryption->’AAAA’

once this is true, we will know the exact value of key which was used to encrypt the flag

after finding the correct key

from hashlib import sha256
enc_flag = "e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b"

ct = bytes.fromhex('edb43249be0d7a4620b9b876315eb430')
pt = bytes.fromhex('4145535f4145535f4145535f41455321')

chars = b'crew_AES*4=$!?'
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

key = '_c*A?SA_*c=e'
w = '_c*'.encode()
x = 'A?S'.encode()
z = 'A_*'.encode()
y= 'c=e'.encode()

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

key = sha256(w + x + y + z).digest()
dec_flag = AES.new(key, AES.MODE_ECB).decrypt(bytes.fromhex(enc_flag))
print(dec_flag)

flag: crew{m1tm_at74cK_1s_g0lD_4nd_py7h0n_i5_sl0w!!}