Antonio Flórez-Gutiérrez

Optimising Linear Key Recovery Attacks with Ane Walsh Transform Pruning

Keywords: Linear cryptanalysis, Key recovery attacks, FFT, Walsh Transform, Pruning, DES, PRESENT Fast Key Recovery Algorithms

 have drawn attention towards the possibility of reducing their time complexity using the fast Walsh transform. These previous contributions ignore the structure of the key recovery rounds, which are treated as arbitrary boolean functions. In this paper, we optimise the time and memory complexities of these algorithms by exploiting zeroes in the Walsh spectra of these functions using a novel ane pruning technique for the Walsh Transform. These new optimisation strategies are then showcased with two application examples: an improved attack on the DES [1] and the rst known atttack on 29-round .

Introduction

General Background Linear Cryptanalysis. Matsui's linear cryptanalysis [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] is a widely studied family of statistical cryptanalysis against block ciphers and other symmetric constructions, and any new proposals are expected to justify their resilience against it. Linear attacks are commonly turned into key recovery attacks, in which a linear distinguisher is extended by one or more rounds by incorporating a key guess.

If the attack requires a data complexity of N and l bits of the key are guessed, the time complexity of a standard linear key recovery attack is O (N ) + O 2 2l [START_REF] Matsui | The rst experimental cryptanalysis of the Data Encryption Standard[END_REF].

2 of the correlation for each guess:

cor(k) = 1 N (x,y)∈D
(-1) α,x + β,F -1 k (y) .

(

) 2
If the value of k corresponding to the correct key K appears within the largest 2 |k|-a in the list 3 , we say that the attack achieves an advantage of a [START_REF] Selçuk | On probability of success in linear and dierential cryptanalysis[END_REF]. As a rule of thumb, the attack requires O cor(α, β) -2 data pairs to succeed. In this paper we use the more precise model of Blondeau and Nyberg [START_REF] Blondeau | Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity[END_REF].

Multiple linear approximations. It is common for linear attacks to make use of more than one linear approximation [START_REF] Biryukov | On multiple linear approximations[END_REF][START_REF] Hermelin | Multidimensional linear cryptanalysis[END_REF]. In the PRESENT attack we use the χ 2 multiple linear cryptanalysis statistic:

Q(k) = M i=1 cor i (k) 2 , (3)
where cor i (k) denotes the experimental correlation for the i-th approximation.

In a multiple linear attack, the data complexity is determined by the capacity C = M i=1 cor(α i , β i ) 2 . Detailed models were given by Blondeau and Nyberg [START_REF] Blondeau | Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity[END_REF].

The Walsh Transform

Denition 1 Let f : F n 2 -→ C be a complex-valued function on F n 2 . We refer to the space of functions of this kind as CF n 2 , which is isomorphic to C 2 n . The Hadamard or Walsh transform of f is another map f : F n 2 -→ C given by 4

f (u) = x∈F n 2
(-1) u,x f (x).

(4) 2 The notation cor should not be confused with the Walsh transform f . 3 |x| will denote the number of bits of a binary vector x. 4 It is common to use the normalised Hadamard transform, which is divided by √ 2 n , but for the purposes of this paper we will not use this factor in the denition.

The transform of any vector in CF n 2 can be computed eciently using: f (u) =

x n-2 ∈F 2 . . .

x 0 ∈F 2 (-1) u n-2 x n-2 +...+u 0 x 0 f (0, x l-2 , . . . , x0) + (-1) u n-1

x n-2 ∈F 2 . . .

x 0 ∈F 2 (-1) u n-2 x n-2 +...+u 0 x 0 f (1, x l-2 , . . . , x0). [START_REF] Biham | Dierential cryptanalysis of the full 16-round DES[END_REF] This formula, in a divide-and-conquer approach, leads to the fast Walsh transform algorithm [START_REF] Cooley | An algorithm for the machine calculation of complex Fourier series[END_REF], which has a time complexity of n2 n additions/subtractions.

An associated transformation can be dened for (vectorial) boolean functions: Denition 2 Let g : F n 2 -→ F m 2 be any vectorial boolean function. We dene its Walsh transform as the map g : F n 2 × F m 2 -→ C given by the formula

g(u, v) = x∈F n 2 (-1) u,x ⊕ v,g(x) . ( 6
)
The coecients of this map g are often called the Walsh spectrum of g. It is a complex matrix whose columns are the Walsh transforms of ind g,v : x → (-1) v,g(x) , complex representations of its linear components x → v, g(x) . When m=1 we can ignore the second input and assume v = (1) to dene g(u). We will also use the Walsh spectrum restricted to a subset X:

Denition 3 Let g : F n 2 -→ F m
2 be a vectorial boolean function, and X ⊆ F n 2 a subset of its domain. The Walsh transform of g restricted to X is dened as (x) . [START_REF] Blondeau | Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis[END_REF] We dene the transform restricted to Y ⊆ F m 2 as g g(x)∈Y = g x∈g -1 (Y ) .

g x∈X (u, v) = x∈X (-1) u,x ⊕ v,g

Walsh Transform-accelerated Linear Cryptanalysis

FFT-accelerated linear cryptanalysis was introduced by Collard et al. [START_REF] Collard | Improving the time complexity of Matsui's linear cryptanalysis[END_REF]. Flórez-Gutiérrez et al. [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF] provided a two-matrix description for instances in which the linear approximation can be separated into two independent parts, such as when key recovery is considered on both the plaintext and the ciphertext sides. We now show a small generalisation of this approach using d-dimensional arrays.

We consider a linear approximation whose value can be expressed as

f 0 (x) ⊕ f 1 (x 1 ⊕ k O 1 , k I 1 ) ⊕ • • • ⊕ f d (x d ⊕ k O d , k I d ) F (X⊕K O ,K I ) , (8)
where (x 1 , . . . , x d ) = X are separate parts of the plaintext-ciphertext pair x (we denote this by x → X). (k O 1 , . . . , k O d ) = K O is outer key material which is xored directly to x, and (k I 1 , . . . , k I d ) = K I is additional inner key material. Our aim is to compute all values of the experimental correlations cor(K O , K I ):

N • cor(K O , K I ) = x∈D (-1) f0(x)⊕f1(x1⊕k O 1 ,k I 1 )⊕...⊕f d (x d ⊕k O d ,k I d ) = X (-1) F (X⊕K O ,K I ) x∈D x →X (-1) f0(x) A[X] = 1 2 |X| Y (-1) K O ,Y Z (-1) Y,Z (-1) F (Z,K I ) X (-1) Y,X A[X] = 1 2 |X| Y (-1) K O ,Y d i=0 f i (y i , k I i ) A[Y ], (9)
using the convolution theorem. The attack can be performed as follows: ity of the search phase is given by models such as [START_REF] Blondeau | Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity[END_REF].

1. For each f i , precompute 2 |k I i | tables of size 2 |k O i | containing f i ( • , k I i ).
Other improvements to this algorithm were proposed by Flórez-Gutiérrez et al. [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF], most notably in the case of multiple linear cryptanalysis. By separating the key guesses into groups, it is possible to perform a complete" key guess k T (accounting for any dependencies which are induced by the key schedule) while still using the FFT algorithm on dierent parts of the key guess for each individual approximation. The authors also introduced some Walsh transform pruning techniques for cases in which some external keybits can be deduced from the internal keybits. This paper builds on that improvement.

DES Specication

The Data Encryption Standard [START_REF]Data Encryption Standard (DES). Federal Information Processing Standards Pub[END_REF] is one of the most widely analysed block ciphers due to its use in the industry. It has a block length of 64 bits and

x [63] x [48] x [START_REF] Sreenivas | FFT algorithm for both input and output pruning[END_REF] x [START_REF] Collard | Improving the time complexity of Matsui's linear cryptanalysis[END_REF] x[0] (L 0 , R 0 ) ← IP (P );

Ki

S S S S S S S S S S S S S S S S

