Linear Cryptanalysis

Tags

cryptography

A [see page 2, form] of cryptanalysis (against many block-ciphers) which exploits the deviation (bias) in the calculation of certain pairs of linear-expressions (of the input and of the output) of a substitution permuation network.

We define a linear expression as simply the xor sum of a subset of the bits in an input and output block.

Note: If we have enough plaintext ciphertext pairs, we can perform linear-analysis with as little as a 50.00001% bias. But where in gods name are you gonna get that much decrypted data?

Formulation

Linear-cryptanalysis [see page 9, exploits] the bias in a linear-relation (the knowledge that two linear-expressions agree a certain percent of the time).

Generally when two linear-expressions of some input and output bit-sequences (for example an S-box) agree more than \(\frac{8}{16}^{\text{ths}} = 50\%\) of the time then knowing the value of 1 of the expressions is a source of information on the other expression.

| \(X_1\) | \(X_2\) | \(X_3\) | \(X_4\) || \(Y_1\) | \(Y_2\) | \(Y_3\) | \(Y_4\) || \( X_2 \xor X_3 \) | \( Y_1 \xor Y_3 \xor Y_4 \) | |------------|------------|------------|------------|------------|------------|------------|------------|------------------------|----------------------------------| | 0 | 0 | 0 | 0 || 1 | 1 | 1 | 0 || 0 | 0 | | 0 | 0 | 0 | 1 || 0 | 1 | 0 | 0 || 0 | 0 | | 0 | 0 | 1 | 0 || 1 | 1 | 0 | 1 || 1 | 0 | | 0 | 0 | 1 | 1 || 0 | 0 | 0 | 1 || 1 | 1 | | 0 | 1 | 0 | 0 || 0 | 0 | 1 | 0 || 1 | 1 | | 0 | 1 | 0 | 1 || 1 | 1 | 1 | 1 || 1 | 1 | | 0 | 1 | 1 | 0 || 1 | 0 | 1 | 1 || 0 | 1 | | 0 | 1 | 1 | 1 || 1 | 0 | 0 | 0 || 0 | 1 | | 1 | 0 | 0 | 0 || 0 | 0 | 1 | 1 || 0 | 0 | | 1 | 0 | 0 | 1 || 1 | 0 | 1 | 0 || 0 | 0 | | 1 | 0 | 1 | 0 || 0 | 1 | 1 | 0 || 1 | 1 | | 1 | 0 | 1 | 1 || 1 | 1 | 0 | 0 || 1 | 1 | | 1 | 1 | 0 | 0 || 0 | 1 | 0 | 1 || 1 | 1 | | 1 | 1 | 0 | 1 || 1 | 0 | 0 | 1 || 1 | 0 | | 1 | 1 | 1 | 0 || 0 | 0 | 0 | 0 || 0 | 0 | | 1 | 1 | 1 | 1 || 0 | 1 | 1 | 1 || 0 | 0 |

For example if we know the input linear-expression \( X_3 \xor X_4 \) agrees with the output linear-expression \( Y_1 \xor Y_4 \), \( \frac{2}{16}^{\text{ths}} \) of the time for an S-box (as shown in table 1), we can define a approximate characterisation of the S-box, or simply an approximation as:

\begin{align} \label{eq:s-box-approximation} X_3 \xor X_4 = Y_1 \xor Y_4 \text{, $\frac{1}{8}^{\text{th}}$ of the time} \end{align}

eq:s-box-approximation can be reformulated in terms of the plaintext input and then re-arranged into an approximation in terms of the key-bits.

\begin{align} X_3 \xor X_4 &= P_3 \xor K_3 \xor P_4 \xor K_4 \
P_3 \xor K_3 \xor P_4 \xor K_4 &= Y_1 \xor Y_4 \
K_3 \xor K_4 &= P_3 \xor P_4 \xor Y_1 \xor Y_4 \label{eq:s-box-key-approx} \end{align}

All these equations, eq:s-box-key-approx especially, agree with the same probability as the original approximation in eq:s-box-approximation.

Now all we need to do is guess a key from the set of all possible permutations of \( k_3,k_4 \) (example: \(0101\), \(0101\), \(0110\), \(0111\) (Note: only \( k_3 \) and \( k_4 \) needs to change)) and then [see page 11, run] it through the encryption system to get \( (X,Y) \) pairs that we can use to find the probability of agreement of eq:s-box-key-approx. If \( P_3 \xor P_4 \xor Y_1 \xor Y_4 \) agrees with the current value of \( K_3 \xor K_4 \) 2 out of 16 times we have found the correct value of these key-bits.

Linear Approximation Table

A Linear Approximation table [see page 12, captures] linear input and output relations for use in linear cryptanalysis. The rows of this table reference the possible combinations of the input bits, the columns do so for the output bits and, the value stored in a cell is the bias of that input-output relation.

Note: Cells store the bias as an integer added onto an unbiased system to get the actual likelihood of the input-output relations agreeing. So a value of \( -6 \) from a baseline of \( \frac{8}{16} \) is \( \frac{8-6}{16} = \frac{2}{16} \).

Hey's Tutorial on Linear and Differential Cryptanalysis

Demonstrates how linear and differential cryptanalysis works on a toy block-cipher based on 16-bit blocks passed through 4 rounds. It works by [see page 20, chaining] approximations from the first round in a SPN to subsequent rounds, cancelling out the intermediate output-bits of rounds (the output of the previous round is the input of the next round so they cancel out) leading to an XOR formula in terms of the input, output and round key-bits. This final formula is known as the end-to-end approximation.

TODO: Explain example using linear approximation table.

We can resolve this equation through Matsui's lemma to get the final probability of agreement across an entire network.