{{ message }}

Instantly share code, notes, and snippets.

# hellman/1_prepare_mitm.py

Last active Oct 8, 2019
0CTF 2018 Quals - zer0TC (Crypto 916)
 #-*- coding:utf-8 -*- ''' In the challenge we have a "toy block cipher". It is an SPN cipher with: - 5 rounds - 8 8-bit S-Boxes (64-bit block) - bit permutations as linear layer We are given 8 random plaintext/ciphertext pairs. The bit permutation is weak: it maps 7 output bits of one S-box to 7 input bits of some S-Box in the next round. Still, 1 extra bit comes to each S-Box input. We can think about it as random/noise. The cipher then splits into 8 chains of 6 S-Boxes with key additions and bit permutations between the S-Boxes (and extra "noisy" bits coming in). We can attack each chain separately first, using meet-in-the-middle. The first half requires us to guess 3 keys and 1 extra incoming bit per each plaintext. The second half requires us to guess 3 keys and 2 extra incoming bits per each plaintext. Using 3 pairs of pt/ct, we get: (2^24 * 2^3) * (2^24 * 2^6) total guesses / 2^24 filtering in the middle. As a result, we get 2^33 valid guesses using 2^30 time (each valid guess corresponds to key + extra bits, so we will actually have less unique keys), We then can use other 5 pairs of pt/ct to reduce the number of key candidates to (2^48 * 2^32) total guesses / 2^64 filtering = 2^16 valid guesses. Again, the number of unique keys will be less (in fact it is around 3500 < 2^12). As a result, we still have lots of key candidates (2^12)^8 = 2^96 total. Even more than 2^64 actual keys. Now we have to use the key schedule to match the candidates correctly and efficiently. The key schedule is AES-like. As it is difficult to find all useful places in key schedule by hand, we generate all byte equations from the key schedule and then choose and use them automatically. ----- In this script we prepare the chains for MITM written on C++. To simplify bruteforce in C++, we inject a "fake" swap permutation such that the extra coming bit is always the leftmost one. It requires modification of S-Boxes and keys. ''' from common import * LOCAL_TEST = 1 # make chains of S-Boxes all_fake_perms = {} all_chains = [] for start_index in xrange(8): chain = [start_index] fake_perms = [ID] sboxes = [] all_fake_perms[0, start_index] = ID for i in xrange(5): prev_index = chain[-1] next_index = prevmapinv[prev_index] if i == 4: # no permutation in the end next_index = prev_index chain.append(next_index) if i < 4: bit_perm = ptable[next_index*8:next_index*8+8] for x in xrange(8): if bit_perm[x] / 8 == prev_index: bit_perm[x] %= 8 else: bit_perm[x] = None fake_perm = make_swap_perm(bit_perm.index(None), 7) bit_perm = bit_perm[::] bit_perm[bit_perm.index(None)] = [v for v in range(8) if v not in bit_perm][0] bit_perm = make_perm(bit_perm) else: fake_perm = ID bit_perm = ID # inject bit swap so that extra coming bit # is always the rightmost one # y = p(s(x)) + k # -> # y = swap( swap(p(s(x)) + swap(k)) ) # merge everything to new s-box # and get equivalent key with swapped bits # s' = swap_new(p(s(swap_prev(x))) # k' = swap(k) s = fake_perms[-1] s = compose(sbox, s) s = compose(bit_perm, s) s = compose(fake_perm, s) all_fake_perms[i+1, start_index] = fake_perm fake_perms.append(fake_perm) sboxes.append(s) all_chains.append(chain) print "start", start_index, "chain", chain if __name__ != '__main__': continue if not LOCAL_TEST: fout = open("sausage%d" % start_index, "w") for pt, ct in pairs: pt = pt[chain[0]] ct = ct[chain[-1]] fout.write("%d %d\n" % (pt, ct)) for s in sboxes: fout.write(" ".join(map(str, s)) + "\n") si = [s.index(i) for i in xrange(256)] fout.write(" ".join(map(str, si)) + "\n") fout.close() else: # verify transformations for pt, ct in test_pairs: pch = pt[chain[0]] cch = ct[chain[-1]] good = False # random extra bits for i in xrange(1000): x = pch for i in xrange(5): k = TEST_ROUND_KEYS[i][chain[i]] x ^= fake_perms[i][k] x = sboxes[i][x] if i < 4: x ^= randint(0, 1) x ^= TEST_ROUND_KEYS[5][chain[-1]] if x == cch: good = True break assert good, "something is wrong"
 #include using namespace std; /* g++ -std=c++11 -O3 2_mitm.cpp -o mitm && time ./mitm sausage0 sausage0.out ... final keys 3576/4290742205 real 2m17.722s user 2m16.635s sys 0m1.040s Can run all 8 sausages in parallel. */ // some sick macros.. #define CONCAT3_NX(x, y, z) x ## y ## z #define CONCAT3(x, y, z) CONCAT3_NX(x, y, z) #define VAR(name) CONCAT3(__tmpvar__, name, __LINE__) #define TYPE(x) __typeof(x) #define FOR(i, s, n) for (TYPE(n) i=(s), VAR(end)=(n); i < VAR(end); i++) #define RFOR(i, s, n) for (TYPE(n) i=(n)-1, VAR(end)=(s); i >= VAR(end); i--) #define FORN(i, n) FOR(i, 0, n) #define RFORN(i, n) RFOR(i, 0, n) #define FOREACH(i, v) for (auto& i: v) typedef unsigned char u8; typedef unsigned int u32; typedef unsigned long long u64; u8 pt[16] = {}; u8 ct[16] = {}; u8 sbox[5][256] = { {103, 172, 53, 159, 102, 168, 133, 197, 174, 182, 41, 164, 220, 58, 118, 63, 161, 50, 89, 242, 253, 74, 250, 119, 108, 122, 120, 216, 60, 208, 178, 20, 180, 187, 117, 213, 48, 90, 218, 46, 190, 188, 111, 252, 56, 77, 169, 232, 135, 72, 44, 115, 130, 57, 96, 155, 105, 181, 83, 0, 204, 139, 9, 7, 138, 23, 145, 97, 185, 13, 254, 69, 24, 34, 158, 76, 222, 165, 2, 247, 226, 6, 183, 116, 206, 21, 225, 210, 219, 36, 129, 100, 141, 62, 198, 28, 207, 84, 184, 99, 160, 215, 52, 73, 153, 42, 191, 26, 162, 194, 235, 81, 238, 110, 43, 214, 234, 221, 70, 80, 148, 176, 251, 245, 151, 244, 132, 14, 29, 94, 137, 131, 189, 31, 231, 47, 68, 8, 11, 249, 243, 37, 203, 200, 202, 255, 236, 112, 51, 10, 98, 79, 19, 59, 228, 177, 192, 75, 85, 45, 121, 27, 147, 179, 1, 201, 123, 18, 167, 166, 239, 146, 49, 196, 163, 109, 15, 143, 144, 150, 65, 106, 25, 124, 54, 241, 16, 92, 227, 217, 104, 173, 223, 86, 113, 39, 157, 199, 126, 71, 33, 61, 38, 142, 87, 22, 237, 152, 55, 212, 248, 175, 149, 170, 246, 88, 17, 64, 209, 171, 240, 224, 154, 211, 78, 93, 205, 114, 136, 12, 40, 101, 5, 95, 233, 35, 186, 195, 230, 127, 91, 229, 193, 32, 30, 4, 140, 66, 134, 128, 125, 82, 3, 67, 107, 156}, {103, 172, 53, 159, 102, 168, 133, 197, 174, 182, 41, 164, 220, 58, 118, 63, 161, 50, 89, 242, 253, 74, 250, 119, 108, 122, 120, 216, 60, 208, 178, 20, 180, 187, 117, 213, 48, 90, 218, 46, 190, 188, 111, 252, 56, 77, 169, 232, 135, 72, 44, 115, 130, 57, 96, 155, 105, 181, 83, 0, 204, 139, 9, 7, 138, 23, 145, 97, 185, 13, 254, 69, 24, 34, 158, 76, 222, 165, 2, 247, 226, 6, 183, 116, 206, 21, 225, 210, 219, 36, 129, 100, 141, 62, 198, 28, 207, 84, 184, 99, 160, 215, 52, 73, 153, 42, 191, 26, 162, 194, 235, 81, 238, 110, 43, 214, 234, 221, 70, 80, 148, 176, 251, 245, 151, 244, 132, 14, 29, 94, 137, 131, 189, 31, 231, 47, 68, 8, 11, 249, 243, 37, 203, 200, 202, 255, 236, 112, 51, 10, 98, 79, 19, 59, 228, 177, 192, 75, 85, 45, 121, 27, 147, 179, 1, 201, 123, 18, 167, 166, 239, 146, 49, 196, 163, 109, 15, 143, 144, 150, 65, 106, 25, 124, 54, 241, 16, 92, 227, 217, 104, 173, 223, 86, 113, 39, 157, 199, 126, 71, 33, 61, 38, 142, 87, 22, 237, 152, 55, 212, 248, 175, 149, 170, 246, 88, 17, 64, 209, 171, 240, 224, 154, 211, 78, 93, 205, 114, 136, 12, 40, 101, 5, 95, 233, 35, 186, 195, 230, 127, 91, 229, 193, 32, 30, 4, 140, 66, 134, 128, 125, 82, 3, 67, 107, 156}, {103, 172, 53, 159, 102, 168, 133, 197, 174, 182, 41, 164, 220, 58, 118, 63, 161, 50, 89, 242, 253, 74, 250, 119, 108, 122, 120, 216, 60, 208, 178, 20, 180, 187, 117, 213, 48, 90, 218, 46, 190, 188, 111, 252, 56, 77, 169, 232, 135, 72, 44, 115, 130, 57, 96, 155, 105, 181, 83, 0, 204, 139, 9, 7, 138, 23, 145, 97, 185, 13, 254, 69, 24, 34, 158, 76, 222, 165, 2, 247, 226, 6, 183, 116, 206, 21, 225, 210, 219, 36, 129, 100, 141, 62, 198, 28, 207, 84, 184, 99, 160, 215, 52, 73, 153, 42, 191, 26, 162, 194, 235, 81, 238, 110, 43, 214, 234, 221, 70, 80, 148, 176, 251, 245, 151, 244, 132, 14, 29, 94, 137, 131, 189, 31, 231, 47, 68, 8, 11, 249, 243, 37, 203, 200, 202, 255, 236, 112, 51, 10, 98, 79, 19, 59, 228, 177, 192, 75, 85, 45, 121, 27, 147, 179, 1, 201, 123, 18, 167, 166, 239, 146, 49, 196, 163, 109, 15, 143, 144, 150, 65, 106, 25, 124, 54, 241, 16, 92, 227, 217, 104, 173, 223, 86, 113, 39, 157, 199, 126, 71, 33, 61, 38, 142, 87, 22, 237, 152, 55, 212, 248, 175, 149, 170, 246, 88, 17, 64, 209, 171, 240, 224, 154, 211, 78, 93, 205, 114, 136, 12, 40, 101, 5, 95, 233, 35, 186, 195, 230, 127, 91, 229, 193, 32, 30, 4, 140, 66, 134, 128, 125, 82, 3, 67, 107, 156}, {103, 172, 53, 159, 102, 168, 133, 197, 174, 182, 41, 164, 220, 58, 118, 63, 161, 50, 89, 242, 253, 74, 250, 119, 108, 122, 120, 216, 60, 208, 178, 20, 180, 187, 117, 213, 48, 90, 218, 46, 190, 188, 111, 252, 56, 77, 169, 232, 135, 72, 44, 115, 130, 57, 96, 155, 105, 181, 83, 0, 204, 139, 9, 7, 138, 23, 145, 97, 185, 13, 254, 69, 24, 34, 158, 76, 222, 165, 2, 247, 226, 6, 183, 116, 206, 21, 225, 210, 219, 36, 129, 100, 141, 62, 198, 28, 207, 84, 184, 99, 160, 215, 52, 73, 153, 42, 191, 26, 162, 194, 235, 81, 238, 110, 43, 214, 234, 221, 70, 80, 148, 176, 251, 245, 151, 244, 132, 14, 29, 94, 137, 131, 189, 31, 231, 47, 68, 8, 11, 249, 243, 37, 203, 200, 202, 255, 236, 112, 51, 10, 98, 79, 19, 59, 228, 177, 192, 75, 85, 45, 121, 27, 147, 179, 1, 201, 123, 18, 167, 166, 239, 146, 49, 196, 163, 109, 15, 143, 144, 150, 65, 106, 25, 124, 54, 241, 16, 92, 227, 217, 104, 173, 223, 86, 113, 39, 157, 199, 126, 71, 33, 61, 38, 142, 87, 22, 237, 152, 55, 212, 248, 175, 149, 170, 246, 88, 17, 64, 209, 171, 240, 224, 154, 211, 78, 93, 205, 114, 136, 12, 40, 101, 5, 95, 233, 35, 186, 195, 230, 127, 91, 229, 193, 32, 30, 4, 140, 66, 134, 128, 125, 82, 3, 67, 107, 156}, {103, 172, 53, 159, 102, 168, 133, 197, 174, 182, 41, 164, 220, 58, 118, 63, 161, 50, 89, 242, 253, 74, 250, 119, 108, 122, 120, 216, 60, 208, 178, 20, 180, 187, 117, 213, 48, 90, 218, 46, 190, 188, 111, 252, 56, 77, 169, 232, 135, 72, 44, 115, 130, 57, 96, 155, 105, 181, 83, 0, 204, 139, 9, 7, 138, 23, 145, 97, 185, 13, 254, 69, 24, 34, 158, 76, 222, 165, 2, 247, 226, 6, 183, 116, 206, 21, 225, 210, 219, 36, 129, 100, 141, 62, 198, 28, 207, 84, 184, 99, 160, 215, 52, 73, 153, 42, 191, 26, 162, 194, 235, 81, 238, 110, 43, 214, 234, 221, 70, 80, 148, 176, 251, 245, 151, 244, 132, 14, 29, 94, 137, 131, 189, 31, 231, 47, 68, 8, 11, 249, 243, 37, 203, 200, 202, 255, 236, 112, 51, 10, 98, 79, 19, 59, 228, 177, 192, 75, 85, 45, 121, 27, 147, 179, 1, 201, 123, 18, 167, 166, 239, 146, 49, 196, 163, 109, 15, 143, 144, 150, 65, 106, 25, 124, 54, 241, 16, 92, 227, 217, 104, 173, 223, 86, 113, 39, 157, 199, 126, 71, 33, 61, 38, 142, 87, 22, 237, 152, 55, 212, 248, 175, 149, 170, 246, 88, 17, 64, 209, 171, 240, 224, 154, 211, 78, 93, 205, 114, 136, 12, 40, 101, 5, 95, 233, 35, 186, 195, 230, 127, 91, 229, 193, 32, 30, 4, 140, 66, 134, 128, 125, 82, 3, 67, 107, 156} }; u8 sboxinv[5][256] = { {59, 164, 78, 252, 245, 232, 81, 63, 137, 62, 149, 138, 229, 69, 127, 176, 186, 216, 167, 152, 31, 85, 205, 65, 72, 182, 107, 161, 95, 128, 244, 133, 243, 200, 73, 235, 89, 141, 202, 195, 230, 10, 105, 114, 50, 159, 39, 135, 36, 172, 17, 148, 102, 2, 184, 208, 44, 53, 13, 153, 28, 201, 93, 15, 217, 180, 247, 253, 136, 71, 118, 199, 49, 103, 21, 157, 75, 45, 224, 151, 119, 111, 251, 58, 97, 158, 193, 204, 215, 18, 37, 240, 187, 225, 129, 233, 54, 67, 150, 99, 91, 231, 4, 0, 190, 56, 181, 254, 24, 175, 113, 42, 147, 194, 227, 51, 83, 34, 14, 23, 26, 160, 25, 166, 183, 250, 198, 239, 249, 90, 52, 131, 126, 6, 248, 48, 228, 130, 64, 61, 246, 92, 203, 177, 178, 66, 171, 162, 120, 212, 179, 124, 207, 104, 222, 55, 255, 196, 74, 3, 100, 16, 108, 174, 11, 77, 169, 168, 5, 46, 213, 219, 1, 191, 8, 211, 121, 155, 30, 163, 32, 57, 9, 82, 98, 68, 236, 33, 41, 132, 40, 106, 156, 242, 109, 237, 173, 7, 94, 197, 143, 165, 144, 142, 60, 226, 84, 96, 29, 218, 87, 223, 209, 35, 115, 101, 27, 189, 38, 88, 12, 117, 76, 192, 221, 86, 80, 188, 154, 241, 238, 134, 47, 234, 116, 110, 146, 206, 112, 170, 220, 185, 19, 140, 125, 123, 214, 79, 210, 139, 22, 122, 43, 20, 70, 145}, {59, 164, 78, 252, 245, 232, 81, 63, 137, 62, 149, 138, 229, 69, 127, 176, 186, 216, 167, 152, 31, 85, 205, 65, 72, 182, 107, 161, 95, 128, 244, 133, 243, 200, 73, 235, 89, 141, 202, 195, 230, 10, 105, 114, 50, 159, 39, 135, 36, 172, 17, 148, 102, 2, 184, 208, 44, 53, 13, 153, 28, 201, 93, 15, 217, 180, 247, 253, 136, 71, 118, 199, 49, 103, 21, 157, 75, 45, 224, 151, 119, 111, 251, 58, 97, 158, 193, 204, 215, 18, 37, 240, 187, 225, 129, 233, 54, 67, 150, 99, 91, 231, 4, 0, 190, 56, 181, 254, 24, 175, 113, 42, 147, 194, 227, 51, 83, 34, 14, 23, 26, 160, 25, 166, 183, 250, 198, 239, 249, 90, 52, 131, 126, 6, 248, 48, 228, 130, 64, 61, 246, 92, 203, 177, 178, 66, 171, 162, 120, 212, 179, 124, 207, 104, 222, 55, 255, 196, 74, 3, 100, 16, 108, 174, 11, 77, 169, 168, 5, 46, 213, 219, 1, 191, 8, 211, 121, 155, 30, 163, 32, 57, 9, 82, 98, 68, 236, 33, 41, 132, 40, 106, 156, 242, 109, 237, 173, 7, 94, 197, 143, 165, 144, 142, 60, 226, 84, 96, 29, 218, 87, 223, 209, 35, 115, 101, 27, 189, 38, 88, 12, 117, 76, 192, 221, 86, 80, 188, 154, 241, 238, 134, 47, 234, 116, 110, 146, 206, 112, 170, 220, 185, 19, 140, 125, 123, 214, 79, 210, 139, 22, 122, 43, 20, 70, 145}, {59, 164, 78, 252, 245, 232, 81, 63, 137, 62, 149, 138, 229, 69, 127, 176, 186, 216, 167, 152, 31, 85, 205, 65, 72, 182, 107, 161, 95, 128, 244, 133, 243, 200, 73, 235, 89, 141, 202, 195, 230, 10, 105, 114, 50, 159, 39, 135, 36, 172, 17, 148, 102, 2, 184, 208, 44, 53, 13, 153, 28, 201, 93, 15, 217, 180, 247, 253, 136, 71, 118, 199, 49, 103, 21, 157, 75, 45, 224, 151, 119, 111, 251, 58, 97, 158, 193, 204, 215, 18, 37, 240, 187, 225, 129, 233, 54, 67, 150, 99, 91, 231, 4, 0, 190, 56, 181, 254, 24, 175, 113, 42, 147, 194, 227, 51, 83, 34, 14, 23, 26, 160, 25, 166, 183, 250, 198, 239, 249, 90, 52, 131, 126, 6, 248, 48, 228, 130, 64, 61, 246, 92, 203, 177, 178, 66, 171, 162, 120, 212, 179, 124, 207, 104, 222, 55, 255, 196, 74, 3, 100, 16, 108, 174, 11, 77, 169, 168, 5, 46, 213, 219, 1, 191, 8, 211, 121, 155, 30, 163, 32, 57, 9, 82, 98, 68, 236, 33, 41, 132, 40, 106, 156, 242, 109, 237, 173, 7, 94, 197, 143, 165, 144, 142, 60, 226, 84, 96, 29, 218, 87, 223, 209, 35, 115, 101, 27, 189, 38, 88, 12, 117, 76, 192, 221, 86, 80, 188, 154, 241, 238, 134, 47, 234, 116, 110, 146, 206, 112, 170, 220, 185, 19, 140, 125, 123, 214, 79, 210, 139, 22, 122, 43, 20, 70, 145}, {59, 164, 78, 252, 245, 232, 81, 63, 137, 62, 149, 138, 229, 69, 127, 176, 186, 216, 167, 152, 31, 85, 205, 65, 72, 182, 107, 161, 95, 128, 244, 133, 243, 200, 73, 235, 89, 141, 202, 195, 230, 10, 105, 114, 50, 159, 39, 135, 36, 172, 17, 148, 102, 2, 184, 208, 44, 53, 13, 153, 28, 201, 93, 15, 217, 180, 247, 253, 136, 71, 118, 199, 49, 103, 21, 157, 75, 45, 224, 151, 119, 111, 251, 58, 97, 158, 193, 204, 215, 18, 37, 240, 187, 225, 129, 233, 54, 67, 150, 99, 91, 231, 4, 0, 190, 56, 181, 254, 24, 175, 113, 42, 147, 194, 227, 51, 83, 34, 14, 23, 26, 160, 25, 166, 183, 250, 198, 239, 249, 90, 52, 131, 126, 6, 248, 48, 228, 130, 64, 61, 246, 92, 203, 177, 178, 66, 171, 162, 120, 212, 179, 124, 207, 104, 222, 55, 255, 196, 74, 3, 100, 16, 108, 174, 11, 77, 169, 168, 5, 46, 213, 219, 1, 191, 8, 211, 121, 155, 30, 163, 32, 57, 9, 82, 98, 68, 236, 33, 41, 132, 40, 106, 156, 242, 109, 237, 173, 7, 94, 197, 143, 165, 144, 142, 60, 226, 84, 96, 29, 218, 87, 223, 209, 35, 115, 101, 27, 189, 38, 88, 12, 117, 76, 192, 221, 86, 80, 188, 154, 241, 238, 134, 47, 234, 116, 110, 146, 206, 112, 170, 220, 185, 19, 140, 125, 123, 214, 79, 210, 139, 22, 122, 43, 20, 70, 145}, {59, 164, 78, 252, 245, 232, 81, 63, 137, 62, 149, 138, 229, 69, 127, 176, 186, 216, 167, 152, 31, 85, 205, 65, 72, 182, 107, 161, 95, 128, 244, 133, 243, 200, 73, 235, 89, 141, 202, 195, 230, 10, 105, 114, 50, 159, 39, 135, 36, 172, 17, 148, 102, 2, 184, 208, 44, 53, 13, 153, 28, 201, 93, 15, 217, 180, 247, 253, 136, 71, 118, 199, 49, 103, 21, 157, 75, 45, 224, 151, 119, 111, 251, 58, 97, 158, 193, 204, 215, 18, 37, 240, 187, 225, 129, 233, 54, 67, 150, 99, 91, 231, 4, 0, 190, 56, 181, 254, 24, 175, 113, 42, 147, 194, 227, 51, 83, 34, 14, 23, 26, 160, 25, 166, 183, 250, 198, 239, 249, 90, 52, 131, 126, 6, 248, 48, 228, 130, 64, 61, 246, 92, 203, 177, 178, 66, 171, 162, 120, 212, 179, 124, 207, 104, 222, 55, 255, 196, 74, 3, 100, 16, 108, 174, 11, 77, 169, 168, 5, 46, 213, 219, 1, 191, 8, 211, 121, 155, 30, 163, 32, 57, 9, 82, 98, 68, 236, 33, 41, 132, 40, 106, 156, 242, 109, 237, 173, 7, 94, 197, 143, 165, 144, 142, 60, 226, 84, 96, 29, 218, 87, 223, 209, 35, 115, 101, 27, 189, 38, 88, 12, 117, 76, 192, 221, 86, 80, 188, 154, 241, 238, 134, 47, 234, 116, 110, 146, 206, 112, 170, 220, 185, 19, 140, 125, 123, 214, 79, 210, 139, 22, 122, 43, 20, 70, 145} }; // for local test u8 keys[6] = {}; u8 test_encrypt_rand(u8 x) { FORN(i, 5) { x ^= keys[i]; x = sbox[i][x]; if (i < 4) { x ^= (x & 1) ^ (rand() & 1); } } x ^= keys[5]; return x; } int NUM_TEXTS = 3; int TOTAL_TEXTS = 8; FILE *fout; inline int check_key(u32 keytop, u32 keybot) { u8 k0 = (keytop >> 0) & 0xff; u8 k1 = (keytop >> 8) & 0x7f; u8 k2 = (keytop >> 15) & 0x7f; k1 <<= 1; k2 <<= 1; u8 k5 = (keybot >> 0) & 0xff; u8 k4 = (keybot >> 8) & 0x7f; u8 k3 = (keybot >> 15) & 0x7f; k4 <<= 1; k3 <<= 1; FOR(ti, NUM_TEXTS, TOTAL_TEXTS) { u8 values[2]; FORN(flag, 2) { u8 x = pt[ti]; x ^= k0; x = sbox[0][x]; x ^= flag; x ^= k1; x = sbox[1][x]; // x ^= 0; // arbitrary flag x ^= k2; x >>= 1; // project mid values[flag] = x; } bool good = 0; FORN(flags2, 4) { u8 flagsbuf = flags2; u8 flag1 = flagsbuf & 1; flagsbuf >>= 1; u8 flag2 = flagsbuf & 1; flagsbuf >>= 1; u8 x = ct[ti]; x ^= k5; x = sboxinv[4][x]; x ^= k4; x ^= flag1; x = sboxinv[3][x]; x ^= k3; x ^= flag2; x = sboxinv[2][x]; x >>= 1; // project mid if (values[0] == x || values[1] == x) { good = 1; break; } } if (!good) return 0; } fprintf(fout, "%d %d %d %d %d %d\n", k0, k1, k2, k3, k4, k5); return 1; } int tmp; #define scan8(dst) {scanf("%d", &tmp); dst=tmp;} int main(int argc, char* argv[]) { ios_base::sync_with_stdio(0); assert(argc == 3); printf("input:%s output:%s\n", argv[1], argv[2]); freopen(argv[1], "r+", stdin); fout = fopen(argv[2], "w"); assert(fout); if (0) { printf("random local key\n"); srand(1337); FORN(i, 6) keys[i] = rand(); FORN(i, TOTAL_TEXTS) pt[i] = rand(); FORN(i, TOTAL_TEXTS) ct[i] = test_encrypt_rand(pt[i]); } else { printf("from input\n"); TOTAL_TEXTS = 8; FORN(i, 8) { scan8(pt[i]); scan8(ct[i]); } FORN(i, 5) { FORN(j, 256) scan8(sbox[i][j]); FORN(j, 256) scan8(sboxinv[i][j]); } } printf("stage 1\n"); unordered_map> table; FORN(key, 256 * 128 * 128) { u8 k0 = (key >> 0) & 0xff; u8 k1 = (key >> 8) & 0x7f; u8 k2 = (key >> 15) & 0x7f; k1 <<= 1; k2 <<= 1; // debug // if (k0 != keys[0]) continue; // if (k1 >> 1 != keys[1] >> 1) continue; // if (k2 >> 1 != keys[2] >> 1) continue; if (k0 == 0 && k1 == 0 && (k2 & 0xf) == 0) printf("k012: %d %d %d\n", k0, k1, k2); FORN(flags, 1 << NUM_TEXTS) { u32 mid = 0; FORN(ti, NUM_TEXTS) { u8 flag = (flags >> ti) & 1; u8 x = pt[ti]; x ^= k0; x = sbox[0][x]; x ^= flag; x ^= k1; x = sbox[1][x]; // x ^= 0; // arbitrary flag x ^= k2; x >>= 1; // project mid mid = (mid << 7) | x; } table[mid].push_back(key); } } printf("stage 2\n"); u64 cntkeys = 0; u64 goodkeys = 0; FORN(key, 256 * 128 * 128) { u8 k5 = (key >> 0) & 0xff; u8 k4 = (key >> 8) & 0x7f; u8 k3 = (key >> 15) & 0x7f; k4 <<= 1; k3 <<= 1; // if (k5 != keys[5]) continue; // if (k4 >> 1 != keys[4] >> 1) continue; // if (k3 >> 1 != keys[3] >> 1) continue; if (k5 == 0 && k4 == 0 && (k3 & 0xf) == 0) { printf("k543: %d %d %d\n", k5, k4, k3); printf("keys %llu/%llu\n", goodkeys, cntkeys); } FORN(flags, 1 << (NUM_TEXTS << 1)) { u32 mid = 0; u32 flagsbuf = flags; FORN(ti, NUM_TEXTS) { u8 flag1 = flagsbuf & 1; flagsbuf >>= 1; u8 flag2 = flagsbuf & 1; flagsbuf >>= 1; u8 x = ct[ti]; x ^= k5; x = sboxinv[4][x]; x ^= k4; x ^= flag1; x = sboxinv[3][x]; x ^= k3; x ^= flag2; x = sboxinv[2][x]; x >>= 1; // project mid mid = (mid << 7) | x; } cntkeys += table[mid].size(); FOREACH(keytop, table[mid]) { goodkeys += check_key(keytop, key); } } } printf("final keys %llu/%llu\n", goodkeys, cntkeys); return 0; }
 #-*- coding:utf-8 -*- ''' 1. Generate equations from the AES-like key schedule 2. Assume we guess 2 chain keys. We need to verify the guess. We need equations which include only guessed values. => Choose the best combination of chain keys and reduce the amount of joint key candidates. Start with 2 chains: best indexes (1, 4) : 2 useful equations ('k3_5', False, 0, 'k4_1', 'k4_5') ('k4_5', False, 0, 'k5_1', 'k5_5') Result: 1571 joint candidate Then at each step guess one more chain key and verify. More equations will become useful and it will go faster: best indexes (1, 4) : 2 useful equations NGOOD 1571 joint candidate best indexes (1, 4, 5) : 5 useful equations NGOOD 19 best indexes (1, 4, 5, 2) : 9 useful equations NGOOD 1 best indexes (1, 4, 5, 2, 0) : 15 useful equations NGOOD 1 best indexes (1, 4, 5, 2, 0, 7) : 20 useful equations NGOOD 1 best indexes (1, 4, 5, 2, 0, 7, 6) : 27 useful equations NGOOD 1 best indexes (1, 4, 5, 2, 0, 7, 6, 3) : 40 useful equations NGOOD 1 The final master key: 7e035ed7c2bc78c3 \$ time pypy 3_equations.py real 0m31.438s user 0m31.225s sys 0m0.212s ''' from common import * mod = __import__("1_prepare_mitm") all_fake_perms = mod.all_fake_perms all_chains = mod.all_chains all_fake_perms = all_fake_perms # generate all equations in the key schedule eqs = [] for i in xrange(5): # left_half ^= rotate(right_half, 1) ^ [rcon, 0, 0, 0] l = "k%d_%d" % (i, 0) r = "k%d_%d" % (i, 5) res = "k%d_%d" % (i+1, 0) eqs.append((r, True, rcon[i+1], l, res)) assert sbox[TEST_ROUND_KEYS[i][5]] ^ rcon[i+1] ^ TEST_ROUND_KEYS[i][0] == TEST_ROUND_KEYS[i+1][0], ("index", i) l = "k%d_%d" % (i, 1) r = "k%d_%d" % (i, 6) res = "k%d_%d" % (i+1, 1) eqs.append((r, True, 0, l, res)) assert sbox[TEST_ROUND_KEYS[i][6]] ^ TEST_ROUND_KEYS[i][1] == TEST_ROUND_KEYS[i+1][1], ("index", i) l = "k%d_%d" % (i, 2) r = "k%d_%d" % (i, 7) res = "k%d_%d" % (i+1, 2) eqs.append((r, True, 0, l, res)) assert sbox[TEST_ROUND_KEYS[i][7]] ^ TEST_ROUND_KEYS[i][2] == TEST_ROUND_KEYS[i+1][2], ("index", i) l = "k%d_%d" % (i, 3) r = "k%d_%d" % (i, 4) res = "k%d_%d" % (i+1, 3) eqs.append((r, True, 0, l, res)) assert sbox[TEST_ROUND_KEYS[i][4]] ^ TEST_ROUND_KEYS[i][3] == TEST_ROUND_KEYS[i+1][3], ("index", i) # right_half ^= left_half for j in xrange(4): l = "k%d_%d" % (i+1, j) r = "k%d_%d" % (i, j+4) res = "k%d_%d" % (i+1, j+4) eqs.append((r, False, 0, l, res)) assert TEST_ROUND_KEYS[i][j+4] ^ TEST_ROUND_KEYS[i+1][j] == TEST_ROUND_KEYS[i+1][j+4], ("index", i) def get_useful_equations(indexes): known_key_ids = set() for i in xrange(6): for sind in indexes: id = "k%d_%d" % (i, all_chains[sind][i]) known_key_ids.add(id) useful = [] for eq in eqs: r, _, _, l, out = eq if r in known_key_ids and l in known_key_ids and out in known_key_ids: useful.append(eq) return useful chain_keys = [] for start_index in xrange(8): keys = [] for line in open("sausage%d.out" % start_index): k = tuple(map(int, line.split())) keys.append(k) keys = sorted(set(keys)) chain_keys.append(tuple(keys)) best = 0, None indexes = [] for num_chains in xrange(2, 9): if not indexes: # first find a pair with most useful equations itr = combinations(range(8), 2) else: # then extend by one each time itr = [] for index in range(8): if index not in indexes: itr.append(indexes + (index,)) for indexes in itr: useful = get_useful_equations(indexes) best = max(best, (len(useful), indexes)) num_useful, indexes = best print "best indexes", indexes, ":", num_useful, "useful equations" useful = get_useful_equations(indexes) for eq in useful: print " ", eq print def setkey(start_index, key_index): key = chain_keys[start_index][key_index] for i in xrange(6): id = "k%d_%d" % (i, all_chains[start_index][i]) val = key[i] fp = all_fake_perms[i, start_index] if i in (0, 5): keydata[id] = fp[val], else: keydata[id] = fp[val], fp[val^1] def evaluate(): numgood = 0 for eq in useful: r, dosbox, const, l, out = eq for r, l, out in product(keydata[r], keydata[l], keydata[out]): if not dosbox: if out == l ^ r: numgood += 1 break else: if out == sbox[r] ^ const ^ l: numgood += 1 break return numgood if num_chains == 2: prev_candidates = [(i,) for i in range(len(chain_keys[indexes[0]]))] else: prev_candidates = candidates candidates = [] keydata = {} ngood = 0 for vals in prev_candidates: for sind, val in zip(indexes, vals): setkey(sind, val) sind = indexes[-1] for val in xrange(len(chain_keys[sind])): setkey(sind, val) if evaluate() >= len(useful): ngood += 1 candidates.append(vals + (val,)) print "NGOOD", ngood for vals in candidates[:100]: for sind, val in zip(indexes, vals): setkey(sind, val) for key in product(*[keydata["k0_%d" % i] for i in xrange(8)]): print "".join("%02x" % c for c in key)
 from random import randint from itertools import product, combinations from collections import Counter from zer0TC import zer0TC, rcon, sbox, ptable sboxinv = [sbox.index(x) for x in xrange(256)] ptableinv = [ptable.index(i) for i in xrange(64)] def tobin(x, n): return tuple(map(int, bin(x).lstrip("0b").rjust(n, "0"))) def frombin(v): return int("".join(map(str, v)), 2 ) def make_swap_perm(i, j): res = [] for x in xrange(256): x = list(tobin(x, 8)) x[i], x[j] = x[j], x[i] x = frombin(x) res.append(x) return tuple(res) def make_perm(perm): res = [] for x in xrange(256): x = list(tobin(x, 8)) x = [x[i] for i in perm] x = frombin(x) res.append(x) return tuple(res) def compose(f, g): return tuple(f[g[x]] for x in xrange(256)) ID = tuple(range(256)) # load data NDATA = 8 s = open("data") pairs = [] for i in xrange(NDATA): pt = tuple(map(ord, s.read(8))) ct = tuple(map(ord, s.read(8))) pairs.append((pt, ct)) # local test data TEST_KEY = "abcdefgh" TEST_ROUND_KEYS = None test_pairs = [] for i in xrange(NDATA): pt, ct = pairs[i] z = zer0TC(TEST_KEY) ctx = z.encrypt(bytearray(pt)) ctx = tuple(ctx) test_pairs.append((pt, ctx)) TEST_ROUND_KEYS = tuple(z.roundkey[i:i+8] for i in xrange(0, len(z.roundkey), 8)) # which S-Box goes to which S-Box prevmap = {} prevmapinv = {} for y in xrange(8): ids = ptable[y*8:y*8+8] prevs = [id / 8 for id in ids] for j in xrange(8): if prevs.count(j) == 7: prevmap[y] = j ids = ptableinv[y*8:y*8+8] prevs = [id / 8 for id in ids] for j in xrange(8): if prevs.count(j) == 7: prevmapinv[y] = j
 2d3f 8142 a655 ef80 88f8 f5f7 7d2f 0870 078d 1690 6bb9 dd67 410b 8ad5 080d 2e68 6551 51ed 316a e3a9 fed3 4043 83aa b276 816a d934 af89 6c6a 94e7 89c7 c331 e816 12c5 7345 9084 f641 3031 e8c1 c3d9 fa2d 856d 1afc 400f 2b5f 9601 4858 8c75 d9a7 b3ed 0058 28cd 0ab8 dd9f 70b4 e410 5fc8 dfb4 1bff 5de1 3e4b 558f 7ddf 019c 8821
 #!/usr/bin/env python # coding=utf-8 rcon = [0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a] sbox = [103, 172, 53, 159, 102, 168, 133, 197, 174, 182, 41, 164, 220, 58, 118, 63, 161, 50, 89, 242, 253, 74, 250, 119, 108, 122, 120, 216, 60, 208, 178, 20, 180, 187, 117, 213, 48, 90, 218, 46, 190, 188, 111, 252, 56, 77, 169, 232, 135, 72, 44, 115, 130, 57, 96, 155, 105, 181, 83, 0, 204, 139, 9, 7, 138, 23, 145, 97, 185, 13, 254, 69, 24, 34, 158, 76, 222, 165, 2, 247, 226, 6, 183, 116, 206, 21, 225, 210, 219, 36, 129, 100, 141, 62, 198, 28, 207, 84, 184, 99, 160, 215, 52, 73, 153, 42, 191, 26, 162, 194, 235, 81, 238, 110, 43, 214, 234, 221, 70, 80, 148, 176, 251, 245, 151, 244, 132, 14, 29, 94, 137, 131, 189, 31, 231, 47, 68, 8, 11, 249, 243, 37, 203, 200, 202, 255, 236, 112, 51, 10, 98, 79, 19, 59, 228, 177, 192, 75, 85, 45, 121, 27, 147, 179, 1, 201, 123, 18, 167, 166, 239, 146, 49, 196, 163, 109, 15, 143, 144, 150, 65, 106, 25, 124, 54, 241, 16, 92, 227, 217, 104, 173, 223, 86, 113, 39, 157, 199, 126, 71, 33, 61, 38, 142, 87, 22, 237, 152, 55, 212, 248, 175, 149, 170, 246, 88, 17, 64, 209, 171, 240, 224, 154, 211, 78, 93, 205, 114, 136, 12, 40, 101, 5, 95, 233, 35, 186, 195, 230, 127, 91, 229, 193, 32, 30, 4, 140, 66, 134, 128, 125, 82, 3, 67, 107, 156] ptable = [ 16, 19, 23, 9, 22, 20, 21, 17, 40, 43, 44, 47, 41, 45, 57, 42, 36, 32, 38, 33, 55, 37, 34, 35, 50, 53, 48, 52, 39, 54, 49, 51, 10, 11, 14, 8, 13, 15, 18, 12, 0, 7, 2, 3, 4, 1, 5, 31, 63, 46, 58, 62, 61, 59, 56, 60, 6, 29, 25, 24, 30, 27, 28, 26 ] def s2b(s): return map(int, format(int(str(s).encode('hex'), 16), '0{}b'.format(8*len(s)))) def b2s(b): return bytearray.fromhex(format(reduce(lambda x,y: 2*x+y, b), '0{}x'.format(len(b)/4))) def addkey(a, b): global flag return bytearray(i^j for i,j in zip(a, b)) def substitute(a): return bytearray(sbox[i] for i in a) def permutation(a): assert len(a) == 8 bits = s2b(a) bits = [bits[ptable[i]] for i in xrange(64)] return b2s(bits) class zer0TC(object): '''0ops Toy Cipher''' def __init__(self, key, key_size=8, rounds=5): assert len(key) == key_size self.key = key self.key_size = key_size self.rounds = rounds self.key_schedule() def key_schedule(self): roundkey = bytearray(self.key) tmp = roundkey[-4:] for i in xrange(1, self.rounds+1): tmp = tmp[1:] + tmp[:1] tmp = bytearray(sbox[i] for i in tmp) tmp[0] ^= rcon[i] for j in range(self.key_size/4): for k in range(4): tmp[k] ^= roundkey[-self.key_size+k] roundkey += tmp self.roundkey = roundkey def get_roundkey(self, k): assert k <= self.rounds return self.roundkey[self.key_size*k:self.key_size*(k+1)] def encrypt(self, plain): assert len(plain) == self.key_size block = bytearray(plain) for i in xrange(self.rounds): block = addkey(block, self.get_roundkey(i)) block = substitute(block) if i != self.rounds - 1: # Permutation in the last round is of no purpose. block = permutation(block) block = addkey(block, self.get_roundkey(i+1)) return block if __name__ == '__main__': from secret import secret from os import urandom from struct import pack print "Your flag is flag{%s}" % secret.encode('hex') f = open('data', 'wb') for _ in xrange(8): c = zer0TC(secret) plaintext = bytearray(urandom(8)) f.write(pack('8B', *plaintext)) ciphertext = c.encrypt(plaintext) f.write(pack('8B', *ciphertext)) f.close()