Antonio Flórez

Gutiérrez Supervised

María Naya-Plasencia

Improving the key recovery in Linear Cryptanalysis: An application to PRESENT M2

Linear cryptanalysis is widely known as one of the fundamental tools for the crypanalysis of block ciphers. Over the decades following its first introduction by Matsui in [Ma94a], many different extensions and improvements have been proposed. One of them is [CSQ07], where Collard et al. use the Fast Fourier Transform (FFT) to accelerate the parity computations which are required to perform a linear key recovery attack. Modified versions of this technique have been introduced in order to adapt it to the requirements of several dedicated linear attacks. This work provides a model which extends and improves these different contributions and allows for a general expression of the time and memory complexities that are achieved. The potential of this general approach will then be illustrated with new linear attacks on reduced-round PRESENT, which is a very popular and widely studied lightweight cryptography standard. In particular, we show an attack on 26 or 27-round PRESENT-80 which has better time and data complexity than any previously known attacks, as well as the first attack on 28-round PRESENT-128.

Introduction

Background and motivation. The constant cryptanalysis effort on symmetric primitives is one of the fundamental arguments which support the security of secret key cryptography: an algorithm is considered secure if a long-enough analysis by the community has not led to the discovery of any significant flaws. For this reason, a toolbox of known cryptanalysis techniques must exist, as this allows the security of new cryptographic candidates to be tested against previous attacks. Furthermore, a good understanding of the nature of the flaws in the design of broken primitives can help designers create new ciphers whose resistance to these attacks is optimal. The effect that the introduction of quantum computers might have on this system is unknown: there are many questions about quantum symmetric cryptanalysis which either remain unresolved or have not even been studied in detail. It is known that in order to keep the same level of security in a post-quantum setting, the length of the private key must be doubled to deal with the speedup of the brute-force attack due to Grover's algorithm. However, little is known about non-generic attacks in a quantum setting. One potential avenue for development in this area is studying how quantum computing can improve the performance of classical attacks, such as differential or linear cryptanalysis. This was already studied in [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF], though several open problems are still unresolved.

Research problem. Linear cryptanalysis was first introduced by Matsui in 1994 ( [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF]), and soon joined differential cryptanalysis as one of the two essential tools in the cryptanalysis of symmetric primitives. In 2008, Collard et al. ([CSQ07]) introduced a new algorithmic technique which uses the Fast Fourier Transform to greatly reduce the time complexity of some linear attacks based on Matsui's Algorithm 2. The aim of this internship, which took place in the context of the ERC project QUASYModo at Inria Paris, was to attempt to answer two questions. In the first place, we wanted to know whether the approach of Collard et al. could be improved and/or generalized in the classical setting. The second question asks whether these FFT-based linear attacks could have improved performance in the quantum setting, and, if so, to which extent.

Contribution. Due to the limited duration of the internship and the amount of findings about the classical setting, almost all of the duration was spent researching the first question. During my internship the approach of [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF] could be transformed into a more general version for multiple rounds of key recovery. Despite several publications ( [START_REF] Nguyen | Improving the Algorithm 2 in Multidimensional Linear Cryptanalysis[END_REF], [START_REF] Zheng | FFT-based Multidimensional Linear Attack on PRESENT using the 2-bit-Fixed Characteristic[END_REF], [START_REF] Bogdanov | Multivariate Profiling of Hulls for Linear Cryptanalysis[END_REF]) mentioning extended versions of the algorithm, it seems that a generalised algorithm has never been fully described in the literature. I have also started to work on an analysis of how the structure of the individual cipher might be exploited (such as the key dependencies induced by the key schedule, for example). These theoretical findings led to some new attacks on the popular ISO-standard lightweight construction PRESENT which are only possible due to the new algorithm. These include the first cryptanalysis of the 28-round, 128-bit key variant of the cipher.

Future directions in research. In the short term, we would like to complete some parts of our generalised algorithm: in particular, we feel that there is a lot of room for improvement in our analysis of the use of dependencies between the key bits. It is also possible that we attempt to improve our time complexity estimates for the attacks on PRESENT by using Bogdanov et al.'s multivariate profiling technique ( [START_REF] Bogdanov | Multivariate Profiling of Hulls for Linear Cryptanalysis[END_REF]), which would lighten the theoretical assumptions. Another obvious avenue for continuing the research is attempting to answer question 2. We are also interested on the possible quantum speedup of Fast Correlation Attacks on stream ciphers, as they share similarities with linear cryptanalysis of block ciphers and can also be accelerated using the FFT.

Structure of this document. The present report is organised as follows: Section 2 offers a condensed overview of the development of the theory of linear cryptanalysis, with an emphasis on some of the prerequisites for our attacks on PRESENT. This section is complemented by appendix B, which contains further detail on some topics, as well as the proofs of the results. Section 3 deals with the FFT version of Matsui's Algortithm 2. Subsection 3.1 describes the original 1 INTRODUCTION improved attack that was described in [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF]. Subsection 3.2 is our first contribution, and provides a description of a generalised version of the algorithm which can be applied to the key recovery over multiple rounds. Subsection 3.3 discusses the possibility of using the key schedule of the attacked cipher to reduce the time complexity of key-recovery linear attacks using the FFT. Section 4 is devoted to PRESENT and our attacks on reduced-round variants. It includes a brief description of the cipher, a thorough rundown of the design of our two attacks (from the choice of the linear distinguisher to the key recovery algorithm) and a short discussion about the experimental verification of our time complexity claims. Appendix A contains the notations that are used throughout the report, some of which are nonstandard. It also includes some short introductions to a few mathematical concepts, such as the correlation of boolean functions and the Walsh-Hadamard Transform.

Observations and acknowledgements. This report is presented in English due to my limited command of the French language, and would like to apologise for any inconvenience to the reader. I would wish to thank the Fondation Mathématique Jacques Hadamard and its staff, whose Sophie Germain scholarship allowed me to study the M2 Algèbre Appliquée at the UVSQ, as well as Ana José Reguera López and Olivier Piltant for helping me find and apply for this scholarship. I also want to acknowledge all the professors at the University of Valladolid and UVSQ who have allowed me to reach this point with their unconditional support. My utmost gratitude is with María Naya-Plasencia for her constant assistance while supervising this internship, and the whole SECRET team at Inria Paris for making me feel right at home.

Some generalities on block ciphers

Throughout the report, we will use some general concepts about symmetric cryptology.

Definition 1.1. A block cipher of length n and key length κ is a map E : F n 2 × F κ 2 -→ F n 2 for which E K = E(•, K) is bijective for any fixed secret key K ∈ F κ 2 . Given a plaintext x and a key K, we will say y = E K (x) is the associated ciphertext. For any fixed key K, the map E K is called the encryption map. Meanwhile, given a fixed key K there exists an inverse map E -1 K , which is called the decryption map. We also write E -1 (y, K) = E -1 K (y) as a slight abuse of notation. Definition 1.2. A block cipher E is said to be a key-alternating cipher if there exists a decomposition

E K = G K r • F • G K r-1 • . . . • F • G K 1 • F • G K 0 (1.1)
where F is a fixed bijective map called internal permutation and G K i (x) = x ⊕ K i is called the round subkey addition. The maps F • G K i are rounds. There is usually another subkey addition at the end. Each subkey K i ∈ F n 2 , i = 0, ..., r is obtained from the master key K by means of an extension map

F κ 2 -→ F n(r+1) 2
which is called the key schedule. Given a plaintext x and a key K, the key schedule is used to compute all the subkeys, and then the round function is applied on the plaintext r times. The intermediate results are usually called states.

A key recovery attack is an algorithm which allows a potential adversary to obtain the secret key K (or part of it) from a selection of pairs (x, y = E K (x)) (the data) with high probability. There are several kinds of attacks depending on how these pairs are generated: if any set of pairs can be used, the attack is said to be a known-plaintext attack. If the attack demands a set of pairs with a specific structure, then the attack is said to be a chosen-plaintext attack (if the adversary chooses the values of x) or even a chosen-ciphertext attack (if the adversary chooses the values of y). A known plaintext key recovery attack using one known plaintext-ciphertext pair is always possible: it suffices to test all possible values of K until one is found for which y = E K (x). This is called the generic attack, brute-force attack, or simply exhaustive search. This attack has a time complexity equivalent to 2 κ encryptions. The aim of cryptanalysts is finding attacks with lower time complexities.

An introduction to linear cryptanalysis

This section consists of an overview of the fundamental aspects of linear cryptanalysis and has the purpose of aiding the understanding of the rest of this report. It begins with an introduction to linear cryptanalysis which follows the approach introduced by Matsui in [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF], and then proceeds to more advanced techniques like linear hulls ( [START_REF] Nyberg | Linear Approximation of Block Ciphers[END_REF]) and the use of multiple linear approximations ( [START_REF] Biryukov | On Multiple Linear Approximations[END_REF]). Subsection 2.2.1 contains an introduction to correlation matrices and how to use them to estimate the linear potential of a linear hull as shown in [START_REF] Daemen | The Design of Rijndael[END_REF]. Subsection 2.4 describes a statistical model ([Se08], [START_REF] Blondeau | Joint Data and Key Distribution of the Linear Cryptanalysis Test Statistic and its Impact to Data Complexity Estimates of Multiple/Multidimensional Linear and Truncated Differential Attacks[END_REF]) which will allow us to estimate the time complexities of our attacks. These topics are developed in more detail in appendix B, which also includes proofs.

Matsui's linear cryptanalysis

Matsui and Yamaguchi introduced an early version of linear cryptanalysis in [START_REF] Matsui | A New Method for Known Plaintext Attack of FEAL Cipher[END_REF] for building an attack on the block cipher FEAL. The two fundamental algorithms used in linear cryptanalysis, Algorithms 1 and 2, were described in [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF]. Algorithm 2 permitted the first experimental attack on the widely-used Data Encryption Standard (DES) in [START_REF] Matsui | The First Experimental Cryptanalysis of the Data Encryption Standard[END_REF]. This subsection contains the essential results of these papers, as they constitute the foundation of linear cryptanalysis. Matsui's linear cryptanalysis is a known plaintext attack which exploits a statistical correlation between some bits of the plaintext, the ciphertext and the secret key of a block cipher. The first step of any linear attack is finding linear approximations of (part of) the cipher.

Definition 2.1. A linear approximation of the block cipher E is an expression of the form

ν : α • x ⊕ β • y ⊕ γ(K) (2.1)
The vectors α, β ∈ F n 2 are called input and output masks, while the map γ : F κ 2 -→ F 2 is often called the key mask. Matsui's attacks use a biased linear approximation, which means that, if the approximation is regarded as a random variable over the key and the plaintext, then the probability that it is equal to 0 is significantly different from 1/2.

ε = P r x,K (α • x ⊕ β • E K (x) ⊕ γ(K) = 0) -1/2 = 0 (2.2)
The quantity ε is called bias or imbalance. A related magnitude is the correlation

c = P r x,K (α • x ⊕ β • E K (x) ⊕ γ(K) = 0) -P r x,K (α • x ⊕ β • E K (x) ⊕ γ(K) = 1) = 0 (2.3)
These two values are linked by the relationship c = 2ε.

The attacker wants approximations with high bias/correlation (in absolute value), since they lead to a better data complexity. High-bias approximations can be found for each round of a key-alternating cipher by looking at the internal permutation F , which is usually a composition of other simpler maps. These one-round approximations can be combined to construct a composite approximation of the whole cipher whose correlation is given by the following result:

Corollary 2.2 (Piling-up lemma, lemma 3 in [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF]). Let us consider r linear approximations of the internal permutation F of a key-alternating cipher E,

α i • x ⊕ β i • F (x), i = 0, . . . , r -1 (2.4)
with bias ε i and correlation c i = 2ε i . We can deduce approximations of each round with the same bias:

α i • x ⊕ β i • F (x ⊕ K i ) ⊕ α i • K i
If we suppose that α i+1 = β i , then by addition, we obtain an approximation of E:

α 0 • x ⊕ β r-1 • E K (x) ⊕ α 0 • K 0 ⊕ . . . ⊕ α r-1 • K r-1 ⊕ β r-1 • K r (2.5)
If we assume the statistical independence of the binary variables, then its bias and correlation are

ε = 2 r-1 r-1 i=0 ε i , c = r-1 i=0 c i (2.6)
Matsui proposed two different key recovery attack algorithms which make use of a linear approximation. Algorithm 1 uses an approximation of the whole cipher to recover one bit of information about the key, while Algorithm 2 uses an approximation of r -1 rounds of the cipher to recover multiple bits.

Matsui's Algorithm 1

Suppose that the attacker has access to a collection

D = {(x, y = E K (x))} ⊂ F n 2 × F n 2
of N known plaintexts which have been encrypted with a fixed secret key K, and knows a linear approximation α • x ⊕ β • y ⊕ γ(K) with bias ε. If N is large enough to detect the bias ε (we will detail how large later), then the following algorithm recovers the value of γ(K):

Algorithm 1: Matsui's Algorithm 1 Input: A collection D = {(x, y = E K (x))} of N plaintext-ciphertext pairs (possibly on-the-fly). Output: A probable value for γ(K). T ← 0; forall (x, y) ∈ D do // Compute the counter T if α • x ⊕ β • y = 0 then T ← T + 1; end switch (T, ε) do // Compare T and N/2 case T > N/2, ε > 0 do return 0 ; case T > N/2, ε < 0 do return 1 ; case T < N/2, ε > 0 do return 1 ; case T < N/2, ε < 0 do return 0 ; end
In other words, the attacker first computes the counter

T = # {(x, y) ∈ D : α • x ⊕ β • y = 0} (2.7)
which is expected to be approximately N/2 ± N ε, with the sign depending on the value of γ(K).

By comparing this number to N/2, this bit of information about the key can be obtained with high probability. The effectiveness of this algorithm depends on the following assumption:

Assumption 2.3. (Right-key equivalence hypothesis) The key K has no influence on the value of the probability p(K)

= P r x (α • x ⊕ β • E K (x) ⊕ γ(K) = 0 | K)
, where P r x (A | K) denotes the probability of the event A assuming that the plaintexts x are uniformly distributed and the key is fixed to K.

Under the right-key equivalence hypothesis, we can estimate the success probability (that is, the probability that the guess for γ(K) is correct) as a function of the number of known plaintexts N .

Proposition 2.4 (Lemma 2 in [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF]). The probability of success of Algorithm 1 is

P S Φ 2 √ N |ε| = Φ √ N c 2 = √ N c 2 -∞ 1 √ 2π e -x 2 2 dx (2.8)
This means that around N ∼ 1/4ε 2 = 1/c 2 known plaintexts are needed for the attack to succeed with reasonable probability. The attacker can recover more information about the key by using other approximations or by finding the rest of the key by exhaustive search.

