# Boston Key Party -- MITM

09 Jun 2013 in SecurityBoston Key Party is the latest CTF I've played in (this time playing with some local friends as part of our team 'Shadow Cats'). The first challenge we cleared (actually, first blood in the CTF) was MITM.

Now, you might think a challenge named "MITM" was some sort of Man-In-The-Middle exercise, but it's actually crypto! We're given five base-64 encoded messages: two plaintext/ciphertext pairs, and a ciphertext (which we're presumably supposed to decrypt).

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

Decoding the two plaintexts gives us:

AES-256 ECB mode twice, two keys Each key zero until last 24 bits

Some useful hints. So our construction is **C = E _{K2}(E_{K1}(P))** where K1 and K2 are both 256-bit keys with the first 29 bytes being all nulls. This means the remaining keyspace for each key is 2

^{24}, or 2

^{24}* 2

^{24}= 2

^{48}for both keys combined. Brute forcing 2

^{48}combinations seems... unlikely during a CTF.

The good news is, we only actually have to try ~2^{25} possible keys, which is quite doable even on my laptop. (Actually completes in a matter of minutes.) The trick is a Meet in the Middle (MITM again!) attack. Because we have a plaintext/ciphertext pair, we can **encrypt** the plaintext with all possible keys, store those encryptions, then **decrypt** the ciphertext with all possible keys and check those keys against the encryptions. They will match when you have found your two keys, which can then be used to decrypt the unknown ciphertext.

from Crypto.Cipher import AES plain = 'QUVTLTI1NiBFQ0IgbW9kZSB0d2ljZSwgdHdvIGtleXM='.decode('base64') cipher = 'THbpB4bE82Rq35khemTQ10ntxZ8sf7s2WK8ErwcdDEc='.decode('base64') unknown = 's5hd0ThTkv1U44r9aRyUhaX5qJe561MZ16071nlvM9U='.decode('base64') KEY_PADDING = chr(0)*29 def NewAES(key): return AES.new(key, mode=AES.MODE_ECB) def Encrypt(short_key, text=plain): return NewAES(KEY_PADDING+short_key).encrypt(text) def Decrypt(short_key, text=cipher): return NewAES(KEY_PADDING+short_key).decrypt(text) def KeyGen(): """Generator for all possible 24 bit keys.""" for a in xrange(0, 256): for b in xrange(0, 256): for c in xrange(0, 256): yield chr(a)+chr(b)+chr(c) def EncryptTable(): """Map of encryptions to keys.""" table = {} for short_key in KeyGen(): table[Encrypt(short_key)] = short_key return table table = EncryptTable() for short_key in KeyGen(): decrypted = Decrypt(short_key) if decrypted in table: # Have a match, now decrypt the unknown print Decrypt(short_key, Decrypt(table[decrypted], unknown)) break

The downside to this technique is that it has 2^{24} memory complexity, as you store an entire hash table of encryption->key pairs for the inner encryption. However, even with the overhead in python, 2^{24} memory seems to amount to ~2.5GB, so a small tradeoff here.