for i ← 1 to 16 do L i ← R i-1 ; R i ← L i-1 ⊕ f (R i-1 , K i ); end C ← IP -1 (R 16 , L 16 );
where IP is a xed initial permutation and each K i is a 48-bit round subkey.

The round function f . First, an expansion function E is applied on the 32-bit input to obtain a 48-bit string. This string is xored with the round subkey, and eight dierent 6-to-4-bit Sboxes S 1 , . . . , S 8 are applied to obtain a 32-bit string. Finally, an output permutation P is applied.

The key schedule. It extracts sixteen 48-bit subkeys K 1 , . . . , K 16 from the key:

(C 0 , D 0 ) ← P C 1 (P );

for i ← 1 to 16 do

C i ← LS p(i) (C i-1 ); D i ← LS p(i) (D i-1 ); K i ← P C 2 (C i , D i );
end where C i and D i are 28 bits long, P C 1 and P C 2 are two permutated choices, LS j is a j bit rotation to the left, and p(i) is either 1 or 2.

Notation. In this paper, X[j] will denote the j-th rightmost (least signicant) bit of X, starting from 0. We will also ignore IP , IP -1 and P C 1 and denote

P = (L 0 , R 0 ), C = (R 16 , L 16 ), K = (C 0 , D 0 ) instead.

PRESENT Specication

PRESENT [START_REF] Bogdanov | PRESENT: an ultra-lightweight block cipher[END_REF] is a lightweight block cipher which has received substantial attention from cryptanalysts since its inroduction, and is a popular target for linear Notation. We denote the i-th rightmost bit of X starting from 0 by X[i].

Ane Pruned Walsh Transform Algorithm

In order to remove unnecesary computations from the algorithm of Section 2.3, we must eciently compute the Walsh transform when the non-zero inputs or desired outputs are limited to previously-known xed subsets of F n

2 . An algo- rithm which obtains the desired outputs with less computations than the full" fast transform will be called a pruned fast Walsh transform algorithm. The case of xed values for some output position bits was already considered by Flórez-Gutiérrez et al. in [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF]. Our algorithms generalise this result.

Denition 4 (Problem statement) Let f : F n 2 -→ C be any vector in CF n 2 . We assume that lists L, M ⊆ F n 2 are given, and that f

(x) = 0 for all x ∈ F n 2 \ L.
The aim is to compute f (y) for all y ∈ M with as few operations as possible.

Overview of Previous Results for the One-dimensional DFT

The pruning problem has already been studied for the one-dimensional discrete Fourier transform (DFT), as it arises naturally in some applications. Markel [START_REF] Markel | FFT pruning[END_REF] prunes the decimation-in-frequency algorithm for the case in which L consists of the rst 2 r , r < s points of the input. Similarly, Skinner [START_REF] Skinner | Pruning the decimation in-time FFT algorithm[END_REF] prunes the decimation-in-time algorithm for the case in which L consists of the rst 2 r points in bit-reversed order. An algorithm limiting both inputs and outputs at the same time was introduced by Sreenivas and Rao [START_REF] Sreenivas | FFT algorithm for both input and output pruning[END_REF]. A pruned decimation-in-time algorithm which can compute the outputs in a consecutive (but possibly shifted) frequency window was presented by Nagai [START_REF] Nagai | Pruning the decimation-in-time FFT algorithm with frequency shift[END_REF]. Sorensen and Burrus [START_REF] Sorensen | Ecient computation of the DFT with only a subset of input or output points[END_REF] proposed an alternative transform decomposition technique, which maps the nonzero inputs to a series of smaller DFTs, and then combines the results. All these algorithms exhibit similar complexities: evaluating 2 r points of a 2 n point transform costs O (r2 n ). However, an interesting phenomenon was observed by Shousheng and Torkelson [START_REF] He | Computing partial DFT for comb spectrum evaluation[END_REF]: when the subset of outputs M is a comb of equidistant points, a smaller complexity of O (2 n + r2 r ) can be achieved.

Alves et al. [START_REF] Alves | General FFT pruning algorithm[END_REF] introduced the rst traceback pruning method for arbitrary input or output sets. Hu and Wan [START_REF] Hu | A novel generic fast Fourier transform pruning technique and complexity analysis[END_REF] showed a similar technique and found the average complexity as a function of n, |L| and |M |. The overhead computations were reduced by Singh and Srinivasan [START_REF] Singh | Architecturally ecient FFT pruning algorithm[END_REF]. Pruning has been recently generalised to mixed-radix and composite length DFTs in works such as [START_REF] Wang | Generic mixed-radix FFT pruning[END_REF][START_REF] Castro-Palazuelos | Unied commutation-pruning technique for ecient computation of composite DFTs[END_REF].

We consider the pruning problem for the Walsh transform or (2, . . . , 2)dimensional DFT, specically the case when L and M lie in ane subspaces of F n 2 . Our algorithm takes a dierent approach to the works mentioned above: we reduce the Walsh transform to one of signicantly smaller dimension.

Walsh Transform Pruning for Ane Sets

We now describe a pruned algorithm which can be used when both the input and output sets of the Walsh transform lie in ane subspaces of F n 2 .

Denition 5 (Ane pruning problem) Let f : F n 2 -→ C be a vector. We are given lists L, M ⊆ F n 2 , vector subspaces X, U ⊆ F n 2 and vectors x 0 , u 0 ∈ F n 2 so that L ⊆ x 0 + X, M ⊆ u 0 + U , and f (x) = 0 for all x ∈ L. The aim is to compute f (y) for all y ∈ M with as few operations as possible.

Example. Consider the Walsh transform of size 16 = 2 4 . The fast transform requires 4 • 2 4 = 64 additions. Let the lists L = x 0 + X and M = u 0 + U be x 0 = (0, 0, 1, 0), X = span {(0, 0, 0, 1), (0, 1, 1, 0), (1, 0, 1, 0)} , u 0 = (0, 1, 0, 0), U = span {(0, 0, 0, 1), (0, 0, 1, 0), (1, 1, 0, 0)} .

A traceback-based pruning approach as done in [START_REF] Markel | FFT pruning[END_REF][START_REF] Skinner | Pruning the decimation in-time FFT algorithm[END_REF][START_REF] Sreenivas | FFT algorithm for both input and output pruning[END_REF][START_REF] Nagai | Pruning the decimation-in-time FFT algorithm with frequency shift[END_REF][START_REF] He | Computing partial DFT for comb spectrum evaluation[END_REF][START_REF] Alves | General FFT pruning algorithm[END_REF][START_REF] Hu | A novel generic fast Fourier transform pruning technique and complexity analysis[END_REF] is shown in Figure 2. By removing unnecesary computations from the fast Walsh transform, we obtain the desired outputs with 32 additions and subtractions. Let us examine the expressions for each of the outputs: f0100 = +f0010 +f0011 -f0100 -f0101 +f1000 +f1001 -f1110 -f1111 f0101 = +f0010 -f0011 -f0100 +f0101 +f1000 -f1001 -f1110 +f1111 f0110 = -f0010 -f0011 -f0100 -f0101 +f1000 +f1001 +f1110 +f1111 f0111 = -f0010 +f0011 -f0100 +f0101 +f1000 -f1001 +f1110 -f1111 f1000 = +f0010 +f0011 +f0100 +f0101 -f1000 -f1001 -f1110 -f1111 f1001 = +f0010 -f0011 +f0100 -f0101 -f1000 +f1001 -f1110 +f1111 f1010 = -f0010 -f0011 +f0100 +f0101 -f1000 -f1001 +f1110 +f1111 f1011 = -f0010 +f0011 +f0100 -f0101 -f1000 +f1001 +f1110 -f1111

We observe the following properties: f0100 = -f1010, f0101 = -f1011, f0110 = -f1000, f0111 = -f1001

