Gaëtan Leurent

Clara Pernot

André Schrottenloher

Clustering Effect in Simon and Simeck

Keywords: Lightweight cipher, Simon, Simeck, differential cryptanalysis, linear cryptanalysis, clustering effect Cipher Rounds Attacked Data Time Ref

Simon and Simeck are two lightweight block ciphers with a simple round function using only word rotations and a bit-wise AND operation. Previous work has shown a strong clustering effect for differential and linear cryptanalysis, due to the existence of many trails with the same inputs and outputs. In this paper, we explore this clustering effect by exhibiting a class of high probability differential and linear trails where the active bits stay in a fixed window of w bits. Instead of enumerating a set of good trails contributing to a differential or a linear approximation, we compute the probability distribution over this space, including all trails in the class. This results in stronger distinguishers than previously proposed, and we describe key recovery attacks against Simon and Simeck improving the previous results by up to 7 rounds. In particular, we obtain an attack against 42-round Simeck64, leaving only two rounds of security margin, and an attack against 45-round Simon96/144, reducing the security margin from 16 rounds to 9 rounds.

Introduction

Simon and Simeck are two lightweight block ciphers with a simple round function and very good hardware and software performances. Simon [START_REF] Beaulieu | The simon and speck lightweight block ciphers[END_REF] was designed by Beaulieu, Shors, Smith, Treatman-Clark, Weeks and Wingers and published without a rationale, but has been considered for ISO standardisation. It follows a Feistel structure with a very simple round function:

f (x) = ((x ≪ 8) ∧ (x ≪ 1)) ⊕ (x ≪ 2).
Simeck is an academic variant of Simon designed by Yang, Zhu, Suder, Aagaard and Gong, and published at CHES 2015 [START_REF] Yang | The simeck family of lightweight block ciphers[END_REF]. It has the same number of rounds, and the same round function as Simon, but with different rotation amounts:

f (x) = ((x ≪ 5) ∧ x) ⊕ (x ≪ 1).
The key schedule of Simeck is also modified to reuse the function f . c IACR 2021. This article is the final version submitted by the authors to the IACR and to Springer on 2021-09-20, with supplementary material. The version published by Springer is available at https://doi.org/10.1007/978-3-030-92062-3_10.

Previous work has shown that the best attacks against these ciphers use differential cryptanalysis or linear cryptanalysis [START_REF] Abed | Differential cryptanalysis of round-reduced Simon and Speck[END_REF][START_REF] Biryukov | Differential analysis of block ciphers SIMON and SPECK[END_REF][START_REF] Chen | Improved linear hull attack on round-reduced simon with dynamic key-guessing techniques[END_REF][START_REF] Kölbl | A brief comparison of simon and simeck[END_REF][START_REF] Qiao | Differential security evaluation of simeck with dynamic key-guessing techniques[END_REF], and has provided a detailed analysis of differential paths and linear trails using various techniques and tools [START_REF] Beierle | Pen and paper arguments for SIMON and SIMON-like designs[END_REF][START_REF] Kölbl | Observations on the SIMON block cipher family[END_REF][START_REF] Liu | Optimal differential trails in SIMON-like ciphers[END_REF][START_REF] Wang | Automatic search for related-key differential trails in SIMON-like block ciphers based on MILP[END_REF]. Moreover they show a strong clustering effect for differential characteristics and linear trails. There exist many trails with the same input and output, and the probability of a differential (respectively the potential of a linear approximation) is significantly higher than the probability of the best characteristic (respectively the best linear trail). In order to estimate the probability of a differential or the potential of a linear approximation, we have to combine the effect of as many trails as possible with the corresponding input/output. This generates a lower bound on the quality of the differential or linear approximation. For instance, the best differential characteristic for 27-round Simeck64 has probability 2 -70 [START_REF] Kölbl | A brief comparison of simon and simeck[END_REF], but a 27-round differential (0, 11) → (5, 2) with probability 2 -60.75 was given in [START_REF] Huang | Improved automatic search algorithm for differential and linear cryptanalysis on SIMECK and the applications[END_REF].

Our Contribution. In this work, we explore this clustering effect in a more systematic way. Instead of building a list of trails with a given input/output, we consider a class of high probability trails where the active bits stay in a fixed window of w bits. In particular, we observe that the differentials and linear hulls used in most previous attacks fit in this framework.

Using properties of the round function, we compute efficiently the probability distribution over this space by multiplication of the differential transition matrix, or the linear correlation matrix. This provides a tighter lower bound on the probability of the differential (or the potential of the linear approximation) than used in previous works, because we implicitly consider all trails with intermediate states fitting in the window. Concretely, the 27-round differential (0, 11) → (5, 2) has probability at least 2 -56.06 for Simeck64. In general, we obtain a good understanding of the propagation of differences and linear masks in this class: there is a high probability to stay in the class because of the slow diffusion of Simon and Simeck.

We observe that this class includes many high quality distinguishers with input/output that are independent of the number of rounds targeted by the attacks. In particular, we use distinguishers with a single active bit in the input and output, because we can add more rounds of key-recovery than when using distinguishers with multiple active bits. Concretely, for Simeck64, the differential (0, 1) → (1, 0) has probability at least 2 -54.72 over 27 rounds, and 2 -60.41 over 30 rounds.

Finally, we use the distinguishers to build key-recovery attacks, using dynamic key-guessing [START_REF] Qiao | Differential security evaluation of simeck with dynamic key-guessing techniques[END_REF][START_REF] Wang | Differential attacks on reduced SIMON versions with dynamic key-guessing techniques[END_REF] for differential attacks, and the Fast Walsh Transform approach of [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF] for linear cryptanalysis. We observe that Simon and Simeck are rotation-invariant, so that any differential or linear attack can be repeated several times using rotations of the original distinguisher. In particular, we can exploit attack parameters with low success rates, and repeat them several times to increase the success rate. We compare our results with the best previous analysis in Table 1. A more detailed comparison is also given as Table 15 in Appendix.

Outline. We begin with preliminaries about differential and linear cryptanalysis in general in Section 2. Then we apply them to Simon-like ciphers in Section 3, starting with previous results and explaining our main contribution. We explain in detail how to apply these ideas to Simeck with differential cryptanalysis (Section 4) and linear cryptanalysis (Section 5). We apply the same techniques to Simon in Section 6, and conclude in Section 7.

The code used to compute the probabilities of differentials and linear approximations (Table 4), as well as the success probability of linear attacks (Section 5), is available at https://github.com/Clustering-Simon.

Notations

The following notations are used in this paper: n/κ block size and key size x (i) left part of the input of round i x j j-th bit of x r number of rounds P/C plaintext and ciphertext P / C plaintext after the first round the ciphertext before the last round D data complexity C 1 time complexity to run an attack a single time F W /F R probability distribution function for a wrong/right key guess P S success probability of an attack a, b, c rotation constants: There are 3 versions of Simeck, using a subset of the Simon parameters marked with * ; in particular, Simeck has κ = 2n, and we often omit the κ parameter. The plaintext P is divided in two parts of n/2 bits named x (0) and x (-1) , which correspond to the initialization of the left and the right parts of our Feistel network. For the round i, we denote by x (i) and x (i-1) the left and the right part of the input of this round. The round function is:

f (x) = ((x ≪ a) ∧ (x ≪ b)) ⊕ (x ≪ c)
x (i+1) = x (i-1) ⊕ f (x (i) ) ⊕ k (i) , with f (x) = ((x ≪ a) ∧ (x ≪ b)) ⊕ (x ≪ c).
We denote by x ≪ d the cyclic rotation of d bits by left, ∧ the bitwise AND, and ⊕ the bitwise exclusive or (XOR). The j-th bit of x is noted x j where the index j is taken modulo n/2. The rotations of Simon are defined as (a, b, c) = (1, 8, 2), while those of Simeck are defined as (a, b, c) = (0, 5, 1) (the rotation amounts are independent of the block size). Since there is no whitening key, the first and last round functions do not depend on the key. We define P as the plaintext after the first round, C as the ciphertext before the last round, and we use them as input for our analysis:

P = (x (0) , x (-1) ) P = (x (-1) ⊕ f (x (0) ), x (0) ) C = (x (r) , x (r-1) ) C = (x (r-1) , x (r) ⊕ f (x (r-1)
))

The input of round 1 corresponds to P ⊕ (k (0) 0 n/2 ) (see Figure 5).

The key schedule allows to derive the subkeys k (i) for 0 ≤ i < r from the master key k. First, the master key is divided into 2κ/n words (k (2κ/n-1) , . . . , k (1) , k (0) ). Then, the subkeys k (i) for i ≥ 2κ/n are obtained using a recursion formula. For Simeck, the recursion is defined as

k (i+4) = k (i) ⊕ f (k (i+1) ) ⊕ C ⊕ z (i) ,
with C and z (i) constants depending on the block size and f is the same function as used in the data path. Simon uses a different key schedule, that is linear. We omit further details because our analysis does not exploit them.

Differential and Linear Cryptanalysis

We begin with some preliminaries on differential and linear cryptanalysis.

x (i) x (i-1) f ⊕ ⊕ x (i+1) x (i) k (i)
Fig. 1. Round function of Simon and Simeck.

