# Day 4: Meet me halfway

challenge description
``Evil elves have deployed their own cryptographic service. The keys are unknown to everyone but them. Fortunately, their encryption algorithm is vulnerable. Could you help Santa break the encryption and read their secret message?``

## Interesting title​

Well... Even before looking at the encryption code, I believe this is probably related to the infamous meet-in-the-middle attack!

Let's verify!

challenge.py
``from random import randintfrom Crypto.Cipher import AESfrom Crypto.Util.Padding import padimport jsonflag = b'HTB{dummyflag}'def gen_key(option=0):    alphabet = b'0123456789abcdef'    const = b'[email protected]#'    key = b''    for i in range(16-len(const)):        key += bytes([alphabet[randint(0,15)]])    if option:        return key + const    else:        return const + keydef encrypt(data, key1, key2):    cipher = AES.new(key1, mode=AES.MODE_ECB)    ct = cipher.encrypt(pad(data, 16))    cipher = AES.new(key2, mode=AES.MODE_ECB)    ct = cipher.encrypt(ct)    return ct.hex()def challenge():    k1 = gen_key()    print(k1)    k2 = gen_key(1)    print(k2)        ct = encrypt(flag, k1, k2)            print('Super strong encryption service approved by the elves X-MAS spirit.\n'+\                    'Message for all the elves:\n' +ct + '\nEncrypt your text:\n> ')    try:                    dt = json.loads(input().strip())        pt = bytes.fromhex(dt['pt'])        res = encrypt(pt, k1, k2)        print(res + '\n')        exit(1)    except Exception as e:        print(e)        print('Invalid payload.\n')        exit(1)    if __name__ == "__main__":    challenge()``

Yup. By doing a brute force search, we would need pow(pow(16, 4), 2) = pow(16, 8) = 4294967296 attempts.

However, using the MitM attack, we can use more space complexity to trade off for time. By storing the result of all possible 65536 (pow(16, 4)) attempts at encrypting, we compare each result with every decryption trial of the ciphertext.

This kind of chosen plaintext attack completely breaks this cipher just like how DES is completely broken because of this, reducing the complexity to just brute forcing at most pow(16, 4) + pow(16, 4) = pow(16, 5) = 1048576 attempts.

(Thanks for the Stanford Cryptography class for introducing me to this concept!)

solve.py
``from Crypto.Cipher import AESfrom Crypto.Util.Padding import pad, unpadfrom Crypto.Util.number import long_to_bytesfrom pwn import *import jsonimport itertoolsfflag = b'HTB{dummyflag}'hex_flag = fflag.hex()dt = {    'pt': hex_flag}fake_flag = json.dumps(dt)p = remote('167.99.204.238', 32464)p.recvuntil(b':\n')ct = long_to_bytes(int(p.recvlineS().strip(), 16))p.sendlineafter(b'>', bytes(fake_flag, 'utf-8'))chosen_ct = long_to_bytes(int(p.recvlineS().strip(), 16))p.close()print('ct:', ct)print('chosen_ct:', chosen_ct)def encrypt(data, key):    cipher = AES.new(key, mode=AES.MODE_ECB)    ct = cipher.encrypt(pad(data, 16))    return ct.hex()def decrypt(data, key, clear=False):    cipher = AES.new(key, mode=AES.MODE_ECB)    pt = cipher.decrypt(data)    if clear:        return unpad(pt, 16)    return pt.hex()def get_message(ct, key1, key2):    imm = decrypt(ct, key2)    flag = decrypt(bytes.fromhex(imm), key1, True)    print(flag.decode('utf-8'))alphabet = b'0123456789abcdef'const = b'[email protected]#'forward = []forward_keys = []backward = []for i in range(16):    for j in range(16):        for k in range(16):            for l in range(16):                key1 = const + alphabet[i:i+1] + alphabet[j:j+1] + alphabet[k:k+1] + alphabet[l:l+1]                key2 = alphabet[i:i+1] + alphabet[j:j+1] + alphabet[k:k+1] + alphabet[l:l+1] + const                encrypted = encrypt(fflag, key1)                forward_keys.append(key1)                forward.append(encrypted)                backward.append(key2)for key in backward:    m = decrypt(chosen_ct, key)    for i, c in enumerate(forward):        if c == m:            print('Found!!!')            print('key1: ', forward_keys[i])            print('key2: ', key)            get_message(ct, forward_keys[i], key)            break``

## Flag​

`HTB{m337_m3_1n_7h3_m1ddl3_0f_3ncryp710n}`