Matsui's Algorithm 2

Matsui also proposed an improved attack which recovers a larger section of the key. The idea is to use a partial approximation of the cipher. If E K (x) = (F • E K )(x) ⊕ K r , then we suppose that the attacker knows an approximation α • x ⊕ β • ŷ ⊕ γ(K) with bias ε of the first r -1 rounds. We suppose that computing β • F -1 (y ⊕ K r ) from y only requires using a few bits k of K r , which can be extracted with the mask χ. For any vector x ∈ F n 2 , x| χ denotes the vector of length HW (χ) whose components are the coordinates of x which correspond to the non-zero entries of χ, so that k = K r | χ . We can substitute the term associated to the decryption of the last round for a map f :

F |k| 2 -→ F 2 : f (y| χ ⊕K r | χ ) = β • F -1 (y ⊕ K r ) for all y ∈ F n 2 , K r ∈ F n 2 (2.9)
Given N plaintext-ciphertext pairs, the partial subkey k can be retrieved as follows:

Algorithm 2: Matsui's Algorithm 2 Input: A collection D = {(x, y = E K (x))} of N plaintext-ciphertext

pairs (possibly on-the-fly).

Output: A probable guess for k.

T ← 0; forall (x, y) ∈ D do // Compute the counters T k for k ← 0 to 2 |k| -1 do if α • x ⊕ f (y| χ ⊕k) = 0 then T k ← T k + 1; end end return argmax k (|T k -N/2|); // Find the T k that's most different to N/2
The attacker guesses all the possible values of k and computes the counter

T k = # {(x, y) ∈ D : α • x ⊕ f (y| χ ⊕k) = 0} (2.10)
and then keeps the guess whose counter is farthest from N/2. This is based on the assumption Assumption 2.5. (Wrong-key randomisation hypothesis) For all the wrong guesses of k, the correlation of the linear approximation is approximately zero. That is, if k = k is a wrong guess,

P r x α • x ⊕ f (y| χ ⊕ k) = 0 1/2 (2.11)
We also assume that α • x ⊕ f (y| χ ⊕ k) are independent variables for all the wrong key guesses.

This assumption seems reasonable, since decrypting the last round of the cipher with the wrong key should have a similar effect to adding an additional round of encryption when it comes to the correlation of the approximation. This leads to the result Corollary 2.6 (Lemma 4 in [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF]). The probability of success of Matsui's Algorithm 2 depends solely on the quantities |k| and 4N ε 2 = N c 2 .

It takes N 2 |k| one-round decryptions and 2 |k| memory registers of up to logN bits to compute the counters T k . The search phase of a full key-recovery attack is faster than in Algorithm 1, as we already know |k| bits of the key K. The time complexity of Matsui's Algorithm 2 is O N

2 |k| + O 2 κ-|k| .
In [START_REF] Matsui | The First Experimental Cryptanalysis of the Data Encryption Standard[END_REF], Matsui noted that since the only information about each (x, y) pair that is required is the values of α • x and y| χ , it is possible to first count the number of occurrences of each (α • x y| χ ) in the data and then compute T k using these. With this technique the attack takes N parity evaluations and 2 2|k| one-round decryptions, which reduces the complexity if 2 |k| < N , which happens very often.

Algorithm 3: Matsui's Algorithm 2, modified Input: A collection D = {(x, y = E K (x))} of N plaintext-ciphertext pairs (possibly on-the-fly).

Output: A probable guess for k. a 0 ← 0; a 1 ← 0; T ← 0; forall (x, y) ∈ D do a α•x y|χ ← a α•x y|χ + 1; // Extract the information from the data

for k ← 0 to 2 |k| -1, j ← 0 to 2 |k| -1 do // Compute the counters T k if f (j ⊕ k) = 0 then T k ← T k + a 0 j else T k ← T k + a 1 j ; end return argmax k (|T k -N/2|); // Find the T k that's most different to N/2
Algorithm 2 can also be used with an approximation over even less rounds of the cipher by skipping several rounds at the beginning and/or the end. The limitation is that the number |k| of involved subkey bits increases with the number of "outer" rounds.

When compared with Algorithm 1, Algorithm 2 has several advantages. Since it uses an approximation over a smaller number of rounds of the cipher, its correlation should be larger, and the data complexity is smaller than for Algorithm 1. Furthermore, recovering more bits of information about the key reduces the time cost of the final exhaustive search. Finally, we will be show in the next subsection that Algorithm 2 can still be used when the right-key equivalence hypothesis is not satisfied. For these reasons, nearly all linear attacks in the literature are variations of Algorithm 2.

Linear trails and linear hulls

The right-key equivalence hypothesis (assumption 2.3) is reasonable as long as all linear approximations which share the same input and output masks α, β but differ in the key mask γ have a much smaller correlation. This is not true in the case of many modern ciphers. This possibility was first considered by Nyberg in [START_REF] Nyberg | Linear Approximation of Block Ciphers[END_REF]. If the right-key equivalence hypothesis is not satisfied, then the value of α • x ⊕ β • E K (x) is influenced by several different γ(K), and Algorithm 1 cannot distinguish between them. In the case of Algorithm 2, however, the probability of success can increase if there are multiple biased linear approximations sharing the same input and output masks. This is substantiated by the following theorem, which applies to ciphers with a simplified key schedule.

Theorem 2.7 (Theorem 1 in [START_REF] Nyberg | Linear Approximation of Block Ciphers[END_REF]). Let ν : α • x ⊕β • y be a linear approximation of a key-alternating block cipher E for which all the subkeys are independent from each other (so κ = n(r + 1)). Then

1 2 n(r+1) K∈F κ 2 P r x (α • x ⊕ β • E K (x) = 0|K) - 1 2 2 = γ0,...,γr∈F n 2 P r x,K (α • x ⊕ β • E K (x) ⊕ γ 0 • K 0 ⊕ . . . ⊕ γ r • K r = 0) - 1 2 2 (2.12)
Let us now consider what this means for the probability of success of Matsui's Algorithm 2. The value of p(K)