x (i) x (i-1) f ⊕ ⊕ x (i+1) x (i) k (i) δ (i) δ (i-1) δ (i+1) δ (i) Fig. 2. Differential char- acteristic with probability Prx[δ (i) f → δ (i-1) ⊕ δ (i+1) ] x (i) x (i-1) f ⊕ ⊕ x (i+1) x (i) k (i) α (i-1) α (i) α (i) α (i+1)
Fig. 3. Linear trail with correlation c(α

(i-1) ⊕ α (i+1) f → α (i) ) C ⊕ E2
x (0) x (-1) P f ⊕ x(1) x (0) P f ⊕ ⊕ ⊕ k (0) k (1) kp x (2) x (1) . . . . . . kt, k b x (r-2) x (r-3) f ⊕ ⊕ ⊕ k (r-1) k (r-2) kc x (r-1) x(r-2) C f ⊕ x (r)
x (r-1) C Fig. 5. Simon/Simeck with our notations: x(1) and x(r-2) respectively stand for x (-1) ⊕ f (x (0) ) and x (r) ⊕ f (x (r-1) ).

Differential cryptanalysis

Differential cryptanalysis is a technique introduced by Biham and Shamir [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF][START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF], exploiting the propagation of differences in (reduced versions of) a cipher. Starting from a well-chosen difference δ, the distribution of E k (x) ⊕ E k (x ⊕ δ) is nonuniform, and there exist differences

δ such that Pr k,x [E k (x) ⊕ E k (x ⊕ δ) = δ ] is high (significantly higher than 2 -n ). Such a pair (δ, δ ) is called a differential.
In practice, we use the notion of differential characteristic (or trail) to estimate the probability of a differential. A differential characteristic (δ 0 , δ 1 , . . . , δ r ) specifies the intermediate state difference after each round of the function. Therefore, we can easily compute the probability that each round follows the characteristic, and we estimate the probability of the differential as the product of the probability of each round, assuming that they are independent.

More formally, we use the following notations for the probability of the round function, the probability of a characteristic, and the probability of a differential, where R denotes the round function of a cipher, and

E (r)
k is a reduced version of the cipher with r rounds:

Pr[δ → δ ] = Pr x [R(x) ⊕ R(x ⊕ δ) = δ ] Pr[δ 0 → δ 1 → . . . → δ r ] = Pr k,x [E (i) k (x) ⊕ E (i) k (x ⊕ δ 0 ) = δ i , ∀i ≤ r] Pr[δ r δ ] = Pr k,x [E (r) k (x) ⊕ E (r) k (x ⊕ δ) = δ ]
Lai, Massey and Murphy have defined the notion of a Markov cipher (Simon and Simeck with independent round keys are Markov ciphers), where the probability of a characteristic is the product of the probabilities of the round function transitions [START_REF] Lai | Markov ciphers and differential cryptanalysis[END_REF]:

Pr[δ 0 → δ 1 → . . . → δ r ] = r i=1 Pr[δ i-1 → δ i ] .
When there is a dominant characteristic, it can be used as an approximation of the probability of the differential. In general, the probability of a differential is the sum over all compatible characteristics:

Pr[δ 0 r δ r ] = δ1,δ2,...δr-1 r i=1 Pr[δ i-1 → δ i ] .
If we write all the transition probabilities Pr[δ → δ ] in a differential transition matrix A, the probabilities of all r-round differentials are given by A r , as shown by [START_REF] Lai | Markov ciphers and differential cryptanalysis[END_REF]. Computing A r is infeasible for practical ciphers, but this approach can be applied to a set of predetermined characteristics, and provide a good approximation of the probability of a differential.

Differential distinguisher. In order to distinguish a cipher with a high probability differential (δ, δ ) from a random permutation, we collect D ciphertexts corresponding to pairs of plaintexts (P, P ⊕ δ), and we compute the number of pairs following the differential:

Q = #{P : E(P ) ⊕ E(P ⊕ δ) = δ } . The expected value of Q is D × Pr[δ δ ]
for the cipher, and D × 2 -n for a random permutation; therefore the distinguisher succeeds with high probability when D = O(1/ Pr[δ δ ]).

Linear cryptanalysis

Linear cryptanalysis was introduced by Matsui [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF]; it uses linear approximations of the round function in order to obtain a biased approximation of the (reduced) cipher. A linear approximation is a pair of masks (α, α ) such that the distribution of

x • α ⊕ E k (x) • α is biased (| Pr x [x • α = E k (x) • α ] -1/2| 2 -n/2
for most keys k), where x • y = i x i y i denotes the dot product. Since the correlation is expected to be zero when averaged over all keys, we define the key-dependent correlation as follows:

c k (α r α ) = 2 Pr x [x • α = E (r) k (x) • α ] -1 .
In practice, we use linear trails where a mask is specified for each intermediate state. For an iterative cipher

E k = R (r) k • • • • • R (2) k • R (1)
k , we can express the correlation c k (α 0 r α r ) as the sum of the correlation over all corresponding linear trails by defining the correlation of the keyed round function R

(i)
k [START_REF] Daemen | Correlation matrices[END_REF]:

c k (α 0 r α r ) = α1,α2,...αr-1 r i=1 c (i) k (α i-1 → α i ) c (i) k (α i-1 → α i ) = 2 Pr x [x • α = R (i) k (x) • α ] -1 .
If the cipher is a key-alternating cipher with independent round keys, the correlation of the keyed round function can be expressed in terms of the correlation of the unkeyed round function:

c k (α 0 r α r ) = α1,α2,...αr-1 (-1) i ki•αi r i=1 c(α i-1 → α i ) c(α → α ) = 2 Pr x [x • α = R(x) • α ] -1 .
Therefore, the correlation of a linear approximation is the sum of the correlations over all linear trails, with signs that depend on the key. When there is a single dominant trail, we can approximate the correlation of the linear approximation as the correlation of the trail, up to a change of sign. However when there are several dominant trails, they can interact constructively or destructively depending on the key.

Nyberg [START_REF] Nyberg | Linear approximation of block ciphers (rump session)[END_REF] defined the expected linear potential as the expected value of the square correlation for a random key, and showed that it is equal to the sum of the squared correlation over all linear trails (assuming a key-alternating cipher with independent keys):

ELP(α 0 r α r ) = Exp k (c 2 k (α 0 r α r )) = α1,α2,...αr-1 r i=1 c 2 (α i-1 → α i ) .
Similarly to the differential case, we can compute the expected linear potential for all linear approximations by computing the powers of a correlation matrix C with coefficients c 2 (α → α ).

Linear distinguisher. In order to distinguish a cipher with a biased linear approximation (α, α ) from a random permutation, we collect D known plaintexts/ciphertexts, and we evaluate the experimental correlation