The dierence in the indices in each of these pairs is (1, 1, 1, 0), which is orthogonal to X. There are also pairs of inputs which always appear with opposite signs: (f 0010 , f 1110 ), (f 0011 , f 1111 ), (f 0100 , f 1000 ), and (f 0101 , f 1001 ). In this case, the dierence between the indices is (1, 1, 0, 0), which is orthogonal to U . This suggests an algorithm which subtracts the input pairs from each other at the beginning and duplicates the output pairs at the end, such as the one in Figure 3. With the appropriate intermediate values, the size 2 4 transform is reduced to a size 2 2 transform. The total cost is 24 additions and subtractions.

We now proceed to formalise the trick", starting with the following lemma: Lemma 6 Let X, U ⊆ F n 2 be vector subspaces of F n 2 . We can dene t as

t := dim X X ∩ U ⊥ = dim U U ∩ X ⊥ . (10) f 1111 f 1111 f 1111 f 1110 f 1110 f 1110 f 1001 f 1001 f 1001 f 1000 f 1000 f 1000 f 0101 f 0101 f 0101 f 0100 f 0100 f 0100 f 0011 f 0011 f 0011 f 0010 f 0010 f 0010 -f 0101 + f 1001 +f 0011 -f 1111 -f 0100 + f 1000
f 1011 f 1011 f 1011 f 1010 f 1010 f 1010 f 1001 f 1001 f 1001 f 1000 f 1000 f 1000 f 0111 f 0111 f 0111 f 0110 f 0110 f 0110 f 0101 f 0101 f 0101 f 0100 f 0100 f 0100
Fig. 3: Organising the inputs and outputs carefully allows us to reduce the cost of the transform to just 24 operations.

There exist isomorphisms

φ : X/(X ∩ U ⊥ ) ∼ = -→ F t 2 and ψ : U/(U ∩ X ⊥ ) ∼ = -→ F t 2
which preserve the inner product:

y, v = φ(y), ψ(v) for all y ∈ X X ∩ U ⊥ , v ∈ U U ∩ X ⊥ . (11)
Proof. The equality of the dimensions is a consequence of the dimension formula and the properties of orthogonal spaces. It is also easy to show that the inner product y, v is well-dened for any y ∈ X/(X ∩ U ⊥ ) and v ∈ U/(U ∩ X ⊥ ).

We will construct a pair of orthonormal" bases starting from two arbitrary bases {y 1 , . . . , y t } and {v 1 , . . . , v t }. We will rst ensure y 1 , v j = δ 1j for all j and y i , v 1 = δ i1 for all i, and then work recursively. There is at least one j so that y 1 , v j = 1 (if y 1 ⊥ v j for all j, we'd have y 1 ⊥ U , y 1 = 0). We swap the v j so that y 1 , v 1 = 1. We then modify both bases as follows:

y new 1 = y 1 y new i = y i + y i , v 1 y 1 for all i = 1 v new 1 = v 1 v new j = v j + y 1 , v j v 1 for all j = 1
These new bases have the following properties:

y new 1 , v new 1 = y 1 , v 1 = 1 y new 1 , v new j = y 1 , v j + y 1 , v j y 1 , v 1 = 0 for all j = 1 y new i , v new 1 = y i , v 1 + y i , v 1 y 1 , v 1 = 0 for all i = 1
This process can be iterated on the rest of the elements until we obtain a pair of bases {y 1 , . . . , y t } and {v 1 , . . . , v t } which verify y i , v j = δ ij . We obtain φ and ψ by mapping these bases to the standard basis of F t 2 .

This lemma provides the basis for the following result and Algorithm 1:

Proposition 7 Let f be the Walsh transform of f ∈ CF n 2 . We are given lists

L ⊆ x 0 + X ⊆ F n 2 and M ⊆ u 0 + U ⊆ F n 2
, where x 0 + X and u 0 + U are ane subspaces, and assume

f (x) = 0 for all x ∈ L. Let t = dim X/(X ∩ U ⊥ ) = dim U/(U ∩ X ⊥ ) .
There is an algorithm which computes f (u) for all u ∈ M with |L| + t2 t + |M | additions using 2 t memory registers.

Algorithm 1: Fast Walsh transform pruned to ane subspaces Parameters:

L ⊆ x0 + X ⊆ F n 2 , M ⊆ u0 + U ⊆ F n 2 , (X, U subspaces). Input: f : L -→ C Output: f : M -→ C BX = {y1, . . . , yt} ← GetBasis(X/(X ∩ U ⊥ )); BU = {v1, . . . , vt} ← GetBasis(U/(U ∩ X ⊥ )); for k ← 1 to t -1 do GG qenerte 4good4 ses while y k , v k = 0 do (v k , v k+1 , . . . , vt-1, vt) ← (v k+1 , v k+2 , . . . , vt, v k ); for i ← k + 1 to t do yi ← yi + yi, v k y k ; for j ← k + 1 to t do vj ← vj + y k , vj v k ; end let g : F t 2 -→ C, g(y) = 0 ∀y ∈ F t 2 ; foreach x ∈ L do GG esor the nonzero inputs (i1, . . . , it) ← GetCoordinates(x -x0, BX ); g(i1, . . . , it) ← g(i1, . . . , it) + (-1) x-x 0 ,u 0 f (x); end g ← FWT(g) ; GG pst lsh trnsform of size P¢t foreach u ∈ M do GG qenerte the desired outputs (j1, . . . , jt) ← GetCoordinates(u -u0, BU ); f (u) ← (-1) x 0 ,u g(j1, . . . , jt); end return f Proof. Let u = u 0 + u , u ∈ U be one of the desired outputs. f (u) = x∈F n 2 (-1) u,x f (x) = x ∈X (-1) u,x0 + u ,x + u0,x f (x 0 + x ) = (-1) u,x0 y∈X/(X∩U ⊥ ) (-1) u ,y x ∈y (-1) u0,x f (x 0 + x ),
where x ∈ y means that x is a representative of the class y, in other words, y = x + (X ∩ U ⊥ ). This suggests the following algorithm:

1. For each y ∈ X/(X ∩ U ⊥ ), compute g(y) =

x ∈y (-1) u0,x f (x 0 + x ), forming an array g of length 2 t . We go over all x ∈ L, compute x = x -x 0 , and add f (x) to the bin corresponding to the class of x . This costs at most |L| additions. We do not need to store any entries of f in memory. 2. We apply the fast Walsh transform on g with t2 t additions. The result is a vector g which contains, for each v ∈ V ∈ U/(U ∩ X ⊥ ):

g(v) = y∈X/(X∩U ⊥ ) (-1) v,y
x ∈y (-1) u0,x f (x 0 + x ).

Lemma 6 justies the validity of this step.

3. For each output u ∈ M , separate u = u 0 + u , and sign-swap the entry of g indexed under the class of u according to x 0 , u to obtain f (u). The total cost is at most |M |. Each output can be queried individually, and we can even store the vector g and query any output in O (1) afterwards.

Example. We return to the example to illustrate how the algorithm of Figure 3 is justied by proposition 7. Indeed, U ∩ X ⊥ = X ⊥ = span {(1, 1, 1, 0)} and X ∩ U ⊥ = U ⊥ = span {(1, 1, 0, 0)}, so t = 2 and the transform reduces to one of size 2 2 . The inputs and outputs of the reduced transform correspond to the bases ((0, 1, 1, 0), (0, 0, 0, 1)) of X/(X ∩ U ⊥ ) and ((0, 0, 1, 0), (0, 0, 0, 1)) of U/(U ∩ X ⊥ ).

A Small Generalisation

We have described a pruned fast Walsh transform algorithm which is eective when the inputs and/or outputs are restricted to ane subspaces of small dimension. We have also shown that the time complexity doesn't just depend on the dimensions of these subspaces, but also on their orthogonality. The next natural step is to look into algorithms for arbitrary subsets of F n 2 .

We can nd the smallest subspaces which cover all inputs and outputs by choosing random x 0 ∈ L and u 0 ∈ M and picking X = span ({x

-x 0 } x∈L ) and U = span ({u -u 0 } u∈M ). However, if |L|, |M | n it is very likely that X = U = F n
2 , and we just obtain the traditional fast Walsh transform algorithm. This is the case in the applications later in the paper.

