0CTF 2018 Quals – zer0TC (Crypto 916)

0ops Toy Cipher, hope you enjoy it:)

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}

Leave a Reply

Your email address will not be published.