Q = (#{P, C : P • α ⊕ C • α = 0} -#{P, C : P • α ⊕ C • α = 1})/D
The expected value of Q is larger (in absolute value) for the cipher than for a random permutation, and this can be detected with high probability when D = O(ELP[α α ] -1 ) (see Section 5.2 for more details).

Last-round Key Recovery

In order to turn a statistical distinguisher (differential or linear) into a key recovery attack, we add a few rounds at the top and/or bottom, and partially encrypt/decrypt the available data to evaluate the statistical property. We denote the statistic used by the distinguisher as Q, and we assume that it can be evaluated by guessing only a subset of the key, shown as (k p , k t , k b , k c ) in Figure 4. We let κ g = κ p + κ t + κ b + κ c denote the corresponding number of key bits. We denote the value obtained for key candidate k as Q(k), and consider it as a random variable (depending on the choice of the encryption key, and the data set). We evaluate Q(k) for all key candidates; in a naive approach, this requires D × 2 κg operations. However, this can often be reduced to roughly D + 2 κg operations using algorithmic tricks (details are given in the next sections). By analysing the theoretical behaviour of the distinguisher, we can predict the distribution of the random variables. We denote the probability distribution function of the statistic for the right key as F R , and for wrong keys as F W . We rank the key candidates according to Q(k), and expect that the correct key will be in the top candidates if the distinguisher is strong enough (w.l.o.g., we assume that the statistic used gives a higher value for the right key).

More precisely, we aim to have the correct key among the top 2 κg-a candidates, where a is called the advantage (in bits). If the key schedule of the cipher is simple enough, the attacker can reconstruct the 2 κ-a master keys corresponding to these candidates and exhaustively test them. In particular, the key schedule of Simon is linear, so that master key candidates can be constructed from any subkey bits using linear algebra. The complexity of this type of attack is roughly:

T = D + 2 κg + 2 κ-a .
In order to keep a fraction 2 -a of the key candidates, we set a threshold of

s = F -1 W (1 -2 -a
) and keep all keys with Q(k) ≥ s. The attack succeeds if the value of Q corresponding to the right key is higher than the threshold, this happens with probability:

P S = 1 -F R (s) = 1 -F R (F -1 W (1 -2 -a )) . (1)
As a first condition, the parameters must satisfy:

D ≤ 2 n D 2 κ 2 κg 2 κ 2 a 1 P S 0 (2)
Complex key schedules. When the key schedule is complex and non-linear, reconstructing the master key candidates corresponding to the κ g recovered bits can be an issue. In particular when adding rounds on both sides of the distinguisher, the attacker recovers candidates for keys bits in the first and last rounds, but it is not possible to efficiently build the corresponding candidates for the master key. In particular, some previous attacks on Simeck [START_REF] Huang | Improved automatic search algorithm for differential and linear cryptanalysis on SIMECK and the applications[END_REF][START_REF] Qiao | Differential security evaluation of simeck with dynamic key-guessing techniques[END_REF][START_REF] Qin | Linear hull attack on round-reduced simeck with dynamic key-guessing techniques[END_REF] use a small advantage a and compute the time complexity as 2 κ-a , but the key recovery would actually have a complexity higher than 2 κ with the parameters used. Instead the attacker can focus on the recovered bits on a single side of the distinguisher, and exhaustively search the missing bits, with a cost of 2 κ-a+min{κp+κt,κ b +κc} .

Analysis of Simon-like ciphers

Since the round function of Simon-like ciphers is quadratic, we can efficiently compute the exact probability of a differential or linear transition through the function f . This was explored in details by Kölbl, Leander and Tiessen [START_REF] Kölbl | Observations on the SIMON block cipher family[END_REF]:

-For a given α, there is an affine space U α such that

Pr x [f (α ⊕ x) ⊕ f (x) = β] = 2 -dim(Uα) if β ∈ U α 0 otherwise
U α is a coset of the image of a linear function:

U α = Img x → f (x) ⊕ f (x ⊕ α) ⊕ f (α) ⊕ f (α)
Given the Feistel structure of the round function, we deduce

Pr[(δ L , δ R ) → (δ L , δ R )] = 2 -dim(U δ L ) if δ L = δ R and δ R ⊕ δ L ∈ U δ L 0 otherwise
-For a given β, there is an affine space V β such that

c(x • α, f (x) • β) 2 = 2 -dim(V β ) if α ∈ V β 0 otherwise
V β is a coset of the image of a linear function:

V β = Img x → (β ∧ (x ≪ a -b)) ⊕ ((β ∧ x) ≫ a -b) ≫ b ⊕ (β ≫ c)
For the Feistel-based round function, this implies

c((α L , α R ) → (α L , α R )) 2 = 2 -dim(Vα R ) if α R = α L and α L ⊕ α R ∈ V α R 0 otherwise
This provides an efficient representation of the differential transition matrix A and of the squared correlation matrix C. However, computing the transitions over the full space is still infeasible for n > 32, because we need at least to store a vector with 2 n elements.

δi ∅ 0 1 0,2 3 0,2,3,4 1,2 0,2,4 3 0,2 1 0 ∅ 0 αi ∅ 4 3 4,2 1 4,2,1,0 3,2 4,2,0 1 4,2 3 4 ∅ 4

A class of high probability trails

In this work we consider a class of trails that are only active in a window of w bits of each word (e.g., the w least significant bits). Several previous works have already shown that there exist iterative trails in this class for Simeck [START_REF] Bagheri | Linear cryptanalysis of reduced-round SIMECK variants[END_REF][START_REF] Qiao | Differential security evaluation of simeck with dynamic key-guessing techniques[END_REF][START_REF] Qin | Linear hull attack on round-reduced simeck with dynamic key-guessing techniques[END_REF] and Simon [21]; we give an example in Table 2. More generally, Simon and Simeck have a relatively slow diffusion. If a difference is restricted to the w least significant bits, it will stay on the w + 5 (for Simeck) or w + 8 (for Simon) least significant bits after one round. Moreover, the diffusion to bit w + 5 (respectively w+8) is non-linear; if it is absorbed then the difference stays on w+1 (respectively w+2) bits only. Therefore, we expect many high probability trails in this class. We detail our results on Simeck in this section, and we discuss Simon in Section 6. Let w ≤ n/2 and ∆ w be the vector space of differences active only in the w least significant bits (LSBs) of a word. Let ∆ 2 w be the product ∆ w × ∆ w where the two words are considered. For a given δ 0 , δ r ∈ ∆ w , we can compute a lower bound of the probability of the differential δ 0 → δ r by summing over all characteristics with intermediate differences in ∆ 2 w :

Pr[δ 0 r w δ r ] = δ1,δ2,...δr-1∈∆ 2 w r i=1 Pr[δ i-1 → δ i ] ≤ Pr[δ 0 r δ r ]
As mentioned in Section 2.1, we can compute these values by evaluating A r w where the coefficients of the matrix A w are the probabilities of transition Pr[δ → δ ] for all δ, δ ∈ ∆ 2 w . In order to reduce the memory requirement, we do not explicitly build the matrix A w but we use the properties of the previous section to compute it on the fly. Moreover, we focus on the probabilities Pr[δ 0 r w δ ] for a fixed δ 0 , i.e., a single line of A r w . Indeed, we can evaluate A r w × e δ0 (where e δ0 is the basis vector corresponding to δ 0 ) using iterated matrix-vector products. This is shown as Algorithm 1: we use a vector X to represent the probability distribution of the differences, and we update it iteratively. The complexity of the algorithm is bounded by r × 2 2w × max α∈∆w |U α | elementary operations. By increasing w, the lower bound is refined but the complexity increases, as seen in Figure 6. Our results show that the lower bounds grows very slowly after w = 16, therefore we expect to have a rather tight approximation. Moreover, we have performed experiments on 20-round distinguishers that closely match the prediction (Figure 7 and Figure 8). In practice, it takes about a week to run the algorithm with w = 18 and r = 30 using 1TB of RAM on a 48-core machine.

We have used this approach to evaluate the probability of differentials used in previous attacks against Simeck, and we find that the probability is significantly better than estimated in previous works (See Table 3). In particular, our approach covers a huge number of trails than cannot be listed individually (See Table 4).

For large numbers of rounds, the best characteristics we have identified with this search are a set of 64 characteristics with essentially the same probability, of the form (using a hexadecimal notation to represent the value in ∆ w ) [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF][START_REF] Abed | Differential cryptanalysis of round-reduced Simon and Speck[END_REF], (23, 1), (5, 2), (7, 2), (45, 2), (47, 2)} However, we note that the characteristic (0, 1) → (1, 0) is almost as good and will lead to a more efficient key-recovery (because it has fewer active bits). Therefore, we focus on this characteristic in the following. The corresponding probabilities are given in Table 4.