In these applications, however, the nonzero coecients can be covered by a small amount of low dimension subspaces. We assume that we separate the lists

L and M as disjoint unions L = L 1 ∪ • • • ∪ L p and M = M 1 ∪ • • • ∪ M q . Let
's also assume that there exist x 1 0 , . . . , x p 0 and u 1 0 , . . . , u q 0 , as well as X 1 , . . . , X p and U 1 , . . . , U q so that L i ⊆ x i 0 + X i and M j ⊆ u j 0 + U j . Although the list families {L i } and {M j } are disjoint, the ane subspace families {x i 0 + X i } and {u j 0 + U j }

need not be disjoint. Because of the linearity of the Walsh transform, we can compute the transform for each pair (L i , M j ) separately, and combine the results at the end. Let t ij := dim X i /(X i ∩ U ⊥ j ) . The time complexity is:

q|L| + p i=1 q j=1 t ij • 2 tij + p|M | additions/subtractions. ( 12
)
4 Zeros in the Walsh Spectra of SPN Constructions

This section adapts some previously-known results on the Walsh transform (see [START_REF] Carlet | Boolean Functions for Cryptography and Coding Theory[END_REF]) to quickly identify zeroes in the Walsh spectra of block cipher constructions which alternate a bricklayer nonlinear map and a linear transformation, such as Substitution Permutation Networks. We also illustrate how in some cases slightly modifying to the key recovery map so that it rejects some plaintexts can drastically reduce the number of nonzero coecients.

Lemma 8 Let f :

F n 2 -→ F m 2 , f (x) = Lx ⊕ c, where L ∈ GL(F n 2 , F m 2 ) is a linear map and c ∈ F m 2 is a constant. Then f (u, v) = 0 if u = L T v (-1) v,c 2 n if u = L T v for all u ∈ F n 2 , v ∈ F m 2 . ( 13
)
Lemma 9 Let f i :

F ni 2 -→ F mi 2 , i = 1, .
. . , d be d vectorial boolean functions. We consider the bricklayer map F :

F i ni 2 -→ F i mi 2 , which is ob- tained by concatenation, F(x 1 , . . . , x d ) = (f 1 (x 1 ), . . . , f d (x d )).
Then, for any

(u 1 , . . . , u d ) ∈ F n1 2 × . . . × F n d 2 and (v 1 , . . . , v d ) ∈ F m1 2 × . . . × F m d 2 , we have F((u 1 , . . . , u d ), (v 1 , . . . , v d )) = d i=1 f i (u i , v i ). (14)
Note that if

m i = 1 and f i is balanced, then f i (u i , v i ) =    f i (u i ) if v i = 1 0 if u i = 0, v i = 0 2 ni if u i = 0, v i = 0 . Lemma 10 Let f : F n 2 -→ F l 2 and g : F l 2 -→ F m 2 be vectorial boolean functions. Let X ⊆ F n 2 , Z ⊆ F l 2 and Y ⊆ F m 2 be subsets. We have 2 l g • f (u, v) = w∈F l 2 f (u, w) • g(w, v) (15)
2 l g • f x∈X (u, v) = w∈F l 2 f x∈X (u, w) • g(w, v) (16
)

2 l g • f g•f (x)∈Y (u, v) = w∈F l 2 f (u, w) • g g(z)∈Y (w, v) (17)
2 l g • f f (x)∈Z (u, v) = w∈F l 2 f f (x)∈Z (u, w) g(w, v) = w∈F l 2 f (u, w) g z∈Z (w, v) (18)
Using these results, we can often obtain compact formulas for the Walsh coecients of some key recovery maps, such as the following:

Proposition 11 Let f i : F n 2 -→ F li 2 be d balanced vectorial boolean functions, let L : F i li 2 -→ F l
2 be a linear map, and let g : F l 2 -→ F 2 be a boolean function. In the applications, the f i will be some Sboxes with possibly truncated outputs, L will be a truncation of the linear layer, and g will be a linear combination of outputs of an Sbox layer. We also consider a subset Z ⊆ F l 2 . We consider the composition h = g • L • F, where F is the bricklayer function F(x 1 , . . . , x d ) = (f 1 (x 1 ), . . . , f d (x d )). The Walsh coecients of h can be obtained through the following formula:

h L(F(x))∈Z (u 1 , . . . , u d ) = 1 2 l w1∈F l 1 2 • • • w d ∈F l d 2 v∈F l 2 wi=0 if ui=0 (w1,...,w d )=L t v d i=1 f i (u i , w i ) g z∈Z (v). (19)
Proof. We use Lemma 10 to write the Walsh coecients of h as

h L(F(x))∈Z (u 1 , . . . , u d ) = 1 2 i li+l w∈F i l i 2 v∈F l 2 F(u, w) L(w, v) g z∈Z (v).
According to Lemma 8, L(w, v) = 0 if and only if w = L t v, in which case L(w, v) = 2 i li . This means we only have to consider the sums over the w i for which an appropriate v exists, and vice versa. Furthermore, we can write F(u, w) = d i=1 f i (u i , w i ) according to Lemma 9. Since f i (0, w i ) = 0 if w i = 0, we can assume w i = 0 for the i for which u i = 0.

In particular, for the case in which all l i = 1:

Corollary 12 Let f i : F ni 2 -→ F 2 be l boolean functions and g : F l 2 -→ F 2 . We consider h(x 1 , . . . , x l ) = g(f 1 (x 1 ), . . . , f d (x l )) and the subset Z ⊆ F d 2 . Then h F(x)∈Z (u 1 , . . . , u l ) = 2 i,u i =0 ni 2 l g z∈Z (w(u 1 , . . . , u l )) i,ui =0 f i (u i ),
where w(u 1 , . . . , u l ) i = 0 if u i = 0 1 if u i = 0 .

We'll show how the previous result describes h f (x)∈Z and its zeroes in a compact manner. We rst look at g z∈Z . Given any w ∈ F l 2 so that g z∈Z (w) = 0, we can deduce that h F(x)∈Z (u 1 , . . . , u l ) = 0 for all (u 1 , . . . , u l ) so that w = w(u 1 , . . . , u l ). Furthermore, for the (u 1 , . . . , u l ) for which g z∈Z (w(u 1 , . . . , u l )) = 0, the Walsh coecient h F(x)∈Z (u 1 , . . . , u l ) can be written as the product of g z∈Z (w(u 1 , . . . , u l )) and the f i (u i ) corresponding to each u i = 0.

An interesting situation appears when g z∈Z (1, . . . , 1) = 0. Given (u 1 , . . . , u l ) so that u i = 0 for all i, we know that h F(x)∈Z (u 1 , . . . , u l ) = 0, and any nonzero Walsh coecient must verify u i = 0 for at least one i. As a result, the nonzero Walsh coecients can be separated into l vector subspaces U i of dimensions j =i n j -n i . Each U i is determined by the n i linear equations u i = 0. When g(1 . . . 1) = 0, we obtain this decomposition without any modications to the key recovery map. When g(1 . . . 1) = 0, we would like to choose some large Z ⊆ F d 2 so that g z∈Z (1, . . . , 1) = 0. We can use the following result:

Proposition 13 Let g : F l 2 -→ F 2 be a map for which g(1 . . . 1) = a = 0. There exists Z ⊆ F l 2 with |Z| = 2 l -|a| so that g z∈Z (1 . . . 1) = 0.

We have substituted the key recovery map, which normally takes values ±1

depending on the linear approximation, for a modied map which is zero when F(x) ∈ Z. From the perspective of the attack, we are rejecting the plaintextciphertext pairs for which the input of g is not in Z. Assuming independence, the resulting attack has the same parameters except for the data complexity, which increases by a factor of 2 l /|Z| to compensate the rejected plaintexts.

These results describe static key recovery maps F (X ⊕ K O ) without inner key guesses. We must also consider maps of the form F (X ⊕ K O , K I ). When all l i = 1 , the xoring of a round subkey between rounds only changes the Walsh coecient signs, and the positions of the zero coecients remain unaltered:

Corollary 14 Let f i : F ni 2 -→ F 2 be l boolean functions, g : F l 2 -→ F 2 ,

and let

k ∈ F l 2 be a xed parameter. We consider the parametric function h(x 1 , . . . , x l ; k) = g((f 1 (x 1 ), . . . , f l (x l )) ⊕ k) and the subset Z ⊆ F l 2 . Then h(•, k) F(x)⊕k∈Z (u 1 , . . . , u l ) = (-1) k,w(u1,...,u l ) h(•, 0) F(x)∈Z (u 1 , . . . , u l ).

Optimised Attack Algorithm

We now provide a linear key recovery algorithm which makes use of the ane pruned Walsh transform. We assume that the target linear approximation is of the form f 0 (x) + f (X ⊕ K O , K I ), but it also applies to key recovery maps with several parts. We will also make some redundancy assumptions:

The parts of the plaintext-ciphertext pair X which are xored with the outer key guess K O lie in an ane subspace of the form

x 0 + Y ⊆ F |K O | 2 .
The nonzero Walsh coecients of F (•, 0) lie in the union of l ane subspaces

u i 0 + U i ⊆ F |K O | 2
. We denote the number of nonzero coecients in u i 0 + U i by |L i |. We also assume that the nonzero Walsh coecients of F (•, K I ) occupy the same subspaces. If the latter is not true, each value of K I must be treated separately, and the cost of the analysis phase is multiplied by 2 |K I | .

Given the key schedule of the cipher, for a given guess of K I , the possible values of K O lie within an ane subspace of the form v

K I 0 + V K I ⊆ F |K O | 2 .
We denote the dimensions of the relevant quotient spaces for the rst Walsh transform as

t i = dim Y /(Y ∩ U ⊥ i ) .
For the last set of Walsh transforms, we assume that these dimensions are constant for all the K I , that is

r i = dim U i /(U i ∩ V ⊥ K I ) for all K I ∈ F |K I | 2
. This assumption is not necessary but it simplies the complexity calculation.

The broad idea of the attack procedure is to compute cor(•, K I ) as the sum of l linear transformations of A. Each linear operation corresponds to the part of the Walsh spectrum of F which lies in the ane subspace u

i 0 + U i ⊆ F |K O | 2 .
The full attack algorithm is the following:

1. Distillation phase: We can merge the rst step of the rst pruned Walsh transform into the distillation phase to save time and memory. Depending on the relative sizes of N and 2 dim(Y ) , we have two options:

Perform the distillation phase as usual (compute A in full) and compute the rst step of the pruned Walsh transform algorithm for each of the l pruned Walsh transforms separately to obtain l tables g i of lengths 2 ti . We note that we only need 2 dim(Y ) counters to store A. The cost of this operation is N + l • 2 dim(Y ) additions.

We can instead construct l distilled tables g i directly, without building the intermediate array A. The cost of this operation is l • N additions.

Both options require l i=1 2 ti registers to store the resulting distilled data.

Analysis phase:

We also save time and memory by mixing the last step of the rst Walsh transform, the eigenvalue multiplication step, and the rst step of the second set of Walsh transforms.

(a) First Walsh transform: Perform the (standard) fast Walsh transform on each of the arrays g i to obtain l arrays g i . The time complexity of this operation is l i=1 t i 2 ti additions.

(b) Walsh spectrum multiplication: This step and the next are repeated for each guess of K I . Inside each subspace u i 0 +U i , we go over all the nonzero Walsh coecients. For the nonzero coecients which belong to more than one subspace, we must only consider them in one of these subspaces. For each coecient, we fetch the appropriate entry of g i and multiply it by the coecient F (u i 0 + u , K I ). The result is then added to the appropriate coordinate of an array h of length 2 ri . This step uses 2

|K I | l i=1 |L i |
products and additions and requires l i=1 2 ri additional memory reg- isters (assuming we can reuse the same memory from one K I to the next). If Corollary 14 applies, it is possible to achieve further savings by performing the multiplication step a single time.

(c) Second set of Walsh transforms: We perform the fast Walsh transform on each of the h i to obtain h i , at a cost of l i=1 r i 2 ri additions.

(d) Unfolding step: For each guess of K O , we compute cor(K O , K I ) by adding l values (with appropriate signs), one from each of the h i . This costs l2 |K I | 2 dim(V ) additions.

By adding up the cost of each step we nd that the total time and memory complexity of the algorithm is, after removing terms of lower order:

2 |K I | * N l + 2 |K I | * l i=1 t i 2 ti + 2 |K I | * * l i=1 L i + 2 |K I | l i=1 r i 2 ri additions, ( 20
)
2 |K I | * * l i=1
L i products, and ( 21)

l i=1 2 ti + l i=1
2 ri registers, [START_REF] Hu | A novel generic fast Fourier transform pruning technique and complexity analysis[END_REF] where the factors indicated by * can be removed when the nonzero Walsh coecients of F (•, K I ) occupy the same subspaces u i 0 + U i independently from K I , and the factors with * * can be removed when the Walsh coecients of the dierent F (•, K I ) only dier by sign as in Corollary 14.

6 Application to the DES As an application example, we present a variant of Matsui's linear attack [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF][START_REF] Matsui | The rst experimental cryptanalysis of the Data Encryption Standard[END_REF] on the DES [START_REF]Data Encryption Standard (DES). Federal Information Processing Standards Pub[END_REF]. This variant has lower data complexity (2 41.5 vs. 2 43 ), but has a larger memory complexity (2 38.75 vs. 2 26.00 ) due to the larger key guess.

We use a 13-round linear approximation identical to the 14-round linear approximation used in [START_REF] Matsui | The rst experimental cryptanalysis of the Data Encryption Standard[END_REF], but with the last round removed. This increases the correlation from -2 -19.75 to 2 -19.07 . The input mask is (00000000, 01040080) at (L 1 , R 1 ) and the output mask is (21040080, 00000000) at (L 14 , R 14 ). ). An attack using the same version of Algorithm 2 as [START_REF] Matsui | The rst experimental cryptanalysis of the Data Encryption Standard[END_REF] would have a time complexity of O(N )+2 43+40 2 83 operations. An attack based on the FFT without any kind of optimisation [START_REF] Collard | Experiments on the multiple linear cryptanalysis of reduced round serpent[END_REF] would require O(N ) + 48 • 2 48 operations.

The Walsh Spectrum of the Key Recovery Map

Figure 5 shows the full key recovery map for the attack, including all the key material. In other words, it shows how the linear approximation is computed from the plaintext, ciphertext, and key. Our aim is to identify the zeroes in this function's Walsh spectrum. We note that all key material is xored to the plaintext/ciphertext, and that there are seven plaintext/ciphertext bits which are xored at the end and can be considered separately as the term f 0 . The rest of the map consists of two independent parts if we ignore the key schedule: one corresponds to the rst round and the other corresponds to the last two rounds.

In the case of the map for the rst round, which we will denote by f 1 , we can see that it consists of the application of S 5 and the xoring of three of its output bits. If we look at the Walsh spectrum of S 5 , we can see that for the output y 1 ⊕ y 2 ⊕ y 3 we have 50 nonzero coecients out of the total 64.

The map for the last two rounds f 2 is a little more complex. It is the composition of three maps: the rst is an F 42 2 → F 12 2 map consisting of the application of the six active Sboxes in round 16 (selecting a single output bit for each), as well as the identity on the six active bits on the left part of the ciphertext. We then apply a linear F

