0CTF 2018 Quals - zer0TC (Crypto 916)

1_prepare_mitm.py

#-*- 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"

2_mitm.cpp

#include <bits/stdc++.h>
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<u32, vector<u32>> 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;
}

3_equations.py

#-*- 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)

common.py

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

data.hex

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

zer0TC.py

#!/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()