Linear Cryptanalyse

The linear cryptanalyse is a technique invented by Mitsuru Matsui, researcher at Mitsubishi. It goes back to 1993 and was developed at the origin to break the symmetrical encryption algorithm . This type of cryptanalyse is based on a concept former to discovered of Matsui: probabilistic linear expressions. These last were studied by Henri Gilbert and A. Tardy-Cordfir within the framework of an attack on FERROALUMINIUM.

The linear cryptanalyse is more effective than the Cryptanalyse differential but less practical for the simple one and good reason which one leaves the principle that the attacker does not lay out of the block box symbolizing the encryption algorithm and that it cannot subject his own texts. In the case of, this attack required in the beginning $2^\; \{47\}$ couples (all quantified with the same key) that the attacker could recover by a means or another. Thereafter, Matsui improves its algorithm in 1994 and proposes a solution with $2^\; \{43\}$ couples. Complexity with a good implementation is however lower and about $2^\; \{39\}$ operations DES.

The linear cryptanalyse consists in making a linear approximation of the encryption algorithm by simplifying it. By increasing the number of couples available, one improves the precision of the approximation and one can extract the key from it. All the new encryption algorithms must take care to be resistant to this type of attack. Was not conceived to prevent this kind of method, the tables of substitution (S-Box be) present indeed certain linear properties whereas they were precisely designed to add a non-linearity to DES.

It was applied thereafter successfully to several algorithms like LOKI, FERROALUMINIUM or a simplified version of Serpent. The more recent algorithms like AES, IDEA and well of others still are insensitive to a linear attack. The complexity of the attack is in these cases largely higher than that of a exhaustive research.

Linear equations and substitutions

That is to say for example a table of substitution with 8 elements, the function S is the function substitution . By carrying out S ( X ), one carries out the first substitution to obtain Y . At the time of the deciphering, one will apply the opposite operation, i.e. S (Y) =S (S ( X ))=X.

Such a table is non-linear but the combination of several substitutions and operations can cancel non-linearity partly; it is the fault sought by the linear cryptanalyse. The linear term refers in fact with an expression of the following form (with $\backslash \; oplus$ the binary operation XOR):

$X\_1\; \backslash \; oplus\; X\_2\; \backslash \; oplus\; X\_3\; \backslash \; oplus\; \backslash \; ldots\; \backslash \; oplus\; X\_N\; =\; Y\_1\; \backslash \; oplus\; Y\_2\; \backslash \; oplus\; Y\_3\; \backslash \; oplus\; \backslash \; ldots\; \backslash \; oplus\; Y\_N$

The vector X is the entry and Y the exit of the function which one tries to approach with this Boolean equation. The variable $X\_i$ corresponds to the value of the I ^ème bit of X.

This expression is equivalent to:

$X\_1\; \backslash oplus\; X\_2\; \backslash oplus\; X\_3\; \backslash oplus\; \backslash ldots\; \backslash oplus\; X\_N\; \backslash oplus\; Y\_1\; \backslash oplus\; Y\_2\; \backslash oplus\; Y\_3\; \backslash oplus\; \backslash ldots\; \backslash oplus\; Y\_N=\; 0$

Example of equations

The linear cryptanalyse aims at allotting probabilities to the possible equations. For example, let us consider the two following equations:

1. $X\_1\; \backslash \; oplus\; X\_2\; \backslash \; oplus\; X\_3\; =\; Y\_1\; \backslash \; oplus\; Y\_2$

2. $X\_2\; \backslash \; oplus\; X\_3\; =\; Y\_3$

One now applies these equations to our table of substitution of the preceding section.

First equation

Second equation

Results

It is seen that the first equation is satisfied 4 times out of 8 whereas the equation (2) is to it only 2 out of 8. The equation (1) is thus a better approximation of substitution but it is not inevitably the best, a calculation on all the possible equations makes it possible to answer this question.

One repeats this type of estimate on various portions of the encryption algorithm, this stage varies according to his architecture. Thanks to these approximations, one tries to find portions of the intermediate keys (the subkeys ).

Example

Now let us consider a very simple encryption algorithm which takes 3 bits in entry and provides 3 quantified bits in exit.

Notation

That is to say $P~$ the data in light of 3 bits. That is to say $C~$, the end result and quantified of 3 bits. That is to say four intermediate keys $K\_1,\; K\_2,\; K\_3,\; K\_4~$ drawn from the principal key and used for the three training courses intermediary and the final XOR. That is to say $S\_i\; (X)\; ~$, the function " substitution" with the table of substitution n° I . That is to say $K\_\; \{I,\; J\}\; ~$ the notation for the bit J of the key I . The three tables are similar to that described before.

Coding

The procedure of coding is carried out as follows:

1. $A\_1\; =\; K\_1\; \backslash \; oplus\; P$

