0CTF 2018 Quals – zer0SPN (Crypto 550)

0ops SPN, hope you enjoy it:)

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}


1 ping

    • MJ on June 19, 2018 at 13:14
    • Reply

    Great writeup,
    Could I ask you, which algorithms/tools do you use to find linear trails?

    1. I used MILP solver for this, but it is a quite complicated approach. See e.g. http://ask2017.nudt.edu.cn/file/slides/ask2017_08_Yu%20Sasaki.pdf

      A simpler way would be to use Matsui algorithm, but it also needs to be implemented.

        • MJ on June 19, 2018 at 18:16
        • Reply

        I have followed linear cryptanalysis tutorial to solve this challenge. As going round by round, I spend lots of time to pick the mask. It still need to brute force 2 bytes each times QQ.

        Thank you very much, I will start on it now :))

Leave a Reply

Your email address will not be published.