S-box cryptanalysis

One of the most common components of a modern cryptographic cipher or hash function is the S-box. Its purpose is simple: it substitutes one value with another. In a substitution-permutation design, the S-box ensures that there are no simple relations between the bits of the plaintext, ciphertext, and key. In ciphers where the key is ‘added’ using the exclusive-or (XOR, ⊕) operation, we need to investigate XOR relations.

S-boxes are typically bijective, which means that there is a one-to-one relation between inputs and outputs. This makes it easier to ensure that there is no information loss at this stage.

The S-box is commonly expressed as a list of output values in the order of increasing input values. You can enter your list of decimal or hexadecimal values in the area below, separated by spaces or any other non-alphanumeric characters. You can also choose one of the examples or generate a random one.

S-box

Input			Output
Binary	Decimal	Hexadecimal	Binary	Decimal	Hexadecimal

Differential cryptanalysis

When we tweak the plaintext, we want the resulting ciphertext to be unpredictable. Focusing on the S-box, we will investigate what happens when we XOR the input with a value Δx. The tweak, or difference Δx, will result in a difference Δy in the output, according to the equality:

S(x ⊕ Δx) = S(x) ⊕ Δy

For each pair (Δx, Δy), we would like the equality to hold true with a small probability. Otherwise, we could be able to trace a high probability relation from the input to the output of our cipher and potentially recover the key from known plaintext-ciphertext pairs. As we increase the number of iterations, the probability should decrease exponentially to a level that we consider negligible.

Depending on the cipher, analysing other types of differences may be appropriate. Modular addition and bit rotation are two examples.

After analysing an S-box you should see the number of times each pair holds true in the following table. Hover over the count to see its probability.

Δx	Δy

Linear cryptanalysis

When we flip a bit of the plaintext, we want the probability of any ciphertext bit to flip to be as close to 50% as possible. We can generalise this as follows: if we XOR together a subset of input and output bits, the result should be 1 with a 50% probability. We say that we have a linear relation when for a subset of input bits i₁, …, i_m and a subset of output bits j₁, …, j_n the following expression is 0 or 1 with high probability:

x_i₁ ⊕ ⋯ ⊕ x_{i_m} ⊕ y_j₁ ⊕ ⋯ ⊕ y_{j_n}

Focusing on the S-box we can perform a similar analysis. We will represent subsets of bits with masks. When a bit of the mask is set, we include that bit, and vice versa. For example, a mask with a value of 3 will select the two least significant bits. For each mask pair (Mx, My), we count the number of times the XOR of the bits is 1. The difference of the count from half the number of inputs should be close to zero.

After analysing an S-box you should see the bias of each pair in the following table. Hover over the count to see its probability bias.

Mx	My

Attacking ciphers

Many ciphers have been broken or had their security reduced with such cryptanalysis. DES for example has been designed to be resistant to differential attacks but can be attacked using linear cryptanalysis. Can you find some weaknesses in its S-boxes?

To learn more, look at the tutorial on Linear and Differential cryptanalysis by Howard Heys.