= P r x (α • x ⊕ β • E K (x) = 0|K
) varies over the keyspace, so the attack will succeed with a higher probability for some keys (which we'll call weak keys), and with a lower probability for others. We know that the probability of success for the key K depends on 4N (p(K) -1/2) 2 , and the previous theorem gives us the expected value of this magnitude over the keyspace. This result usually provides reasonable predictions even when the hypothesis about the key schedule is not satisfied.

Definition 2.8. Let ν : α • x ⊕ β • y be a linear approximation of a key-alternating block cipher E. A linear trail is any linear approximation of the cipher of the form

ν γ γ γ : α • x ⊕ β • y ⊕ γ 0 • K 0 ⊕ . . . ⊕ γ r • K r , γ γ γ = (γ 0 = α, . . . , γ r = β) ∈ (F n 2 ) (r+1) (2.13)
The set of all the linear trails of the approximation is called the approximate linear hull, ALH(α, β).

The probability of success of an Algorithm 2 attack using the approximation ν depends on the value N • ELP (α, β), where ELP (α, β) is the estimated linear potential of the linear hull

ELP (α, β) = γ γ γ∈F n(r+1) 2
γ0=α,γr=β (P r x,K0,...,Kr (ν γ γ γ = 0) -P r x,K0,...,Kr (ν γ γ γ = 1))

2

(2.14)

Computing the ELP with orrelation matrices

The aim of this subsection is to illustrate an efficient way of estimating the ELP of linear approximations whose input and output masks have low Hamming weight by using correlation matrices. This is the technique that will be used to compute the capacity of our linear distinguishers for the PRESENT block cipher in section 4. We begin by defining the correlation matrix of a boolean function:

Definition 2.9. Let f : F n 2 -→ F n 2 be a boolean function. Its correlation matrix C (f ) ∈ R 2 n ×2 n is defined as the matrix whose entries are the correlations of all possible linear approximations of f :

C (f ) ij = 1 2 n (# {x ∈ F n 2 : i • x ⊕ j • f (x) = 0} -# {x ∈ F n 2 : i • x ⊕ j • f (x) = 1}) , 0 ≤ i, j < 2 n (2.15)
Another common way of expressing the correlation of all the linear approximations of a boolean function is the linear approximation table or LAT, whose entries are

# {x ∈ F n 2 : i • x ⊕ j • f (x) = 0} -2 n-1 .
In many block ciphers the inner permutation is the composition of a linear map and the parallel application of several smaller non-linear maps called S-boxes on parts of the state. In this case the linear approximation tables or the correlation matrices of the S-boxes can be used to construct the correlation matrix of the whole round function using a variant of the piling-up lemma. Given an approximation of the round function, it decomposes into a sum of approximations of some S-boxes. These are often called active S-boxes of the approximation. This notion extends to linear trails, as all linear trails have a unique decomposition as approximations of each round.

The following result is deduced from the piling-up lemma and the definition of the ELP :

Theorem 2.10. Let E be a key-alternating cipher of r rounds with internal permutation F , and let Ĉ(F ) be the element-wise square of the correlation matrix of the round function. Then the ELP of a linear approximation of E with input mask α and output mask β is

ELP (α, β) = Ĉ(F ) r αβ (2.16)
In most practical ciphers n is too large to construct the correlation matrix of the round function in full, but in many cases a good estimation of the ELP can still be obtained by considering a submatrix of C (F ) containing a carefully picked selection of masks, such as those with a bound Hamming weight or those which lead to a limited amount of active S-boxes in the previous and the next rounds. This limits the amount of linear trails which are considered to those whose intermediate masks belong to the selected family. If all other linear trails have a very small correlation (in other words, if the submatrix of C (F ) is chosen well enough), then the obtained estimation of the ELP can be very accurate.

Multiple linear cryptanalysis

Linear cryptanalysis can also be extended by using more than one linear approximation. This possibility was first discussed by Kaliski and Robshaw in [START_REF] Kaliski | Linear Cryptanalysis Using Multiple Approximations[END_REF], where the information obtained from several linear approximations using a single key mask γ but different input and output masks α i , β i was combined by the attacker to achieve a better success probability. An approach allowing for the use of any set of linear approximations was introduced by Biryukov et al. in [START_REF] Biryukov | On Multiple Linear Approximations[END_REF], and is commonly referred to as multiple linear cryptanalysis. However, the analysis of the probability of success relies on the assumption that all the approximations are statistically independent, and this is not always the case.

For this reason, Hermelin et al. proposed multidimensional linear cryptanalysis in [START_REF] Hermelin | Multidimensional Linear Cryptanalysis of Reduced Round Serpent[END_REF] and [START_REF] Hermelin | Multidimensional Extension of Matsui's Algorithm 2[END_REF]. Multidimensional linear cryptanalysis uses linear approximations whose input and output masks constitute a linear subspace of F n 2 × F n 2 , which means that the estimation of the probability of success takes into account the joint distribution of all these approximations and doesn't require the assumption of statistical independence. Multidimensional attacks are covered in appendix B. We will now describe a simple multiple version of Matsui's Algorithm 2. Let ν i be M linear approximations of the r -1 first rounds of the cipher,

ν i : α i • x ⊕ β i • ŷ, i = 1, . . . , M
(2.17)

We suppose that β i • F -1 (y ⊕ K r ) can be replaced by f i (y| χ ⊕k) for each approximation as in the simple version of Algorithm 2. Then an attack using N known plaintext-ciphertext pairs (x, y) can be performed as follows:

Algorithm 4: Multiple version of Matsui's Algorithm 2 Input: A collection D = {(x, y = E K (x))} of N plaintext-ciphertext

pairs (possibly on-the-fly).

Output: A probable guess for k. for i ← 1 to M do q i ← 0; forall (x, y) ∈ D do // Compute the counters q i k for all keys and approximations

for i ← 1 to M, k ← 0 to 2 |k| -1 do if α i • x ⊕ f i (y| χ ⊕k) = 0 then q i k ← q i k + 1 else q i k ← q i k -1; end end for k ← 0 to 2 |k| -1 do Q k ← 1 N M i=1 (q i k ) 2 ; // Aggregate the information return argmax k (Q k ); // Find the largest value of Q k
For each guess of k, the attacker computes the empirical correlation for all the approximations:

q i k = # {(x, y) ∈ D : α i • x ⊕ f i (y| χ ⊕k) = 0} -# {(x, y) ∈ D : α i • x ⊕ f i (y| χ ⊕k) = 1} (2.18)
which are then aggregated into the multiple linear cryptanalysis statistic

Q k = 1 N M i=1 q i k 2 (2.19)
The guess with the largest associated value of Q k is probably correct. Under the assumption that all the linear approximations are statistically independent, the probability of success of the attack can be estimated using the notion of capacity of the set of approximations:

Proposition 2.11. The probability of success of a multiple linear attack using M statistically independent linear approximations depends on the number of available plaintexts N , the number of approximations M and the capacity of the set of linear approximations. If c i (K) is the correlation of the i-th approximation for the key K, then the capacity for the key K and the overall capacity are defined as

C(K) = M i=1 (c i (K)) 2 , C = Exp K (C(K)) = M i=1 (ELP (α i , β i )) 2 (2.20)

Estimating the probability of success

Another "branch" in the theory of linear cryptanalysis which has been developed in the last few decades deals with the analysis of the probabilistic behaviour of linear approximations and how it can be used to better estimate the probability of success of a linear attack.

In an attack based on Matsui's Algorithm 2, it is possible to keep more than one key candidate: for example, we can keep a fixed number of the highest ranked key candidates, or all candidates which surpass a certain correlation threshold. This increases the probability of success of the attack. Selçuk introduced the notion of advantage ( [START_REF] Selçuk | On Probability of Success in Linear and Differential Cryptanalysis[END_REF]) in order to measure the effectiveness of this type of attack:

Definition 2.12. An attack that ranks the partial key guesses k according to a statistic X k achieves an advantage of a bits if the right key ranks among the best 2 |k|-a key candidates. Given a desired advantage, the probability of success is the probability that the actual advantage surpasses the desired value. If an advantage of a bits is achieved, then the time complexity of the exhaustive search phase of the attack is 2 κ-a full encryptions.

The probability of success given a target advantage can be computed using the following result: [START_REF] Selçuk | On Probability of Success in Linear and Differential Cryptanalysis[END_REF]). Supposing that the key-ranking statistic X k has the cumulative distribution function F R for the right key guess and F W for any wrong guess, then the success probability of the associated statistical attack for a given desired advantage a is

Theorem 2.13 ([
P S = 1 -F R F -1 W (1 -2 -a ) (2.21)
If the right-key distribution can be approximated by a normal distribution N (µ R , σ 2 R ), then

P S Φ µ R -F -1 W (1 -2 -a ) σ R (2.22)
For multiple linear cryptanalysis, the distributions of the test statistics which are required for the previous result can be approximated by the widely-accepted theorem from [BN17]:

Theorem 2.14 (Theorem 6 in [START_REF] Blondeau | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis[END_REF]). In a multiple linear attack using M linear approximations and N available plaintexts, the right-key statistic Q k approximately follows a normal distribution:

Q k ∼ N (µ R , σ R ), where µ R = Exp D,K (Q k ) = BM + N Exp K (C(K)) σ 2 R = V ar D,K (Q k ) = 2B 2 M + 4BN Exp K (C(K)) + N 2 V ar K (C(K)) B = 1 if repeated plaintexts are allowed 2 n -N 2 n -1
if the plaintexts are all different (distinct known plaintext)

(2.23)

Exp K (C(K)) and V ar K (C(K)) can be estimated using a subset S of significant linear trails,

Exp K (C(K)) M i=1 γ∈S P r x, K (ν i ⊕ γ • K = 0) -P r x, K (ν i ⊕ γ • K = 1) 2 + M 2 -n (2.24) V ar K (C(K)) 2 M i=1   γ∈S P r x, K (ν i ⊕ γ • K = 0) -P r x, K (ν i ⊕ γ • K = 1) 2 + 2 -n   2 (2.25)
Meanwhile, if the key guess k = k is different from the right one, a multiple of the wrong key statistic follows a χ 2 distribution with M degrees of freedom:

1 B + N 2 -n Q k ∼ χ 2 M , so µ W = Exp D,K (Q k) = BM + N M 2 -n σ 2 W = V ar D,K (Q k) = 2M (B + N 2 -n ) 2
(2.26)

Matsui's Algorithm 2 using FFT

As was shown in the previous section, the naïve implementation of Matsui's Algorithm 2 requires N 2 |k| one-round decryptions in order to compute the test statistic for all possible guesses of the subkey. This number can be reduced to O(N ) + 2 2|k| if the attacker divides the statistical analysis into two phases and 2 |k| < N . Since we are only interested in some bits of information about each plaintext-ciphertext pair, we begin by counting the number of appearances of each possibility for these relevant bits. Then the calculations are only performed once for each one of these possibilities, and then the result is multiplied by the number of appearances that was stored in the first table. This is a recurring strategy in statistical attacks, which can often be divided into the following phases:

1. Distillation phase: The relevant information for the attack is extracted from the data by partitioning the space of plaintexts and ciphertexts and counting the number of occurrences of each category. This can be done on-the-fly, which means that each plaintext-ciphertext pair can be processed separately as it is received by the attacker without storing the whole collection.

2. Analysis phase: The information that was extracted during the analysis phase is manipulated in order to obtain one or more candidates for a part of the key K.

The original algorithm

In [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF] it was shown that the parity calculations for Matsui's Algorithm 2 can be performed more efficiently by using the FFT. This improved algorithm can be used when the cipher is of the form

E K (x) = (F • E K )(x) ⊕ K r
and the attacker uses one approximation of the form α • x ⊕ β • ŷ. As usual, we will suppose that the last round of the cipher can be truncated so that the partial decryption which obtains β • F -1 (y ⊕ K r ) from y only requires using a few bits of K r . The partial subkey guess will be denoted by k, and there are 2 |k| possibilities for this segment of the key. Let χ be the mask which extracts these relevant bits, so that k

= K r | χ . Let f (y| χ ⊕k) = β •F -1 (y ⊕K r )
denote the term of the approximation associated to the partial last round decryption. The attacker wants to compute the vector of experimental correlations whose entries are

q k = # {(x, y) ∈ D : α • x ⊕ f (y| χ ⊕k) = 0} -# {(x, y) ∈ D : α • x ⊕ f (y| χ ⊕k) = 1} (3.1)
with the aim of extracting the key candidate(s) with the largest value(s) of |q k |. The experimental correlation can be rewritten as a sum in the following manner:

q k = (x,y)∈D (-1) α•x⊕f (y|χ⊕k) = 2 |k| -1 j=0 (-1) f (j⊕k) (x,y)∈D y|χ=j (-1) α•x , 0 ≤ k ≤ 2 |k| -1 (3.2)
so that j represents the relevant |k| bits of the ciphertext. This suggests that the attack should begin by computing the integer vector a ∈ Z 2 |k| with coordinates

a j = (x,y)∈D y|χ=j (-1) α•x , 0 ≤ j ≤ 2 |k| -1 (3.3)
This constitutes the distillation phase of the algorithm of [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF]. We can also define the matrix

C ∈ Z 2 |k| ×2 |k| with entries c jk = (-1) f (j⊕k) , 0 ≤ j, k ≤ 2 |k| -1 (3.4)
The vector q = (q 0 , . . . , q 2 |k| -1 ) can thus be calculated as the matrix-vector product

q T = a T C (3.5)
However, the time complexity of constructing C and computing the matrix-vector product is still O 2 2|k| . The product can be computed in a much more efficient manner by making use of the following result on spectral analysis:

Proposition 3.1. Let f : F m 2 -→ F 2 be a boolean function. We consider a matrix of 1s and -1s C ∈ Z 2 m ×2 m whose entries are of the form

c ij = (-1) f (i⊕j) , 0 ≤ i, j ≤ 2 m -1 (3.6)
This matrix diagonalizes as

2 m C = H 2 m ∆H 2 m (3.7)
where H 2 m is the Walsh-Hadamard matrix of size 2 m whose entries are h ij = (-1) i•j , and

∆ = diag(λ λ λ), λ λ λ ∈ Z 2 m is a diagonal matrix.
The eigenvalue vector λ λ λ is the matrix-vector product H 2 m C •1 , where C •1 denotes the first column of C.

Proof. We will show that the columns of the Walsh-Hadamard matrix (often called Walsh functions) are eigenvectors of C. In the process we will also obtain an expression for the associated eigenvalues. Let h •j denote the j-th column of H 2 l . Its coordinates are therefore (h •j ) i = h ij = (-1) i•j . The i-th component of the matrix-vector product Ch •j is equal to:

2 m -1 k=0 c ik h kj = 2 m -1 k=0 (-1) f (i⊕k) (-1) k•j = 2 m -1 k=0 (-1) f (i⊕k)⊕k•j
Since the sum is taken over all the possible values of k, we can change the indices k ⊕ i for k to obtain

2 m -1 k=0 (-1) f (k)⊕(k⊕i)•j = 2 m -1 k=0 (-1) f (k)⊕k•j⊕i•j = 2 m -1 k=0 (-1) f (k)⊕k•j (-1) i•j ,
which is a multiple of the i-th component of h •j . The associated eigenvalue is

λ j = 2 m -1 k=0 (-1) k•j (-1) f (k) ,
which is indeed the j-th component of the product of H 2 m and the first column of C.

The matrix-vector product a T C can then be further decomposed into:

2 |k| q T = a T H 2 |k| diag(H 2 |k| C •1 )H 2 |k| (3.8)
The cost of computing q is now three products of the form H 2 |k| v, which can in turn be evaluated efficiently with the Fast Walsh-Hadamard transform (see appendix A) with |k|2 |k| additions/substractions. The decomposition of C justifies the following algorithm:

1. Distillation phase: Construct a list of zeros a of length 2 |k| . For each plaintext-ciphertext pair (x, y), calculate α • x. If it is equal to zero (resp. one), then increment (resp. decrement) the entry of a corresponding to the |k| relevant bits of y| χ by one.

The time complexity of this phase is ρ D N ,where ρ D is the cost (in binary operations) of evaluating α • x and y| χ and incrementing one of the counters.

2. Analysis phase: Compute the vector q of experimental correlations:

(a) Compute the first column of C, and apply the Fast Walsh-Hadamard Transform to obtain λ λ λ, the vector containing the eigenvalues of C.

(b) Apply the Fast Walsh-Hadamard transform to a.

(c) Multiply the previous vector by λ λ λ elementwise.

(d) Apply the Fast Walsh-Hadamard transform to the resulting vector to find 2 |k| q.

Select the subkey guesses k with the largest values for |q k |.

The time complexity of this phase is

ρ f 2 |k| + 3ρ A |k|2 |k| + ρ M 2 |k| + ρ C 2 |k| .
The constant ρ f denotes the cost in binary operations of evaluating f (j), and ρ A , ρ M , ρ C denote the cost of adding, multiplying and comparing two integers whose length is bound by n.

3. Search phase: For each of the remaining candidate guesses, try all the possibilities for the remainder of the key until either the complete key K is found or all the candidates have been tested without success.

The time complexity of this phase is ρ E 2 κ-a , where ρ E is the cost of one encryption with E and a is the achieved advantage of the attack.

Proposition 3.2. The previous algorithm for a key recovery linear attack using a linear approximation between the first and penultimate rounds of a block cipher has a time complexity

ρ D N distillation phase + 3ρ A |k|2 |k| + (ρ f + ρ M + ρ C )2 |k| analysis phase + ρ E 2 κ-a search phase (3.9)
The memory requirement is 2 • 2 |k| n bits.

Algorithm 5: The algorithm of [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF] (without the final phase)

Input: A collection D = {(x, y = E K (x))} of N plaintext-ciphertext

pairs (possibly on-the-fly).

Output: The experimental correlations q k (multiplied by a constant factor).

// DISTILLATION PHASE a ← 0; forall (x, y) ∈ D do if α • x = 0 then a y|χ ← a y|χ + 1 else a y|χ ← a y|χ -1; end // ANALYSIS PHASE for j ← 0 to 2 |k| -1 do λ j ← f (j); // Compute the first column of C λ λ λ ← FWHT(λ λ λ); // Compute the eigenvalues of C a ← FWHT(a);
// Apply the FWHT to a for j ← 0 to 2 |k| -1 do a j ← a j • λ j ;

// Multiply a by λ λ λ elementwise q ← FWHT(a);

// Apply the FWHT to a return q;

The extended algorithm

After the publication of [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF], several linear attacks have made use of this FFT technique. Although it was originally only described for the case in which the adversary only wants to guess bits of the last round subkey, it is possible to apply the same approach in broader scenarios, as showcased in [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF], [START_REF] Nguyen | Improving the Algorithm 2 in Multidimensional Linear Cryptanalysis[END_REF], [START_REF] Zheng | FFT-based Multidimensional Linear Attack on PRESENT using the 2-bit-Fixed Characteristic[END_REF], and [START_REF] Bogdanov | Multivariate Profiling of Hulls for Linear Cryptanalysis[END_REF]. The main original result of this internship is the description of an algorithm which allows for an efficient partial key recovery on an arbitrary number of rounds at both the beginning and the end of the cipher, as well as a generic analysis of the time complexity. Consider a block cipher E of block size n and key size κ which can be decomposed as in figure 2. The outer ciphers E 1 and E 2 represent the first and last few rounds of E. These ciphers take some inner keys K 1 ∈ F κ1 2 and K 2 ∈ F κ2 2 as input. In a key-alternating cipher, these inner keys correspond to the round subkeys involved in the key recovery attack, excluding the first and the last. The first and last round subkeys correspond to the outer keys K 0 and K 3 , and will be treated separately. We will suppose that the inner cipher E M has a linear linear approximation of the form

ν : α • x ⊕ β • ŷ (3.10)
As with the previous algorithms, we assume that the values of α

• E 1 (x ⊕ K 0 , K 1 ) (resp. β • E -1 2 (y ⊕ K 3 , K 2 )
) can be obtained from a part of x (resp. y) by guessing some bits of the keys K 0 and K 1 (resp. K 3 and K 2 ). We will denote the necessary part of the plaintext by i (resp. ciphertext, j), while the guessed parts of the subkeys will be denoted by k 0 , k 1 (resp. k 3 , k 2 ). We can consider masks

y E2 ŷ EM x E1 x K0 K1 KM K2 K3 Key Schedule K Figure 2:
The general description of the cipher.

3 MATSUI'S ALGORITHM 2 USING FFT χ 0 , χ 1 , χ 2 , χ 3 , so that i = x| χ0 , k 0 = K 0 | χ0 , k 1 = K 1 | χ1 , k 2 = K 2 | χ2 , y = y| χ3 , k 3 = K 3 | χ3 (3.11) Let f 1 : F 2 |k 0 | 2 × F 2 |k 1 | 2 -→ F 2 and f 2 : F 2 |k 3 | 2 × F 2 |k 2 | 2 -→ F 2 denote the maps verifying f 1 (x| χ0 ⊕K 0 | χ0 , K 1 | χ1 ) = α • E 1 (x ⊕ K 0 , K 1 ) for all possible x, K 0 , K 1 (3.12) f 2 (y| χ3 ⊕K 3 | χ3 , K 2 | χ2 ) = β • E -1 2 (y ⊕ K 3 , K 2 ) for all possible y, K 3 , K 2 (3.13)
The attacker is given a set D of N plaintext-ciphertext pairs (x, y = E K (x)) which have been encrypted with a fixed key K. In order to perform a linear key recovery attack, the adversary needs to compute the experimental correlation for each possible guess of the subkeys:

q(k 0 , k 1 , k 2 , k 3 ) = # {(x, y) ∈ D : f 1 (i ⊕ k 0 , k 1 ) ⊕ f 2 (j ⊕ k 3 , k 2 ) = 0} -# {(x, y) ∈ D : f 1 (i ⊕ k 0 , k 1 ) ⊕ f 2 (j ⊕ k 3 , k 2 ) = 1} , (k 0 , k 1 , k 2 , k 3 ) ∈ F |k0| 2 × F |k1| 2 × F |k2| 2 × F |k3| 2 (3.14)
The attack begins with a modified distillation phase which is inspired by the work of Nguyen et al. in [START_REF] Nguyen | Improving the Algorithm 2 in Multidimensional Linear Cryptanalysis[END_REF]. A matrix A ∈ Z 2 |k 0 | ×2 |k 3 | , whose entries a ij are the number of plaintext-ciphertext pairs for which the relevant bits are i and j, respectively, is constructed.

a ij = # {(x, y) ∈ D : x| χ0 = i, y| χ3 = j} , 0 ≤ i ≤ 2 |k0| -1, 0 ≤ j ≤ 2 |k3| -1 (3.15)
We can thus rewrite the experimental correlation for any key guess as the following sum:

q(k 0 , k 1 , k 2 , k 3 ) = 2 |k 0 | -1 i=0
2 |k 3 | -1 j=0 a ij (-1) f1(i⊕k0,k1) (-1) f2(j⊕k3,k2) (3.16)
Let us now consider that the values of 0 ≤ k 1 ≤ 2 |k1| -1 and 0 ≤ k 2 ≤ 2 |k2| -1 are fixed. All the associated experimental correlations (which now only depend on the choice of k 0 and k 3 ) form a matrix

Q k1,k2 ∈ Z 2 |k 0 | ×2 |k 3 | with entries q k1,k2 k0,k3 = q(k P , k 1 , k 2 , k C ), 0 ≤ k 0 ≤ 2 |k0| -1, 0 ≤ k 3 ≤ 2 |k3| -1 (3.17)
We can see that Q k1,k2 = B k1 AC k2 , where

B k1 ∈ Z 2 |k 0 | ×2 |k 0 | and C k2 ∈ Z 2 |k 3 | ×2 |k 3 |
, and the elements of these matrices are defined as

b k1 k0,i = (-1) f1(i⊕k0,k1) , 0 ≤ k 0 , i ≤ 2 |k0| -1 (3.18) c k2 j,k3 = (-1) f2(j⊕k3,k2) , 0 ≤ j, k 3 ≤ 2 |k3| -1 (3.19)
All the matrices B k1 , C k2 adhere to the structure described in Proposition 3.1 and thus the product of a vector by one of these matrices can be computed by using tree Fast Walsh-Hadamard Transforms (FWHT). More precisely, these matrices decompose as

2 |k0| B k1 = H 2 |k 0 | diag λ λ λ k1 1 H 2 |k 0 | , where λ λ λ k1 1 = H 2 |k 0 | B k1 •1 (3.20) 2 |k3| C k2 = H 2 |k 3 | diag λ λ λ k2 2 H 2 |k 3 | , where λ λ λ k2 2 = H 2 |k 3 | C k2 •1 (3.21)
The matrices Q k1k2 can therefore be calculated as

2 |k0|+|k3| Q k1k2 = H 2 |k 0 | diag H 2 |k 0 | B k1 •1 H 2 |k 0 | AH 2 |k 3 | diag H 2 |k 3 | C k2
•1

H 2 |k 3 | (3.22)
The end result is that the attack can be performed efficiently as follows:

1. Distillation phase: Construct the matrix A by looking at each plaintext-ciphertext pair (x, y), finding the associated values of i and j and incrementing the corresponding a ij by one.

The time complexity of the distillation phase is ρ D N binary operations, where ρ D is the cost of checking one pair. The distilled data needs 2 |k0|+|k3| memory registers of up to n bits.

2. Analysis phase: Compute all the experimental correlations q(k 0 , k 1 , k 2 , k 3 ):

(a) Apply the FWHT on all rows and columns of A to obtain a matrix A.

The cost of applying the transform on all the rows is ρ A •2 |k0| •|k 3 |2 |k3| and the cost of applying it on all the columns is ρ

A • 2 |k3| • |k 0 |2 |k0| , so the total cost is ρ A (|k 0 |+|k 3 |) 2 |k0|+|k3| .
No additional memory is required. (b) Construct all the eigenvalue vectors λ λ λ k1

1 and λ λ λ k2 2 . This is done by calculating the first column of B k1 or C k2 and then applying the FWHT on this vector. This step can be precomputed before the distillation phase, and requires ρ f1 2 |k0|+|k1| + ρ A |k 0 |2 |k0|+|k1| operations to compute all the vectors λ λ λ k1 1 (where ρ f1 is the cost of evaluating f 1 ) and ρ f2 2 |k2|+|k3| + ρ A |k 3 |2 |k2|+|k3| time to compute the λ λ λ k2 2 . The memory requirement is 2 |k0|+|k1| + 2 |k2|+|k3| registers of n bits. (c) Compute Q k1,k2 for all the values of k 1 and k 2 : i. Multiply each column of a copy of A by λ λ λ k1 1 and each row by λ λ λ k2 2 elementwise. ii. Apply the FWHT on all the rows and columns of this matrix to obtain Q k1,k2 . Since these calculations need to be done for each one of the 2 |k1|+|k2| guesses for the inner keys, the overall time cost is 2ρ

M 2 |k0|+|k1|+|k2|+|k3| + ρ A (|k 0 |+|k 3 |) 2 |k0|+|k1|+|k2|+|k3|
k P , k 1 , k 2 , k C )|.
The cost is ρ C 2 |k0|+|k1|+|k2|+|k3| .

3. Search phase: The selected candidate subkeys are tested by searching for the rest of the key exhaustively. The cost is ρ E 2 κ-a .

Algorithm 6: General key recovery algorithm using FFT (without the final phase)

Input: A collection D = {(x, y = E K (x))} of N plaintext-ciphertext pairs (possibly on-the-fly). Output: The experimental correlations Q k1,k2 k0,k3 . // DISTILLATION PHASE A ← 0; forall (x, y) ∈ D do a x|χ 0 ,y|χ 3 ← a x|χ 0 ,y|χ 3 + 1; // ANALYSIS PHASE for i ← 0 to 2 |k0| -1 do A i• ← FWHT(A i• ); // Apply the FWHT to the rows of A for j ← 0 to 2 |k3| -1 do A •j ← FWHT(A •j ); // Apply the FWHT to the columns of A for k 1 ← 0 to 2 |k1| -1; i ← 0 to 2 |k0| -1 do (λ k1 1 ) i ← f 1 (i, k 1 ); // First column of B k1 for k 2 ← 0 to 2 |k2| -1; j ← 0 to 2 |k3| -1 do (λ k2 2 ) j ← f 2 (j, k 2 ); // First column of C k2 for k 1 ← 0 to 2 |k1| -1 do λ λ λ k1 1 ← FWHT(λ λ λ k1 1 ); // Compute λ λ λ k1 1 for k 2 ← 0 to 2 |k2| -1 do λ λ λ k2 2 ← FWHT(λ λ λ k2 2 ); // Compute λ λ λ k2 2 for k 1 ← 0 to 2 |k1| -1; k 2 ← 0 to 2 |k2| -1 do // Compute Q k1,k2 k0,k3 for k 0 ← 0 to 2 |k0| -1; k 3 ← 0 to 2 |k3| -1 do Q k1,k2 k0k3 ← A k0k3 • (λ k1 1 ) k0 • (λ k2 2 ) k3 ; for k 0 ← 0 to 2 |k0| -1 do Q k1,k2 k0• ← FWHT(Q k1,k2 k0• ); for k 3 ← 0 to 2 |k3| -1 do Q k1,k2 •k3 ← FWHT(Q k1,k2 •k3 ); end return Q k1,k2
k1,k2 ;

Result 3.1. The time complexity of the general algorithm is (ignoring the significantly smaller terms)

ρ D N distillation phase + 2ρ M 2 |k0|+|k1|+|k2|+|k3| + ρ A (|k 0 |+|k 3 |) 2 |k0|+|k1|+|k2|+|k3| analysis phase + ρ E 2 κ-a search phase (3.23)
The memory use is 2 |k0|+|k1|+|k2|+|k3| + o 2 |k0|+|k1|+|k2|+|k3| memory registers of n bits.

A look at the structure of the analysis phase shows that a time-memory tradeoff in the lower order terms can be achieved if some of the steps are mixed: for example, slightly less memory is required if the eigenvalue vectors are only computed as needed (this has a small additional time cost, however). Furthermore, if the attacker doesn't need to store all the experimental correlations, it is possible to compute the matrices Q k1,k2 one by one without storing them, so that only 2 • 2 |k0|+|k3| memory registers of n bits are used. This algorithm also generalises the case in which no part of the key is guessed at the beginning of the cipher (for example, the original attack of [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF]): it suffices to only compute the experimental correlations corresponding to the case k 0 = 0. This means that instead of applying the FWHT on all the rows of A, it suffices to right-multiply A by the first column of C to obtain a. This is different from the original algorithm that was shown in [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF], as the calculation of the vector a, which was originally done in one step, is now separated into two different computations. This is slightly more costly in memory, but has the advantage that, in the case of multiple linear cryptanalysis, only one distillation phase needs to be performed, instead of one distillation for each possibility for the input mask α.

We also compared the computational costs ρ D , ρ f1 , ρ f2 , ρ C , ρ A , ρ M and ρ E . In general, ρ D , ρ f1 and ρ f2 should be negligible when compared to the others, as they are much simpler operations. For most cases ρ C ρ A and ρ M should be comparable to or smaller than ρ E (this depends on the implementations of the cipher and the operations). The adaptability of this algorithm to multiple and multidimensional linear attacks was also considered in [START_REF] Nguyen | Improving the Algorithm 2 in Multidimensional Linear Cryptanalysis[END_REF], [START_REF] Zheng | FFT-based Multidimensional Linear Attack on PRESENT using the 2-bit-Fixed Characteristic[END_REF] and [START_REF] Bogdanov | Multivariate Profiling of Hulls for Linear Cryptanalysis[END_REF]. For the general algorithm, since the distillation phase only needs to be performed once, we arrive at the following complexity:

Result 3.2. A multiple/multidimensional Algorithm 2 attack using M approximations with the extended FFT algorithm has complexity (ignoring the significantly smaller terms)

ρ D N distillation phase + 2M ρ M 2 |k0|+|k1|+|k2|+|k3| + M ρ A (|k 0 |+|k 3 |)2 |k0|+|k1|+|k2|+|k3| analysis phase + ρ E 2 κ-a search phase (3.24)
If there are several approximations which share the same input mask α but differ in their output masks (or the other way around), then it is possible to reuse some partial results such as B k1 A, which only need to be computed once. This can lead to a further reduction of the time complexity.

Exploiting the key schedule

In the algorithm of the previous subsection, the attacker has no prior knowledge of the relationship between the different round subkeys: they guess |k 0 |+|k 1 |+|k 2 |+|k 3 | bits of subkey independently. However, real ciphers have a key schedule, which means that relationships between the different subkeys will exist. In a "classical" implementation of Matsui's Algorithm 2 over multiple rounds (that is, without using the FWHT), these relationships are easily exploited: if k 0 , k 1 , k 2 and k 3 can all be deduced from |k T | bits of information about the subkey, then the time complexity of the attack can be reduced to N 2 |k T | or O(N ) + 2 2|k T | , depending on the chosen variant of the algorithm. This subsection deals with how the known dependencies between subkey bits which are induced by the key schedule can be used to improve the time complexity of our algorithm, especially in the case of multiple linear cryptanalysis. Two different but compatible strategies will be introduced: the first exploits bit dependencies when computing the experimental correlations for each one of the approximations. The second computes the experimental correlations for each approximation using only the subkey bits which are strictly necessary, and then combines all the information to obtain the Q k statistics.

Top-down strategy

The first approach consists of directly trying to use the dependency relationships between the subkey bits in order to reduce the time complexity of the general algorithm, so it can be used for simple, multiple and multidimensional linear cryptanalysis. We have so far been unable to provide an efficient general algorithm which takes account of all dependency relationships between k 0 , k 1 , k 2 , k 3 . However, we have considered several possible instances in which the attacker can obtain a time complexity gain by using their knowledge of the subkeys that's derived from the key schedule:

• Dependency within k 1 or within k 2 : This case is already covered by the general algorithm, as it is sufficient to redefine k 1 and k 2 with a smaller number of bits.

• Dependency between k 1 and k 2 : If k 1 and k 2 can be deduced from |k T |< |k 1 |+|k 2 | bits of information about the master key, then it is possible to only consider the matrices Q k1,k2 corresponding to all possible values of k T while running the algorithm. The time complexity of the analysis phase is thus reduced to

2ρ M 2 |k0|+|k T |+|k3| + ρ A (|k 0 |+|k 3 |)2 |k0|+|k T |+|k3| (3.25)
• Dependency within k 0 or within k 3 : If the key schedule means that k 0 (or k 3 ) can't take all the 2 |k0| possible values (one particular case is when the round subkey is only XORed with a part of the state, that is, when some bits of k 0 are always zero), then the attacker doesn't need to compute q(k 0 , k 1 , k 2 , k 3 ) for the impossible values of k 0 . This can be done by ignoring these output positions when computing the FWHTs of step 2c of the algorithm (this is often called a "pruned" transform, see [START_REF] Jankovic | Decision Diagram Method for Calculation of Pruned Walsh Transform[END_REF], [START_REF] Hu | A novel generic Fast Fourier Transform pruning technique and complexity analysis[END_REF]). This can lead to a gain in time complexity which depends on the set of required outputs.

• Dependency between k 0 and k 3 : If some bits of k 3 can be deduced from k 0 , then the last set of FWHTs can be pruned according to the possible values of k 0 which are associated to the row of Q k1k2 currently being calculated.

• Dependency between k 0 and (k 1 k 2 ) (or (k 1 k 2 ) and k 3 ): If some bits of k 0 (or k 3 ) can be deduced from k 1 and k 2 , then the attacker can use the same strategy of pruning the FWHT as in the previous cases. This time, however, the set of possible values of k 0 and k 3 changes according to the value of k 1 and k 2 currently under consideration.

Bottom-up strategy: multiple linear cryptanalysis

Another approach which is specific to multiple attacks is to use the FWHT algorithm to compute the experimental correlation for each approximation but considering only the subkey bits which are strictly necessary, and then combining the information from all the approximations to obtain Q k more quickly. This is similar to the approach of [ZZ15] and [START_REF] Bogdanov | Multivariate Profiling of Hulls for Linear Cryptanalysis[END_REF] and seems to allow for a greater flexibility than the top-down strategy. Let ν i :

α i • x ⊕ β i • ŷ, i = 1, .
. . , M be linear approximations of the inner cipher E M . Multiple linear cryptanalysis requires the attacker to compute

Q(k 0 , k 1 , k 2 , k 3 ) = 1 N m i=1 q i (k 0 , k 1 , k 2 , k 3 ) 2
In order to calculate one particular q i (k 0 , k 1 , k 2 , k 3 ) some subkey bits might be unnecessary: some part of the subkey might be necessary for one approximation but not for a different one. Let us suppose

Application to the block cipher PRESENT

In order to showcase the potential of our key recovery techniques, we will describe some new attacks on reduced-round variants of the block cipher PRESENT, which surpass any previously known attacks, linear or otherwise. Our new results on PRESENT are of independent interest by themselves: in particular, we will describe our attacks on the 26 and 27-round variants of PRESENT- We will describe two new linear attacks on reduced-round variants of PRESENT which make use of different sets of linear approximations (or linear distinguishers). The first one only uses approximations with input and output masks of Hamming weight one, which makes the key recovery part of the attack light enough to allow attacks on up to 27-rounds of PRESENT-80. Later we will describe a more effective (in the sense that it has a larger capacity for the same number of rounds) linear distinguisher using masks of Hamming weight 2: this allows to reach 28 rounds, but also means that the key recovery is more expensive and the attack only applies to PRESENT-128. This section is structured as follows: the first subsection contains a description of the PRESENT block cipher specifications for both key sizes. The next subsections explain the development of our linear attacks: from the selection of sets of suitable linear approximations to the key recovery algorithm. Finally, we provide some experimental verification of our claims on the data and time complexity of our attacks by implementing computer simulations on 10-round PRESENT.

Description of PRESENT

PRESENT is a key-alternating block cipher which takes a 64-bit plaintext x = x 63 . . . x 0 and an 80-bit (or 128-bit) key K = κ 79 . . . κ 0 (or K = κ 127 . . . κ 0 ) and returns a 64-bit ciphertext y = y 63 . . . y 0 . The encryption is performed by iteratively applying a round transformation to the state b = b 63 . . . b 0 = w 15 . . . w 0 , where each of the w i represents a 4-bit nibble,

w i = b 4i+3 b 4i+2 b 4i+1 b 4i .
Both variants of PRESENT consist of 31 rounds, plus the addition of a final whitening key at the output. Each round is the composition of the following three transformations:

• addRoundKey: Given the round key K i = κ i 63 . . . κ i 0 , 0 ≤ i ≤ 31 and the state b, the round key is XORed bitwise to the state.

• sBoxLayer: A fixed 4-bit to 4-bit S-box S : F 4 2 -→ F 4 2 is applied to each 4-bit nibble of the state w i . The S-box S is given as a lookup table (here in hexadecimal notation): • pLayer: A fixed bitwise permutation P is applied to the state b. All the components of a PRESENT round are invertible, so it is easy to invert each round and therefore the whole cipher. The following algorithm summarises the structure of PRESENT: The only element left to describe is the key schedule, which is the only difference between both variants:

The 1-bit linear distinguisher for up to 23 rounds

This subsection provides a multiple linear distinguisher which can be used on up to 23 rounds of PRESENT (thus allowing for an Algorithm 2 attack on up to 27 rounds by adding two rounds at the beginning and two at the end), and only uses approximations with input and output masks of Hamming weight 1 (which will be called 1-bit approximations). We begin our analysis by looking at the Linear Approximation Table of the PRESENT S-box (table 1). This table shows that the S-box has eight (out of the total sixteen) biased linear approximations for which both the input and output masks have Hamming weight 1. These approximations can be used to construct linear trails which only have one active S-box on each round and involve one bit of each round subkey. These trails lead to the presence of approximations for multiple rounds with one-bit input and output masks and a large ELP. This phenomenon is exploited by all the linear attacks on PRESENT that we are aware of, such as [START_REF] Ohkuma | Weak Keys of Reduced-Round PRESENT for Linear Cryptanalysis[END_REF], [START_REF] Nakahara | Linear (Hull) and Algebraic Cryptanalysis of the Block Cipher PRESENT[END_REF], [START_REF] Cho | Linear Cryptanalysis of Reduced-Round PRESENT[END_REF], [START_REF] Zheng | FFT-based Multidimensional Linear Attack on PRESENT using the 2-bit-Fixed Characteristic[END_REF] and [START_REF] Bogdanov | Multivariate Profiling of Hulls for Linear Cryptanalysis[END_REF]. We will now select a few high-bias one-bit approximations of 22/23 rounds of PRESENT which we will use on the 26/27-round attack of the next subsection. Since there are only 64 × 64 = 2 12 possible one-bit approximations, we can just estimate the ELP of all of them and keep the ones with the largest values. To this end we used the correlation matrix method considering all linear trails with up to two active S-boxes on each intermediate round (this means that the correlation submatrix is of size 2800 × 2800). The results of this computation have been condensed into table 2.

Output mask β β β 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Input mask α α α 0 8 - - - - - - - - - - - - - - - 1 - - - - --4 --4 - - - - - -4 - 4 2 - - 2 2 -2 -2 - - 2 -2 - 4 - 4 -2 2 3 - - 2 2 2 -2 -4 - -2 2 -4 - - - -2 -2 4 - - -2 2 -2 -2 - 4 -2 -2 - -4 - - -2 2 5 - - -2 2 -2 2 - - 2 2 -4 - 4 - 2 2 6 - - --4 - --4 - --4 - - 4 - - - 7 - - - 4 4 - - - --4 - - - - 4 - 8 - - 2 -2 - --2 2 -2 2 - - -2 2 4 4 9 - 4 -2 -2 - - 2 -2 -2 -2 -4 - -2 2 - - 10 - - 4 - 2 2 2 -2 - - - -4 2 2 -2 2 11 - -4 - - -2 -2 2 -2 -4 - - - 2 2 2 -2 12 - - - - -2 -2 -2 -2 4 - - -4 -2 2 2 -2 13 - 4 4 - -2 -2 2 2 - - - - 2 -2 2 -2 14 - - 2 2 -4 4 -2 -2 -2 -2 - - -2 -2 - - 15 - 4 -2 2 - --2 -2 -2 2 4 - 2 2 - -
Table 1: Linear Approximation Table (LAT) for the S-box of PRESENT. The entries with value 0 have been indicated with a -to facilitate reading. Furthermore, the entries corresponding to input and output masks of Hamming weight 1 have been highlighted.

Table 2: Classification of the most correlated 1-bit approximations for 22 and 23 rounds of PRESENT.

For each row of the table, an approximation can be constructed by masking one of the possible input bits and one of the possible output bits. The bits in bold represent the approximations which are used in our linear distinguisher.

There seems to be a structure in these approximations: the values of the ELP cluster around a few discrete values which differ from each other by a factor of 2 -0.7 , and the input and output bits can be classified in groups according to the correlation of their associated approximations. This might be caused by the interaction between the Linear Approximation Table of the PRESENT S-box and the permutation P , and it would be interesting to find a thorough explanation of this phenomenon.

For our attack we have chosen 128 linear approximations with high correlation: we use all 64 approximations from group A, 32 from group B1 (those corresponding to output bits 22,30,54,62) and 32 from group B2 (with input bits 53,54,57,58). If the reader looks at the figures in the next subsection, the choice of the approximations from groups B1 and B2 should become clearer: they involve the same subkey bits as the approximations in group A, thus minimizing the time cost of the key recovery. This set of linear approximations has a total capacity of 2 -54.81 (for 22 rounds) and 2 -56.71 (for 23 rounds).

It should be noted that these approximations are not statistically independent: they are not even linearly independent. One possible solution would be the application of multidimensional linear cryptanalysis, which would make the key recovery too costly as it would be necessary to consider all the linear combinations of our set of approximations, so the benefits of using approximations of Hamming weight 1 would be lost. Instead, the multiple linear cryptanalysis statistic will be used for these attacks, and we will estimate the probability of success under the assumption that the approximations are independent. In order to justify the validity of the resulting estimation, we will provide experimental results which conform to the theoretical predictions for a reduced number of rounds at the end of this section.

We have used the statistical model of [START_REF] Blondeau | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis[END_REF] to compute the achievable advantage depending on the amount of data when the 22 and 23-round distinguishers are used to mount attacks on 26 and 27round PRESENT, as well as comparing it to other previously known attacks. The results can be found on figure 4. For all the attacks, the probability of success has been fixed to 0.95, while a distinct known plaintext scenario is supposed (in other words, N is the number of strictly different available plaintexts). In both cases, our new linear distinguisher can either permit a lower data complexity or a larger advantage when using the same data when compared to previous attacks.

Attacks on 26 and 27-round PRESENT-80

We will now proceed to use the linear distinguisher from the previous subsection to construct linear attacks on 26 and 27-round PRESENT-80. This is done by utilising Matsui's Algorithm 2 on the first two and the last two rounds of the cipher. We begin by studying the first and last two rounds of PRESENT.

Proposition 4.1. (Key recovery on the first two rounds) Let x be the state at the beginning of the second round of PRESENT. Given two fixed values of i, j between 0 and 3, the value of the four bits x48+4i+j , x32+4i+j , x16+4i+j , x4i+j can be obtained from the 16 bits of the plaintext x 16j+15 . . . x 16j , as well as the 16 bits of the first round subkey κ 0 16j+15 . . . κ 0 16j and the 4 bits of the second round subkey κ 1 16i+4j+3 κ 1 16i+4j+2 κ 1 16i+4j+1 κ 1 16i+4j . In particular, for a fixed j the 16 bits of the state x60+j , x56+j , . . . , x4+j , xj can be obtained from the 16 bits of the plaintext x 16j+15 . . . x 16j , the 16 bits of the first round subkey κ 0 16j+15 . . . κ 0 16j , and the 16 bits of the second round subkey

κ 1 48+4j+3 . . . κ 1 48+4j , κ 1 32+4j+3 . . . κ 1 32+4j , κ 1 16+4j+3 . . . κ 1 16+4j , κ 1 4j+3 κ 1 4j+2 κ 1 4j+1 κ 1 4j
Proof. The reader is invited to convince themselves by looking at figure 5. We can also prove this formally by noting that the inverse permutation P -1 is of the form

P -1 (j) = 4j mod 63 if j = 63, P -1 (63) = 63
This means that x16l+4i+j is equal to the bit of position P -1 (16l + 4i + j) = 64l + 16i + 4j mod 63 = 16i + 4j + l before the second application of pLayer. If we then undo sBoxLayer, we find that we need bits κ 1 16i+4j+3 . . . κ 1 16i+4j of the second round subkey K 1 . If we continue by undoing the first round, we find that we need bits P -1 (16i+4j +3) = 16j +12+i, P -1 (16i+4j +2) = 16j +8+i, P -1 (16i+4j +1) = 16j + 4 + i, P -1 (16i + 4j) = 16j + i of the state before the first application of pLayer. Finally, by undoing the first sBoxLayer, we find that we require bits x 16j+15 . . . x 16j of the plaintext x and bits κ 16j+15 . . . κ 16j of the first round subkey K 0 . Proposition 4.2. (Key recovery on the last two rounds) Let ŷ be the state after the application of addRoundKey in the second to last round of PRESENT. Given two fixed values of i, j between 0 and 3, the value of all the four bits ŷ16i+4j+3 , ŷ16i+4j+2 , ŷ16i+4j+1 , ŷ16i+4j can be obtained from the 16 bits of the ciphertext y 60+i , y 56+i , . . . , y 4+i , y i , as well as the 16 bits of the last round subkey κ r 60+i , κ r 56+i , . . . , κ r 4+i , κ r i and 4 bits of the second-to-last round subkey κ r-1 48+4i+j κ r-1 32+4i+j κ r-1 16+4i+j κ r-1 4i+j . In particular, for a fixed i the 16 bits of the state ŷ16i+15 . . . ŷ16i can be obtained from the 16 bits of the ciphertext y 60+i . . . y 4+i , y i , the 16 bits of the last round subkey κ r 60+i . . . κ r 4+i , κ r i , and the 16 bits of the second-to-last round subkey

κ r-1 48+4i+3 . . . κ r-1 48+4i , κ r-1 32+4i+3 . . . κ r-1 32+4i , κ r-1 16+4i+3 . . . κ r-1 16+4i , κ r-1 4i+3 κ r-1 4i+2 κ r-1 4i+1 κ 1 4i
Proof. The proof is analogous to that of the previous result. Figure 5 also illustrates this.

With these observations and the bottom-up strategy from the previous section, we can describe an attack on 26-round PRESENT which uses the 22-round one-bit linear distinguisher between the third and the 24th rounds. If x denotes the state after the second round and ŷ denotes the state before the 25th round, in order to evaluate the experimental correlation for all the approximations it is necessary to compute

x58 , x57 , x54 , x53 , x42 , x41 , x38 , x37 , x26 , x25 , x22 , x21 ∈ {x 16r+4•2+2 , x16r+4•2+1 , x16r+4•1+2 , x16r+4•1+1 , r = 0, . . . , 3} (4.2) ŷ63 , ŷ62 , ŷ61 , ŷ55 , ŷ54 , ŷ53 , ŷ31 , ŷ30 , ŷ29 , ŷ23 , ŷ22 , ŷ21 ∈ {ŷ 16•3+4•3+s , ŷ16•3+4•1+s , ŷ16•1+4•3+s , ŷ16•1+4•1+s , s = 0, . . . , 3} (4.3)
For any individual one-bit to one-bit approximation, because of the previous results, we need to guess 16 bits of K 0 , 4 bits of K 1 , 4 bits of K 25 and 16 bits of K 26 . That means that for all approximations

|k i 0 |= |k i 3 |= 16 and |k i 1 |= |k i 2 |= 4.
We also know that the total number of subkey bits which require guessing (without taking the key schedule into account) in the key recovery is |k 0 |= |k 3 |= 32 and |k 1 |= |k 2 |= 16. We will now consider the set of approximations as a whole in order to compute l 1 (the number of different plaintext-ciphertext masks) and l 2 (the number of different sets of subkey bits). Since all the input mask bits are of the form x4r+1 or x4r+2 , there are two groups of bits of the plaintext which are relevant (x 31 . . . x 16 and x 47 . . . x 32 ). Analogously, since all the output bits are of the form ŷ16+s or ŷ48+s , we conclude that only the groups of ciphertext bits y 61 , . . . , y 5 , y 1 and y 63 , . . . , y 7 , y 3 are necessary. This means that l 1 ≤ 2 • 2 = 4. A look at the approximations confirms that indeed l 1 = 4. In a similar manner, we can show that l 2 = 4 • 4 = 16. We also need to compute the number of master key bits which are actually involved in the key recovery, |k T |. In order to do this, we must consider the key schedule in detail. We found that guessing the Figure 6: Our attack on 26-round PRESENT using 128 approximations with the analysis of the key schedule. In total there are 96 bits of the subkeys which need to be guessed, which have been indicated by a cross in the figure. However, they can all be deduced from the |k T |= 61 bits of key which have been highlighted in (dark) red. From these bits of key, all the bits in (light) green can be deduced, which includes all the necessary bits for the attack. The 16 bits to the right represent the fraction of the key register which is not used for the current round subkey.

32 necessary bits of K 0 and 8 bits of K 1 already allows us to deduce 6 necessary bits of K 25 and 16 necessary bits of K 26 . Furthermore, by guessing two additional bits of K 0 and three additional bits of K 1 , it is possible to compute 10 additional bits of K 25 and K 26 . This means that there are only 6 bits of K 25 and 10 bits of K 26 which need to be guessed separately. This makes for a total of |k T |= 61 total information bits of the master key. The reader can study these considerations in further detail by looking at figure 6. Finally, we must compare ρ M and ρ A to ρ E . We can find a lower bound for ρ E by noticing that in a PRESENT encryption 64 bit additions are required for the addition of each round subkey, while at least 64 bit operations are required for the application of sBoxLayer (at the very least, every bit of the new state must be computed). This means that we can assume that ρ E ≥ 64 • (27 + 26) = 3392. On the other hand, we only expect to multipl and add integers of up to 64 bits. This means that ρ A 64 and ρ M 3 • 64 1.58 2142 (using Karatsuba's algorithm). We conclude that the complexity of the attack (in 26-round encryptions) is N + 2 65 + 2 80-a . The fact that the time complexity of the analysis phase is "only" 2 65 (when compared to the 80 bits of key) allows for a trade-off between the data complexity and the time complexity of the linear attack. As an extreme example, we can consider an attack with N = 2 61.9 (distinct) data complexity. This provides an advantage of 17 bits with probability 0.95, so that the search phase has a significantly smaller time complexity than the analysis phase and the whole time complexity of the attack is thus 2 65 . On the other hand, a smaller (distinct) data complexity of N = 2 60.8 provides an advantage of 8 bits, thus increasing the time complexity to 2 72 full round encryptions. The attack requires storing 2 44 integers in memory. In a similar fashion, we can design an attack on 27 rounds by using the same approximations between rounds 3 and 25. All the parameters for the key recovery algorithm are the same as on the 26-round attack, except for |k T |, which in this case is 68 (see figure 7 for details). This means that an attack can be mounted with time complexity 2 72 + 2 80-a . Since the time complexity of the analysis phase is larger in this attack because of the larger value of |k T |, it is not possible to obtain better time complexities by incrementing the amount of data. When N = 2 63.4 distinct known plaintexts are available, the advantage is 8 bits with probability 0.95, and the overall time complexity of the attack is 2 72 full round encryptions. The memory requirement to perform this attack is again 2 44 memory positions. These attacks can be extended to the 128-bit key variant, since there is no need to exploit the key schedule because |k 0 |+|k 1 |+|k 2 |+|k 3 |= 96 < 128. The data complexities and the time complexities of the distillation and analysis phases of these attacks are the same, while the cost of the search phase increases with the key size.

The 2-bit linear distinguisher for up to 24 rounds

The capacity of our linear distinguisher using only approximations with masks of Hamming weight one diminishes as the number of rounds increases, so that the achievable advantage becomes too small when the number of rounds reaches 24 for the internal cipher (that is, when we attempt to attack 28-round PRESENT with the key recovery algorithm from the previous subsection). We will now construct a linear distinguisher for 24 rounds which uses approximations with masks of Hamming weight 1 or 2: this leads to a larger capacity because of the larger amount of available approximations, but it also means that the key recovery becomes more computationally expensive, so that the resulting attack will only compare favorably with a brute-force attack in the case of PRESENT-128.

In order to construct the new distinguisher, we start by looking for highly biased approximations over a larger search space than before. In particular, we considered approximations with up to two active S-boxes in their first and last rounds, and with input and output masks so that prolonging the approximation for an additional round at the beginning or the end would only require two additional active S-boxes (this is in fact equivalent to imposing that the mask for each of the active S-boxes in either the input or the output rounds has Hamming weight 1 or 2). Approximations with two active S-boxes in the first and last round but with a larger amount of active S-boxes when they are extended lead to a too expensive key recovery, so it makes sense to ignore them. There are 2800 input masks and 2800 output masks which verify this property. A correlation matrix was constructed for one round of PRESENT, and by elevating the element-wise square of this matrix to the 24th power we obtained estimations of the ELPs of all the approximations with these input and output masks for up to 24 rounds. The results showed that no candidate approximations with two active S-boxes in either the first or the last round exhibit large biases (at least when compared to approximations where the first and last round only have one active S-box). We decided to classify the best approximations according to the active S-box in the first and the last round, as well as the input/output mask of that S-box (note that the final output mask is obtained after applying pLayer Table 3: Linear approximations for 24 rounds of PRESENT with input and output masks of Hamming weight 1 or 2 and an ELP larger than 2 -67 . Note that the approximations from the one-bit distinguisher are all in groups D,G1 and G4. The approximations which have been chosen for the two-bit linear distinguisher are highlighted in a bold typeface.

on the mask of the S-box). The results are condensed in table 3. From these candidates, we have selected 448 approximations which lead to a total capacity of 2 -56.98 , and have been indicated on the table. As before, the choice of the approximations obeys both their ELP and their suitability for a reasonably expensive key recovery. Once again, these approximations are not linearly independent, and we will justify our predictions about the advantage by providing experimental results. As before, we have estimated the advantage that would be provided by these approximations by using the model of [START_REF] Blondeau | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis[END_REF]. If the attacker has access to the full codebook (that is, N = 2 64 distinct known plaintext-ciphertext pairs), then the advantage will be of 6 bits or more with probability 0.95.

Attack on 28-round PRESENT-128

The linear distinguisher from the previous subsection will now be used to construct a multiple linear attack on 28-round PRESENT-128, which to the best of our knowledge is the first to reach this number of rounds. We begin by slightly updating proposition 5 to account for the mask on the S-box of the last round instead of the output mask:

Proposition 4.3. (Key recovery on the last two rounds, revisited) Let ỹ be the state after the application of sBoxLayer in the (r -2)-th round of PRESENT. Given two fixed values of i, j between 0 and 3, the value of all the four bits ỹ16j+12+i ⊕ κ r-2 P (16j+12+i) , ỹ16j+8+i ⊕ κ r-2 P (16j+8+i) , ỹ16j+4+i ⊕ κ r-2 P (16j+4+i) , ỹ16j+i ⊕ κ r-2 P (16j+i) (4.4) can be obtained from the 16 bits of the ciphertext y 60+i , y 56+i , . . . , y 4+i , y i , as well as the 16 bits of the last round subkey κ r 60+i , κ r 56+i , . . . , κ r 4+i , κ r i and the 4 bits of the second-to-last round subkey κ r-1 48+4i+j κ r-1 32+4i+j κ r-1 16+4i+j κ r-1 4i+j . In total there are 156 bits of the subkeys which need to be guessed, which have been indicated by a cross. However, if the |k T |= 114 bits of key which have been highlighted in (dark) red are known, then all the bits in (light) green can be deduced, which include all the necessary bits for the attack. The 64 bits to the right represent the half of the key register which is not used for the current round subkey.

We can mount an attack using the bottom-up algorithm from the previous section, we just need to compute the parameters using the previous result as well as proposition 4.1. Since there are 4 different possibilities for the input mask in the active S-box for the first round and 4 possibilities for the output mask of the active S-box of the last round, we conclude that l 2 = 4 • 4 = 16. With a similar argument but also taking the choice of the active S-box into account, we deduce that l 1 = 12 8 illustrates how |k T |= 114. As discussed in the previous subsection, the advantage of the linear distinguisher is at least 6 bits with probability 0.95 when the full codebook of N = 2 64 plaintext-ciphertext pairs is available. The time complexity of the attack in number of 28-round PRESENT encryptions is thus bounded (with probability 0.95) by 2 122 full encryptions. The attack requires 448 • 2 80 = 2 89 memory positions, which is the bottleneck of the attack as it is, and more than is required to just store the 2 64 plaintext-ciphertext pairs. We will try to reduce the memory requirements of this attack in the future.

Experimental verification

As was previously stated, our analysis of the achievable advantage of these attacks made some assumptions which do not completely hold. Apart from the linear dependence of the approximations conforming the linear distinguisher, there are other possible sources of problems: such as PRESENT not being a long-key cipher (which means that the ELP might not correspond to the real correlation of the approximations) and the fact that the wrong-key randomisation hypothesis doesn't hold for all approximations and all wrong keys (as not all bits of key influence the value of all approximations). For this reason it is necessary to provide some additional justification that these theoretical simplifications of the analysis still lead to reasonably accurate predictions. Since it's practically impossible to simulate our attacks because of the high time complexity, we performed computer simulations of the same attacks on 10 rounds of PRESENT instead of 26/27/28, using the linear distinguishers between rounds 3 and 8. These distinguishers have a much higher capacity than those over a larger number of rounds, which means that a manageable number of plaintext-ciphertext pairs needs to be generated. Since it is also unfeasible to perform the full key recovery algorithm on a real computer, we decided to estimate the advantage instead by comparing the right key against a large number of random wrong keys. More specifically, for each randomly chosen key and each randomly drawn sample of plaintexts, the right-key χ 2 statistic was computed. Then, 2 12 random keys were drawn, and these keys were used to perform partial encryption and decryption of the first and last two rounds, in order to create a sample of 2 12 wrong-key χ 2 statistics. The position of the right-key statistic among these provides an estimation of the advantage of up to 12 bits. This process was repeated for 20 different random right keys and 20 different random data samples, which provides a sample of 400 values of the advantage for a given value of N . The 5th percentile of these was used as an estimation of the advantage that's achieved with probability 0.95. Figure 9 compares the observed results to the theoretical predictions for these attacks. Given the proximity of these results, we are confident that our predictions for attacks on a larger number of rounds will also be accurate, especially in the case of the 1-bit distinguisher for the attacks on 26 and 27 rounds.

Conclusion

Our analysis of the FFT/FWHT technique for linear cryptanalysis which was introduced in [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF] has shown that the acceleration applies to most Algorithm 2 attacks over any number of rounds of key recovery. This algorithm also introduces a new distillation phase algorithm which extends the ideas of [START_REF] Nguyen | Improving the Algorithm 2 in Multidimensional Linear Cryptanalysis[END_REF] and allows the reuse of the distilled data in multiple and multidimensional linear cryptanalysis. We have also commenced the study of the compatibility of these accelerated attacks with the exploitation of the key schedule of the cipher. In particular, we have found that this can lead to effective results in the case of some multiple (but not multidimensional) attacks. However, we believe that there are many possible improvements on this area. We have been able to showcase the real use of these theoretical developments by designing new attacks on reduced-round variants of PRESENT, which surpass any previously known attacks in terms of data and time complexity, and we have provided the first (bar biclique cryptanalysis) shortcut attack on 28-round PRESENT, albeit only for the 128-bit key variant, and with a high memory requirement. We hope to refine this attack in the future to make it compatible with the 80-bit variant, as well as reducing the memory requirement. Table 4 compares our attacks on PRESENT with other attacks found in the literature. Our hope is that further developments in the algorithmic theory of linear cryptanalysis can make it more comparable with differential cryptanalysis, in the sense that some differential attacks showcase very intricate key recovery algorithms, which is fairly uncommon in linear attacks. We also believe that some block ciphers intended for lightweight cryptography with limited diffusion properties and simple key schedules might find their security eroded because of the possibility of linear attacks using multiple approximations: during this internship, I found a linear attack on the full-round primitive of the NIST Lightweight candidate TRIFLE ([TRF19])1 , which did not pass to the second round of the contest. Our intention is to publish a refined version of this attack with smaller data and time complexity in the near future. where ⊗ denotes the Kronecker (or tensor) product of matrices. These matrices are called Hadamard-Sylvester matrices. The entry in the i-th row and j-th column of

H 2 m is h 2 m ij = (-1) i•j , 0 ≤ i, j ≤ 2 m -1 (A.13)
where • denotes the inner product of binary vectors. H 2 m is always a symmetrical matrix of 1s and -1s which verifies the orthogonality property:

H 2 m H T 2 m = 2 m I 2 m (A.14)
Matrices of these characteristics (which are not necessarily symmetrical but must be composed of 1s and -1s) are called Hadamard matrices.

Proof. All the properties can be proven by induction on m.

Given a real vector x ∈ R 2 m of length 2 m , we say that its Walsh-Hadamard transform is the matrixvector product H 2 m x. This product can be computed efficiently using the following result:

Proposition A.8. The Hadamard-Sylvester matrix H 2 m can be obtained by multiplying the matrices

H i m = I 2 m-i ⊗ H 2 ⊗ H 2 i-1 . In other words, H 2 m = m i=1 H i m .
Proof. This result is deduced from the mixed-product property

(A ⊗ B)(C ⊗ D) = (AC) ⊗ (BD). m i=1 H i m = m i=1 (I 2 m-i ⊗ H 2 ⊗ H 2 i-1 ) = m i=1   m-i j=1 I 2 ⊗ H 2 ⊗ m j=m-i+1 I 2   = m j=1 H 2 = H 2 m
This means that the Walsh-Hadamard Transform of a given vector of length 2 m can be computed directly on the input registers with exactly m2 m additions and substractions using the following algorithm, which succesively multiplies the vector by the matrices H i m : Algorithm 10: The Fast Walsh-Hadamard Transform Input: A binary vector x of length 2 m . Output: A binary vector y of length 2 m . y ← x;

for i ← 1 to m do for j ← 0 to 2 m-i do for k ← 0 to 2 i-1 do tmp ← y[j2 i + 2 i-1 + k]; y[j2 i + 2 i-1 + k] ← y[j2 i + k] -y[j2 i + 2 i-1 + k]; y[j2 i + k] ← tmp + y[j2 i + k]; end end end return x
The Walsh-Hadamard Transform is a particular case of the Generalised Discrete Fourier Transform (in particular, the one corresponding to the abelian group Z m 2 ) and the Fast Walsh-Hadamard Transform is a particular case of the Generalised Fast Fourier Transform. The spectral analysis of boolean functions using the Walsh Transform is a very interesting topic in cryptography (see [START_REF] Daemen | The Design of Rijndael[END_REF]) and has a very strong relationship with linear cryptanalysis. Probability distributions. Finally, table 5 contains a condensed description of the probability distributions which are used in the statistical models for linear cryptanalysis and their properties, as well as the notations that we use for them.

B Linear cryptanalysis revisited

This appendix acts as a complement to section 2.

B.1 Proofs of the results of subsections 2.1 and 2.2

We begin by proving Matsui's piling up lemma, which is a direct consequence of the following general result on the addition of independent binary random variables: Proposition B.1. If X 1 , . . . , X r are independent Bernoulli random variables whose value is 0 with probability 1/2 + ε i (and 1 with probability 1/2 -ε i ), then

P r(X 1 ⊕ X 2 ⊕ . . . ⊕ X r = 0) = 1 2 + 2 r-1 r i=1 ε i (B.1)
Proof. The proof will proceed by induction on r.

If r = 2, we have X 1 ⊕ X 2 = 0 if and only if X 1 = X 2 = 0, which happens with probability (1/2 + ε 1 )(1/2 + ε 2 ), or X 1 = X 2 = 1, which happens with probability (1/2 -ε 1 )(1/2 -ε 2 ). The sum of these two probabilities is 1/2 + 2ε 1 ε 2 . For greater values of r, from the formula for r -1 variables we deduce P r(X 1 ⊕ . . . ⊕ X r = 0) = P r(X 1 = 0, X 2 ⊕ . . . ⊕ X r = 0) + P r(X 1 = 1, X 2 ⊕ . . . ⊕ X r = 1)

= 1 2 + ε 1 1 2 + 2 r-2 r i=2 ε i + 1 2 -ε 1 1 2 -2 r-2 r i=2 ε i = 1 2 + 2 r-1 r i=1 ε i
which is the expression we wanted to obtain.

We now proceed to the proof of proposition 2.4.

Proposition (2.4). Under the right-key equivalence hypothesis, the probability of success of Matsui's Algorithm 1 is approximately

P S Φ 2 √ N |ε| = Φ √ N c 2 = √ N c 2 -∞ 1 √ 2π e -x 2 2 dx (B.2)
Proof. Without loss of generality, we can suppose that γ(K) = 0 and ε > 0. The right-key equivalence hypothesis implies that P r x (α

• x ⊕ β • E K (x) = 0) = 1/2 + ε.
The number T is thus a random variable which follows a binomial distribution B(1/2+ε, N ) and can be approximated by the normal N (N (1/2+ε), N/4). The probability of success is the probability that T > N/2. We conclude by expressing T as a linear transformation of a standard normal distribution.

We can also prove the following proposition, which is an extended version of corollary 2.6: Proposition B.2 (Lemma 5 in [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF]). Under the right-key equivalence and the wrong-key randomisation hypotheses, he probability of success of Matsui's algorithm 2 is approximately

P S ∞ -2 √ N |ε| x+2 √ N |ε| -x-2 √ N |ε| 1 √ 2π e -1 2 y 2 dy 2 |k| -1 1 √ 2π e -1 2 x 2 dx (B.3)
Proof. Without loss of generality, we can suppose that ε > 0 and γ(K) = 0. From the statistical assumptions about the linear approximation, we deduce that the distribution of T k can be approximated by N (N/2 + N ε, N/4) if k is the right subkey, while for any wrong subkey T k follows the distribution N (N/2, N/4), and they are all independent. The probability of success P S is the probability that the counter T k for the right key is larger than N/2 and |T k -N/2| is larger than all the |T k -N/2|. This is Nyberg's proof of theorem 2.7, which is a version of Parseval's identity for the Walsh Transform:

Theorem (2.7). Let ν : α • x ⊕ β • y be a linear approximation of a key-alternating block cipher E for which all the round subkeys are independent (this is often called a long-key cipher, and it implies κ = n(r + 1)). Then, for any key mask γ :

F κ 2 → F 2 : 1 2 κ K∈F κ 2 (P r x (α • x ⊕ β • E K (x) = 0|K) -P r x (α • x ⊕ β • E K (x) = 1|K)) 2 = γ0,...,γr∈F n 2 (P r x,K (α • x ⊕ β • E K (x) ⊕ γ 0 • K 0 ⊕ . . . ⊕ γ r • K r = 0) -P r x,K (α • x ⊕ β • E K (x) ⊕ γ 0 • K 0 ⊕ . . . ⊕ γ r • K r = 1)) 2 (B.4)
Proof. The second member of the equality can be reweitten as follows: (-1) γ0•K0⊕...⊕γr•Kr⊕γ0•K 0 ⊕...⊕γr•K r   

Because E is a long-key cipher, we have K = K ⇐⇒ (K 0 , . . . , K r ) = (K 0 , . . . , K r ) ⇐⇒ (K 0 ⊕ K 0 , ..., K r ⊕ K r ) = 0 Therefore, by using proposition A.3, we have (-1) (γ0,...,γr)•(K0⊕K 0 ,...,Kr⊕K r ) = 0

if K = K 2 κ if K = K
We can substitute this in the previous expression:

1 2 2n+κ K∈F κ 2 x,x ∈F n 2 (-1) α•(x⊕x )⊕β•(E K (x)⊕E K (x )) = 1 2 κ K∈F κ 2   1 2 n x∈F n 2 (-1) α•x⊕β•E K (x)   2
This concludes the proof.

In definition 2.8, we can say γ 0 = α, γ r = β because if, for example, we had γ 0 = α, then α • x ⊕ γ 0 • K 0 is 0 with probability exactly 1/2, so no matter what the rest of the linear trail is, its correlation is 0 because of the piling-up lemma. We will now prove theorem 2.10: It is also true that the correlation matrix for the composition of two boolean functions is the matrix product of their respective correlation matrices, and the proof can be found in chapter 7 of [START_REF] Daemen | The Design of Rijndael[END_REF] or deduced from the piling-up lemma.

Theorem (2.

B.2 Multidimensional linear cryptanalysis

We now provide a very short description of a multidimensional version of Algorithm 2 using the χ 2 statistic as introduced in [HCN08], [START_REF] Hermelin | Multidimensional Extension of Matsui's Algorithm 2[END_REF], [START_REF] Hermelin | Multidimensional Linear Cryptanalysis[END_REF] (multidimensional attacks using the log-likelihood ratio as well as Algorithm 1-type attacks are also introduced in these publications). Consider a set of M = 2 m -1 approximations whose masks form an m-dimensional vector subspace of F n 2 ×F n 2 (ignoring the approximation with both masks equal to zero). There are m linearly independent linear approximations ν j given by α j , β j ∈ F n 2 , j = 0, . . . , m -1 which span the complete set of approximations. These m approximations follow a joint discrete distribution in F m 2 . In other words, for each K we have the distribution η η η(K) = (η 0 (K), . . . , η 2 m -1 (K)), where η i (K) = P r x ((ν m-1 , . . . , ν 0 ) = i | K) (B.6) using the identification between F m 2 and the integers from 0 to 2 m -1. Hermelin et al. proposed a variation of Algorithm 2 based on a new wrong-key randomisation hypothesis. They assumed that for any wrong guess of the partial subkey k, then η η η(K) will be the uniform distribution over F m 2 . Given k, this distribution can be tested for uniformity using the χ 2 test of fit. The attacker begins by computing the 2 m • 2 |k| statistics ξ i k = # {(x, y) ∈ D : (α m-1 • x ⊕ f m-1 (y| χ ⊕k), . . . , α 0 • x ⊕ f 0 (y| χ ⊕k)) = i} (B.7)

These are then combined into the χ 2 statistic for each key:

Q k = 1 N 2 -m 2 m -1 i=0 ξ i k -N 2 -m 2 (B.8)
The attacker then chooses the subkey guesses k corresponding to the largest values of Q k .

Figure 1 :

 1 Figure 1: Attack on last round of a cipher.

  , while 2 |k0|+|k1|+|k2|+|k3| memory registers of n bits are required. (d) Select the subkey guesses with the largest values for |q(

Algorithm 7 :

 7 The PRESENT block cipher Input: A 64-bit plaintext x, an 80 or 128-bit key K. Output: A 64-bit ciphertext y. b ← x; K ← KeySchedule(K,31); // Compute all the round subkeys for i ← 0 to 30 do b 63 , . . . , b 0 ←-b 63 ⊕ κ i 63 , . . . , b 0 ⊕ κ i 0 ; // addRoundKey w 15 . . . w 0 ←-S(w 15 ) . . . S(w 0 ); // sBoxLayer b 63 , . . . , b 0 ←-b P -1 (63) , . . . , b P -1 (0) ; // pLayer end b 63 , . . . , b 0 ←-b 63 ⊕ κ 31 63 , . . . , b 0 ⊕ κ 31 0 ; // Whitening key return b

Figure 3 :

 3 Figure 3: Graphic representation of one round of PRESENT.

Figure 4 :

 4 Figure 4: Comparison of the expected advantage (with 0.95 probability) of some known linear attacksattacks on 26 and 27-round PRESENT for a given amount of data (in a DKP scenario).

Figure 5 :

 5 Figure5: The four groups of bits for the key recovery on last two rounds.

Figure 8 :

 8 Figure8: Our attack on 28-round PRESENT-128. In total there are 156 bits of the subkeys which need to be guessed, which have been indicated by a cross. However, if the |k T |= 114 bits of key which have been highlighted in (dark) red are known, then all the bits in (light) green can be deduced, which include all the necessary bits for the attack. The 64 bits to the right represent the half of the key register which is not used for the current round subkey.

Figure 9 :

 9 Figure 9: The results of our experiments testing the 1-bit and 2-bit distinguishers on 10-round PRESENT. The correlation for the right key was compared with 2 12 other random keys, thus obtaining an estimation of the advantage for up to 12 bits. The experiment was repeated with 20 different master keys and 20 data samples for each key and value of N .

PN

  S =P r x T k > N/2, |T k -N/2|> |T k -N/2| for all k =P r x T k -N/2 > 0, -(T k -N/2) < T k -N/2 < T k -N/2 for all k = (x-N ε) 2 dxThe desired expression is obtained after a change of variables in the previous integral.

  α•x⊕β•E K (x)⊕γ0•K0⊕...⊕γr•Kr ∈F n 2 K,K ∈F κ 2 (-1) α•x⊕α•x ⊕β•E K (x)⊕β•E K (x )⊕γ0•K0⊕...⊕γr•Kr⊕γ0•K 0 ⊕...⊕γr•K r = 1 2 2n+2κ x,x ∈F n 2 K,K ∈F κ 2 (-1) α•x⊕α•x ⊕β•E K (x)⊕β•E K (x )

  γ0•K0⊕...⊕γr•Kr⊕γ0•K 0 ⊕...⊕γr•K r = γ γ γ∈F n(r+1) 2

  10). Let E be a key-alternating cipher of r rounds with internal permutation F , and let Ĉ(F ) be the element-wise square of the correlation matrix of the round function. Then the ELP of a linear approximation of E with input mask α and output mask β isELP (α, β) = Ĉ(F ) r αβ (B.5)Proof. The equality is deduced from the definition of the ELP and the piling-up lemma:ELP (α, β) = x,K0,...,Kr (ν γ γ γ = 0) -P r x,K0,...,Kr (νγ γ γ = 1)) x (γ i-1 • x ⊕ γ i • F (x) = 0) -P r x (γ i-1 • x ⊕ γ i • F (x) = 1))

  Rotate key register 19 bits to the right κ 79 κ 78 κ 77 κ 76 ←-S(κ 79 κ 78 κ 77 κ 76 ); // Apply S-box on leftmost nibble κ 19 κ 18 κ 17 κ 16 κ 15 ←-κ 19 κ 18 κ 17 κ 16 κ 15 ⊕ i; ← 1 to r do κ 127 . . . κ 0 ←-κ 66 . . . κ 67 ; // Rotate key register 61 bits to the left κ 127 κ 126 κ 125 κ 124 ←-S(κ 127 κ 126 κ 125 κ 124 ); κ 123 κ 122 κ 121 κ 120 ←-S(κ 123 κ 122 κ 121 κ 120 ); // Apply S-box on 2 leftmost nibbles κ 66 κ 65 κ 64 κ 63 κ 62 ←-κ 66 κ 65 κ 64 κ 63 κ 62 ⊕ i;

																	addRoundKey
	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S	sBoxLayer
																	pLayer
															// Add 5-bit round counter
	κ i 63 . . . κ i 0 ←-κ 79 . . . κ 16 ;											// Extract round subkey
	end
	return {K i } r i=0 ;
	Algorithm 9: Key schedule of PRESENT-128
	Input: A master key K of 128 bits, a number of rounds r.
	Output: r + 1 round subkeys K i of 64 bits.
	κ 0 63 . . . κ 0 0 ←-κ 127 . . . κ 64 ;								// Extract the first round subkey
	for i r i=0 ;

Algorithm 8: Key schedule of PRESENT-80 Input: A master key K of 80 bits, a number of rounds r. Output: r + 1 round subkeys K i of 64 bits. κ 0 63 . . . κ 0 0 ←-κ 79 . . . κ 16 ; // Extract the first round subkey for i ← 1 to r do κ 79 . . . κ 0 ←-κ 18 . . . κ 19 ; // // Add 5-bit round counter κ i 63 . . . κ i 0 ←-κ 127 . . . κ 64 ; // Extract i-th round subkey end return {K i }

  Our attack on 27-round PRESENT using 128 approximations and taking account of the key schedule. All the necessary subkey bits can be deduced from the |k T |= 68 bits which have been highlighted in (dark) red.

	K0
	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S
								pLayer
	K1
	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S
								pLayer
								23 rounds
	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S
								pLayer
	K26
	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S	S
								pLayer
	K27
	Figure 7:

  • 8 = 96. It can also be shown that |k i 0 |≤ 32, |k i 1 |≤ 8, |k i 2 |≤ 8 and |k i 3 |≤ 32 for all approximations, and |k 0 |= 48, |k 1 |= 36, |k 2 |= 36, |k 3 |= 48. Figure

  Multidimensional linear cryptanalysis is used. ‡: Only one fourth of the known plaintexts is effectively used for each key guess.

	Rounds Appr. Capacity Data	Time (κ = 80)	Time (κ = 128)	Memory	PS PS PS	Source
		2995 †	2 -55.58	2 63.8	2 70	2 118	2 34	0.95	[Ch10]
	26	135 128	2 -55.47 2 -54.81	2 62 2 61.9	2 72 2 65	2 120 2 113	2 48 2 44	0.95 [BTV18] 0.95 This
		128	2 -54.81	2 60.8	2 72	2 120	2 44	0.95	This
		405 †	2 -55.33	2 63.8 ‡	2 77	2 125	2 70	0.95	[ZZ15]
	27	135	2 -58.06	2 63.8	2 77.5	2 125.5	2 48	0.95 [BTV18]
		128	2 -56.71	2 63.4	2 72	2 120	2 44	0.95	This
	28	448	2 -56.98	2 64	-	2 122	2 89	0.95	This
			†:

Table 4 :

 4 Comparison of linear attacks on PRESENT. All the time complexities have been evaluated using the same model assuming in a distinct known plaintext scenario.

MATSUI'S ALGORITHM 2 USING FFT

Search phase: The rest of the key is found by testing all the possibilities for the remainder of the key exhaustively until the correct key is found.Collard, Standaert and Quisquater showed in[START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF] that the Generalised Fast Fourier Transform (and, in particular, the Fast Walsh-Hadamard Transform) can speed up the time complexity of the analysis phase of the modified Algorithm 2 from O 2 2|k| to O |k|2 |k| in last-round attacks (the original paper also briefly discusses first and last-round attacks, as well as attacks on ciphers in which the round subkey is added modulo 2 n instead of being XORed). During this internship we described an extended version of the algorithm which can be used for any number of rounds at the beginning and/or the end of the cipher, and is inspired by several applications of the technique in subsequent papers ([NWW11],[START_REF] Zheng | FFT-based Multidimensional Linear Attack on PRESENT using the 2-bit-Fixed Characteristic[END_REF],[START_REF] Bogdanov | Multivariate Profiling of Hulls for Linear Cryptanalysis[END_REF]). This section contains both the original approach of[START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF] as well as our new generalised algorithm, and provides more accurate expressions of the time complexity. We also discuss how the key schedule might be exploited in generalised FFT-accelerated linear attacks.

Our attack can be found on https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/ as an official comment on the TRIFLE candidate or through this link.

3 MATSUI'S ALGORITHM 2 USING FFT that q i (k 0 , k 1 , k 2 , k 3 ) can be calculated as qi (k i 0 , k i 1 , k i 2 , k i 3 ) (where k i 0 = k 0 | χ i 0 is a part of k 0 , and so on), and that all the k i 0 , k i 1 , k i 2 and k i 3 (for all values of i) can be extracted from a part k T of the master key K, so Q(k 0 , k 1 , k 2 , k 3 ) = Q(k T ). We will also suppose that the sets of masks (χ i 0 , χ i 3 ) and (χ i 0 , χ i 1 , χ i 2 , χ i 3 ) take l 1 and l 2 different values over the set of M approximations, respectively. In this situation, the attacker can perform a modified algorithm:

1. Perform a modified distillation phase in which l 1 tables instead of one are constructed: one for each plaintext-ciphertext mask pair (χ i 0 , χ i 3 ).

2. For each approximation ν i , compute a table of length 2 |k i 0 |+|k i 1 |+|k i 2 |+|k i 3 | containing all the possible values of q i (k i 0 , k i 1 , k i 2 , k i 3 ) by using the algorithm from the previous subsection and the appropiate table from the distillation phase.

3. The M tables from the previous step are combined into l 2 "condensed" tables by adding the square correlations of approximations corresponding to the same choice of subkey bits, that is, one table for each possible value of (χ i 0 , χ i 1 , χ i 2 , χ i 3 ). In other words, given a fixed set of masks (X 0 , X 1 , X 2 , X 3 ), the associated condensed table contains the coefficients:

4. For each possible guess of the partial master key k T , use the key schedule to compute the associated values of k i 0 , k i 1 , k i 2 , k i 3 . Use the tables from the previous step to compute Q(k T ). Keep the key candidates with a large enough value of the statistic for the search phase.

Result 3.3. The improved linear attack algorithm using the bottom-up strategy has the following time complexity (ignoring significantly smaller terms):

and requires

This algorithm can produce large gains in the case of multiple linear cryptanalysis, but its success is more limited in multidimensional attacks, as there is always a linear approximation of maximum Hamming weight masks for which

A Mathematical background and notation

The purpose of this appendix is to provide an overview of some mathematical concepts which are used in the report, as well as establishing some notations, some of which are non-standard.

Binary vector spaces. We will begin by describing some properties of boolean vector spaces.

Definition A.1. Let F n 2 be the vector space of dimension n over the finite field F 2 = {0, 1}. There is an identification between the elements of this vector space and the natural numbers between 0 and 2 n -1, which takes the form of the following bijective map:

These two descriptions of F n 2 are used without distinction in this report. We will always consider that the rightmost bit of a binary vector is the least significant one. Additionally, sometimes binary vectors will be represented without parentheses as is common in Computer Science literature. All real vectors and matrices in this report are considered with coordinates starting at 0 (instead of the usual 1). We can define several operations on and between elements of F n 2 :

Definition A.2. Given x ∈ F n 2 , its Hamming Weight HW (x) is its number of non-zero coordinates. Given a binary vector x of any length, we will denote its length by |x|, that is, |x|= n if x ∈ F n 2 . We say that two vectors x, y ∈ F n 2 are disjoint if they don't share any non-zero coordinates. Given x, y ∈ F n 2 , then x⊕y ∈ F n 2 denotes the addition of x and y as vectors over F 2 . We use the symbol ⊕ instead of + to distinguish this operation from addition modulo 2 n when describing the elements of F n 2 as integers, as well as to keep consistency with the previous literature on linear cryptanalysis. Given x, y ∈ F n 2 , then x•y ∈ F 2 denotes the inner product of both vectors (which should not be confused with their product as integers), that is:

2 can also be concatenated:

as the vector of the components of x corresponding to the non-zero coordinates of y (this is not a standard notation).

The following is a useful result about the inner product: Proposition A.3. For any x ∈ F n 2 , the following equality holds:

Proof. The equality is clear when x = 0 0 0, since (-1) 0 = 1. In the case x = 0 0 0, the equality y • x = 0 is a non-trivial linear equation over F n 2 which is satisfied by the elements of a hyperplane, which has dimension n -1 and therefore has 2 n-1 elements. The sum is thus 2

The correspondence between elements of F n 2 and numbers between 0 and 2 n -1 induces a correspondence between the space of boolean functions over F n 2 and the vector space F 2 n 2 , as a boolean function can be seen as a vector whose components are the images of each element of F n 2 . This identification is compatible with the notion of the addition of maps, in the sense that the addition of two boolean functions corresponds to the addition of their representation as vectors. Additionally, the product of two maps is the same as the element-wise product of their vectorial representations.

The following definition mimics the definitions of bias and correlation in linear cryptanalysis, so that the bias of a linear approximation ν is just the bias of the boolean function

Definition A.5. The Hamming Weight of a boolean function f is

The bias of f is

We also define the correlation of f as

If X is a uniformly distributed random vector over F n 2 (or, equivalently, a uniformly distributed random variable over {0, . . . , 2 n -1}), then Y = f (X) is a random variable in F 2 , and we have the following alternative definitions of bias and correlation:

These magnitudes are all related by Proposition A.6. Let f : F n 2 -→ F 2 be a boolean function. Then

Proof. It suffices to look at the definitions and note that

The relationship follows from this equality.

The Fast Walsh-Hadamard Transform. We will now describe the Walsh-Hadamard Transform and its efficient computation algorithm.

Definition A.7. We define the family of matrices

Bernoulli distribution Be(p)

A discrete distribution which takes value 1 with probability p and 0 otherwise. Probability function: P r(X = 1) = p, P r(X = 0) = 1 -p Expected value: p Variance: p(p -1)

The sum of n independent Bernoulli random variables Be(p).

Expected value: np Variance: np(p -1) For a large enough value of n and a value of p that's not too close to 0 or 1, this distribution can be approximated by the normal distribution of the same expected value and variance.

Hypergeometric distribution HG(K, N, n)

The distribution of the number of successes among n ≤ N draws without replacement of a population of size N containing K ≤ N marked elements.

This distribution can be approximated by the normal distribution of the same expected value and variance, although the resulting error depends on the parameters.

Probability density function:

The distribution of the absolute value of normal random variable of the same parameters.

Probability density function:

i . The distribution is said to have m degrees of freedom and non-centrality parameter λ.

Cumulative distribution function: Ψ m,λ (x), Ψ m = Ψ m,0 Expected value: m + λ Variance: 2(m + 2λ) For a large enough value of m, this distribution can be approximated by the normal distribution of the same expected value and variance because of the Central Limit Theorem.

Table 5: Definitions, notations and properties of some probability distributions.

Algorithm 11: Multidimensional Algorithm 2 using the χ 2 statistic Input:

ciphertext pairs (possibly on-the-fly).

Output: A probable guess of k.

The probability of success depends on the capacity of the set of approximations, and in this case there is no need to suppose statistical independence:

). The probability of success of a multidimensional linear attack using M = 2 m -1 linear approximations depends on the number of available plaintexts N , the number of approximations and the capacity of the set of linear approximations, which is

B.3 The statistical model of subsection 2.4

B.3.1 Statistical attacks as a hypothesis testing problem

Selçuk introduced the notion of advantage that was discussed in subsection 2.4 in [START_REF] Selçuk | On Probability of Success in Linear and Differential Cryptanalysis[END_REF], and also provided a way of estimating the probability of success of this type of attack by using a result on order statistics. Subsequent reformulations such as the one found in [START_REF] Bogdanov | Zero Correlation Linear Cryptanalysis with Reduced Data Complexity[END_REF] have reframed the problem as a hypothesis testing scenario, which leads to the same estimate. Here we will discuss the latter approach. Given a guess for the partial subkey k, we want to test whether it corresponds to the actual secret key K (alternative hypothesis H 1 ) or whether it is a wrong guess (null hypothesis H 0 ). We are interested in the significance level α and the power 1-β of the test (not to be confused with the input and output masks of the linear approximations). The significance level α is the probability that the null hypothesis is rejected erroneously (probability of false alarm), in this case, the probability that a wrong guess is marked as a candidate for the search phase. Since we expect α2 |k| wrong key guesses to be marked as candidates, we deduce that α2 |k| 2 |k|-a . This means that, if we want to achieve an advantage of a, we should use a test with α = 2 -a . On the other hand, the power 1 -β is the probability that the null hypothesis is rejected when the alternative hypothesis is true (β is the probability of non-detection), in other words, the probability that the right guess for the subkey is marked as a candidate for the search phase. This means that the success probability of the attack is P S = 1 -β.

To distinguish between both hypotheses, we use a test statistic X k . In Matsui's Algorithm 2, this statistic is |T k -N/2| while in multiple or multidimensional attacks it's Q k . Let us suppose that, for the right guess of k, this statistic has a cumulative distribution function F R . Analogously, we will suppose that for any wrong guess, the distribution function is F W . We will consider a threshold Θ:

We reject the null hypothesis (keep the subkey guess as a candidate) if X k > Θ and accept it (discard the subkey guess) if X k < Θ. Usually, we will choose the significance level α = 2 -a according to the desired advantage and then take Θ = F -1 W (1 -α). The power of the test will then be β = F R (Θ). We deduce the following result about the probability of success: Theorem (2.13). Under the previous hypothesis testing model for a statistical attack, the success probability for a given desired advantage a is

If the right-key distribution can be approximated by a normal distribution N (µ R , σ 2 R ), then

If the wrong-key distribution can also be approximated by a normal distribution N (µ W , σ 2 W ), then

Since 1 -2 -a is close to 1, the normal approximation of F -1 W might induce a non-negligible error. For this reason we only recommend using this approximation when there is no other option.

Corollary B.4. ([Se08])

The probability of success of Algorithm 2 with target advantage a is

Proof. We will suppose that ε > 0 and γ(K) = 0. From the right-key equivalence and wrong-key randomisation hypotheses, we know that T k -N/2 follows the normal distribution N (N ε, N/4) if k is the right guess, and N (0, N/4) if it is a wrong guess. Therefore |T k -N/2| follows the folded normal distribution FN (N ε, N/4) for the right guess and FN (0, N/4) for any wrong guess. If X is a random variable with distribution N (0, N/4), we have

). We finish by substituting this in equation 2.22/B.12.