C[ 7] C[ 8] C[ 9] C[10] C[11] C[12] C[15] C[16] C[17] C[18] C[19] C[20] C[21] C[22] C[23] C[24] C[25] C[26] C[27] C[28] C[29] C[30] C[31] C[ 0] C[ 1] C[ 2] C[ 3] C[ 4] K[ 8] K[ 8] K[ 8] K[23] K[11] K[ 5] K[ 5] K[ 5] K[16] K[16] K[16] K[26] K[26] K[26] K[54] K[43] K[36] K[29] K[49] K[40] K[48] K[30] K[52] K[44] K[37] K[33] K[46] K[35] K[50] K[41] K[28] K[53] K[51] K[55] K[32] K[45] K[39] K[42] K[24] K[24] K[24] K[27] K[20] K[20] K[20] K[ 6] K[14] K[14] K[14] K[10] K[10] K[10] S 8 S 1 S 2 S 3 S 4 S 6 K[ 2] K[10] K[10] K[10] K[20] K[20] K[20] K[26] K[26] K[26] K[ 5] K[ 5] K[ 5] K[16] K[16] K[16] C[43] C[44] C[45] C[46] C[47] C[48] S 5 C[ 7] C[
K[ 0] K[ 8] K[ 8] K[ 8] K[18] K[24] K[24] K[24] K[ 4] K[14] K[14] K[14]
S 5

P [39] P [50] P [56]
Fig. 5: Schematic of the key recovery map for the DES attack. Qp 0 look at the Walsh spectrum of S 5 with output mask F (Table 1), we note that there are 32 zeros, one of them corresponding to the input mask 3F.

We consider the coecients f 2 (u 0 , . . . , u 5 , u 6 ), where u 6 corresponds to the six active bits in the left half of the ciphertext. The mask u 6 will be determined by the rest of parts of the mask, as from Corollary 12 we can deduce that

f 2 (u 0 , . . . , u 5 , u 6 ) = 0 =⇒ (u 6 [i] = 1 ←→ u i = 0 for all i). (23)
Furthermore, the following expression for the Walsh coecient can be deduced: f2(u0, . . . , u5, ind(u0, . . . , u5)) = S8(u0, 1) S4(u1, 4) S6(u2, 1) S2(u3, 1) S1(u4, 4) S3(u5, 4) S5(ind(u0, . . . , u5), F), [START_REF] Markel | FFT pruning[END_REF] where ind(u 0 , . . . , u 5 )[i] = 1 ⇐⇒ u i = 0. We also collect the following information about the Walsh spectra of the active Sboxes in the last round: By adding the number of nonzero coecients associated to each value in Table 1, we conclude that despite being a map dened in F 42 2 , the Walsh spectrum of f 2 only has around 2 30.31 nonzero coecients. Furthermore, since S 5 (3F, F) = 0, u 0 , . . . , u 5 cannot all be nonzero at the same time. All nonzero coecients belong to at least one of six vector subspaces of dimension 35. Each subspace U i is determined by xing one u i = 0, which is a six bit condition, as well as the bit condition u 6 [i] = 0. Since S 5 (3D, F) = 0, we can ignore the subspace U 1 .

Attack Algorithm and Complexity

Based on the observations we have made on the key recovery map for the attack, we propose the following attack algorithm. We have provided a more thorough description of the subspaces Y, V and U i as supplementary material.

Distillation phase and rst set of Walsh transforms. The nonzero Walsh coefcients of the key recovery map form ve ane subspaces which are handled separately. The rst step in the analysis phase consists of ve pruned transforms whose inputs are restricted to a subspace Y of dimension 40 (due to the duplicate input bits in the key recovery map) and whose outputs are restricted to sub-

spaces U i = F 6 2 × U i of dimension 41. We can show that dim(Y /(Y ∩ U ⊥ 2 )) = 33, dim(Y /(Y ∩ U ⊥ 0 )) = 35, and dim(Y /(Y ∩ U ⊥ i ))
= 37 for i = 3, 4, 5.

1. Initialise three arrays g 3 , g 4 , g 5 of length 2 37 , one array g 0 of length 2 35 and one array g 2 of length 2 33 . 2. For each pair (x, y), increment or decrement one position in each of the g i according to the values of the appropriate parts of the plaintext and ciphertext and to P [39] + P

[50] + P [56] + C[7] + C[18] + C[24] + C[29]. 3.
Apply the fast Walsh transform on each of the g i .

The time complexity of these steps is around 6N memory accesses and Multiplying by the Walsh coecients. The key recovery map has 50 • 2 30.31 2 35.95 nonzero Walsh coecients. They can be enumerated by separating them into 32 sets, one for each S5( • , F) = 0, and looking at the nonzero positions in the LATs of (up to) 7 other active Sboxes.

1. Initialise one array h 2 of length 2 38 , one array h 0 of length 2 37 , and three arrays h 3 , h 4 , h 5 of length 2 34 .

2. For each of the nonzero Walsh coecients, retrieve the associated output of the rst Walsh transform from one of the g i (if the coecient lies in more than one of the U i , we can choose any), multiply it by the coecient and add or subtract the result to the appropriate position of the array h i .

The time complexity of this step is 7 • 2 35.95 2 38.76 products.

Second set of Walsh transforms and exhaustive search. The Walsh transforms in the second set are pruned at the inputs according to the subspaces U i , and at the outputs according to a subspace V of dimension 40 given by the key schedule. We can show that dim(V

/(V ∩ U ⊥ 2 )) = 38, dim(V /(V ∩ U ⊥ 0 )) = 37, and dim(V /(V ∩ U ⊥ i )) = 34 for i = 3, 4, 5.
1. Perform the standard Walsh transform on the ve arrays h 0 , h 2 , h 3 , h 4 , h 5 . 2. For each of the 2 40 possible key guesses, we add one coordinate from of each of the ve arrays to obtain the experimental correlations. We keep the 2 24

guesses with the highest correlation, as we aim for an advantage of 16 bits.

3. For each one of the 40-bit partial key guesses, we try all possibilities of the 16 other keybits exhaustively until either the key is found or the attack fails.

The time complexity of these steps is 38 Attack complexity. The data complexity of the attack was determined using the model of Blondeau and Nyberg [START_REF] Blondeau | Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity[END_REF]. We obtain a 16 bit advantage with 70% probability with N = 2 41.5 data. The memory complexity is dominated by the ten arrays, which require 2 39.74 memory registers of 64 bits. This can be reduced to around 2 38.75 by performing the multiplication step in a way in which the g i and the h i do not have to be allocated at the same time.

For the time complexity, we consider that on a modern processor a DES encryption takes 16 clock cycles, a product takes 6 clock cycles, and a memory access or an addition take 1 clock cycle. We obtain The attack uses one of the three sets of linear approximations which were dened in [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF] and provide a trade-o between capacity and key recovery complexity. We will use set II, which has 296 approximations and a total capacity of 2 -57.8 . Table 3 shows all the approximations which conform this distinguisher in a compact form. All of them have a single active Sbox in the rst round and a single active Sbox in the last round, and the input mask always has Hamming weight 1 or 2 while the output mask always has Hamming weight 1.

Key Recovery Example for a Single Approximation

As an example, we consider the 24-round linear approximation with input mask 0000000000A00000 and output mask 0000000000200000, between the 3rd and the 26th rounds. We add two rounds of key recovery at the input side and three rounds at the output side. We will apply the pruned Walsh tranform-based attack algorithm to compute its experimental correlation for all key guesses.

For comparison purposes, we consider the cost when using the Walsh transform without pruning. There are 32 active bits in K 1 , 8 active bits in K 2 , 4 active bits in K 28 , 16 active bits in K 29 , and 64 active bits in K 30 (crossed-out in Figure 6). They add up to 28 bits of inner key guess K I and 96 bits of outer key guess K O . We thus require 2 96 memory registers, and the time complexity is in the order of 96 • 2 96+28 2 130.6 additions, which leaves little margin to repeat it for several approximations using less than 2 128 equivalent encryptions.

In order to reduce this cost as much as possible, we consider both the structure of the key recovery map and the key schedule in order to prune both stages of Walsh transforms. The key recovery map consists of three independent parts corresponding to each of the three active bits in the input and output masks.

Both parts corresponding to the input mask are essentially identical.

(x 3 ), S 1 (x 2 ), S 1 (x 1 ), S 1 (x 0 ) ⊕ k I ).
Using Corollary 14, each of their Walsh coecient is the product of up to ve coecients of the Walsh spectrum of S 1 , which we note has six zeros.

