0ops Toy Cipher, hope you enjoy it:)
zer0TC.zip
Summary: meet-in-the-middle and key-schedule constraints
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
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.
Full solution: https://gist.github.com/hellman/10206114e790fd3e8d92b41209ac8381
The flag: flag{7e035ed7c2bc78c3}
