0CTF 2018 Quals – zer0SPN (Crypto 550)

0ops SPN, hope you enjoy it:)
zer0SPN.zip

Summary: linear cryptanalysis on toy block cipher

In the challenge we have a “toy block cipher”. It is an SPN cipher with:

• 4 rounds
• eight 8-bit S-Boxes (64-bit block)
• bit permutations as linear layer

We are given $2^{16}$ random plaintext/ciphertext pairs.

On contrast with the zer0TC challenge, the bit permutation is strong and provides full diffusion. The S-Box is weak both differentially and linearly. Since we have known plaintexts, the way to go is linear cryptanalysis.

We shall attack the first round in order to get the master key and avoid need of key-schedule reversal. First, we need to find good 3-round linear trails. This can be done using various algorithms/tools.

For example:
Masks after first round: [ 64, 0, 0, 0, 0, 0, 0, 0],
Masks on ciphertexts: [242, 0, 0, 0, 0, 0, 242, 0],
Bias: $2^{-5.675513}$

We need to have bias $>2^{-8}$ because we have $2^{16}$ data. It actually is easier if the bias is around $2^{-6}$, then the right key byte will be the top candidate in our list with high probability.

The attack procedure:
1. Guess the first key byte $k$ of the master key
2. Partially encrypt the first byte of all plaintexts: $x’ = S(x^k)$.
3. Compute linear product: $c = scalar(x’, mask)$
4. Compute the bias of all c (i.e. how dis-balanced is the distribution of 0/1).
The right key byte should be in the top candidates sorted by the bias.

After we recover a couple of key bytes, we can use linear trails which have more active S-Boxes in the first round. The constraint is only that we have to guess only one extra key byte each time.

Full solution: https://gist.github.com/hellman/4950bff09b615e613d46be9eed4bc414

Finally, we get the flag: flag{48667ec1a5fb3383}