Byte Bandits 2020: Crypto - Meet Me There
12/Apr 2020TL;DR Easy challenge, as the name suggests it can be solved with a Meet-in-the-middle attack.
Problem statement
Bob asked Alice to make the keys easier to guess. She did it but to keep the data safe, she used two keys and encrypted the data twice. Can you prove that she is absolutely wrong by getting the flag?
Let’s start
we are given an output.txt file, containing:
Give me a string:
aaaaaaaaaaaaaaaa
Encrypted string:
ef92fab38516aa95fdc53c2eb7e8fe1d5e12288fdc9d026e30469f38ca87c305ef92fab38516aa95fdc53c2eb7e8fe1d5e12288fdc9d026e30469f38ca87c305
Encrypted Flag:
fa364f11360cef2550bd9426948af22919f8bdf4903ee561ba3d9b9c7daba4e759268b5b5b4ea2589af3cf4abe6f9ae7e33c84e73a9c1630a25752ad2a984abfbbfaca24f7c0b4313e87e396f2bf5ae56ee99bb03c2ffdf67072e1dc98f9ef691db700d73f85f57ebd84f5c1711a28d1a50787d6e1b5e726bc50db5a3694f576
the authors give us also the source code, in a file called meet-me-there.py:
#!/usr/bin/python
import random
from Crypto.Cipher import AES
from os import urandom
from string import printable
random.seed(urandom(32))
key1 = '0'*13 + ''.join([random.choice(printable) for _ in range(3)])
key2 = ''.join([random.choice(printable) for _ in range(3)]) + '0'*13
cipher1 = AES.new(key=key1, mode=AES.MODE_ECB)
cipher2 = AES.new(key=key2, mode=AES.MODE_ECB)
print "\nGive me a string:"
pt = raw_input()
val = len(pt) % 16
if not val == 0:
pt += '0'*(16 - val)
c1 = cipher1.encrypt(pt.encode('hex'))
c2 = cipher2.encrypt(c1.encode('hex'))
print 'Encrypted string:\n' + c2.encode('hex')
with open("flag.txt") as f:
flag = f.read().strip()
# length of flag is a multiple of 16
ct1 = cipher1.encrypt(flag.encode('hex'))
ct2 = cipher2.encrypt(ct1.encode('hex'))
print '\nEncrypted Flag:\n' + ct2.encode('hex') + '\n'Analysis of the code
As soon as we look at the code a few lines stand out. They are using AES in ECB mode:
cipher1 = AES.new(key=key1, mode=AES.MODE_ECB)
cipher2 = AES.new(key=key2, mode=AES.MODE_ECB)The keys used, key1 and key2 are generated by respectively prepending and appending three random printable characters to thirteen zeros:
key1 = '0'*13 + ''.join([random.choice(printable) for _ in range(3)])
key2 = ''.join([random.choice(printable) for _ in range(3)]) + '0'*13The code asks us to provide a string that will be encrypted two times with AES. Using the first key during the first encryption a cipherthext c1 is obtained. This ciphertext is then encrypted again using the second key:
c1 = cipher1.encrypt(pt.encode('hex'))
c2 = cipher2.encrypt(c1.encode('hex'))The flag is encrypted in the same way and using the same keys, the result of this encryption is also printed.
If we look at the file output.txt we can see that it is a run of the program. We have a plaintext with the corresponding ciphertext and the encrypted flag.
Let’s break it
From Wikipedia:
When trying to improve the security of a block cipher, a tempting idea is to encrypt the data several times using multiple keys. One might think this doubles or even n-tuples the security of the multiple-encryption scheme, depending on the number of times the data is encrypted, because an exhaustive search on all possible combination of keys (simple brute-force) would take 2^nk attempts if the data is encrypted with k-bit keys n times.
However here comes into play Meet-in-the-middle!
The MITM attack attempts to find the keys by using both the range (ciphertext) and domain (plaintext) of the composition of several functions (or block ciphers) such that the forward mapping through the first functions is the same as the backward mapping (inverse image) through the last functions, quite literally meeting in the middle of the composed function.
So, in simple terms, we just need to encrypt the plaintext with all possible keys, obtaining a set of ciphertext, let’s call this set CS. Now we start from the ciphertext and try to decrypt it by bruteforcing all possible keys until we find a decrypted ciphertext that is in the CS set. Once we have found a match we can stop bruteforcing, since we have already found our two keys!
Wait, did I say bruteforcing? It will take time? Nah… Remember the poor choice for the keys? It only helps us in bruteforcing them! We just need to bruteforce three characters for every key. Thanks to Meet-in-the-middle we don’t need to bruteforce all len(printable_chars)^6 combinations, but we just need len(printable_chars)^3 + len(printable_chars)^3 in the worst case! A significative improvement!
The code
I used Python to solve the challenge. I started creating the following variable from the data in the file output.txt
pt = 'aaaaaaaaaaaaaaaa'
ct = 'ef92fab38516aa95fdc53c2eb7e8fe1d5e12288fdc9d026e30469f38ca87c305ef92fab38516aa95fdc53c2eb7e8fe1d5e12288fdc9d026e30469f38ca87c305'
encrypted_flag = 'fa364f11360cef2550bd9426948af22919f8bdf4903ee561ba3d9b9c7daba4e759268b5b5b4ea2589af3cf4abe6f9ae7e33c84e73a9c1630a25752ad2a984abfbbfaca24f7c0b4313e87e396f2bf5ae56ee99bb03c2ffdf67072e1dc98f9ef691db700d73f85f57ebd84f5c1711a28d1a50787d6e1b5e726bc50db5a3694f576'Then I created a dictionary in which the key is the result of the encryption of the plaintext pt with any possible key.
print('[+] Creating dict')
ciphertext_dict = {}
for i in printable:
for j in printable:
for k in printable:
suffix = ''.join([i, j, k])
key1 = '0'*13 + suffix
cipher1 = AES.new(key=key1, mode=AES.MODE_ECB)
c1 = cipher1.encrypt(pt.encode('hex')).encode('hex')
ciphertext_dict[c1] = suffix
print('[+] Done')Once done I started the reverse step, bruteforcing the second key by decrypting the ciphertext:
for i in printable:
for j in printable:
for k in printable:
prefix = ''.join([i, j, k])
key2 = prefix + '0'*13
cipher2 = AES.new(key=key2, mode=AES.MODE_ECB)
c2 = cipher2.decrypt(ct.decode('hex'))
if c2 in ciphertext_dict:
print("[+] Wow, found {} {}".format(ciphertext_dict[c2].encode('hex'), prefix.encode('hex')))
win_suffix = ciphertext_dict[c2]
win_prefix = prefixAfter finding the correct keys I can simply decrypt the flag:
key1 = '0'*13 + win_suffix
key2 = win_prefix + '0'*13
c = AES.new(key=key2, mode=AES.MODE_ECB)
middle = c.decrypt(encrypted_flag.decode('hex'))
c = AES.new(key=key1, mode=AES.MODE_ECB)
flag = binascii.unhexlify(c.decrypt(middle.decode('hex')))
print('[+] FLAG {}'.format(flag))Here is the complete source code:
#!/usr/bin/python
import binascii
import sys
import random
from Crypto.Cipher import AES
from string import printable
pt = 'aaaaaaaaaaaaaaaa'
ct = 'ef92fab38516aa95fdc53c2eb7e8fe1d5e12288fdc9d026e30469f38ca87c305ef92fab38516aa95fdc53c2eb7e8fe1d5e12288fdc9d026e30469f38ca87c305'
encrypted_flag = 'fa364f11360cef2550bd9426948af22919f8bdf4903ee561ba3d9b9c7daba4e759268b5b5b4ea2589af3cf4abe6f9ae7e33c84e73a9c1630a25752ad2a984abfbbfaca24f7c0b4313e87e396f2bf5ae56ee99bb03c2ffdf67072e1dc98f9ef691db700d73f85f57ebd84f5c1711a28d1a50787d6e1b5e726bc50db5a3694f576'
print('[+] Creating dict')
ciphertext_dict = {}
for i in printable:
for j in printable:
for k in printable:
suffix = ''.join([i, j, k])
key1 = '0'*13 + suffix
cipher1 = AES.new(key=key1, mode=AES.MODE_ECB)
c1 = cipher1.encrypt(pt.encode('hex')).encode('hex')
ciphertext_dict[c1] = suffix
print('[+] Done')
for i in printable:
for j in printable:
for k in printable:
prefix = ''.join([i, j, k])
key2 = prefix + '0'*13
cipher2 = AES.new(key=key2, mode=AES.MODE_ECB)
c2 = cipher2.decrypt(ct.decode('hex'))
if c2 in ciphertext_dict:
print("[+] Wow, found {} {}".format(ciphertext_dict[c2].encode('hex'), prefix.encode('hex')))
win_suffix = ciphertext_dict[c2]
win_prefix = prefix
key1 = '0'*13 + win_suffix
key2 = win_prefix + '0'*13
c = AES.new(key=key2, mode=AES.MODE_ECB)
middle = c.decrypt(encrypted_flag.decode('hex'))
c = AES.new(key=key1, mode=AES.MODE_ECB)
flag = binascii.unhexlify(c.decrypt(middle.decode('hex')))
print('[+] FLAG {}'.format(flag))Which gives the flag: flag{y0u_m@d3_i7_t0_7h3_m1dddl3}.