B.3.2 Distribution of the multiple linear cryptanalysis statistic

We will replicate the reasoning by Blondeau and Nyberg in [START_REF] Blondeau | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis[END_REF] to deduce the distribution of the multiple linear cryptanalysis statistics to plug into Selçuk's formula. We begin with updated versions of the right-key and wrong-key hipotheses. As usual, let ν i : α i • x ⊕ β i • ŷ be M linear approximations of the first r -1 rounds of the cipher, so that β i • F -1 (y ⊕ K r ) can be substituted by f i (y| χ ⊕k).

follow the normal distribution N (0, ELP (α i , β i )) and are statistically independent.

Since the ELP is the expected value of the square of the correlation, it is clear that it must be equal to the variance if the expected value of the correlation is zero.

Assumption B.6. (Wrong-key randomisation) The wrong-key empirical correlations ( k = k)

follow the normal distribution N (0, 2 -n ) and are statistically independent.

This assumption can be justified if we imagine that the value of

is a random variable which follows the binomial distribution B(1/2, 2 n ), and thus has expected value 2 n-1 and variance 2 n-2 . This means that the expected value of c W i (K, k) is 0 and its variance is 2 -n .

Distribution of the capacity. To calculate the estimated linear potentials the M linear approximations, we identify a set of "dominant" trails, as discussed in 2.2.1. In other words, we consider a set S of key masks γ so that the approximations ν i ⊕ γ • K are highly biased, while the rest have a much smaller correlation, and are modeled as random noise.

