Along side the challenge description above, we got the following python code:
from hashlib import md5 from binascii import hexlify, unhexlify from secret import key, flag import sys BLOCK_LENGTH = 16 KEY_LENGTH = 3 ROUND_COUNT = 16 sbox = [210, 213, 115, 178, 122, 4, 94, 164, 199, 230, 237, 248, 54, 217, 156, 202, 212, 177, 132, 36, 245, 31, 163, 49, 68, 107, 91, 251, 134, 242, 59, 46, 37, 124, 185, 25, 41, 184, 221, 63, 10, 42, 28, 104, 56, 155, 43, 250, 161, 22, 92, 81, 201, 229, 183, 214, 208, 66, 128, 162, 172, 147, 1, 74, 15, 151, 227, 247, 114, 47, 53, 203, 170, 228, 226, 239, 44, 119, 123, 67, 11, 175, 240, 13, 52, 255, 143, 88, 219, 188, 99, 82, 158, 14, 241, 78, 33, 108, 198, 85, 72, 192, 236, 129, 131, 220, 96, 71, 98, 75, 127, 3, 120, 243, 109, 23, 48, 97, 234, 187, 244, 12, 139, 18, 101, 126, 38, 216, 90, 125, 106, 24, 235, 207, 186, 190, 84, 171, 113, 232, 2, 105, 200, 70, 137, 152, 165, 19, 166, 154, 112, 142, 180, 167, 57, 153, 174, 8, 146, 194, 26, 150, 206, 141, 39, 60, 102, 9, 65, 176, 79, 61, 62, 110, 111, 30, 218, 197, 140, 168, 196, 83, 223, 144, 55, 58, 157, 173, 133, 191, 145, 27, 103, 40, 246, 169, 73, 179, 160, 253, 225, 51, 32, 224, 29, 34, 77, 117, 100, 233, 181, 76, 21, 5, 149, 204, 182, 138, 211, 16, 231, 0, 238, 254, 252, 6, 195, 89, 69, 136, 87, 209, 118, 222, 20, 249, 64, 130, 35, 86, 116, 193, 7, 121, 135, 189, 215, 50, 148, 159, 93, 80, 45, 17, 205, 95] p = [3, 9, 0, 1, 8, 7, 15, 2, 5, 6, 13, 10, 4, 12, 11, 14] def xor(a, b): return bytearray(map(lambda s: s[0] ^ s[1], zip(a, b))) def fun(key, pt): assert len(pt) == BLOCK_LENGTH assert len(key) == KEY_LENGTH key = bytearray(unhexlify(md5(key).hexdigest())) ct = bytearray(pt) for _ in range(ROUND_COUNT): ct = xor(ct, key) for i in range(BLOCK_LENGTH): ct[i] = sbox[ct[i]] nct = bytearray(BLOCK_LENGTH) for i in range(BLOCK_LENGTH): nct[i] = ct[p[i]] ct = nct return hexlify(ct) def toofun(key, pt): assert len(key) == 2 * KEY_LENGTH key1 = key[:KEY_LENGTH] key2 = key[KEY_LENGTH:] ct1 = unhexlify(fun(key1, pt)) ct2 = fun(key2, ct1) return ct2 print("16 bit plaintext: %s" % toofun(key, b"16 bit plaintext")) print("flag: %s" % toofun(key, flag))
Like the challenge description suggests, a 6 byte key is too big to be bruteforced since there are 2566 possible keys (in other words waaay to many), however the "toofun" function splits the key in half. Each half is used seperatly for encryption when passed to the "fun" function. With this, along side the given plaintext example ("16 bit plaintext") and the corresponding ciphertext ("b'0467a52afa8f15cfb8f0ea40365a6692'") we can establish a Meet In The Middle Attack (the same vulnerability that affects 2-DES) by bruteforcing all possible 3 byte keys instead of 6. If we code the reverse of the "fun" function and pass all possible keys to fun(key,"16 bit plaintext") and reversed_fun(key,b'0467a52afa8f15cfb8f0ea40365a6692') there will be a certain pair of keys (let's call them keyA and keyB) such that fun(keyA,"16 bit plaintext") is equal to reversed_fun(keyB,b'0467a52afa8f15cfb8f0ea40365a6692')
Our original key will be the concatenation of keyA with keyB.
First I wrote a simple function to help invert the permutation schemes created using "p" and "sbox".
sbox = [210, 213, 115, 178, 122, 4, 94, 164, 199, 230, 237, 248, 54, 217, 156, 202, 212, 177, 132, 36, 245, 31, 163, 49, 68, 107, 91, 251, 134, 242, 59, 46, 37, 124, 185, 25, 41, 184, 221, 63, 10, 42, 28, 104, 56, 155, 43, 250, 161, 22, 92, 81, 201, 229, 183, 214, 208, 66, 128, 162, 172, 147, 1, 74, 15, 151, 227, 247, 114, 47, 53, 203, 170, 228, 226, 239, 44, 119, 123, 67, 11, 175, 240, 13, 52, 255, 143, 88, 219, 188, 99, 82, 158, 14, 241, 78, 33, 108, 198, 85, 72, 192, 236, 129, 131, 220, 96, 71, 98, 75, 127, 3, 120, 243, 109, 23, 48, 97, 234, 187, 244, 12, 139, 18, 101, 126, 38, 216, 90, 125, 106, 24, 235, 207, 186, 190, 84, 171, 113, 232, 2, 105, 200, 70, 137, 152, 165, 19, 166, 154, 112, 142, 180, 167, 57, 153, 174, 8, 146, 194, 26, 150, 206, 141, 39, 60, 102, 9, 65, 176, 79, 61, 62, 110, 111, 30, 218, 197, 140, 168, 196, 83, 223, 144, 55, 58, 157, 173, 133, 191, 145, 27, 103, 40, 246, 169, 73, 179, 160, 253, 225, 51, 32, 224, 29, 34, 77, 117, 100, 233, 181, 76, 21, 5, 149, 204, 182, 138, 211, 16, 231, 0, 238, 254, 252, 6, 195, 89, 69, 136, 87, 209, 118, 222, 20, 249, 64, 130, 35, 86, 116, 193, 7, 121, 135, 189, 215, 50, 148, 159, 93, 80, 45, 17, 205, 95] p = [3, 9, 0, 1, 8, 7, 15, 2, 5, 6, 13, 10, 4, 12, 11, 14] def inversePerm(p): ret = [] for i in range(0,len(p)): ret.append(i) for i in range(0,len(p)): ret[p[i]] = i return ret invert_p = inversePerm(p) invert_sbox = inversePerm(sbox)
And then a reverse version of the original “fun” function.
def no_fun_allowed(key, ct): ct = unhexlify(ct) key = bytearray(unhexlify(md5(key).hexdigest())) mitm = bytearray(ct) for _ in range(ROUND_COUNT): nct = bytearray(BLOCK_LENGTH) for i in range(BLOCK_LENGTH): nct[i] = mitm[invert_p[i]] mitm = nct for i in range(BLOCK_LENGTH): mitm[i] = invert_sbox[mitm[i]] mitm = xor(mitm,key) return hexlify(mitm)
Now we're ready to iterate through all possible keys. We'll be passing them as arguments to both the "fun" function and our newly created "no_fun_allowed" function as discussed previously. I chose to save the respective outputs to seperate files as you can see below.
# Stage 0 - Collect all possible keys ptout = open("ptOutput.txt","w") ctout = open("ctOutput.txt","w") for i in range(0,256): for j in range(0,256): for k in range(0,256): key = bytearray(3) key[0] = i; key[1] = j; key[2] = k ptout.write(hexlify(key) + " :: " + fun(key,b'16 bit plaintext') + "\n") ctout.write(hexlify(key) + " :: " + no_fun_allowed(key,b'0467a52afa8f15cfb8f0ea40365a6692') + "\n") ptout.close() ctout.close()
I then used python sets to find the hash that's common to both files, which turned out to be: 36e8c221ea84efcaab2c393786f938d0
# Stage 1 - Find Meet In The Middle Collision ptSet = set(line.split(" ")[2].strip() for line in open("ptOutput.txt","r")) ctSet = set(line.split(" ")[2].strip() for line in open("ctOutput.txt","r")) collision = ptSet & ctSet print "Collision > " + collision
With the common hash in hand we can now recover both halfs of the original key. When concatenated we get the original key: a277b5c1bc8b
# Stage 2 - Get Key key = "" with open("ptOutput.txt","r") as f: for line in f: if line.split(" ")[2].strip() == collision: print "Left side key > " + line.split(" ")[0].strip() key += line.split(" ")[0].strip() with open("ctOutput.txt","r") as f: for line in f: if line.split(" ")[2].strip() == collision: print "Right side key > " + line.split(" ")[0].strip() key += line.split(" ")[0].strip() print "Key > " + key
Finally all that's left is to recover the flag by reversing the "toofun" function.
# Stage 3 - Get Flag flag = b'04b34e5af4a1f5260f6043b8b9abb4f8' key = unhexlify(key) def not_so_fun_anymore(key,ct): assert len(key) == 2 * KEY_LENGTH key1 = key[:KEY_LENGTH] key2 = key[KEY_LENGTH:] hash = no_fun_allowed(key2, ct) pt = no_fun_allowed(key1,hash) return pt.decode("hex") print "hackim19{" + not_so_fun_anymore(key,flag) + "}"
As a result we get the flag: hackim19{1337_1n_m1ddl38f}
Full Solver:
from hashlib import md5 from binascii import hexlify, unhexlify import sys import os BLOCK_LENGTH = 16 KEY_LENGTH = 3 ROUND_COUNT = 16 sbox = [210, 213, 115, 178, 122, 4, 94, 164, 199, 230, 237, 248, 54, 217, 156, 202, 212, 177, 132, 36, 245, 31, 163, 49, 68, 107, 91, 251, 134, 242, 59, 46, 37, 124, 185, 25, 41, 184, 221, 63, 10, 42, 28, 104, 56, 155, 43, 250, 161, 22, 92, 81, 201, 229, 183, 214, 208, 66, 128, 162, 172, 147, 1, 74, 15, 151, 227, 247, 114, 47, 53, 203, 170, 228, 226, 239, 44, 119, 123, 67, 11, 175, 240, 13, 52, 255, 143, 88, 219, 188, 99, 82, 158, 14, 241, 78, 33, 108, 198, 85, 72, 192, 236, 129, 131, 220, 96, 71, 98, 75, 127, 3, 120, 243, 109, 23, 48, 97, 234, 187, 244, 12, 139, 18, 101, 126, 38, 216, 90, 125, 106, 24, 235, 207, 186, 190, 84, 171, 113, 232, 2, 105, 200, 70, 137, 152, 165, 19, 166, 154, 112, 142, 180, 167, 57, 153, 174, 8, 146, 194, 26, 150, 206, 141, 39, 60, 102, 9, 65, 176, 79, 61, 62, 110, 111, 30, 218, 197, 140, 168, 196, 83, 223, 144, 55, 58, 157, 173, 133, 191, 145, 27, 103, 40, 246, 169, 73, 179, 160, 253, 225, 51, 32, 224, 29, 34, 77, 117, 100, 233, 181, 76, 21, 5, 149, 204, 182, 138, 211, 16, 231, 0, 238, 254, 252, 6, 195, 89, 69, 136, 87, 209, 118, 222, 20, 249, 64, 130, 35, 86, 116, 193, 7, 121, 135, 189, 215, 50, 148, 159, 93, 80, 45, 17, 205, 95] p = [3, 9, 0, 1, 8, 7, 15, 2, 5, 6, 13, 10, 4, 12, 11, 14] def inversePerm(p): ret = [] for i in range(0,len(p)): ret.append(i) for i in range(0,len(p)): ret[p[i]] = i return ret invert_p = inversePerm(p) invert_sbox = inversePerm(sbox) def xor(a, b): return bytearray(map(lambda s: s[0] ^ s[1], zip(a, b))) def fun(key, pt): assert len(pt) == BLOCK_LENGTH assert len(key) == KEY_LENGTH key = bytearray(unhexlify(md5(key).hexdigest())) ct = bytearray(pt) for _ in range(ROUND_COUNT): ct = xor(ct, key) for i in range(BLOCK_LENGTH): ct[i] = sbox[ct[i]] nct = bytearray(BLOCK_LENGTH) for i in range(BLOCK_LENGTH): nct[i] = ct[p[i]] ct = nct return hexlify(ct) def no_fun_allowed(key, ct): ct = unhexlify(ct) key = bytearray(unhexlify(md5(key).hexdigest())) mitm = bytearray(ct) for _ in range(ROUND_COUNT): nct = bytearray(BLOCK_LENGTH) for i in range(BLOCK_LENGTH): nct[i] = mitm[invert_p[i]] mitm = nct for i in range(BLOCK_LENGTH): mitm[i] = invert_sbox[mitm[i]] mitm = xor(mitm,key) return hexlify(mitm) # Stage 0 - Collect all possible keys ptout = open("ptOutput.txt","w") ctout = open("ctOutput.txt","w") for i in range(0,256): for j in range(0,256): for k in range(0,256): key = bytearray(3) key[0] = i; key[1] = j; key[2] = k ptout.write(hexlify(key) + " :: " + fun(key,b'16 bit plaintext') + "\n") ctout.write(hexlify(key) + " :: " + no_fun_allowed(key,b'0467a52afa8f15cfb8f0ea40365a6692') + "\n") ptout.close() ctout.close() # Stage 1 - Find Meet In The Middle Collision ptSet = set(line.split(" ")[2].strip() for line in open("ptOutput.txt","r")) ctSet = set(line.split(" ")[2].strip() for line in open("ctOutput.txt","r")) collision = ptSet & ctSet print "Collision > " + collision # Stage 2 - Get Key key = "" with open("ptOutput.txt","r") as f: for line in f: if line.split(" ")[2].strip() == collision: print "Left side key > " + line.split(" ")[0].strip() key += line.split(" ")[0].strip() with open("ctOutput.txt","r") as f: for line in f: if line.split(" ")[2].strip() == collision: print "Right side key > " + line.split(" ")[0].strip() key += line.split(" ")[0].strip() print "Key > " + key # Stage 3 - Get Flag flag = b'04b34e5af4a1f5260f6043b8b9abb4f8' key = unhexlify(key) def not_so_fun_anymore(key,ct): assert len(key) == 2 * KEY_LENGTH key1 = key[:KEY_LENGTH] key2 = key[KEY_LENGTH:] hash = no_fun_allowed(key2, ct) pt = no_fun_allowed(key1,hash) return pt.decode("hex") print "hackim19{" + not_so_fun_anymore(key,flag) + "}"