We next look at the remaining part, which has a similar structure but over three rounds. In round 27, we consider S -1 (F, 2) = S(2, F) = 4. By rejecting the ciphertexts which lead to an input 3, 5, B or D to this Sbox, this coecient becomes zero. We can split all nonzero Walsh coecients into two ane subspaces of dimension 48 corresponding to the nonzero Walsh coecients S -1 x∈F 4

2 \X (B, 2) and S -1 x∈F 4 2 \X (D, 2). The inactive" bits in each of these subspaces have been surrounded by a thicker outline in Figure 6. The cost of this modication is a reduction of the available data by a factor of 3/4 = 2 -0.42 . We now consider the key schedule. When pruning the Walsh transforms, we prefer relationships which are linear or which describe outer active keybits in terms of inner active keybits. We rst guess the 28 innner keybits, painted (dark) red in the gure. The outer bits which can be deduced from these are colored (light) green. The other outer bits are guessed individually. There are three bits of K 30 which can be deduced from the guess for K 28 .

Let us compute the time complexity of obtaining all the cor(K O , K I ). The second pair of Walsh transforms is repeated once for each of the 2 28 guesses of K I . In every case, the Walsh transforms have inputs restricted to subspaces of dimension 80 and outputs restricted to subspaces of dimension 93.

The dimension of X/(X ∩U ⊥ ) is minimal and equal to 77. The total cost of these transforms is thus 2 28 • 2 • 77 • 2 77 2 112.27 additions. The cost of combining the resulting arrays would be 2 120 additions. However, 25 bits of the key guess at K 1 and three bits of the guess at K 28 can be deduced from the guess at K 30 , and the calculation can be performed with 2 92 additions.

We note that we have decreased the time complexity by a factor of almost 2 16 by increasing the data complexity by a factor of 4/3 2 0.42 , illustrating that a carefully picked ltering of the data can lead to signicant time gains.

Overview of the complete attack

We divide the 296 linear approximations into two groups depending on the Hamming weight of the input mask and their time complexity contribution: Type I (groups D,G). These are the 160 approximations with input masks of Hamming weight 1. For these approximations, there are 16 active bits in K 1 , 4 in K 2 , 4 in K 28 , 16 in K 29 and 64 in K 30 . We can compute cor for these approximations with around 160•2 24 •80•2 80 2 117.64 additions without pruning.

Type II (groups A,B,C,E,F). These are the 136 approximations with input masks of Hamming weight 2. There are 32 active bits in K 1 , 8 in K 2 , 4 in K 28 , 16 in K 29 , and 64 bits in K 30 . We treat these approximations as in the example: we study the Walsh spectrum of the active Sbox in round 27 (see Table 4). For 48 approximations, we are interested in S(2, •), and we can split the Walsh spectrum of the key recovery map into two ane subspaces of dimension 80 by discarding 1/4 of the data. For 40 approximations, the coecient is S(4, •), and we can split the spectrum into 2 spaces of dimension 80 by discarding 1/4 of the data.

For the other 48 approximations, the coecient is S(4, •), in which case the spectrum lies on a subspace of dimension 80 after discarding 1/2 of the data.

Given these restrictions, we can compute cor with either 2 • 2 28 • 80 • 2 80 2 115.32 or 2 28 • 80 • 2 80 2 114.32 additions. Further reductions are possible if we used the key schedule, but they are dierent for each approximation. Ignoring these, 2 123.08 additions are required in total. We also have to combine both arrays corresponding to each approximation, which requires at most 2 92 additions per approximation if we consider the key schedule.

Computing the multiple linear cryptanalysis statistic: rst step. We must also consider the cost of computing the multiple linear cryptanalysis statistic. Using the notation of [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF], the approximations form M 2 = 32 groups (8 groups for type I and 24 groups for type II) which share the same key guesses K O and K I .

We can compute the sum of squares within each group and combine them in the next step. Considering the key schedule, for the Type II approximations we need to guess at most 92 bits, and for Type I at most 88 bits. This step can thus be performed with 136 • 2 92 + 160 • 2 88 2 99.2 products and additions.

Conclusion

Summary of results. We have introduced a new framework for pruning of the fast Walsh transform to ane subspaces and used it as part of an optimised version of the attack algorithms of [START_REF] Collard | Improving the time complexity of Matsui's linear cryptanalysis[END_REF][START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF], whose time complexity can be signicantly lowered with respect to previous iterations.

In general terms, the time complexity of a key recovery attack using the fast Walsh transform largely depends on three factors: the number of active bits in the plaintext/ciphertext, the number of active keybits, and the number of input bits to the key recovery map which combines the two to evaluate the linear approximation. Previous versions of the Walsh-based attack algorithm often ran into a bottleneck imposed by the latter, in the sense that any additional redundancy in the key or the data would not reduce the time complexity or only reduce it by a logarithmic factor. Our improved algorithm can eectively exploit the construction of the map. In the application examples, the number of independent active keybits becomes the bottleneck of the attack.

We have showcased the usability of this improved version of the algorithm by describing two attacks which are only possible (in the sense of having a smaller time complexity than exhaustive search) thanks to it. We have provided the best known attack on the DES with regards to data complexity as well as the rst attack on 29-round PRESENT-128 in the literature.

Further research. The rst continuation to this work would be application to other ciphers. This technique might prove particularly useful in dierentiallinear cryptanalysis [START_REF] Langford | Dierential-linear cryptanalysis[END_REF][START_REF] Biham | Dierential-linear cryptanalysis of serpent[END_REF], as using the same key guess for both ciphertexts in a pair introduces a lot of redundancy. We also think that, since applying the framework to an attack is a fairly technically involved task, an automatic tool which computes an optimal key recovery algorithm given a linear distinguisher of a block cipher could be of great use to the community.

The results shown in this paper are most eective in the case of specic cipher constructions, such as ciphers which use a bit permutation as the linear layer, a case in which the Walsh spectrum can be described in a succint way. It would be of interest to try to generalise these results to other common constructions. In the applications, we also nd that the attacks become limited by the number of active keybits. For this reason, another open question would be whether it is possible to adapt conditional guessing techniques such as [START_REF] Broll | Generic framework for key-guessing improvements[END_REF] to Walsh transform-based linear key recovery attacks. A broader open problem would be to nd interesting applications of pruned fast Walsh transform algorithms to other problems in symmetric cryptology.

2 .

 2 Distillation phase: Construct the 2 |x1| × • • • × 2 |x d | -dimensional array A. 3. Analysis phase: (a) Apply the FWT on the array A to obtain A. We can consider A is a one-dimensional array of 2 |X| elements. (b) For each value of K I : i. Multiply each entry A[Y ] of A by d i=0 f i (y i , k I i ). ii. Apply another FWT to obtain an array containing cor[ • , K I ].

4 .

 4 Search phase: Exhaustive search over the rest of the key for the guesses with the largest values of 2 |X| N cor[K O , K I ]. The memory complexity of this algorithm mainly consists 2 |X| memory registers to store A. The time complexity of the distillation phase is O (N ), as each plaintext-ciphertext pair is checked once and discarded. The time complexity of the analysis phase is dominated by the loop on K I , and consists of d2 |K I |+|K O | multiplications and |K O |2 |K I |+|K O | additions/subtractions. The time complex-

Fig. 1 :

 1 Fig. 1: A round of PRESENT.

  +f 0010 -f 1110 +f 0010 +f 0011 -f 0100 -f 0101 +f 1000 +f 1001 -f 1110 -f 1111 +f 0010 +f 0011 +f 0100 +f 0101 -f 1000 -f 1001 -f 1110 -f 1111 +f 0010 -f 0011 -f 0100 +f 0101 +f 1000 -f 1001 -f 1110 +f 1111 +f 0010 -f 0011 +f 0100 -f 0101 -f 1000 +f 1001 -f 1110 +f 1111