Theorem B.7 (Theorem 3 in [START_REF] Blondeau | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis[END_REF]). For each approximation ν i :

we can estimate the linear potential by choosing a set S containing the linear trails with the largest correlation contribution, and using the formula:

is uniformly distributed.

The next step towards an estimation of the success probability in the case of multiple linear cryptanalysis is finding the distribution of the capacity C(K) for the set of approximations.

Theorem B.8 (Theorems 4,5 in [START_REF] Blondeau | Improved Parameter Estimates for Correlation and Capacity Deviates in Linear Cryptanalysis[END_REF]). The expected value of the capacity of a set of M linear approximations ν i :

Meanwhile, the variance of C(K) is

Proof. These formulas are deduced from the assumption of the independence of the correlations and our previous estimation for the linear potential. In the case of the expected value, we have

For the variance, we have

Since we assumed 1/ELP (α i , β i )c i (K) follows a standard normal distribution, then its square 1/ELP (α i , β i ) (c i (K))

2 should follow a χ 2 distribution with one degree of freedom. This distribution has a variance of 2, so we deduce that V ar

Distribution of the right key and wrong key statistics. The final component of the model is the computation of the distribution of the right and wrong key statistics over the key K and the data D. Two different scenarios can be considered: the classical known plaintext attack (KP), where the plaintexts x are randomly drawn from F n 2 with replacement (so there can be repeated plaintextciphertext pairs in the data), or the distinct known plaintext attack (DKP), where the plaintexts are drawn without replacement and there are no repetitions. The difference between these two scenarios will be accounted for in the success probability estimations by changing the value of the constant

for DKP (B.20)

Theorem (2.14). In multiple and multidimensional linear cryptanalysis, the sttatistic Q k approximately follows a normal distribution whose mean and variance are the following:

Meanwhile, if the key guess k = k is different from the right one, a multiple of the wrong key statistic follows a χ 2 distribution with M degrees of freedom:

Proof. Here we will only consider the case of multiple linear cryptanalysis, although the result is also true for multidimensional attacks. We will begin by deducing the distribution of the right-key statistic. We initially consider that the key K is fixed. This means that α i • x ⊕ f i (y| χ ⊕k) ⊕ 1 is drawn from the Bernoulli distribution with parameter (1 + c i (K))/2. Therefore From this we deduce that q i k ∼ N (N c i (K), N B). We then obtain, for a fixed K,

Therefore, assuming a normal approximation of the χ 2 distribution,

We now proceed to the case of the wrong key statistic. For a fixed K, we now have

, N for KP # (x, y) ∈ D :

2 n , 2 n , N for DKP Therefore q i k ∼ N (N c W i (K, k), N B) for a fixed key K and q i k ∼ N (0, N B + N 2 2 -n ) when K and D are uniformly distributed. We thus deduce

which concludes the proof.