2. $B\_1\; =\; S\_1\; (A\_1)\; ~$
3. $A\_2\; =\; K\_2\; \backslash \; oplus\; B\_1$
4. $B\_2\; =\; S\_2\; (A\_2)\; ~$
5. $A\_3\; =\; K\_3\; \backslash \; oplus\; B\_2$
6. $B\_3\; =\; S\_3\; (A\_3)\; ~$
7. $C\; =\; K\_4\; \backslash \; oplus\; B\_3$

In short, one applies a XOR with an intermediate key, one substitutes with a different table each time and one starts again.

Creation of the linear approximation

One now considers two following linear approximations for the first two tables of substitution. :

• $S\_1\; :\; X\_1\; \backslash \; oplus\; X\_2\; \backslash \; oplus\; X\_3\; =\; Y\_2$

• $S\_2:\; X\_2\; =\; Y\_1\; \backslash \; oplus\; Y\_3$

We agree, for this example, that the first table has a probability of 3/4 and the second a probability of 2/7. These linear equations can now be built-in the procedure of coding.

First stage of coding

In the beginning, we have

$B\_1\; =\; S\_1\; (A\_1)\; ~$

With the approximation on the first S₁ substitution, one can write:

$B\_\; \{1,2\}\; =\; A\_\; \{1,1\}\; \backslash \; oplus\; A\_\; \{1,2\}\; \backslash \; oplus\; A\_\; \{1,3\}$

However $A\_1~$ is equivalent to $K\_1\; \backslash \; oplus\; P$, we thus replace $A\_1~$:

$B\_\; \{1,2\}\; =\; (K\_\; \{1,1\}\; \backslash \; oplus\; P\_\; \{1,1\})\; \backslash \; oplus\; (K\_\; \{1,2\}\; \backslash \; oplus\; P\_\; \{1,2\})\; \backslash \; oplus\; (K\_\; \{1,3\}\; \backslash \; oplus\; P\_\; \{1,3\})$

Second phase of coding

The following stage in coding consists in making a XOR between B₁ and the K₂ key. We directly integrate this result with the last equation obtained at the preceding stage

$A\_\; \{2,2\}\; =\; B\_\; \{1,2\}\; \backslash \; oplus\; K\_\; \{2,2\}$

$A\_\; \{2,2\}\; =\; \backslash \; Big\; ((K\_\; \{1,1\}\; \backslash \; oplus\; P\_\; \{1,1\})\; \backslash \; oplus\; (K\_\; \{1,2\}\; \backslash \; oplus\; P\_\; \{1,2\})\; \backslash \; oplus\; (K\_\; \{1,3\}\; \backslash \; oplus\; P\_\; \{1,3\})\; \backslash \; Big)\; \backslash \; oplus\; K\_\; \{2,2\}$

Third stage of coding

This stage, we have the following linear equation:

$A\_\; \{2,2\}\; =\; \backslash \; Big\; ((K\_\; \{1,1\}\; \backslash \; oplus\; P\_\; \{1,1\})\; \backslash \; oplus\; (K\_\; \{1,2\}\; \backslash \; oplus\; P\_\; \{1,2\})\; \backslash \; oplus\; (K\_\; \{1,3\}\; \backslash \; oplus\; P\_\; \{1,3\})\; \backslash \; Big)\; \backslash \; oplus\; K\_\; \{2,2\}$

We apply the 2nd substitution $S\_2\; now:\; X\_2\; =\; Y\_1\; \backslash \; oplus\; Y\_3$:

$A\_\; \{2,2\}\; =\; B\_\; \{2,1\}\; \backslash \; oplus\; B\_\; \{2,3\}$

In substituent:

$\backslash \; Big\; ((K\_\; \{1,1\}\; \backslash \; oplus\; P\_\; \{1,1\})\; \backslash \; oplus\; (K\_\; \{1,2\}\; \backslash \; oplus\; P\_\; \{1,2\})\; \backslash \; oplus\; (K\_\; \{1,3\}\; \backslash \; oplus\; P\_\; \{1,3\})\; \backslash \; Big)\; \backslash \; oplus\; K\_\; \{2,2\}\; =\; B\_\; \{2,1\}\; \backslash \; oplus\; B\_\; \{2,3\}$

Fourth stage

The exit of the preceding stage is now quantified with the key $K\_3~$ thus $A\_3\; =\; B\_2\; \backslash \; oplus\; K\_3$:

This gives finally:

$\backslash \; Big\; ((K\_\; \{1,1\}\; \backslash \; oplus\; P\_\; \{1,1\})\; \backslash \; oplus\; (K\_\; \{1,2\}\; \backslash \; oplus\; P\_\; \{1,2\})\; \backslash \; oplus\; (K\_\; \{1,3\}\; \backslash \; oplus\; P\_\; \{1,3\})\; \backslash \; Big)\; \backslash \; oplus\; K\_\; \{2,2\}\; =\; (A\_\; \{3,1\}\; \backslash \; oplus\; K\_\; \{3,1\})\; \backslash \; oplus\; (A\_\; \{3,3\}\; \backslash \; oplus\; K\_\; \{3,3\})$

We arrange this equation to gather the terms:

$(K\_\; \{1,1\}\; \backslash \; oplus\; K\_\; \{1,2\}\; \backslash \; oplus\; K\_\; \{1,3\}\; \backslash \; oplus\; K\_\; \{2,2\}\; \backslash \; oplus\; K\_\; \{3,1\}\; \backslash \; oplus\; K\_\; \{3,3\})\; \backslash \; oplus\; (P\_\; \{1,1\}\; \backslash \; oplus\; P\_\; \{1,2\}\; \backslash \; oplus\; P\_\; \{1,3\})\; \backslash \; oplus\; (A\_\; \{3,1\}\; \backslash \; oplus\; A\_\; \{3,3\})\; =\; 0$

In a more condensed way:

$\backslash \; Sigma\; K\; \backslash \; oplus\; (P\_\; \{1,1\}\; \backslash \; oplus\; P\_\; \{1,2\}\; \backslash \; oplus\; P\_\; \{1,3\})\; \backslash \; oplus\; (A\_\; \{3,1\}\; \backslash \; oplus\; A\_\; \{3,3\})\; =\; 0$

with $\backslash \; Sigma\; K\; =\; (K\_\; \{1,1\}\; \backslash \; oplus\; K\_\; \{1,2\}\; \backslash \; oplus\; K\_\; \{1,3\}\; \backslash \; oplus\; K\_\; \{2,2\}\; \backslash \; oplus\; K\_\; \{3,1\}\; \backslash \; oplus\; K\_\; \{3,3\})$

We now have a linear approximation which depends on:

• part of the three intermediate keys

• the plaintext
• part of the entry of the last table of substitution

By the application of the Lemme Piling-Up of Matsui and by fixing $\backslash \; Sigma\; K$ at 0 or 1, we can discover the probability that this equation is valid. We have two approximations of which we know the probabilities (thanks to the analysis of the boxes of substitution). With two approximations, N = 2:

$1/2\; +\; 2^\; \{n-1\}\; (1/2\; -\; 3/4)\; (1/2\; -\; 2/7)\; \backslash \; approx\; 0.607$

Our approximation has approximately 3 chances out of 5 to be valid. While trying to improve this probability, one refines the linear approximation and one recovers more and more information on the algorithm. For that, it is necessary to have a number of messages in light and their equivalents quantified. The effects of the once combined boxes of substitution being difficult to estimate, of the important data are capable to improve the model.

A crucial stage in the linear cryptanalyse is the recovery of the last key, that which buckles coding after a last substitution.

Recovery of the keys

We have under the hand an approximation of the 3 first turns of our encryption algorithm but it misses the key of the last turn, that is to say $K\_4~$ in our case. It is here that the coded messages at our disposal intervene. We take a message and try to decipher it by testing all the possible keys $K\_4~$. One is interested more particularly in the results at the end of coding. More precisely, we take a coded message $C~$ and carry out a XOR with the last key $K\_4~$: $C\; \backslash oplus\; K\_4$. That corresponds to the exit of the last table of substitution. We carry out now opposite substitution, the table being known: $S\_3^\; \{-\; 1\}\; (C\; \backslash \; oplus\; K\_4)$.

However this value corresponds in fact to the member of left of our linear equation. We have as follows: $S\_3^\; \{-\; 1\}\; (C\; \backslash \; oplus\; K\_4)\; =\; A\_3$. One can thus have an estimate of the validity of the keys tested by comparing the exact value turned over by opposite substitution and our linear approximation on all or part of the bits. With a great number of pairs of messages, one can make more precise the estimates. To discover the other intermediate keys, one attacks the algorithm while going up gradually in the turns until arriving at the first key.

On more complex codings like, one is not interested that in part of the under-keys in order to decrease the complexity of the attack. A more thorough study makes it possible to determine which bits of the last under-key have really an influence on the linear approximation. In its example with one OF 8 turns, Matsui indicates that, in spite of the presence of the last key (of 48 bits) in the equation, only 6 bits of this last key influence the term where it appears.

Several other techniques were developed to improve the performances of this cryptanalyse.

References and bonds

See too

• Cryptanalyse differential
• Attack Boomerang
• Cryptanalyse χ ²

References

• Mr. Matsui. Linear cryptanalysis method for OF the cipher . Proc. Eurocrypt '93, volume 765 off LNCS, pages 386--397. Springer, 1993.

External bonds

• Version scannée of the paper of Matsui
• a list of the papers devoted to the linear cryptanalyse

• Thesis of Pascal Junod on the linear cryptanalyse and a fast implementation for

• " How far edge we go beyond linear cryptanalysis" , Pascal Junod, Thomas Baignères and Serge Vaudenay
• " One Matsui' S linear cryptanalysis" , attack by Eli Biham

analyzes

Random links:

Thorius | Holy-Gem-in-Sancerrois | Charter of freedoms | Sangu | Automobile Grand Prix of Germany 1966 | Pédé_comme_gens_(série_télévisée_BRITANNIQUE)

© 2007-2008 speedlook.com; article text available under the terms of GFDL, from fr.wikipedia.org