Boston Key Party CTF 2013 - Crypto 200 - MITM - [Team xbios]

We were given a text file with the below contents

message 1:  QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=
encrypted:  THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=
message 2:  RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=
encrypted:  01YZbSrta2N+1pOeQppmPETzoT/Yqb816yGlyceuEOE=
ciphertext: s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=

>>> import base64
>>> message1 = "QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM="
>>> message2 = "RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM="
>>> base64.b64decode(message1)
'AES-256 ECB mode twice, two keys'
>>> base64.b64decode(message2)
'Each key zero until last 24 bits'

So we have the following details:

[*] Two pair of plain text and cipher text
[*] AES-256 ECB mode is used, so no IV. Length of key is 32 bytes
[*] Message is encrypted twice with two keys
[*] 29 bytes of key is zero, bruteforce the last 3 bytes
[*] Name of the challenge says its Meet In The Middle Attack

To find the key:

[*] Generate a dictionary of all possible {cipher:key} from plain text(message1). Since we bruteforce last 3 bytes of key, there would be 256*256*256 entries
[*] Then decrypt the cipher text(encrypted1) using all possible key(2nd key) and lookup the dictionary {cipher:key}
[*] If there is a hit, thats our key pair (k1, k2)
[*] Decrypt the cipher text as Dk1(Dk2(Cipher))), thats our flag

Below is the code to do that:

#!/usr/bin/env python

from Crypto.Cipher import AES  # requires pycrypto package
from struct import pack
import base64
import sys

# ECB mode, each block of 16 bytes encrypted independently
plain_text = base64.b64decode("QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=")[:16] 
cipher_text = base64.b64decode("THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=")[:16]
enc_message = base64.b64decode("s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=")

lookuptable = {}
key_prefix = pack("B", 0x00) * 29

# genarate list of possiblities
for i in range(256):
    for j in range(256):
        for k in range(256):
            brute = chr(i) + chr(j) + chr(k)
            cipher = AES.new(key_prefix + brute, AES.MODE_ECB).encrypt(plain_text)
            lookuptable.update({cipher:key_prefix + brute})

print "Lookup table Generated!"

for x in range(256):
    for y in range(256):
        for z in range(256):
            brute = chr(x) + chr(y) + chr(z)
            cipher = AES.new(key_prefix + brute, AES.MODE_ECB).decrypt(cipher_text)
            if lookuptable.has_key(cipher):  # find key
                key1 = lookuptable[cipher]
                key2 = key_prefix + brute
                c1 = AES.new(key2, AES.MODE_ECB).decrypt(enc_message)
                print AES.new(key1, AES.MODE_ECB).decrypt(c1)
                sys.exit(0)  

[ctf@renorobert BKPCTF]$ python solve200.py
Lookup table Generated!
This time I didn't include sol'n

Flag for the challenge is This time I didn't include sol'n