import base64
import struct
from Crypto.Cipher import AES

# reduce 2^48 to 2^27-ish using time-memory tradeoff

def crack(plaintext1, ciphertext1, plaintext2, ciphertext2):
        print "Cracking plaintext '%s'" % plaintext1
        zeroes = "\x00"*29
        for table in range(0,7):
                print "Generating table %s of 8 with 2^21 candidates" % (table+1)
                ciphertext_table1 = {}
                ciphertext_table2 = {}
                key_value = init = 2**21*table
                while key_value < init + 2**21:
                        key = zeroes + struct.pack('>I', key_value)[1:]
                        cipher = AES.new(key, AES.MODE_ECB)
                        ciphertext_table1[cipher.encrypt(plaintext1)] = key
                        ciphertext_table2[cipher.encrypt(plaintext2)] = key
                        key_value += 1
                        if key_value % 100000 == 0:
                                print "generated %s ciphertexts for key1 candidates" % key_value
                key_value = 0
                while key_value < 2**24:
                        key = zeroes + struct.pack('>I', key_value)[1:]
                        cipher = AES.new(key, AES.MODE_ECB)
                        if (ciphertext_table1.get(cipher.decrypt(ciphertext1)) and
                            ciphertext_table2.get(cipher.decrypt(ciphertext2)) and
                           (ciphertext_table1[cipher.decrypt(ciphertext1)] ==
                            ciphertext_table2[cipher.decrypt(ciphertext2)])):
                                return (ciphertext_table1[cipher.decrypt(ciphertext1)], key)
                        key_value += 1
                        if key_value % 100000 == 0:
                                print "tried %s key2 candidates" % ((table+1)*key_value)

# Challenge
mess1 = base64.b64decode("QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM=")
cypr1 = base64.b64decode("THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc=")
mess2 = base64.b64decode("RWFjaCBrZXkgemVybyB1bnRpbCBsYXN0IDI0IGJpdHM=")
cypr2 = base64.b64decode("01YZbSrta2N+1pOeQppmPETzoT/Yqb816yGlyceuEOE=")

final = base64.b64decode("s5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U=")

print mess1
print mess2

# Hax
key1, key2 = crack(mess1, cypr1, mess2, cypr2)
#key1 = base64.b64decode("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACa6Ac=")
#key2 = base64.b64decode("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD/P0U=")

# Done
cipher = AES.new(key2, AES.MODE_ECB)
decrypted = cipher.decrypt(final)
cipher = AES.new(key1, AES.MODE_ECB)
decrypted = cipher.decrypt(decrypted)
print decrypted