Figure 4

 4 Figure 4 indicates the active keybits in the key recovery in rounds 1, 15, and 16. There are 40 active keybits in total: 3 are active in round 1, one is active in round 15, 28 are active in round 16, 3 are active in both rounds 1 and 16, and 5 are active in both rounds 15 and 16. All active keybits are represented as part of K, after applying the appropriate bit rotation. There are 43 active plaintext/ciphertext bits (four of which are duplicated before the key addition because of the expansion map) and 40 active keybits (eight of which are used twice). An attack using the same version of Algorithm 2 as[START_REF] Matsui | The rst experimental cryptanalysis of the Data Encryption Standard[END_REF] would have a

Fig. 4 :

 4 Fig. 4: Key recovery in rounds 1, 15 and 16 of the DES. States are represented as divided into nibbles, except for those before the S-box layer which are divided in groups of 6 bits. The least signicant bit is the one on the upper right. represents a bit which appears linearly in the linear approximation, while represents any other active (nonlinear) bit. , , and represent keybits which are active in rounds 1, 15 and 16, respectively.

S 8 (

 8 • , 1) has 15 zeros. S 4 ( • , 4) has 12 zeros.

S 6 (

 6 • , 1) has 17 zeros. S 2 ( • , 1) has 20 zeros. S 1 ( • , 4) has 14 zeros. S 3 ( • , 4) has 18 zeros.

S

  S(x)∈F 4 2 \X (2, •) v H I P Q R S T U V W e f g h i p

  cryptanalysis. PRESENT has a block size of 64 and can operate with keys of either 80 or 128 bits. It is a substitution permutation network with 31 rounds:

X ← P ; for i ← 1 to 31 do end K 32 ← K[127, . . . , 64];

Table 1 :

 1 Part of the Walsh spectrum of S 5 : S 5 (•, F).

	HH 0	HV 8	IH -40	IV -8	PH	0	PV 0	QH 8	QV 0
	HI 0	HW -8	II	8	IW -8	PI	0	PW 0	QI 8	QW 0
	HP -8	He 0	IP	0	Ie 0	PP -24	Pe 8	QP 0	Qe -8
	HQ -8	Hf 0	IQ	0	If 0	PQ -8	Pf 8	QQ 0	Qf 8
	HR 0	Hg -8	IR	0	Ig 0	PR	0	Pg 0	QR 0	Qg 8
	HS 8	Hh 0	IS	8	Ih 8	PS -8	Ph -8	QS 8	Qh 0
	HT 0	Hi -8	IT	0	Ii 0	PT	0	Pi 0	QT 0	Qi 8
	HU -8	Hp 0	IU	8	Ip -8	PU -8	Pp -8	QU -8

  3 • 37 • 2 37 + 35 • 2 35 + 33 • 2 33 2 43.93 additions and subtractions.

  • 2 38 + 37 • 2 37 + 3 • 34 • 2 34 + 5 • 2 40 2 44.41 additions/subtractions and 2 40 trial encryptions.

Table 2 :

 2 Comparison of selected attacks on the Data Encryption Standard.In this section we introduce the rst, to the best of the authors' knowledge, attack on 29-round PRESENT-128. It is based on a previous attack on PRESENT-80[START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF] and adds an additional key recovery round. The attack uses the full codebook and has a time complexity of 2 124.06 29-round PRESENT encryptions.

	1 16	• 6 • 2 41.5 +	1 16	2 43.93 + 2 44.41 +	6 16	• 2 38.76 + 2 40 2 42.13 DES encryptions.
		This attack is, to the best of our knowledge, the best in terms of data com-
	plexity. However, it has rather high time (if we exclude data generation) and
	especially memory complexities when compared to previous attacks.

Table 4 :

 4 If we denote by S 1 the second component of S (that is, the second output bit), then Restricted Walsh spectra used in the PRESENT-128 attack.

	112	96	80	64		48	32	16	0
	K1
	48	32	16	0	S	48	32	16	0	S
	112	96	80	64	P	112	96	80	64	P
	K2				K28
	48	32	16	0	S	48	32	16	0	S
	48	32	16	0	P	112	96	80	64	P
					K29
			24 rounds		48	32	16	0	S
						112	96	80	64	P
					K30
	Fig. 6: Key recovery for one approximation.

Table 3 :

 3 The linear approximations of 24-round PRESENT which conform set II of[START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF], and which are also used in our attack.

	Group	Input	Input	Output	Output		24R
	([19])	Mask	S-Box	Mask	S-Box	Qty. ELP
	A	e 5, 6, 9, 10 PDV 5, 7, 13, 15 32 2 -65.1
	B	g 5, 6, 9, 10 PDV 5, 7, 13, 15 32 2 -65.6
	C	e 5, 6, 9, 10 PDV e 13, 14 PDV 5, 7, 13, 15 16 6, 14 16 2 -65.8
	D	PDR 5, 6, 9, 10 PDV 5, 7, 13, 15 64 2 -66.0
	E	g 5, 6, 9, 10 PDV g 13, 14 PDV 5, 7, 13, 15 16 6, 14 16 2 -66.3
	F	e	13, 14	PDV	6, 14	8 2 -66.5
		PDR 5, 6, 9, 10 PDV	6, 14	32
	G	V 5, 6, 9, 10 PDV 5, 7, 13, 15 32	2 -66.7
		PDR	13, 14	PDV 5, 7, 13, 15 32
					Total 296 2 -57.8

these F

16

2 -→ F 2 maps are of the form S 1 (S 1

  We start with two Walsh transforms whose outputs are restricted to subspaces of dimension 48 + 32 = 80. The distillation phase costs 2N operations and requires 2 • 2 80 memory registers. The cost of the Walsh transforms themselves is 2 • 80 • 280 2 87.32 additions. The cost of the Walsh coecients multiplication is at

	most	10 16	20 • 2 • 2 80 2 67.44 products.

Table 5 :

 5 Comparison of linear attacks on reduced-round PRESENT. Attacks on PRESENT-80 are also included for the sake of completeness. KP = Known Plaintext. DKP = Distinct Known Plaintext. DKP 2 124.06 2 99.2 67% Section 7 a 29-round PRESENT encryption requires at least 3776 (64 for each subkey addition and Sbox layer), these will be equivalent to at most 2 123.12 encryptions. The total time complexity is thus 2 124.06 encryptions.

			Complexity
	Key Rds. Data	Time Memory P S P S P S Source
			2 63.8 KP	2 72.0	2 32.0	51% [15, 7]
		26	2 63.0 KP 2 61.1 KP	2 68.6 2 68.2	2 48.0 2 44.0	95% [10] 95% [19]
			2 60.8 KP	2 71.8	2 44.0	95% [19]
	80		2 64.0 KP	2 74.0	2 67.0	95% [34]
		27	2 63.8 DKP 2 77.3	2 48.0	95% [10]
			2 63.4 DKP 2 72.0	2 44.0	95% [19]
		28	2 64.0 DKP 2 77.4	2 51.0	95% [19]
		28	2 64.0 DKP 2 122	2 84.6	95% [19]
	128	29	2 64.0

Acknowledgements. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 714294 -acronym QUASYModo).

 7: Determining all the active keybits for all approximations (crossed out in the gure) with as few guesses as possible. We can deduce the (light) green bits if we know the 123 keybits highlighted in (dark) red.

Computing the multiple linear cryptanalysis statistic: second step. The combined tables of the previous step are used to compute Q k T for each value of a global key guess k T . Figure 7 shows a guess of 123 keybits from which all the key guesses can be deduced. For each guess of k T , we must add 32 values, one from each of the tables constructed in the previous step, at a cost of 32 •2 123 = 2 128 additions.

After this we can nd the the ve remaining keybits with an exhaustive search costing 2 123 encryptions if we aim for a ve-bit advantage.

Data complexity. We once again use the model from [START_REF] Blondeau | Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity[END_REF], with careful consideration that the number of available plaintexts depends on the approximation. We nd that if the whole codebook is used ( 264 distinct known plaintexts), a 5 bit advantage is achieved with 67% probability.

Memory complexity. There are two main steps which contribute to the memory complexity. The distillation phase requires 160