{(1, 2), (1, 3), (1, 22), (1, 23), (2, 5), (2, 7), (2, 45), (2, 47)} → {(2, 1), (3, 1),

Links between Linear and Differential trails

Alizadeh et al. have shown a duality between differential and linear trails in

Simon [START_REF] Alizadeh | Cryptanalysis of SIMON variants with connections[END_REF], that also applies to Simeck. Given a differential trail with probability p:

(α 0 , β 0 ) → (α 1 , β 1 ) → . . . → (α r , β r )
we can convert it into a linear trail:

( ← - β 0 , ← - α 0 ) → ( ← - β 1 , ← - α 1 ) → . . . → ( ← - β r , ← - α r )
where ←x denotes bit-reversed x. If all the non-linear gates are independent, the linear trail has squared correlation p. This explains that linear distinguishers and differential distinguishers of Simon-like ciphers are very similar. However they are not equivalent: when trails are more dense, there are dependencies when two different AND gates share an input, and the probabilities of the linear and differential trail are not the same.

Since our approach applies almost identically to differential cryptanalysis and linear cryptanalysis, we have also applied it to linear cryptanalysis. We consider masks in the set Λ 2 w active only in the w least significant bits, and we compute a lower bound on the ELP by summing over trails with intermediate masks in the set Λ 2 w . Since the diffusion of linear masks goes from most significant bits to least significant bits, the highest-bias trail with a single active bit is (2 w-1 , 0) → (0, 2 w-1 ). For simplicity, we rotate the trail by w -1 bits and display it as (1, 0) → (0, 1). We obtain a set of 64 (almost) optimal trails, corresponding to the bit-reversed versions of the optimal differential characteristics. We represent them after a rotation of w -7 bits for simplicity:

{(20,
(δ L , δ R )] X ← [0 for i ∈ ∆ 2 w ] X[δL, δR] ← 1 for 0 ≤ i < r do Y ← [0 for i ∈ ∆ 2 w ] for α ∈ ∆w do for β ∈ ∆w do for γ ∈ Uα do Y [β ⊕ γ, α] = Y [β ⊕ γ, α] + 2 -dim(Uα) X[α, β] X ← Y return X[δ L , δ R ]
Our results are given in Table 4 (where the trail (1, 2) → (2, 1) corresponds to (20, 40) → (40, 20)), and show that the results obtained for linear cryptanalysis and differential cryptanalysis are very close, but not identical.

Key Bits for Last-round Key Recovery

When a differential or linear distinguisher is extended into a key recovery attack, we have to study what are the key bits necessary to evaluate the statistical property after a few rounds. We denote the required key as k p , k t on the plaintext side, and k b , k c on the ciphertext side (see Figure 4), and the corresponding number of bits as κ p , κ t (respectively κ b , κ c ). The total number of required key bits is denoted as κ g = κ p + κ t + κ b + κ c . For simplicity, we focus on distinguishers with a single active bit, as used in this work.

Linear cryptanalysis. For linear cryptanalysis, we have to compute an internal bit x (i) j from the plaintext (or from the ciphertext). We compute recursively the necessary key bits following the expression of the round function. In the case of Simeck (see Algorithm 3 in Appendix A), the formula is: for Simeck64. We take 336 random keys with 2 46 random plaintext pairs each, and we count the number of pairs following the differential. The theoretical curve is a Poisson distribution with parameter λ = 2 46 × 2 -41.75 . We have 6408 good pairs in total, which gives an experimental probability of 2 -41.75 , matching our analysis.

x (i) j = (x (i-1) j ∧ x (i-1) j+5 ) ⊕ x (i-1) j+1 ⊕ x (i-2) j ⊕ k (i-1) j . ( 3
-4σ -3σ -2σ -σ 0 σ 2σ 3σ 4σ
Experimental Theoretical Fig. 8. Experimental verification of the 20-round linear distinguisher (1, 0) → (0, 1) for Simeck64. We take 336 random keys with 2 48 random plaintexts each, and we measure the experimental correlation over the available plaintexts. The theoretical curve is a normal distribution with parameter σ 2 = ELP +B/N ≈ 2 -41.74 + 2 -48 ≈ 2 -41.72 . The average square correlation observed is 2 -41.7 , matching the analysis.

Table 4. Comparison of the probability of differentials and the linear potential of linear approximations for Simeck (log 2 , computed with w = 18). We also give the total number of trails included in the bound in parenthesis (log 2 ) Differential Linear The algorithm returns the key bits that x (i) j depends on: a list of (linear combinations of) key bits with a linear effect on x (i) j , and a list of (linear combinations of) key bits with non-linear effect. Differential cryptanalysis. For differential cryptanalysis, we have to determine whether a pair of plaintexts (or ciphertexts) P, P reaches a specific internal state difference ∆x (i) = x (i) ⊕ x (i) after a few rounds. However, the plaintexts are not chosen randomly. Instead they have a specific pattern of differences that is fixed in advance, and known to potentially reach the target difference.

Rounds (0, 1) → (1, 0) (1, 2) → (2, 1) (1, 0) → (0, 1) (1, 2) → (2, 1) 1 0 (0) -∞ 0 (0) -∞ 2 -∞ -4.00 -∞ -4.000 3 -∞ -4.00 -∞ -4.000 4 -∞ -∞ -∞ -∞ 5 -∞ -∞ -∞ -∞ 6 -∞ -∞ -∞ -∞ 7 -∞ -∞ -∞ -∞ 8 -∞ -∞ -∞ -∞ 9 -∞ -∞ -∞ -∞ 10 -∞ -∞ -∞ -∞ 11 -
More precisely, we follow the approach of [START_REF] Qiao | Differential security evaluation of simeck with dynamic key-guessing techniques[END_REF][START_REF] Wang | Differential attacks on reduced SIMON versions with dynamic key-guessing techniques[END_REF] to track the propagation of differences in the additional rounds, assuming that a pair follows the differential. We use the rule that the output difference of an AND operator is 0 if and only if its input differences are (0, 0) and we identify bits with a fixed difference (0 or 1) and those with an unknown difference ( * ), as shown in Table 6. The number of bits with a fixed difference for round i is denoted i .

Next, we determine sufficient bit conditions for pairs following the input and output constraints of the extended path: a small set of bit conditions that ensure that we get the desired difference at the input and output of our differential when they are satisfied. The other differences are automatically satisfied if the bit conditions of the external rounds have already been checked. To determine the sufficient bit conditions, we proceed round by round, from the outer to the inner rounds. For each bit with a fixed output difference (0 or 1, not * ), we look at the input of the associated AND operator, and if they are different from (0, 0), then we add the condition corresponding to this output difference to the set of sufficient bit conditions.

Finally, for each sufficient bit condition, we compute the set of subkey bits required to check the condition. The goal is to determine which subkey bits are needed to compute a difference ∆x (i) j . For Simeck, we use the following relation:

∆x (i) j = (∆x (i-1) j ∧ x (i-1) j+5 ) ⊕ (∆x (i-1) j+5 ∧ x (i-1) j ) ⊕ (∆x (i-1) j ∧ ∆x (i-1) j+5 ) ⊕ ∆x (i-1) j+1 ⊕ ∆x (i-2) j . (4)
The resulting algorithm for the upper part is given as Algorithm 2 in Appendix A.

Comparison. Table 5 shows the number of key bits to guess for a linear or differential attack on Simeck with a single active bit, depending on the number of rounds. (Similar tables for Simon are given as Table 13 and Table 14 in Appendix A). The list of bits returned by the previous algorithms is simplified in order to keep only linearly independent combinations of bits. Moreover, we report the number of independent bits after removing bits that can be computed using the key schedule. We see that linear cryptanalysis requires a lower number of key bits to guess.

We now explain in detail key-recovery attacks against Simeck based on those distinguishers. We consider differential attacks in Section 4, and linear attacks in Section 5. 4 Key-recovery attacks using Differential Cryptanalysis

In this section, we detail differential key-recovery attacks on Simeck. We explain the dynamic key-guessing technique [START_REF] Qiao | Differential security evaluation of simeck with dynamic key-guessing techniques[END_REF][START_REF] Wang | Differential attacks on reduced SIMON versions with dynamic key-guessing techniques[END_REF] in Section 4.1 and we give our results in Section 4.2.

The dynamic key-guessing technique

Offline phase. Starting from a differential ∆ i → ∆ o covering R rounds, we append r 0 rounds before and r 1 rounds after and we build the extended differential as explained in Section 3.3. Then we identify sufficient bit conditions as shown in Table 6, and we identify the key bits required to check whether a pair reaches the difference specified by the distinguisher.

Online phase. Here we describe how the attack takes place from the construction of the pairs to the recovery of the possible master keys. First, we build structures of plaintexts such that the bits with a fixed difference in round 1 are identical for all the plaintexts in each structure. Each structure is composed of 2 n-1 plaintexts and if D denotes the data complexity, there are D × 2 1-n structures.

The structures are associated in pairs such that the differences between the two structures for bits with a fixed difference in round 1 correspond to the desired difference in the extended path. For each structure, the corresponding ciphertexts are saved in a table according to their value in the bits with fixed difference in C. This allows to filter the pairs at the output and 2 2(n-1)-r-1 pairs remains in each pair of structures.

Our goal is to associate partial key guesses to each of these pairs, such that they validate the internal differential. We proceed in a dynamic way. Round by round and for each sufficient bit condition, we associate to each pair the possible combinations of key bits that lead to the desired difference in the input and output of the distinguisher, according to the extended path. Some pairs and/or combinations of key guesses are progressively eliminated when they create an incompatibility with the required differential path. For each pair, when a combination of key bits that leads to ∆ i and ∆ o is found, we increment the counter corresponding to this combination of key bits. In total, at the end of the procedure we have incremented λ W × 2 κg counters on average, with λ W the average value of a counter for a wrong key guess. This process is partially compatible with the use of key schedule relations on one side of the distinguisher. Indeed, we guess key bits independently, and filter the combinations of bits which do not verify the relations given by the key schedule afterwards. The details of the attack (round by round) must be considered to calculate the time complexity of the attack.

When all pairs have been processed, we set a threshold s, and for each counter greater than s, we have to find the corresponding master keys. The information given by the κ g key bits is separated into 2 parts: we have bits of information on the first subkeys, and others on the last subkeys. Due to the non-linear key-schedule of Simeck, we cannot directly combine this information and do an exhaustive search on the κ -κ g missing bits. Instead, we use only the side for which we have the most information bits, and then we do an exhaustive search on the missing bits.

Complexity and success probability. In order to compute the complexity and the success probability of this attack, we need to estimate the average value of the counters for the right key and for wrong key guesses: we denote those values λ R and λ W .

As explained before, structures are associated in pairs. Let S 1 and S 2 denote two structures that form a pair. For each plaintext P1 in S 1 and for each key guess, we compute P2 = E -1

1 (E 1 ( P1 ) ⊕ ∆ i ) such that we have the relation E 1 ( P1 )⊕E 1 ( P2 ) = ∆ i . P2 necessarily belongs to S 2 , due to structures construction. So, if D denotes the data complexity of the attack, for each key guess we have D/2 pairs with the desired difference at the input of our distinguisher.

For the right key guess, if our differential occurs with probability p, we have λ R = p × D/2 pairs that satisfy ∆ o . By construction, all these pairs belong to the structures and pass the filters. On the other hand, for wrong key guesses, P1 and P2 don't actually have a difference ∆ i at the input of the distinguisher with the real encryption key, so the probability that they have a fixed difference ∆ o at the output is 1/2 n . The value of the counter for wrong key guesses is expected to be λ W = D/2 n+1 on average 1 .

We model the counter associated to the right key guess and a wrong key guess as a Poisson distribution with parameters λ R and λ W . We denote the cumulative distributive function as F R and F W . The probability that a counter associated to a wrong key guess is greater than a threshold s is 1 -F W (s), and the expected number of counters greater than s is

2 κg • (1 -F W (s)).
Let κ min and κ max be the minimum and the maximum of κ p + κ t and κ b + κ c . The cost of reconstructing the master keys from the remaining combinations is

2 κg • (1 -F W (s)) × 2 κ-κmax = 2 κ+κmin • (1 -F W (s))
. The time complexity is therefore determined by this term, but also by the data and the time required to scan all the counters at the end of the key-recovery: 2 κg . Knowing that most of the counters are at 0, this term could be reduced to the number of remaining pairs: 2 κg • λ W . The time complexity and success probability are:

C 1 = D + 2 κg • λ W + 2 κ+κmin • (1 -F W (s)) P S = 1 -F R (s)

40-round Key-recovery on Simeck64/128

We apply the methods described in the previous subsection with the differential (0, 1) to (1, 0) covering 30 rounds with probability p = 2 -60.41 . We append 3 rounds before and 7 rounds after. The extended path is given in Table 6 and the details of the bits to guess round by round are given in Table 12 (Appendix A). Round by round, we use the sufficient bit conditions from Table 6 to guess the key bits that lead to the desired differences. When possible, we filter using the relations of the key schedule. In the rightmost column, we detail the time complexity of each step starting from 2 t pairs. To compute this complexity more precisely, we split the round 33 in two parts corresponding to the two sufficient bit conditions. In total, the complexity of guessing the key bits leading to ∆ i and ∆ o , and incrementing the corresponding counters is 2 t+71 . During this step, κ min = 9 bits from the first subkeys and κ max = 114 from the last subkeys are guessed.

Attack parameters. If all the codebook (D = 2 64 ) is taken, knowing that 1 = 57 and 39 = 19, we split the data into 2 57 structures of 2 7 plaintexts and after constructing our pairs of structures and filtering the ciphertexts C, there remain 2 57-1 × 2 7×2 /2 19 = 2 51 pairs. So t = 51 and the time complexity for the counter incrementing part is 2 t+71 = 2 122 . The average value for the counter of the right key guess is λ R = p × D/2 = 2 2.59 . And for a bad key guess, we expect the counter to be close to λ W = D/2 64-1 = 2 -1 . So, if we choose to set the threshold s at 5, the complexity is 2 120.89 + 2 122 = 2 122.54 with a success probability of 55%.

We show parameters with different time/data trade-offs, as well as parameters for other variants of Simeck in Table 7.

Key-recovery attacks using Linear Cryptanalysis

The first description of a last-round key recovery attack using linear cryptanalysis was given by Matsui's Algorithm 2 [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF]. We consider a biased linear approximation P • α ⊕ C • β with P and C intermediate values after a few rounds of

q(k p , k t , k c , k b ) = 1 D #{P, C : P • α = C • β} -#{P, C : P • α = C • β} = 1 D P,C
(-1) P •α⊕C •β P • α and C • β are computed as a function of the partial key and some bits of the plaintexts/ciphertexts denoted as χ c (C) and χ p (P ) respectively (we assume that the bit positions correspond to the key bits in k p and k c ):

P • α = f (k t , k p ⊕ χ p (P )) C • β = g(k b , k c ⊕ χ c (C))
5.1 The FWT Approach 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] The time complexity of the attack is dominated by the time necessary to compute the statistic for all key candidates. Several tricks have been introduced to make this step more efficient. Since the values of P • α and C • β do not depend on the full plaintext/ciphertext, we can "compress" the dataset using a distillation phase where we only count how many plaintext/ciphertext pairs reach each value of those bits [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF]:

q(k p , k t , k c , k b ) = 1 D P,C (-1) f (kt,kp⊕χp(P ))⊕g(k b ,kc⊕χc(C)) = 1 D i∈F κp 2 j∈F κc 2 #{P, C : χ p (P ) = i, χ c (C) = j} × (-1) f (kt,kp⊕i)⊕g(k b ,kc⊕j)
We remark that the previous expression is actually a convolution:

= 1 D i,j φ(i, j) × ψ kt,k b (k p ⊕ i, k c ⊕ j) = 1 D (φ * ψ kt,k b )(k p , k c ), with φ(x, y) = #{P, C : χ p (P ) = x, χ c (C) = y} ψ kt,k b (x, y) = (-1) f (kt,x)⊕g(k b ,y)
Therefore, for a given k t , k b , we can evaluate q(k p , k t , k c , k b ) for all k p , k c with complexity Õ(2 κp+κc ) using a Fast Walsh Transform. This was first in [START_REF] Collard | Improving the time complexity of Matsui's linear cryptanalysis[END_REF] (with additional rounds on one side only), and then generalized in [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF]. The time complexity of the analysis is reduced to Õ(D + 2 κg ).

Statistical Models to Estimate the Success Probability

We follow the analysis of Blondeau and Nyberg [START_REF] Blondeau | Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis[END_REF][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], taking into account the impact of the variance of the correlation due to the random key, and the sampling model with a factor B depending on the type of attack: B = 1 if the plaintexts are randomly chosen with repetition, and B = (2 n -D)/(2 n -1) if they are distinct (in the following, we assume distinct plaintexts).

Single dominant characteristic. When there is a single dominant characteristic with absolute bias ε, the correlation of the approximation is either ε or -ε depending of the key. The empirical correlation for the right key follows one of two possible normal distributions, with parameters

µ R = ±ε σ 2 R = B/D + 2 -n .
When the key guess is wrong, we assume that the computed statistic follows the correlation of a random permutation; it follows a normal distribution with parameters

µ W = 0 σ 2 W = B/D + 2 -n .
Since there are two possible distributions for the right key, we have to slightly modify the analysis of (1). For an attack with gain a, we set a threshold s =

F -1 W (1 -2 -a-1 ) = σ W Φ -1 (1 -2 -a-1
) and keep key candidates with |q| ≥ s. The attack succeeds with probability P S = 1 -F R (s) when µ R > 0, and P S = F R (-s) otherwise:

P S = Φ |ε| -σ W Φ (1 -2 -a-1 ) σ R ,
where Φ is the cumulative distribution function of the standard normal distribution.

Single approximation with many trails. When using a single linear hull with many high correlation trails (rather than a dominant trail), the correlations for the right and wrong keys follow normal distributions with parameters:

µ R = 0 σ 2 R = B/D + ELP µ W = 0 σ 2 W = B/D + 2 -n ,
Following [START_REF] Blondeau | Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis[END_REF], we estimate the expected linear potential ELP using the correlations ε τ for characteristics τ in a set S of dominating characteristics:

ELP ≈ 2 -n + τ ∈S ε 2 τ ,
using the results of Section 3.1 to compute τ ∈S ε 2 τ with S the set of characteristics with masks in Λ w .

The distributions are both centered on zero, but since the variance is larger for the right key, we can sort the keys according to the absolute value of the measured correlation, and we expect a larger value for the right key than for wrong keys. More precisely, using a threshold s = σ W Φ -1 (1 -2 -a-1 ) on the absolute value of the correlation, the success rate is given by [10, Theorem 2]:

P S = 2 -2Φ σ W σ R Φ -1 (1 -2 -a-1
) .

Equivalently, we can consider the squared correlation, which follows a χ 2 distribution with one degree of freedom, and use the generic formula (1) with the following distributions:

F R /σ R ∼ χ 2 1 F W /σ W ∼ χ 2 1
The attack is decomposed in three phases:

Distillation phase. Compute φ(x, y) = #{P, C : χ p (P ) = x, χ c (C) = y} for 0 ≤ x < 2 κp , 0 ≤ y < 2 κc .
This only requires to set up 2 κp+κc counters, and to iterate over the D available plaintext/ciphertext pairs. Analysis phase. For each guess of k t , k b , for all 0 ≤ x < 2 κp , 0 ≤ y < 2 κc , compute ψ kt,k b (x, y) = (-1) f (kt,x)⊕g(k b ,y) , then evaluate the convolution φ * ψ kt,k b using the Fast Walsh Transform.

For each k t , k b , this requires 2 κp+κc evaluations of f and g to generate ψ kt,k b , and 3(κ p + κ c )2 κp+κc additions and 2 κp+κc multiplications to evaluate the convolution. Assuming that the cost of κ p + κ c additions and the cost of a multiplication are comparable to the cost of an encryption call, the total complexity of the analysis phase is O(2 κg ) using a memory of size 2 κp+κc . Search phase. For all keys with q(k p , k t , k c , k b ) ≥ s, exhaustively try all master keys corresponding to

k p , k t , k c , k b . With a threshold s = F -1 W (1 -2 -a )
we expect a fraction 2 -a of the keys to remain. We iterate over 2 88+16 candidates k p , k t , k c , k b that satisfy the 14 key schedule equations between k t and k p , keep only the 88 independent bits of k p , k t for keys meeting the threshold, and exhaustively search the remaining 40 bits, with a complexity of 2 88+16-a × 2 40 = 2 144-a .

With our parameters, we have κ g = 118 (after removing the two relations between bits of k t ). Using the Walsh transform pruning technique of [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF] (and partially precomputing the Walsh transform of ψ), the complexity of the analysis phase is reduced to2 :

68ρ A 2 68 + 2ρ M 2 118 + ρ A 2 64 (2 54 + 39 × 2 40 ) + ρ A 2 90 (2 14 + 13 × 2 14 ) ≈ 2ρ M 2 118
with ρ A the cost of an addition, and ρ M the cost of a multiplication. Assuming that 2 multiplications correspond to roughly one evaluation of the cipher, we end up with a complexity of 2 κg . This variant uses a memory of 2 κp+κc +2 κp+κt +2 κc+κ b = 2 68 + 2 102 + 2 16 ≈ 2 102 elements.

Attack Parameters

We use this attack to target 41 or 42 rounds of Simeck64, and smaller variants of Simeck, with various time/data trade-offs summarized in Table 8. We explain two attacks in detail here and defer some others to Appendix B.

42-round

Simeck64 with 2 63.5 plaintexts. The ELP of the linear approximation (1, 0) → (0, 1) over 30 rounds is 2 -64 + 2 -60.36 = 2 -60. 25 . The complexity of the analysis phase is 2 118 . With an advantage of a = 24, the complexity of the search phase is 2 120 and the success probability is P S = 8.3%. Since Simeck is rotation-invariant, we can repeat the attack 32 times by rotating the linear approximation used. On average we expect the attack to succeed after 1/P S = 12 attempts, leading to an average complexity of 2 123.9 . If we fix this as the maximum complexity, we expect a success rate of roughly 1 -1/e ≈ 63%.

41-round Simeck64 with 2 63 plaintexts. Alternatively, we can use multiple linear approximations to reduce the time complexity of a 41-round attack. We use the following 29-round linear approximations:

(1, 0) → (0, 1) : ELP = 2 -64 + 2 -58.47 (1, 0) → (1, 0) : ELP = 2 -64 + 2 -60.36
(1, 0) → (1, 1) : ELP = 2 -64 + 2 -60.36 (0, 1) → (0, 1) : ELP = 2 -64 + 2 -60.36

(1, 1) → (0, 1) : ELP = 2 -64 + 2 -60.36

The extra approximations have been chosen because the corresponding masks can be computed from the same keys bits as the main approximation (1, 0) → (0, 1); they have a combined capacity of 2 -57.39 . Thanks to the higher capacity, we can aim for a higher advantage a = 52, and obtain a success rate of 23% with 2 63 plaintexts. Therefore, we split the key recovery rounds as 7 rounds on the plaintext side and 5 on the ciphertext side (rather than 8 and 4), leading to parameters κ p = 45, κ t = 30, κ c = 23, κ b = 7; this reduces the complexity of the analysis phase to 5 × 2 105 , while the search phase has a complexity of 2 128+23+7-52 = 2 106 .

Experimentations

We have performed experimentations to verify the theory leading to the probabilities of success P S . To do this, we take a set of D plaintext/ciphertext pairs and we compute the experimental correlation Q(k) for the right key and for a random sample of wrong keys. We choose an advantage a and we consider that a success is obtained when the correlation of the right key is among the 2 -a highest correlations. This experiment was repeated 1000 times with random keys to compute an experimental success probability. Our results are presented in Table 9. We compare attacks with a single approximation (1, 0) → (0, 1) and attacks with five approximations (1, 0) → (0, 1), (1, 0) → (0, 1), (1, 0) → (0, 1), (1, 0) → (0, 1), (1, 0) → (0, 1), as used in the 41-round attack with 2 63 plaintexts. The experimental probability of success is close to the prediction, confirming that both the model for the success probability, and our estimation of the ELP are accurate.

For Simeck32, we compute the exact ELP of the linear approximation using our algorithm with w = 16; we obtain an ELP of 2 -30.73 over 15 rounds for (1, 0) → (0, 1) and 2 -31.59 for the four other approximations.

Application to Simon

Similarly to Simeck, previous results [START_REF] Liu | Optimal differential trails in SIMON-like ciphers[END_REF] have shown the existence of iterative trails for Simon with a single active bit in the input and output, where all intermediate states fit in a small window of active bits. This makes Simon an interesting target for our analysis, just like Simeck. In this section we focus on linear cryptanalysis, and we obtain improved attack against Simon96 and Simon128, gaining between 3 and 7 rounds compared to previous attacks.

Previous works have shown that Simon offers a higher security against differential and linear cryptanalysis than Simeck. In particular, iterative trails have a higher weight, and require a larger window of active bits. Moreover, we notice that the trail (1, 0) → (0, 1) is only possible for round numbers of the form 4r + 1, because some bits have a linear update when the trail is limited to a window smaller than the word size. More precisely, for linear trails, the high order bits follow a pattern Since the transition matrix is sparser than for Simeck we can run our analysis with larger values of w. The lower bound on the ELP that we obtain for the trail (1, 0) → (0, 1) is given in Table 11. The bounds show a smaller linear potential (and differential probability) for Simon than for Simeck. However, we see in Figure 9 that the linear potential still increases significantly with the window size w; this indicates that our bound is not as tight as on Simeck. Further work is needed to capture the full clustering effect on Simon, and this could further reduce the security margin of the cipher. The approximations (1, 0) → (0, 1) can be extended by one round on either side with correlation 2 -2 , leading to two active bits. After rotating the approximation by two bits to (4, 0) We summarize the parameters of the best attacks we have identified against Simon96 and Simon128 in Table 10; our analysis does not seem to improve previous results on Simon32, Simon48 and Simon64. As shown in Table 13 and Table 14, we don't have any key-schedule relation between bits of k t or k b , but we have relations between k t and k p or between k b and k c . Therefore we can use the Walsh transform pruning technique of [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF], as in the Simeck attacks. We explain two attacks in detail below.

56-rounds Simon128/256. We use the 41-round linear approximation (1, 0) → (0, 1) with ELP lower bound of 2 -123.07 +2 -128 . We add 8 rounds on the plaintext side, and 7 rounds on the ciphertext side, obtaining parameters κ p = 80, κ t = 65, κ c = 64, κ b = 37. The complexity of the analysis phase is about 2 246 . With 2 126 data, and an advantage a = 10, we have a success probability of 26% and the search phase has a complexity of 2 246 . Finally we obtain an average complexity of (2

Perspectives

Our work provides the first attack against 42-round Simeck64, showing that the security margin is very slim (the full version has 44 rounds). Moreover, if the designers of Simeck had proposed a 128-bit variant with the same number of rounds as Simon128, the full version would be broken by our analysis. We also improve significantly previous attacks on Simon. In particular we show that Simon96/144 only has 17% of the rounds as security margin, while the designers wrote [START_REF] Beaulieu | Notes on the design and analysis of SIMON and SPECK[END_REF]: "After almost 4 years of concerted effort by academic researchers, the various versions of Simon and Speck retain a margin averaging around 30%, and in every case over 25%. The design team's analysis when making stepping decisions was consistent with these numbers."

Comparison of differential and linear cryptanalysis. Our work shows that differential and linear attacks against Simon and Simeck are very similar. The differential characteristics and linear approximations are almost equivalent; we use trails with a single input/output bit in both cases, and the differential probability p is almost the same as the linear potential ELP (See Table 4). Using advanced techniques (dynamic key-guessing and Fast Walsh Transform respectively), both attacks have a complexity that is essentially D + 2 κg (with

D = O(1/p) or D = O(1/ ELP) respectively).
However, there is an important difference in the key-recovery part. As seen in Table 5, we have to guess more key bits for differential cryptanalysis than for linear cryptanalysis (for the same number of additional rounds). This explains why linear cryptanalysis is more efficient than differential cryptanalysis on those ciphers, as shown by previous analysis.

Impact of the rotations. The main difference between Simeck and Simon is the value of the rotations of the round function. In order to find which combinations of the rotation constants a, b and c would be a bad or a good choice, we reuse Algorithm 1 to obtain a lower bound for the probability of a differential for several values of a, b and c. We set the following parameters: w = 13, r = 30, and 0 ≤ a, b, c ≤ 10. A lower bound of the probability of all the differentials with input (δ L , δ R ) = (0, 1) is computed, and this allows to confirm that the following trivial conditions must be verified: a, b and c must all be different, c must be different from 0, and a, b and c must be of different parity: the three shifts must not be all even or all odd.

We also notice that (a, b, c) must not be of the form (i, 2j -i, j) or (2j -i, i, j) and that the bias we observe strongly decreases when c increases. However, this does not allow us to conclude that taking a large value of c ensures a better security since it is possible that there exists other differentials with high bias. Our approach does not allow to conclude when a and b are smaller than c because in this case, the difference cannot remain in a fixed window after a large number of rounds. This is due to the fact that the difference generated by the linear part can never cancel out with the difference of the non-linear part.

Alternative class. Instead of using differences or masks in a fixed window of w bits, we could consider low-weight values. Indeed, this class also includes the iterative trails given in previous works, and should contain many high-probability trails. We have implemented the search algorithm with this alternative class, using 32-bit words of weight at most 5 (a set of 2 17.9 values).

In terms of resources, this requires roughly the same amount of memory as with a window of size w = 18, but it runs about 50 times faster, because there are fewer possible transitions at each round: the probability to reach a value with weight lower than 5 is smaller than the probability to stay in a fixed window. However, the bounds given with this class on Simeck and Simon are not competitive with those obtained with a fixed window. On Simeck, using words of weight 5 gives probabilities comparable to using a window with w = 9, largely below w = 18. On Simon, the gap is smaller: we obtain results similar to using a window of size w = 15. In both cases, using a fixed window requires fewer resources (time and memory) to achieve the same quality of results. Fig. 10. Evolution of the probabilities, starting from (0, 1). We took w = 8 but the figure is cropped to a quarter. We can observe the convergence towards a stationary distribution. Note that when starting from (0, 1), we can never obtain a pair of even differences by going through ∆ 2 w , which is why a quarter of the points are missing.

B Details of additional attacks

Fig. 4 .

 4 Fig. 4. General description of a cipher.

  40), (22, 40), (60, 40), (62, 40), (50, 20), (51, 20), (70, 20), (71, 20)} → {(40, 20), (40, 22), (40, 60), (40, 62), (20, 50), (20, 51), (20, 70), (20, 71)}

Fig. 6 .Fig. 7 .

 67 Fig.6. Effect of w on the probability of Simeck differentials.

  000 * * 001 * * 0000000000000000 * 000 * * 00 * * * 01 * * * 50 1 00000000000000000000000000 * 0001 * 000000000000000000000 * 000 * * 001 * * 57 2 00000000000000000000000000000001 00000000000000000000000000 * 0001 * 62 3 00000000000000000000000000000000 00000000000000000000000000000001 64 30-round differential (3 → 33) 33 00000000000000000000000000000001 00000000000000000000000000000000 64 34 00000000000000000000000000 * 0001 * 00000000000000000000000000000001 62 35 000000000000000000000 * 000 * * 001 * * 00000000000000000000000000 * 0001 * 57 36 0000000000000000 * 000 * * 00 * * * 01 * * * 000000000000000000000 * 000 * * 001 * * 50 37 00000000000 * 000 * * 00 * * * 0 * * * * 1 * * * * 0000000000000000 * 000 * * 00 * * * 01 * * * 41 38 000000 * 000 * * 00 * * * 0 * * * * * * * * * * * * * * 00000000000 * 000 * * 00 * * * 0 * * * * 1 * * * * 30 39 0 * 000 * * 00 * * * 0 * * * * * * * * * * * * * * * * * * * 000000 * 000 * * 00 * * * 0 * * * * * * * * * * * * * * 19 40 * * 00 * * * 0 * * * * * * * * * * * * * * * * * * * * * * * * 0 * 000 * * 00 * * * 0 * * * * * * * * * * * * * * * * * * * 10

( 10 *

 10 ..., 0*0...) → (0*0..., 10*...) → (10*..., 0*1...) → (0*1..., 10*...) → (10*..., 0*0...)

r→

  (0, 4) with ELP c, the extended approximations are (4, 0) r+1 → (4, 1) and (1, 4) r+1 → (0, 4) with ELP 2 -2 c, and (1, 4) r+2 → (4, 1) with ELP 2 -4 c.

Table 13 .

 13 Comparison of key recovery rounds for linear attacks against Simon (plaintext side

  1.2 Description of Simon and SimeckSimonn/κ and Simeckn/κ are Feistel block ciphers with block size n ∈ {32, 48, 64, 96, 128} and key size κ ∈ {n, 1.5n, 2n}. There are 10 versions of Simon, with the following parameters:

	n 32	48	64	96	128
	κ 64 72 96 96 128 96 144 128 192 256
	r 32 * 36 36 * 42 44 * 52 54 68 69 72

Table 2 .

 2 An example of 12-round iterative trail (differential and linear) for Simeck. We show a list of active bits.

	i	0	1	2	3	4	5	6	7	8	9	10	11	12	13

Table 3 .

 3 Comparison of our lower bound on the differential probability for Simeck (with w = 18), and estimates used in previous attacks.

	Rounds	Differential	Proba (previous) Ref Proba (new)
	26	(0, 11) → (22, 1)	2 -60.02	[18]	2 -54.16
	26	(0, 11) → (2, 1)	2 -60.09	[25]	2 -54.16
	27	(0, 11) → (5, 2)	2 -61.49	[21]	2 -56.06
	27	(0, 11) → (5, 2)	2 -60.75	[16]	"
	28	(0, 11) → (A8, 5)	2 -63.91	[16]	2 -59.16
	Algorithm 1. Computation of Pr[(δL, δR)

r w

  )

		-44
		-48
		-52
		-56
	2 (Pr[(0,	-60 -64 -68
	log	-72
		6	8	10	12	14	16	18
				w

Table 5 .

 5 Comparison of key recovery rounds for differential and linear attacks against Simeck64/128.

	Key bits	Differential		Linear
	Rounds total independent total independent
	1	0	0	0	0
	2	2	2	2	2
	3	9	9	7	7
	4	27	27	16	16
	5	56	56	30	30
	6	88	88	50	48
	7	120	114	75	68
	8			104	88

Table 6 .

 6 Extended path for 40 rounds of Simeck64/128. Red bold bits represent the sufficient bit conditions.

Table 7 .

 7 Attack parameters for differential attacks on Simeck. C1 is the time complexity to run the attack a single time, and the corresponding success probability is PS. The average time is obtained as C1/PS, by assuming that the attack is repeated until it succeeds, using rotations of the initial differential. 64 2 2.59 2 -1 6 2 122 + 2 117.07 0.40 2123.4 Simeck64/128 40 = 3 + 30 + 7 9 114 2 64 2 2.59 2 -1 5 2 122 + 2 120.89 0.55 2123.4

	Cipher	Rounds	κmin κmax D λR λW s	C1	PS Time
	Simeck64/128 40 = 3 + 30 + 7 9 114 2 Simeck64/128 40 = 3 + 30 + 7 9 114 2 63 2 1.59 2 -2 4 2 121 + 2 119.79 0.19 2 123.9
	Simeck48/96 30 = 2 + 22 + 6 2	74 2 48 2 1.58 2 -1 5 2 75 + 2 81.9 0.08 2 85.5
	Simeck48/96 30 = 2 + 22 + 6 2	74 2 47 2 0.58 2 -2 3 2 74 + 2 85.1 0.06 2 89.1
	Simeck32/64 22 = 3 + 13 + 6 8	51 2 32 2 2.98 2 -1 5 2 58 + 2 55.9 0.80 2 58.6
	Simeck32/64 22 = 3 + 13 + 6 8	51 2 31 2 1.98 2 -2 4 2 57 + 2 54.8 0.36 2 58.8

encryption/decryption. Given a set of D known plaintexts/ciphertexts pair (P, C), we can compute the intermediate values P and C for each partial key guess k g = (k p , k t , k c , k b ) for the first and/or last rounds, and compute the experimental correlation of the linear approximation:

Table 8 .

 8 Attack parameters for linear attacks on Simeck. C1 is the time complexity to run the attack a single time, and the corresponding success probability is PS. The average time is obtained as C1/PS.

	Cipher	Rounds	#app. Capacity D Adv.	C1	PS Time
	Simeck64 41 = 7+29+5	5	2 -57.34	2 63	52 5 × 2 105 + 2 106 0.23 2 110
		41 = 8+29+4	1	2 -58.44	2 62	26	2 118 + 2 118	0.11 2 122.2
		42 = 8+30+4	1	2 -60.25 2 63.5 24	2 118 + 2 120	0.08 2 123.9
		42 = 8+30+4	1	2 -60.25	2 64	29	2 118 + 2 115	0.10 2 121.5
	Simeck48 32 = 7+21+4	1	2 -43.50	2 47	26	2 87 + 2 86	0.10 2 90.9
	Simeck32 23 = 5+13+5	1	2 -27.68 2 31.5 37	2 58 + 2 56	0.07 2 62.2

Table 9 .

 9 Comparison of the theoretical (PS) and experimental success probability for linear attacks. We perform 1000 experiments, taking D pairs of plaintext/ciphertext and testing whether the correlation associated to the right key is among the 2 -a highest correlations with a sample of random wrong keys.

	Cipher	Rounds D # app. capacity # wrong keys Adv. Success PS
	Simeck32/64	15	2 31	1	2 -30.73	2 8	5	7.4% 9.9%
	Simeck32/64	15	2 31	5	2 -29.05	2 8	5	9%	7.4%
	Simeck32/64	16	2 31	1	2 -31.59	2 8	5	4.9% 4.5%
	Simeck32/64	16	2 31	5	2 -29.44	2 8	5	3.6% 2.3%
	Simeck64/128	12	2 28	1	2 -26.39	2 12	10	9.9% 10.1%
	Simeck64/128	12	2 28	5	2 -25.17	2 12	10	14.8% 14.8%

Table 10 .

 10 Attack parameters for linear cryptanalysis of Simon.

	Cipher	Rounds	κp, κt, κc, κ b D a	C1	PS Time	Approx
	S128/256 56 = 8+41+7 80, 65, 64, 37 2 126 10 2 246 + 2 246 0.26 2 249 (1, 0) → (0, 1)
	S128/192 55 = 7+42+6 64, 37, 56, 23 2 127 10 2 180 + 2 182 0.13 2 185.2 (4, 0) → (4, 1)
	S128/128 53 = 6+42+5 47, 18, 38, 9 2 127 10 2 112 + 2 118 0.13 2 121 (4, 0) → (4, 1)
	S96/144 45 = 6+33+6 47, 18, 47, 18 2 95 10 2 130 + 2 134 0.19 2 136.5 (1, 0) → (0, 1)
	S96/96 43 = 5+33+5 30, 7, 30, 7 2 94 10 2 74 + 2 86 0.08 2 89.6 (1, 0) → (0, 1)

Table 11 .

 11 ELP of the linear approximation (1, 0) → (0, 1) and probability of the differential (0, 1) → (1, 0) for Simon (log 2 , computed with w =[START_REF] Lai | Markov ciphers and differential cryptanalysis[END_REF]

	r	13	17	21	25	29	33	37	41	45
	ELP -41.99 -46.30 -67.87 -77.90 -87.25 -92.60 -113.06 -123.07 -132.95
	Pr	-40.68 -47.31 -67.56 -78.08 -86.96 -94.62 -113.67 -124.22 -133.66

  246 + 2 246 )/0.26 ≈ 2 249 . Effect of w on the probability of Simon linear hulls.55-rounds Simon128/192. For Simon128/192, we use the 42-round linear approximation (4, 0) → (4, 1) with an ELP lower bound of 2 -125.07 + 2 -128 . We add 7 rounds on the plaintext side, and 6 rounds on the ciphertext side, obtaining parameters κ p = 64, κ t = 37, κ c = 56, κ b = 23. The complexity of the analysis phase is about 2 180 . With 2 127 data, and an advantage a = 10, we have a success probability of 13% and the search phase has a complexity of 2 182 . Finally we obtain an average complexity of (2 180 + 2 182 )/0.13 ≈ 2 185.2 . -93.57 + 2 -96 . We add 6 rounds on each side, obtaining parameters κ p = 47, κ t = 18, κ c = 47, κ b = 18. The complexity of the analysis phase is about 2 130 . With 2 95 data, and an advantage a = 10, we have a success probability of 19% and the search phase has a complexity of 2 134 . Finally we obtain an average complexity of (2 130 + 2 134 )/0.19 ≈ 2 136.5 .

	1)]) (0, r w 0) 2 (ELP[(1, log	-80 -84 -88 -92 -96 -100 -104 -108 -112 -116 -120 -124 -128 -132 -136 -140 -148 -144									r = 25 r = 33 r = 41
		9	10	11	12	13	14	15	16	17	18	19
							w
		Fig. 9.

45-rounds Simon96/144. We use the 33-round linear approximation (1, 0) → (0, 1) with an ELP lower bound of 2

Table 15 .

 15 Summary of attacks against Simon and Simeck. Attacks marked with † recover information about subkey bits, but the advantage is too low to attack the cipher. Attacks marked with ‡ use the duality between linear and differential trails, which is not exact.

	Cipher	Rnds Data Time Mem Succ. rate Ref Note
	Simeck32/64	22	2 32	2 57.9	2 32	0.47	[24] Differential †
		22	2 32	2 56	2 26.3	0.73	[16] Differential †
		22	2 31	2 63	2 55.9	1	[20] Integral
		23 2 31.91 2 61.78		0.47	[25] Linear † ‡
		27	3	2 62.94 2 50	1	[26] Correlated sequence
		22	2 31	2 58.8	2 59	0.63	New Differential
		23	2 31.5 2 62.2	2 44	0.63	New Linear
	Simeck48/96	26	2 47	2 95 2 82.52	1	[20] Integral
		26	2 47	2 62	2 47	0.75	[18] Differential
		28	2 46	2 68.3		0.47	[24] Differential †
		29	2 47	2 83.1 2 31.5	0.78	[16] Differential †
		30 2 47.66 2 88.04		0.87	[25] Linear † ‡
		30	2 48	2 85.5	2 76	0.63	New Differential
		32	2 47	2 90.9	2 55	0.63	New Linear
	Simeck64/128 33	2 63	2 115	2 63		[18] Differential
		35	2 63 2 116.3 2 63	0.55	[24] Differential †
		35	2 62 2 105.5 2 30.7	0.73	[16] Differential †
		37 2 63.09 2 121.25		0.47	[25] Linear † ‡
		40	2 63 2 123.9 2 123	0.63	New Differential
		41	2 63	2 110	2 105	0.63	New Linear
		42	2 63.5 2 123.9 2 68	0.63	New Linear
		42	2 64 2 121.5 2 68	0.63	New Linear
	Simon96/96	37	2 95.2	2 88		0.48	[12] Linear
		37	2 95	2 87.2			[27] Differential
		43	2 94	2 89.6	2 94	0.63	New Linear
	Simon96/144	37	2 95 2 130.8			[27] Differential
		38	2 95.2 2 136		0.48	[12] Linear
		45	2 95 2 136.5 2 95	0.63	New Linear
	Simon128/128 49 2 127.6 2 120		0.48	[12] Linear
		50	2 127 2 119.2			[27] Differential
		53	2 127	2 121	2 127	0.63	New Linear
	Simon128/192 51 2 127.6 2 184		0.48	[12] Linear
		51	2 127 2 183.2			[27] Differential
		55	2 127 2 185.2 2 127	0.63	New Linear
	Simon128/256 51	2 127 2 247.2			[27] Differential
		53 2 127.6 2 249		0.48	[12] Linear
		56	2 126	2 249	2 144	0.63	New Linear

Table 12 .

 12 Details of the bits to guess round by round and the corresponding complexity when starting from 2 t

	pairs.

The same result can be obtained using the formulas in[START_REF] Qiao | Differential security evaluation of simeck with dynamic key-guessing techniques[END_REF] and the code provided by the authors of this paper.

With their notations, we have k0 = 54, k1 = 50, k2 = 2, k3 = 14, l12 = 2, l0 = 14, l3 = 0

Acknowledgements. We would like to thank the authors of [24] for sharing their automatic tool. The second author is funded by a grant from Région Ile-de-France. and the third author by ERC ADG 740972 (ALGSTRONGCRYPTO). This work was also supported by ANR grant ANR-20-CE48-0017 (SELECT).

Multiple approximations. When using M linear approximations, there are different ways to exploit the information to rank the keys. Again, we follow the analysis of [START_REF] Blondeau | Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis[END_REF], and we rank the keys according to

According to [START_REF] Blondeau | Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis[END_REF], we can model the statistics for the right key as a Gaussian distribution with parameters

On the other hand the statistic for the wrong key is proportional to a χ 2 distribution with M degrees of freedom:

In our analysis, we consider either a single approximation (1, 0) → (0, 1), or the approximation (1, 0) → (0, 1) combined with lower quality approximations that can be used with the same key bits.

12-round Key-recovery

We apply the previous techniques to Simeck64, starting from the linear approximation (0, 1) → (0, 1), and adding 8 rounds on the plaintext side and 4 rounds on the ciphertext side. Following Algorithm 3, x [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] 0 can be computed from κ p = 54 bits of P , κ p = 54 bits of the whitening key k p = k (0) k (1) , and κ t = 50 additional key bits. Similarly, x (r-5) 0 can be computed from κ c = 14 bits of C, κ c = 14 bits of the whitening key k (r-1) k (r-2) , and κ b = 2 additional key bits:

[0,-1,...,-13,-15,-16,-17,-20,-21,-25] , k

[0,-1,-2,-3,-5,-6,-7,-8,-10,-11,-12,-15,-16,-20] , k

[0,-1,-2,-5,-6,-7,-10,-11,-15] , k

[0,-1,-5,-6,-10] , k

We ignore bits that have a linear effect because they only flip the sign of the imbalance. Moreover, we can use key schedule relations to reduce κ t by 2:

There are 14 additional relations between bits of κ t and κ p .

A Key bits involved in the key recovery Algorithm 2. key_bits_for_diff (i, j) Input: a round number i and a bit position j. The extended path is supposed to be known and readable. Output: a list of the necessary subkey bits to compute ∆x

Input: a round number i and a bit position j. Output: the subkey bits needed to compute x (i) j split into a bit combination that affects x (i) j linearly, and the remaining bit combinations.

B.1 Linear cryptanalysis of 23-rounds Simeck32

Starting from the linear approximations (0, 1) → (1, 0), we add 5 rounds on the plaintext side, and 5 on the ciphertext side. We need the following key bits, with κ p = 22, κ t = 7, κ c = 22, κ b = 7:

[0,-1,...,-8,-10,-11,-12,-15] , k

[0,-1,-2,-5,-6,-7,-10,-11,-15]

[0,-1,-5,-6,-10] , k The complexity of the analysis phase is about 2 κg = 2 58 . For Simeck32, we can compute the exact ELP of the linear approximation using our algorithm with w = 16; we obtain an ELP of 2 -27.68 over 13 rounds. With 2 31.5 data, and an advantage a = 37, we have a success probability of 7% and the search phase has a complexity of 2 56 . Finally we obtain an average complexity of (2 58 + 2 56 )/0.07 ≈ 2 62.2 .

B.2 Linear cryptanalysis of 32-round Simeck48

Starting from the linear approximations (0, 1) → (1, 0), we add 7 rounds on the plaintext side, and 4 on the ciphertext side. We need the following key bits, with κ p = 41, κ t = 30, κ c = 14, κ b = 2:

[0,-1,-2,-3,-5,-6,-7,-8,-10,-11,-12,-15,-16,-20] , k

[0,-1,-2,-5,-6,-7,-10,-11,-15] , k

[0,-1,-5,-6,-10] , k

The complexity of the analysis phase is about 2 κg = 2 87 . Over 21 rounds, we have ELP = 2 -43.56 ; with 2 47 data, and an advantage a = 26, we have a success probability of 10% and the search phase has a complexity of 2 86 . Finally we obtain an average complexity of (2 87 + 2 86 )/0.1 ≈ 2 90.9 .

C Observations on Simeck differentials

Let A w be the matrix of difference propagations in a Simeck64 round, in the space ∆ 2

w . If we start from an arbitrary difference, then it represents a distribution vector C with a single non-zero component, and the distribution of differences after r rounds is given by A r w C.

35

When r increases, A r w C will eventually converge towards λ r w V where λ w is the highest eigenvalue of A, and V is a corresponding eigenvector. Taking a higher w decreases the value λ w . This vector V represents a stationary distribution of differences in ∆ 2

w . Once we approach this distribution, each round is passed with the same probability. This is represented in Figure 10.

With our first experiments, we conjectured that λ w converged towards 1/4 when w increased. This turned out to be disproved by w = 10. Thus for w higher than 10, an input difference following the stationary distribution remains in ∆ 2 w with probability larger than 1/4 after one Simeck round.

Observing the Truncated Differential Path. A quick look at the probabilities of (0, 1) → (1, 0) given in Table 4 shows that they are well approximated by 2 -1.9r-3.5 , where r is the number of rounds. The 1.9 value comes from the stationary distribution, and corresponds to the largest eigenvalue of A w for w = 18. The additional 3.5 comes from the connection between (0, 1), (1, 0) and ∆ 2 w in the first and last rounds of the differential path. When starting from (0, 1), the single-bit differential can expand at a low cost before it starts to reach outside ∆ 2 w . Since the largest rotation in Simeck is by 5 bits, for w = 18, the three first rounds are even completely free. After that, the difference will stay in ∆ 2 w with some probability, converging towards the stationary distribution.

In fact, the typical behavior in this first expansion phase is to increase the number of active bits by a small amount, typically one (two for the two words), at each round. This is because the probability of such transitions is larger than the probability of a stationary transition. Indeed, to increase by only one bit, it is enough to have 4 ANDs equal to zero, with probability ≥ 2 -1.7 instead of the stationary 2 -1.9 .

In the stationary phase, the truncated difference remains in the space ∆ 2 w . At some point, it needs to connect with the final difference (1, 0). This is the last, compression phase. Similarly as the first phase, the typical intermediate steps consist in reducing progressively the range of active bits. A single-bit reduction at each round is the most probable.