Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/1_prepare_mitm.py

Last active October 8, 2019 06:02
Show Gist options
  • Save hellman/10206114e790fd3e8d92b41209ac8381 to your computer and use it in GitHub Desktop.
Save hellman/10206114e790fd3e8d92b41209ac8381 to your computer and use it in GitHub Desktop.
Download ZIP
0CTF 2018 Quals - zer0TC (Crypto 916)
Raw
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"
Raw
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;
}
Raw
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)
Raw
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
Raw
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
Raw
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment