Skip to main content

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 randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import json

flag = 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 + key

def 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 AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import long_to_bytes
from pwn import *
import json
import itertools

fflag = 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}