Christof Beierle
email: christof.beierle@rub.de

Marek Broll
email: marek.broll@rub.de

Federico Canale
email: federico.canale@rub.de

Nicolas David
email: nicolas.david@inria.fr

Antonio Flórez-Gutiérrez
email: antonio.florez-gutierrez@inria.fr

Gregor Leander
email: gregor.leander@rub.de

María Naya-Plasencia
email: maria.nayaplasencia@inria.fr

Yosuke Todo
email: yosuke.todo.xt@hco.ntt.co.jp

Improved Differential-Linear Attacks with Applications to ARX Ciphers

Keywords: Symmetric Cryptanalysis, ARX, Chaskey, ChaCha

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Symmetric cryptographic primitives play major roles in virtually any cryptographic scheme and security-related application. The main reason for this massive deployment of symmetric primitives, i.e., (tweakable) block ciphers, stream ciphers, hash functions, or cryptographic permutations, is their significant performance advantage. Symmetric primitives usually outperform other cryptographic schemes by up to several orders of magnitude.

One class of design of symmetric primitives that is inherently motivated by (software) efficiency is the ARX-based design. ARX is short for addition (modulo a power of two), word-wise rotation and XOR. Indeed, ciphers following this framework are composed of those operations and avoid the computation of smaller S-boxes through look-up tables. As CPUs may have these operations implemented on the hardware level, particularly an addition unit and a barrel shifter, executing them on such CPUs based on a suitable register size is inherently fast.

The block cipher FEAL [START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF] was probably the first ARX cipher presented in the literature, and by now, several state-of-the-art ciphers follow this approach. One of the most important (families of) ARX ciphers is certainly the one formed by Salsa20, ChaCha and their variants [START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Bernstein | ChaCha, a variant of Salsa20[END_REF]. Designed by Bernstein, these ciphers are now the default replacement for RC4 in TLS due to their high efficiency and the simplicity of their implementations, and are thus some of the most widely-used ciphers in practice. Besides being used in TLS, ChaCha is also deployed in several other products, and in particular, it is used as a building block in the popular hash functions Blake and Blake2 [START_REF] Aumasson | SHA-3 proposal Blake[END_REF][START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF].

The ARX-based design approach is not restricted to stream ciphers, as it can also be used in the design of efficient block ciphers (e.g., Sparx [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF]), cryptographic permutations (e.g., Sparkle [START_REF] Beierle | Lightweight AEAD and hashing using the Sparkle permutation family[END_REF]), and message authentication codes (MACs). For the latter, Chaskey [START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF] is among the most prominent examples.

Besides the advantage of having efficient implementations, there are also good reasons for ARX-based designs regarding security. The algebraic degree of ARX ciphers is usually high after only a very few rounds, as the carry bit within one modular addition already has an almost maximal degree. Structural attacks like integral [START_REF] Knudsen | Integral cryptanalysis[END_REF] or invariant attacks [START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF] are less of a concern and rotational cryptanalysis [START_REF] Khovratovich | Rotational cryptanalysis of ARX[END_REF], originally invented for ARX ciphers, can be efficiently prevented in most cases by the XOR of constants.

When it comes to differential [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] and linear attacks [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], ARX-based designs often show a peculiar behavior. For a small number of rounds, i.e., only very few modular additions, the differential probabilities (resp., absolute linear correlations) are very high. In particular, for a single modular addition, those are equal to 1 due to the linear behavior of the least significant and, in the case of differentials, most significant bits. Moreover, for a single modular addition, the differential probabilities and linear correlations are well understood, and we have at hand nice and efficient formulas for their computation [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Wallén | Linear approximations of addition modulo 2 n[END_REF]. In the case of (dependent) chains of modular additions, bitwise rotations, and XORs, the situation is different, and experimentally checking the probabilities is often the best way to evaluate the behavior. While a few rounds are thus very weak, for a well-crafted ARX scheme, the probabilities of differentials and the absolute correlations of linear approximations decrease very quickly as the number of rounds increases. Indeed, this property led to the long-trail strategy for designing ARX-based ciphers [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF]. Now, for symmetric primitives, the existence of strong differentials and linear approximations for a few rounds with a rapid decrease of probabilities (resp. absolute correlations) is exactly the situation in which considering differential-linear attacks [START_REF] Langford | Differential-linear cryptanalysis[END_REF] is promising. In a nutshell, differential-linear attacks combine a differential with probability p for the first r rounds of the cipher and a linear approximation with correlation q for the next t rounds into a linear approximation for r + t rounds with correlation pq 2 that can be turned into an attack with data complexity of roughly p -2 q -4 . Indeed, it is not surprising that the best attacks against many ARX constructions, including ChaCha and Chaskey, are differential-linear [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF][START_REF] Dey | Improved analysis for reduced round Salsa and Chacha[END_REF]. Our work builds upon those ideas and improves differential-linear attacks on ARX ciphers along several dimensions. Improved Differential-Linear Attacks with Applications to ARX Ciphers

Our Contribution

In this paper, we present the best known 1 attacks on Chaskey and ChaCha. Our improvements over prior work are based on improvements in the differential, the linear part, the LLR statistic, and the key-recovery part of differential-linear attacks.

Differential part

For the differential part, our observation is both simple and effective. Recall that for a differential-linear attack. One needs many (roughly q -4 ) pairs to fulfill the difference in the first part of the cipher, that is many right pairs for the differential. Now, imagine that an attacker could construct many right pairs with probability (close to) one, given only a single right pair. It would immediately reduce the data complexity of the attack by a factor of p -1 . As we will see, this situation is rather likely to occur for a few rounds of many ARX ciphers, particularly for ChaCha and Chaskey. The details of those improvements are presented in Sect. 5.

Linear part

For the linear part, our first observation is that it is often beneficial to not restrict to a single mask but rather consider multiple linear approximations. As we detail in Sect. 6, this nicely combines with an improved version of the partitioning technique for ARX ciphers [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Biham | An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[END_REF], which splits the space of ciphertexts into subsets to increase the correlation of linear approximations. The starting point of our attacks is a new way of partitioning the ciphertexts, summarized in Sect. 3. Note that, although we use multiple linear masks in the attack, because of partitioning the ciphertexts, we basically use only a single linear mask for each ciphertext. This way, we avoid possible dependencies that would be hard to analyze otherwise.

LLR statistic

Our advanced partitioning technique for the linear part exploits linear approximations with different correlations for every ciphertext. One ciphertext pair causes high absolute correlation, but another might cause lower absolute correlation. It is not appropriate to treat these ciphertext pairs in the same manner. We use the log-likelihood ratio (LLR) statistic to solve this problem. According to the Neyman-Pearson lemma [START_REF] Neyman | On the problem of the most efficient tests of statistical hypotheses[END_REF], the LLR test is the most powerful statistical test and, as such, has been used as a cryptanalytic tool (see e.g. [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF][START_REF] Blondeau | Multiple differential cryptanalysis using LLR and χ 2 statistics[END_REF]). In our case, the use of the LLR statistic is beneficial because we can exploit all partitions which were discarded by the original partitioning technique in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF]. The details of the LLR-based technique are presented in Sect. 7. 1 After presenting those results at CRYPTO 2020 [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], improved attacks on ChaCha have been proposed [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF]. Later, [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF] pointed out mistakes in some parts of [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], leading to an updated version that has been published on the Cryptology ePrint Archive [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF]. Very recently, another improved differential-linear attack has been presented [START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF].

Key recovery

Related to the improvement in the linear part and LLR statistic, we present a significant speed-up in the key recovery part. Here, the main observation is that after considering multiple masks and the partitioning technique, several key bits appear only linearly in the approximations. In particular, their value does not affect the absolute value of the correlation but rather the sign only. Instead of guessing those keys individually as done in previous attacks, this observation allows us to recover them by applying the Fast Walsh-Hadamard Transform (FWHT). Similar ideas have already been described in [START_REF] Collard | Improving the time complexity of Matsui's linear cryptanalysis[END_REF]. Details of this approach are given in Sect. [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF].

Putting these improvements into one framework and applying this framework to round-reduced variants of ChaCha and Chaskey results in significantly reduced attack complexities. Our attacks and their corresponding complexities are summarized in Table 1, together with a comparison to the best attacks published so far. It is important to note that, as these attacks are on round-reduced variants of the ciphers only, they do not pose any threat on the full-round versions of ChaCha or Chaskey. Rather, these attacks strengthen our trust in the design. We expect that our improvements have applications to other ciphers, especially ARX-based designs.

Preliminaries

By ⊕ we denote the XOR operation, i.e., addition in F n 2 and by + we either denote the addition in Z, or the modular addition mod 2 n (we identify elements of F n 2 with elements of Z by regarding them as binary representations), depending on the context. For x ∈ F n 2 , we denote by x the bitwise complement of x. Note that we have -x = x + 1. Given a non-empty set S ⊆ F n 2 and a Boolean function

f : F n 2 → F 2 , we define Cor x∈S [f (x)] := 1 |S| x∈S (-1) f (x) .
If for (another) Boolean function g :

F n 2 → F 2 we have Cor x∈S [g(x) ⊕ f (x)] = c, we say that g(x) ≈ f (x) holds with correlation c if x ∈ S.
We denote the ith unit vector of a binary vector space by [i] and the sum of unit vectors

[i 1 ] ⊕ [i 2 ] ⊕ • • • ⊕ [i t ] by [i 1 , i 2 , . . . , i t ]. Given a vector x ∈ F n 2 , x[i] denotes the ith bit of x, and x[i 1 , i 2 , . . . , i t ] denotes t j=1 x[i j ]. For γ, x ∈ F n 2 , we define the inner product by γ, x = n-1 i=0 γ[i]x[i]. In particular, x[i 1 , i 2 , . . . , i t ] = x, [i 1 , i 2 , . . . , i t ] .
In the remainder of this paper we assume that, when a randomly chosen sampling set S ⊆ F n 2 is a (sufficiently large) subset of

F n 2 , Cor x∈S [f (x)] is a good approximation for Cor x∈F n 2 [f (x)].
In other words, we assume that the empirical correlations obtained by sampling for a sufficiently large number of messages closely match the actual correlations.

E 1 E 2 E 1 E 2 ∆ in ∆ m p q q Γ m Γ m Γ out Γ out
Fig. 1 The structure of a classical differential-linear distinguisher.

E 1 E m E 1 E m ∆ in ∆ m p E 2 E 2 q q r Γ m Γ m Γ out Γ out
Fig. 2 A differential-linear distinguisher with experimental evaluation of the middle correlation r.

We denote by N (µ, σ 2 ) the normal distribution with mean µ and variance σ 2 . By Φ we denote the cumulative distribution function of the standard normal distribution N (0, 1). Thus if X ∼ N (µ, σ 2 ), it holds that

Pr [X ≤ Θ] = Φ Θ -µ σ .

Differential-Linear Attacks

We first recall the basic variant of differential-linear cryptanalysis as introduced by Langford and Hellman [START_REF] Langford | Differential-linear cryptanalysis[END_REF], and the enhancement by Biham, Dunkelman, and Keller [START_REF] Biham | Enhancing differential-linear cryptanalysis[END_REF]. Figure 1 shows the overview of the distinguisher. An entire cipher E is divided into two sub ciphers E 1 and E 2 , such that E = E 2 • E 1 , and a differential distinguisher and a linear distinguisher is applied to the first and second part, respectively. In particular, assume that the differential ∆ in

E1

→ ∆ m holds with probability

Pr x∈F n 2 [E 1 (x) ⊕ E 1 (x ⊕ ∆ in ) = ∆ m ] = p . Let us further assume that the linear approximation Γ m E2 → Γ out has correlation Cor x∈F n 2 [ Γ m , x ⊕ Γ out , E 2 (x) ] = q.
The differential-linear distinguisher exploits the fact that, under the assumption that E 1 (x) and E 2 (x) are independent random variables, we have

Cor x∈F n 2 [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] = pq 2 .
(1) Therefore, by preparing p -2 q -4 pairs of chosen plaintexts (x, x), for x = x ⊕ ∆ in , where ∈ N is a small constant, one can distinguish the cipher from a pseudorandom permutation.

In practice, there might be a problem with the assumption that E 1 (x) and E 2 (x) are independent, resulting in wrong estimates for the correlation. To provide a better justification of this independence assumption (and in order to improve attack complexities), adding a middle part is a simple solution and usually done in recent attacks (including ours). Here, the cipher E is divided into three sub ciphers

E 1 , E m and E 2 such that E = E 2 • E m • E 1 and the middle part E m is experimentally evaluated. In particular, let r = Cor x∈S [ Γ m , E m (x) ⊕ Γ m , E m (x ⊕ ∆ m ) ]
, where S denotes the set of samples over which the correlation is computed. Then, the total correlation in Equation 1 can be estimated as prq 2 . Recently, as a theoretical support for this approach, the Differential-Linear Connectivity Table (DLCT) [START_REF] Bar-On | DLCT: A new tool for differential-linear cryptanalysis[END_REF], has been introduced. The overall attack framework is depicted in Fig. 2 and we will use this description in the remainder of the paper.

Finally, in order to better understand Equation (1), we denote the differential-linear correlation (known as the auto-correlation in the theory of Boolean functions) on E by Aut E (∆ in , α, α

) := 2 -n x∈F n 2 (-1) α,E(x) ⊕ α ,E(x⊕∆in) ,
where Equation ( 1) is special case such that α = α = Γ out .

Partitioning Technique for ARX-based Designs

Partitioning allows increasing the correlation of the differential-linear distinguisher by deriving linear equations which hold conditioned on ciphertext and key bits. We recall the partitioning technique as used in [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF].

z[i] = a[i] ⊕ b[i] ⊕ a[i -1] if a[i -1] = b[i -1] a[i] ⊕ b[i] ⊕ a[i -2] if a[i -1] = b[i -1] and a[i -2] = b[i -2] .

New Partitioning Technique

Before introducing our new attack framework for differential-linear attacks, we first introduce some new partitioning techniques. The original idea of the partitioning technique [START_REF] Biham | An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[END_REF] is to divide all the data into some partitions, and only using those partitions that can decrease the data complexity. The generalized partitioning technique in [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF] also has the same feature, i.e., when a single modular addition is analyzed, all the data is divided into four partitions and one out of those four is discarded.

Our new partitioning techniques are twofold. First, we introduce linear masks for partitions that have originally been discarded. Our new FWHTbased key recovery using the LLR statistic allows us to efficiently use such partitions. Second, we additionally introduce a partitioning technique to compute z[i] ⊕ z[i -1] with the same key guessing cost as the evaluation of z[i].

There are multiple linear trails with high correlation in the ARX ciphers. The new partition is useful when we dynamically change available linear trails for each partition. Let us consider two m-bit words z 0 and z 1 and a modular addition operation

F 2m 2 → F 2m 2 , (z 1 , z 0 ) → (y 1 , y 0 ) = (z 1 , z 0 + z 1 )
, as depicted in Fig. 3. In the attacks we present later, we are interested in the value z 0

[i] = (y 0 -y 1 )[i] = (y 0 + ȳ1 + 1)[i].
Notice that for i ≤ 2 there exist trivial relations for z 0 [i]. The following lemma deals with the case i ≥ 3, which is relevant for our applications.

Lemma 2 Let s = y 0 ⊕ ȳ1 and let i ≥ 3. Let S b0b1 := {(y 1 , y 0 ) ∈ F 2m 2 | s[i -1] = b 0 and s[i -2] = b 1 }. We have z 0 [i] ≈      y 0 [i] ⊕ y 1 [i] ⊕ y 0 [i -1], with cor. -1, if (y 1 , y 0 ) ∈ S 0 * , y 0 [i] ⊕ y 1 [i] ⊕ y 0 [i -2], with cor. -1, if (y 1 , y 0 ) ∈ S 10 , y 0 [i] ⊕ y 1 [i] ⊕ y 0 [i -3], with cor. -2 -1 , if (y 1 , y 0 ) ∈ S 11 , (2)
where S 0 * = S 00 ∪ S 01 .

Proof Figure 4 represents the computation of z 0 [i], where z 0 = y 0 -y 1 = y 0 + ȳ1 + 1. In fact, if c[i] denotes the carry occurring at bit position i, and assume that c[-1] := 1, we have that z 0

[i] = y 0 [i] ⊕ y 1 [i] ⊕ 1 ⊕ c[i -1] for all i ≥ 0.
Let us first assume that (y 1 , y 0 ) ∈ S 0 * , i.e., y 0

[i -1] ⊕ ȳ1 [i -1] = 0. Then, c[i -1] = y 0 [i -1] if i ≥ 1. Thus, z 0 [i] = y 0 [i] ⊕ y 1 [i] ⊕ 1 ⊕ y 0 [i -1],
for all i ≥ 1, and we obtain the first equality.

Next, let us assume that (y 1 , y 0 ) ∈ S 10 , i.e., y 0

[i -1] ⊕ ȳ1 [i -1] = 1 and y 0 [i - 2] ⊕ ȳ1 [i -2] = 0. Then, c[i -1] = c[i -2], and c[i -2] = y 0 [i -2] if i ≥ 2. Thus, z 0 [i] = y 0 [i] ⊕ y 1 [i] ⊕ 1 ⊕ y 0 [i -2],
for all i ≥ 2, and we obtain the second equality.

Finally, let us assume that (y 1 , y 0 ) ∈ S 11 , i.e., y 0

[i -1] ⊕ ȳ1 [i -1] = 1 and y 0 [i -2] ⊕ ȳ1 [i -2] = 1. Then, c[i -1] = c[i -2], and c[i -2] = c[i -3] if i ≥ 3. Thus, z 0 [i] = y 0 [i] ⊕ y 1 [i] ⊕ 1 ⊕ c[i -3]
holds for all i ≥ 3. The carry c[i -3] is the output of the majority function as

c[i-3] = maj(c[i-4], y 0 [i-3], ȳ1 [i-3]
), and a linear approximation, c[i-3] ≈ y 0 [i-3], holds with correlation 2 -1 . Thus, we have

z 0 [i] ≈ y 0 [i] ⊕ y 1 [i] ⊕ y 0 [i -3]
with correlation -2 -1 , and we obtain the final approximation. The representations for the partitions S 0 * and S 10 are the same as in Lemma 1. We additionally introduce a linear approximation for the partition S 11 , which was discarded in the original partitioning technique. Note that the cost to determine partitions is not increased compared to the previous partitioning technique because we simply use the discarded partition. The cost increase only involves the new bit y 0 [i -3], but thanks to our FWHT-based key recovery technique, the cost increase will be negligible. We discuss it in detail in Sect. 8. Due to the propagation rules for linear trails over modular addition, we may end up with multiple linear trails that are closely related to each other. As an example, Fig. 5 shows two possible trails, where [i] and [i, i -1] denote the corresponding linear masks. The partitioning technique described above evaluates z 0 [i], but we can expect that there is a highly-biased linear trail in which z 0 [i] ⊕ z 0 [i -1] needs to be evaluated instead of z 0 [i]. In the trivial method, we would apply the partitioning technique of Lemma 2 for z 0 [i] and z 0 [i-1] separately, which requires the knowledge of 3 bits of information from y in total. Our new partitioning method allows us to determine the partition with the knowledge of only the same 2 bits of information as needed for evaluating the case of z 0 [i], namely (y

z 0 [i] z 0 [i -1] z 0 [i -2] z 0 [i -3] y 0 [i] y 0 [i -1] y 0 [i -2] y 0 [i -3] ȳ1 [i] ȳ1 [i -1] ȳ1 [i -2] ȳ1 [i -3] + • • • • • • • • • c[i -1] c[i -2] c[i -3] c[i -4]

[i]

[ ] [ ] [i] [i] [i]
0 [i -1] ⊕ y 1 [i -1]) and (y 0 [i -2] ⊕ y 1 [i -2]
). This is especially helpful if y consists of the ciphertext XORed with the key, so we need to guess less key bits to evaluate the partition.

Lemma 3 Let s = y 0 ⊕ ȳ1 and let i ≥ 3. Let S b0b1 := {(y 1 , y 0 ) ∈ F 2m 2 | s[i -1] = b 0 and s[i -2] = b 1 }. We have z 0 [i] ⊕ z 0 [i -1] ≈      y 0 [i] ⊕ y 1 [i], with cor. 1, if (y 1 , y 0 ) ∈ S 1 * , y 0 [i] ⊕ y 1 [i] ⊕ y 0 [i -1] ⊕ y 0 [i -2], with cor. -1, if (y 1 , y 0 ) ∈ S 00 , y 0 [i] ⊕ y 1 [i] ⊕ y 0 [i -1] ⊕ y 0 [i -3], with cor. -2 -1 , if (y 1 , y 0 ) ∈ S 01 ,
where S 1 * = S 10 ∪ S 11 .

Proof By evaluating the modular addition z 0 = y 0 + ȳ1 + 1, we have

z 0 [i] ⊕ z 0 [i -1] = y 0 [i] ⊕ ȳ1 [i] ⊕ c[i -1] ⊕ y 0 [i -1] ⊕ ȳ1 [i -1] ⊕ c[i -2] ,
where c[i -1], resp., c[i -2] denotes the carry occurring at bit position i -1, resp., i -2. As before, we define c[-1] := 1.

Let us first assume that (y 1 , y 0 ) ∈ S 1 * , i.e., y 0

[i -1] ⊕ ȳ1 [i -1] = 1. Then, clearly c[i -1] = c[i -2]. Thus, z 0 [i] ⊕ z 0 [i -1] = y 0 [i] ⊕ y 1 [i],
and we obtain the first equality.

Next, let us assume that (y 1 , y 0 ) ∈ S 00 , i.e., y 0

[i -1] ⊕ ȳ1 [i -1] = 0 and y 0 [i - 2] ⊕ ȳ1 [i -2] = 0. Since y 0 [i -1] ⊕ ȳ1 [i -1] = 0, we have c[i -1] = ȳ1 [i -1]. Since y 0 [i -2] ⊕ ȳ1 [i -2] = 0, we have c[i -2] = y 0 [i -2]. Thus, z 0 [i] ⊕ z 0 [i -1] = y 0 [i] ⊕ y 1 [i] ⊕ 1 ⊕ y 0 [i -1] ⊕ y 0 [i -2],
and we obtain the second equality.

Finally, let us assume that (y 1 , y 0 ) ∈ S 01 , i.e., y 0

[i -1] ⊕ ȳ1 [i -1] = 0 and y 0 [i -2] ⊕ ȳ1 [i -2] = 1. Since y 0 [i -1] ⊕ ȳ1 [i -1] = 0, we have c[i -1] = ȳ1 [i -1]. Since y 0 [i -2] ⊕ ȳ1 [i -2] = 1, we have c[i -2] = c[i -3]. Thus, z 0 [i] ⊕ z 0 [i -1] = y 0 [i] ⊕ y 1 [i] ⊕ 1 ⊕ y 0 [i -1] ⊕ c[i -3].
The carry c[i -3] is the output of the majority function as c

[i -3] = maj(c[i - 4], y 0 [i -3], ȳ1 [i -3]
), and a linear approximation, c[i -3] ≈ y 0 [i -3], holds with correlation 2 -1 . Thus,

z 0 [i] ⊕ z 0 [i -1] ≈ y 0 [i] ⊕ y 1 [i] ⊕ y 0 [i -1] ⊕ y 0 [i -3]
holds with correlation -2 -1 , and we obtain the final approximation.

In practice, we need to consider a more complicated partition. For example, we sometimes consider the case that the approximated function consists of multiple modular subtractions and rotation. A summary of our partitioning is given in Appendix A.

4 High-Level Overview of the New Attack Framework p2) . . . γ (ps) γ (p1) γ (p2) . . . γ (ps) . . . . . .

x x z = (z P , z R ) z = (z P , zR ) y = (y P , y R ) ỹ = (ỹ P , ỹR ) c = (c P , c R ) c = (c P , cR ) ∆ in ∆ m Γ m Γ m Γ (p1) out Γ (p2) out . . . Γ (ps) out Γ (p1) out Γ (p2) out . . . Γ (ps) out γ (p1) γ (
E 1 E 1 E m E m E 2 E 2 F F exp. exp. k = (k P , k R ) k = (k P , k R ) k in k in
Fig. 6 The new attack framework.

In this section, we introduce a high-level overview of our new attack framework for differential-linear attacks with the partitioning technique. The framework consists of several novel techniques, which are: 1) amplifying the probability of the differential part by carefully choosing an appropriate linear subspace U for generating good pairs, 2) choosing the linear masks dynamically depending on each partition, and 3) an FWHT-based technique for improving the key recovery part when using partitions.

Figure 6 shows the high-level description of the general structure. Here F corresponds to the part of the cipher that we are going to cover using our improved key-guessing strategy. Our aim is to recover parts of the last whitening key k by using a differential-linear distinguisher given by s (multiple) linear approximations Γ (pi) out , z ⊕ Γ (pj ) out , z . In the following, we assume that the ciphertext space F n 2 is split into a direct sum P ⊕ R with n P := dim P and n R := dim R = nn P , so that the partitions will be given by the cosets T pi = p i ⊕ R for any p i ∈ P (i.e. p i represents a set of the partition). Notice that, without loss of generality, we can also assume that c ∈ F n 2 is divided into two parts c P ∈ F n P 2 = P and c R ∈ F n-n P 2 = R, and c = (c P , c R ); similarly, we can write k = (k P , k R ) and y = (y P , y R ). Then, for any p i ∈ P, the partition T pi ⊂ F n 2 is defined as T pi = {y ∈ F n 2 | y P = p i }. Since both formalizations are equivalent, we will use either interchangeably depending on the context.

The Differential Part

The first step of the attack is to collect many (x, x ⊕ ∆ in ) satisfying E 1 (x) ⊕ E 1 (x ⊕ ∆ in ) = ∆ m , which are called right pairs. Let X be the set defined as

X = {x ∈ F n 2 | E 1 (x) ⊕ E 1 (x ⊕ ∆ in ) = ∆ m }.
If pairs are used from X , the probability of the differential part becomes 1 and the correlation of the differential-linear distinguisher also increases. To collect many such pairs efficiently, we use a linear subspace U. In the simplest case, this subspace is chosen such that for any x ∈ X and any u ∈ U it holds that x ⊕ u ∈ X , i.e. (x ⊕ u, x ⊕ u ⊕ ∆ in ) is a right pair as well. However, this strict requirement restricts the size of U significantly and for the attack it is sufficient if this implication is true for most elements in X . To capture this precisely, we define a subset X of the set of right pairs X as X = {x ∈ X | x ⊕ u ∈ X for all u ∈ U}. Once we find an x ∈ X , we can find 2 dim U right pairs for free. The differential probability p is in fact defined as p = |X |/2 n , which means we can reduce the data complexity by the factor p -1 when X = X . We would like to remark that this idea has already been used in other contexts, e.g., the differential attack [START_REF] Knellwolf | Conditional differential cryptanalysis of NLFSR-based cryptosystems[END_REF], but to best of our knowledge, it has not been applied to differentiallinear attacks. We discuss the differential part in detail in Sect. 5.

The Linear Part

The idea is to identify several tuples (T pi , Γ (pi) out , γ (pi) ), i ∈ {1, . . . , s}, where γ (pi) ∈ R, for which we can observe a high absolute correlation

ε i := Cor y∈Tp i Γ (pi)
out , z ⊕ γ (pi) , y . In the simplest case, we would have

ε i = 1, i.e., y ∈ T pi ⇒ Γ (pi)
out , z = γ (pi) , y = γ (pi) , c ⊕ γ (pi) , k . In other words, by considering only a specific subset of the ciphertexts (defined by T pi ) we obtain linear relations in the key with a high correlation.

The correlation of the differential-linear distinguisher for E 2 • E m • E 1 , which is denoted by q i,j , is defined as

q i,j := Cor x∈X such that (y,ỹ)∈Tp i ×Tp j Γ (pi) out , z ⊕ Γ (pj ) out , z .
In practice, it is not feasible to compute q i,j for all partitions indexed by (i, j) when each correlation is low and the number of partitions is large. Therefore, we introduce the following assumption. Assumption 1 The correlation q i,j is independent of Tp i × Tp j . In other words, we assume

q i,j = Cor x∈X Γ (pi) out , z ⊕ Γ (pj )
out , z for all i, j.

We finally observe the following correlation for (y, ỹ) by guessing the secret key, and the final correlation is defined as ρ i,j := Cor x∈X such that (y,ỹ)∈Tp i ×Tp j γ (pi) , y ⊕ γ (pj ) , ỹ .

In addition to Assumption 1, we use the following assumption in order to estimate the final correlation.

Assumption 2

The correlations q i,j , ε i , and ε j are independent of each other, and ρ i,j can be estimated as

ρ i,j = ε i ε j q i,j . (3)
Unfortunately, Assumption 2 does not hold in general because it ignores the impact of the auto-correlation-linear hull effect. Namely, for a more precise evaluation, we need to consider multiple differential-linear trails with tuples (T pi , * , γ (pi) ), where * represents arbitrary linear masks, and ρ i,j can be computed as the sum of these correlations. In other words, we need to consider multiple Γ (pi) out for each fixed (T pi , γ (pi) ). We later discuss the auto-correlationlinear hull in Sect. 6. There it is also shown that, when considering the auto-correlation-linear hull, Assumptions 1 and 2 are replaced by the assumption that the hull is dominated by a single trail in order to justify Equation [START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF].

How to identify belonging partitions is very important. It highly depends on the specification of the target cipher. Applications to Chaskey and ChaCha are too complicated to understand this behavior. We provide some simple cases for a more easy understanding of this behavior in Appendix B.

LLR-Based Statistical Test

According to the Neyman-Pearson Lemma, the LLR test is the most powerful statistical test and as such has been used as a cryptanalysis tool (see e.g. [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF][START_REF] Blondeau | Multiple differential cryptanalysis using LLR and χ 2 statistics[END_REF]). Considering the use of multiple linear trails with different correlations, the LLR test is more appropriate than the simple sum without considering the different correlations of each linear approximation.

Let us consider our differential-linear attacks using N pairs. An important remark is that each of the N pairs contributes differently to the correlations. Therefore, we need to consider the contribution to the theoretical correlation of each of them. Let (y, ỹ) be the th pair and let us assume that y and ỹ belong to the ith and jth partitions respectively, i.e., y P = p i and ỹP = p j (for ease of notation, we do not make the dependency of y, ỹ, i, j on explicit). We then get the 1-bit representation w = y, γ (pi) ⊕ ỹ, γ (pj ) and consider the probability π = Pr y,ỹ [w = 0] . We refer to the theoretical correlation as ρ i,j when the ith and jth partitions are used. Namely, π = ρi,j +1 2

. For simplicity, let C denote this correlation for the th pair (and the ith and jth partitions are used for this pair), i.e., C = ρ i,j = 2π -1.

Let D 0 and D 1 be the random vector distributions

D 0 : (B(1, π 1 ), . . . , B(1, π N )) , D 1 : (B(1, 1/2), . . . , B(1, 1/2))
. where B(n, π ) are independent binomial distributions with n trials and success probability π , and where the π are not necessarily distinct.

Our goal is to distinguish whether w := (w 1 , . . . , w N ) is the result of sampling from D 0 (i.e., the real distribution) or D 1 (i.e., the random distribution). Let q 0 and q 1 be the probability that w := (w 1 , . . . , w N ) is the result of sampling from D 0 or D 1 respectively. Thus,

q 0 = Pr [X = w | X ∼ D 0 ] , q 1 = Pr [X = w | X ∼ D 1 ] .
The LLR statistic is defined as ln(q 0 /q 1 ), and it is computed as

ln q 0 q 1 = 1 2 N =1 ln 1 -C 2 + 1 2 N =1 ln 1 -C 1 + C (-1) w .
Let us assume that the LLR statistic follows normal distributions N (µ 0 , σ 2 0 ) and N (µ 1 , σ 2 1 ) when the correct and wrong keys are guessed, respectively. We have

µ 0 = -µ 1 = 1 2 N =1 C 2 = N 2 C, σ 2 0 = σ 2 1 = N =1 C 2 = N C,
where by C we denote the average of the squared correlation, i.e. C :=

1 N N =1 C 2 .
We later show the formula described above in Sect. 7.

WHT-Based Key Recovery Technique

We use (y, ỹ) to identify partitions and compute the LLR statistic. Note that y ∈ T pi ⇔ c ∈ T pi ⊕ k P , so we need to guess n P bits of k to partition the ciphertexts into the corresponding T pi . Note that, since we require γ (pi) ∈ R, we obtain linear relations only on k R . Let (c, c) be the pair of ciphertexts. The partition the pair belongs to is determined by y P = c P ⊕ k P . Therefore, part of the key k P is guessed to identify the partition. After guessing k P , we get the following approximation.

y, γ (y P ) ≈ ỹ, γ (ỹ P ) ⇒ c ⊕ k, γ (y P ) ≈ c ⊕ k, γ (ỹ P ) ⇒ c, γ (y P ) ⊕ c, γ (ỹ P ) ≈ k, γ (y P ) ⊕ γ (ỹ P )
Since the left side is known, we get the parity of k with respect to the linear mask γ (y P ) ⊕ γ (ỹ P ) . For a linear subspace W defined by W := Span{γ (pi) ⊕ γ (pj ) | i, j ∈ {1, . . . , s}}, the approximations above involve dim W bits of information for k. By using the Fast Walsh-Hadamard Transform (FWHT), we do not need to guess dim W bits for every pair of texts, and the time complexity is estimated as

2 n P (2N + dim W • 2 dim W )
, where n P is the bit length of k P . We discuss this procedure in detail in Sect. 8.

The Differential Part -Finding Many Right Pairs

Let us be given a permutation

E 1 : F n 2 → F n 2 and a differential ∆ in E1 → ∆ m that holds with probability p. In other words, |{x ∈ F n 2 | E 1 (x) ⊕ E 1 (x ⊕ ∆ in ) = ∆ m }| = p • 2 n . In a usual differential-linear attack on a permutation E = E 2 • E m • E 1 as explained in Sect. 2.
1, the internal structure of E 1 could be in general arbitrary and we would consider randomly chosen x ∈ F n 2 to observe the ciphertexts of the plaintext pairs (x, x ⊕ ∆ in ). For each of those pairs, the differential over E 1 is fulfilled with probability p, which results in a data complexity of roughly p -2 r -2 q -4 for the differential-linear attack. In other words, we did not exploit the particular structure of E 1 . In particular, it would be helpful to know something about the distribution of right pairs (x, x ⊕ ∆ in ) ∈ F n 2 × F n 2 which fulfill the above differential.

Let us denote by X the set of all values that define right pairs for the differential, i.e.,

X = {x ∈ F n 2 | E 1 (x) ⊕ E 1 (x ⊕ ∆ in ) = ∆ m } .
To amplify the correlation of a differential-linear distinguisher, instead of choosing random plaintexts from F n 2 , we could consider only those that are in X . In particular, we have 2 Cor

x∈X [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] = rq 2 .
Since the set X might have a rather complicated structure and is keydependent, we cannot use this directly for an arbitrary permutation E 1 . However, if X presents a special structure such that, given one element x ∈ X , we can generate many other elements in X for free, 3 independently of the secret key, we can use this to reduce the data complexity in a differentiallinear attack. For example, if X contains a large affine subspace A = U ⊕ a, Improved Differential-Linear Attacks with Applications to ARX Ciphers given x ∈ A, we can generate (roughly) 2 dim U elements in X for free, namely all elements x ⊕ u, for u ∈ U. In order to obtain an effective distinguisher, we must be able to generate enough plaintext pairs to observe the correlation of the differential-linear approximation. In particular, we require |U| > r -2 q -4 .

This will be exactly the situation we find in ChaCha. Here the number of rounds covered in the differential part is so small that it can be described by the independent application of two functions (see Sect. 5.1).

If |U| is smaller than the threshold of r -2 q -4 , we cannot generate enough right pairs for free to obtain a distinguisher by this method and we might use a probabilistic approach, see Sect. 5.2.

In Sect. 5.3 we show how the conditional differential framework can be used to efficiently find bigger sets U, as well as to recover some information on the key, and provide some ideas to adapt it to the ARX scenario.

Fully Independent Parts

Let E 1 : F n 2 → F n 2 with n = 2m be a parallel application of two block ciphers

E (i) 1 : F m 2 → F m 2 , i ∈ {0, 1} (for a fixed key), i.e., E 1 : (x (1) , x (0) ) → (E (1) 1 (x (1) ), E (0) 1 (x (0) )) . Suppose that, E (0) 1 presents a differential α E (0) 1 → β with probability p. We consider the differential ∆ in E1
→ ∆ m with ∆ in = (0, α) and ∆ m = (0, β), which also holds with probability p. Given one element (x (1) , x (0) ) ∈ X , any (x (1) ⊕ u, x (0) ) for u ∈ F m 2 is also contained in X , and we can thus generate 2 m right pairs for free.

If 2 m > r -2 q -4 , a differential-linear distinguisher on E = E 2 • E m • E 1 would work as follows:

1. Choose a = (a (1) , a (0) ) ∈ F n 2 uniformly at random.

Empirically compute

Cor x∈a⊕(F m 2 ×{0}) [ Γ out , E(x) ⊕ Γ out , E(x ⊕ ∆ in ) ] . 3.
If we observe a correlation of rq 2 using r -2 q -4 many x, the distinguisher succeeded. If not, start over with Step 1.

With probability p, we choose an element a ∈ X in Step 1. In that case, the distinguisher succeeds in Step 3. Therefore, the data complexity of the distinguisher is p -1 r -2 q -4 , compared to p -2 r -2 q -4 as in the classical differential-linear attack.

Probabilistic Independent Parts

Since the previous decomposition is not always possible or 2 m might not be big enough, we are also interested in the situations in which the differential part cannot be simply written as the parallel application of two functions. Again, the goal is, given one element x ∈ X , to be able to generate r -2 q -4 other elements in X , each one with a much lower cost than

p -1 . Suppose that U ⊆ F n 2 is a subspace with |U| > r -2 q -4 and suppose that Pr u∈U [x ⊕ u ∈ X | x ∈ X ] = p 1 ,
where p 1 is much larger than p. The data complexity of the improved differential-linear distinguisher would then be p -1 p -2 1 r -2 q -4 . Note that the probability p 1 may also depend on x. In particular, there might be x ∈ X ⊆ X for which p 1 is (almost) 1, but the probability to draw such an initial element x from F n 2 is p , which is smaller than p. Then, the data complexity would be p -1 p -2 1 r -2 q -4 . For instance, this will be the case for the attack on Chaskey (Sect. 9), where we have p 1 ≈ 1 and p = p × 222/256.

In such situations, we propose an algorithmic way to experimentally detect suitable structures in the set of right pairs. The idea, see Algorithm 1 for the pseudo code, is to detect canonical basis vectors within the subspace U. Running this algorithm for enough samples will return estimates of the probability γ j that a right pair x ∈ X stays a right pair when the jth bit is flipped, i.e.,

γ i = Pr [x ⊕ [i] ∈ X | x ∈ X ] .
When applied to a few rounds of ARX ciphers it can be expected that there are some bits that will always turn a right pair into a right pair, i.e. γ i = 1. Moreover, due to the property of the modular addition that the influence of bits on distant bits degrades quickly, high values of γ j = 1 can also be expected. As we will detail in Sect. 9 this will be the case for the application to Chaskey.

Algorithm 1 Computing probabilistic independent bits

Require: Number of samples T , input difference ∆ in , output difference ∆ m Ensure: Probabilities γ 0 , γ 1 , . . . , γ n-1 1: Let s = 0 and c j = 0 for j ∈ {0, . . . , n -1}.

2: for i = 1 to T do 3:

Pick a random X and compute E 1 (X) and

E 1 (X ⊕ ∆ in ) 4: if E 1 (X) ⊕ E 1 (X ⊕ ∆ in ) = ∆ m then 5:
Increment s 6:

for j ∈ {0, . . . , n -1} do 7:
Prepare X where the jth bit of X is flipped.

8: if E 1 ( X) ⊕ E 1 ( X ⊕ ∆ in ) = ∆ m then 9:
Increment c j 10:

end if 11:
end for 12:

end if 13: end for 14: for j ∈ {0, . . . , n -1} do 15:

γ j = c j /s 16: end for

Using the Conditional Differential Framework for Finding Better Subspaces

A practical way for producing a set of pairs of data whose elements all verify a certain differential path reflects a similar scenario to the one which is considered in conditional differential attacks. In [START_REF] Knellwolf | Conditional differential cryptanalysis of NLFSR-based cryptosystems[END_REF], in the context of NLFSR-based primitives, the elements of the basis of U are called freebits and involve more complex relations derived from the differential paths than just simple singlebit relations. In Sect. 3.2 of [START_REF] Knellwolf | Conditional differential cryptanalysis of NLFSR-based cryptosystems[END_REF], three types of conditions are presented: type zero, which only involve public bits (which is common in NLFSR initialization, but not in ARX or SPN constructions); type one, which involve both secret and public bits; and type two, which are conditions directly on the keybits. The freebits are actually the ones that do not affect type one conditions. Using these definitions we can improve previous attacks in two ways: increasing for free the number of keybits recovered by the differential-linear attack thanks to type 2 conditions, and increasing the size of U by using the freebits as defined in [START_REF] Knellwolf | Conditional differential cryptanalysis of NLFSR-based cryptosystems[END_REF].

In this section we provide some hints and general ideas on how to use this framework for improving the analysis in ARX constructions. In Appendix C we provide a detailed example on how to determine additional keybits with type 2 conditions and on how to increase the number of freebits with evolved relations for Chaskey.

Conditional differential framework for differential-linear attacks

Using the definitions from [START_REF] Knellwolf | Conditional differential cryptanalysis of NLFSR-based cryptosystems[END_REF]Sect. 3.2], it is easy to see how to improve the differential part of some attacks (quite straightforwardly for ARX) in three main ways:

1. We can increase the size of U by exhausting the input values that keep the conditions of type-1 fixed to a certain value (as was done in the applications in that paper), as if these conditions were true, they would stay true for all the sampling set. These exhausted bits might not be completely free as type one conditions need to remain constant. 2. When considering a particular set of plaintexts to check if it is the one verifying the differential path, some information on the value of some associated keybits or keybit relations can be presupposed (given directly by conditions of type-2 and indirectly by conditions of type-1). This means that, for all the cases, we can suppose some information on the key as known. This information might be used to recover more bits and more importantly, could reduce the complexity of the key-search part in the final rounds. 3. Combination of both: guessing some keybits, that might be useful for the linear part, and that simultaneously might allow to detect sampling bit relations that follow the path with probability 1.

Main ideas for exploiting the conditions on ARX

We now present some general ideas for exploiting conditions on ARX constructions. Even though some of them might seem trivial, it is nonetheless helpful to set them as rules to follow. We can define some rules that apply when flipping the parity of differences. Instead of using only single non-active bit flipping for defining the freebits, we can study the effect of flipping the parity of the differences as additional sampling bits when possible. We can identify several relevant cases, and we present here four cases of particular interest: (i) If a pair of differences is going to be erased after a modular addition (which implies they have a different parity), changing the parity of one will need changing the parity of the other. (ii) If a bit-difference is staying at the same position (and not propagating further) after a modular transition, changing its parity will not affect the transition. (iii) If two active bits at position i will produce a difference after the modular addition at position i + 1 (move the difference), flipping both active bits at the same time will change the parity of the output at i + 1. (iv) If two words are added with a difference in position i and in positions i and i + 1 respectively, and we want to absorb the differences after the modular additions, the carries of the previous positions will not affect the bits after position i. We can also change the parity of the three bits simultaneously, and the differences will still be absorbed, and the values will stay the same. Of course, all this might have an effect on further rounds, which will have, in turn, to be taken into account.

It is also useful to keep in mind that when we identify several input bits that only influence the differential transitions by a xor, swapping a pair number of these will not alter the verification of the path.

When dealing with carries, they might affect transitions with low probability. It is interesting to keep in mind that, when there is a sum of two zeros at position i, the value of all the bits at lower positions will not affect the carries at any higher positions. That might imply that a small guess (for instance 2 keybits for fixing two bits to zero) can generate many more bits for the sampling part with probability one if they only affected the differential path through these carries.

Auto-Correlation-Linear Hulls and Partitioning

In this section, we want to better understand how to compute the correlations ρ i,j when the ith and jth partitions are used. This will allow us to shed light on Assumptions 1 and 2.

For this, we will derive general formulas which express the differential-linear correlation with restricted output of a function composed of two parts. Note that in the following we do not make any assumptions on the independence of these parts. Furthermore, the notion of an auto-correlation-linear hull developed below will allow to improve upon the attacks by considering multiple intermediate masks.

G 1 G 1 G 2 G 2 ∆ Γ Γ γ γ (∈ M ) (∈ N )
We start by considering the unrestricted variant. Given two functions G 1 , G 2 : F n 2 → F n 2 , an input difference ∆ and two output-masks γ and γ , let

H := G 2 • G 1 and Aut H (∆, γ, γ ) := 2 -n x∈F n 2 (-1) γ,H(x) ⊕ γ ,H(x⊕∆)
be the differential-linear correlation on H.

We are interested in how to compute the differential-linear correlation when considering intermediate masks Γ and Γ . In a second step, the outputs will be restricted to coming from a set M and a set N , respectively.

Note that this approach is different from the considerations in [START_REF] Blondeau | Differential-linear cryptanalysis revisited[END_REF] as there it was about how to compute the auto-correlation by connecting the differential and the linear part correctly, while here we extend a differential-linear correlation using a second linear approximation of the parts.

This auto-correlation can be expressed as

Aut H (∆, γ, γ ) = u∈F n 2 H(u, γ) H(u, γ )(-1) u,∆ , (4)
where we denote by

H(u, γ) = 2 -n x∈F n 2 (-1) γ,H(x) + u,x
the correlation of the approximation of H with input and output masks u and γ. This follows from the connection of the Walsh-Hadamard transform and the convolution of functions, see e.g. [START_REF] Carlet | Boolean Functions for Cryptography and Coding Theory[END_REF]Proposition 11], but can also be verified directly.

In our attack framework, G 1 would correspond to E 2 • E m • E 1 and G 2 to F and we would experimentally estimate the auto-correlation and multiply it with the correlation of G 2 with input mask Γ and output mask γ, i.e., we estimate

Aut H (∆, γ, γ ) ≈ G 2 (Γ, γ) G 2 (Γ , γ ) Aut G1 (∆, Γ, Γ ) . ( 5
)
This is of course only an approximation and we now want to get an explicit expression of the hull effect, i.e., of all the parts we ignore in the above expression without making any assumptions. Furthermore, we have to take the partitioning of the outputs into account.

For this, we use the fact (see [START_REF] Nyberg | Linear approximation of block ciphers[END_REF]) that we can split the correlation of

H into H(u, γ) = Γ∈F n 2 G 1 (u, Γ) G 2 (Γ, γ)
with an intermediate mask Γ, i.e. the linear hull. Putting this back in the definition of the auto-correlation, we get the following.

Proposition 1 (Auto-Correlation-Linear Hull) Let G 1 , G 2 : F n 2 → F n 2 . For any ∆, γ, γ ∈ F n 2 we then have Aut G2•G1 (∆, γ, γ ) = Γ,Γ ∈F n 2 G 2 (Γ, γ) G 2 (Γ , γ ) Aut G1 (∆, Γ, Γ ) . Proof Let H = G 2 • G 1 . Then Aut G2•G1 (∆, γ, γ ) = u∈F n 2 H(u, γ) H(u, γ )(-1) u,∆ = u∈F n 2   Γ∈F n 2 G 1 (u, Γ) G 2 (Γ, γ)     Γ ∈F n 2 G 1 (u, Γ ) G 2 (Γ , γ )   (-1) u,∆ = Γ,Γ ∈F n 2 G 2 (Γ, γ) G 2 (Γ , γ ) u∈F n 2 G 1 (u, Γ) G 1 (u, Γ )(-1) u,∆ = Γ,Γ ∈F n 2 G 2 (Γ, γ ) G 2 (Γ , γ) Aut G1 (∆, Γ, Γ ) .
So, as could be expected, the linear hull theorem has a natural extension to an auto-correlation-linear hull theorem and the approximation in Equation ( 5) corresponds to focusing on a single (Γ, Γ ) while actually all pairs (Γ, Γ ) have to be considered. It remains to see how restricting the input, i.e. partitioning, affects this expression.

Impact of Partitioning on the Correlation

We again consider a function H : F n 2 → F n 2 , an input difference ∆, outputmasks γ and γ and two non-empty subsets M, N of F n 2 . We are interested in

Aut (M,N ) H (∆, γ, γ ) := 2 n |M ||N | x∈F n 2 H(x)∈M,H(x⊕∆)∈N (-1) γ,H(x) ⊕ γ ,H(x⊕∆) .
One would hope that one can still use Equation ( 4) with minor modifications. That is basically by replacing the correlation of H by its restricted version.

To capture this, for a function F : F n 2 → F n 2 and a non-empty set S ⊆ F n 2 we denote by

F | S (a, b) := 1 |S| x∈S (-1) b,F (x) ⊕ a,x
the correlation when the input is restricted to the set S. Later, it will actually be the output that is restricted, which will be handled by considering the inverse of the function (and swapping input and output-mask). Using Lemmas 4 and 5 below, we can state the main insight of this Section as Proposition 2.

Lemma 4 We have Aut

(M,N ) H (∆, γ, γ ) = u∈F n 2 H -1 | M (γ, u) H -1 | N (γ , u)(-1) u,∆ .
Proof We start by expanding the right-hand side of the equation, denoted by L, as follows

L = u∈F n 2 H -1 | M (γ, u) H -1 | N (γ , u)(-1) u,∆ = 1 |M ||N | u∈F n 2   y∈M (-1) u,H -1 (y) ⊕ γ,y     y ∈N (-1) u,H -1 (y ) ⊕ γ ,y   (-1) u,∆ = 1 |M ||N | y∈M,y ∈N (-1) γ,y ⊕ γ ,y u∈F n 2 (-1) u,H -1 (y)⊕H -1 (y )⊕∆ = 2 n |M ||N | y∈M,y ∈N H -1 (y )=H -1 (y)⊕∆
(-1) γ,y ⊕ γ ,y .

We now define x as H -1 (y) and we get

L = 2 n |M ||N | x∈F n 2 H(x)∈M,H(x⊕∆)∈N (-1) γ,H(x) ⊕ γ ,H(x⊕∆) which is equal to Aut (M,N ) H (∆, γ, γ ) by definition.
In order to get the restricted version of the auto-correlation-linear hull, we have to understand the linear hull of a restriction first.

Lemma 5 Let H = G 2 • G 1 : F n 2 → F n 2 and let S ⊆ F n 2 be a non-empty set. Then H| S (γ, Γ) = µ∈F n 2 G 2 (µ, Γ) G 1 | S (γ, µ) Proof We have µ∈F n 2 G 2 (µ, Γ) G 1 | S (γ, µ) = 1 2 n |S| µ∈F n 2   y∈F n 2 (-1) Γ,G2(y) ⊕ µ,y     x∈S (-1) µ,G1(x) ⊕ γ,x   = 1 2 n |S| y∈F n 2 ,x∈S (-1) Γ,G2(y) ⊕ γ,x µ∈F n 2 (-1) µ,y⊕G1(x) = 1 |S| x∈S,y=G1(x) (-1) Γ,G2(y) ⊕ γ,x = 1 |S| x∈S (-1) Γ,G2(G1(x)) ⊕ γ,x = H| S (γ, Γ) . Proposition 2 (Auto-Correlation-Linear Hull with Restriction) Let G 1 , G 2 : F n 2 → F n
2 and let M, N ⊆ F n 2 be non-empty sets. For any ∆, γ, γ ∈ F n 2 we then have Aut

(M,N ) G2•G1 (∆, γ, γ ) = Γ,Γ ∈F n 2 G -1 2 | M (γ, Γ) G -1 2 | N (γ , Γ ) Aut G1 (∆, Γ, Γ ) .
Proof Starting with Lemma 4, we express the restricted auto-correlation as

T = Aut (M,N ) H (∆, γ, γ ) = u∈F n 2 H -1 | M (γ, u) H -1 | N (γ , u)(-1) u,∆ ,
and substitute the correlations by using Lemma 5 as

H -1 | M (γ, u) = Γ∈F n 2 G -1 1 (Γ, u) G -1 2 | M (γ, Γ)
and

H -1 | N (γ , u) = Γ ∈F n 2 G -1 1 (Γ , u) G -1 2 | N (γ , Γ ).
Doing this we get

T = u∈F n 2   Γ∈F n 2 G -1 1 (Γ, u) G -1 2 | M (γ, Γ)     Γ ∈F n 2 G -1 1 (Γ , u) G -1 2 | N (γ , Γ )   (-1) u,∆ = Γ,Γ ∈F n 2 G -1 2 | M (γ, Γ) G -1 2 | N (γ , Γ ) u∈F n 2 G -1 1 (Γ, u) G -1 1 (Γ , u)(-1) u,∆ .
Using the fact that, when considering the correlation of the inverse, input and output masks get swapped, we can rewrite this as

T = Γ,Γ ∈F n 2 G -1 2 | M (γ, Γ) G -1 2 | N (γ , Γ ) u∈F n 2 G 1 (u, Γ) G 1 (u, Γ )(-1) u,∆ .
Improved Differential-Linear Attacks with Applications to ARX Ciphers

The last part, according to Equation (4), is nothing else than the auto-correlation of G 1 and thus we conclude

T = Γ,Γ ∈F n 2 G -1 2 | M (γ, Γ) G -1 2 | N (γ , Γ ) Aut G1 (∆, Γ, Γ )
as claimed.

Relation to Assumptions 1 and 2

Proposition 2 provides a more precise interpretation of Equation [START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF]. Recall that

G 1 corresponds to E 2 •E m •E 1 and G 2 to F . The part ε i and ε j correspond directly to G -1 2 | M (γ, Γ) and G -1 2 | M (γ, Γ
), while the value q i,j is now replaced by Aut G1 (∆, Γ, Γ ). Our main observation is that we can still consider the unrestricted auto-correlations of G 1 in this hull, which means that Assumption 1 is actually not needed, and Assumption 2, about the independence of the parts, can be replaced by the assumption that the hull is dominated by a single trail, that is a single choice of intermediate masks Γ, Γ .

Moreover, using Proposition 2 allows to improve upon the correlation by considering multiple intermediate masks, as we demonstrate in the application to Chaskey in Sect. 9.

LLR-based Statistical Test

Let us consider our differential-linear attacks using N pairs. Following the notation introduced in Sect. 4.3, we let (y, ỹ) be the th pair and we assume that y and ỹ belong to the ith and jth partitions respectively (we recall that, for ease of notation, we do not make the dependency of y, ỹ, i, j on explicit). Then, let us consider w = y, γ (pi) ⊕ ỹ, γ (pj ) for the th pair (y, ỹ), and consider the probability

π = Pr y,ỹ [w = 0] . Note that π = ρi,j +1 2
, and for simplicity, let C denote this correlation for the th pair (and the ith and jth partitions are used for this pair), i.e., C = ρ i,j = 2π -1.

Let D 0 and D 1 be the distributions

D 0 : (B(1, π 1 ), . . . , B(1, π N )) , D 1 : (B(1, 1/2), . . . , B(1, 1/2))
. where B(n, π ) is the binomial distribution with n trials, each having probability π of success, where 0 ≤ π ≤ 1 are not necessarily distinct.

Let q 0 and q 1 be the probabilities that w := (w 1 , . . . , w N ) is the result of sampling from D 0 (i.e. from the real distribution) or D 1 (i.e. the random distribution) respectively. Thus

q 0 = Pr [w = X | X ∼ D 0 ] = N =1 π w (1 -π ) 1-w , q 1 = Pr [w = X | X ∼ D 1 ] = N =1 2 -1 = 2 -N .
The LLR statistic is defined as ln(q 0 /q 1 ). The likelihood of D 0 is larger than that of D 1 when ln(q 0 /q 1 ) > 0. Then the LLR statistic can be rewritten as

ln q 0 q 1 = ln 2 N × N =1 π w (1 -π ) 1-w = N ln(2) + N =1 w ln(π ) + N =1 (1 -w ) ln(1 -π ) = N ln(2) + N =1 ln(1 -π ) + N =1 ln π 1 -π w .
Note that the first term is constant, but the second and third term depend on the value of the guessed key bits, which affects the partition of the pairs. With a slight abuse of notation, we treat q i as a random variable.

Note that, when we use C instead of π , the LLR statistic is rewritten as

LLR = N ln(2) + N =1 ln (1 -π ) + N =1 ln π 1 -π w = N ln(2) + N =1 ln 1 -C 2 + N =1 ln 1 + C 1 -C 1 -(-1) w 2 = N =1 ln 1 -C 1 + C 0.5 ln (1-C 2 ) + 1 2 N =1 ln 1 -C 1 + C (-1) w .
We can now determine the means and variances of the LLR statistic under D 0 and D 1 in terms of the correlations C l .

Proposition 3 Let W and R be the LLR statistics when w is chosen from D 1 and D 0 , respectively. Then, the means E[W] and E[R] are estimated as

E [W] ≈ - 1 2 N =1 C 2 , E [R] ≈ 1 2 N =1 C 2 .
Improved Differential-Linear Attacks with Applications to ARX Ciphers

Proof Assuming that w is chosen from D 1 , the average value of each w is 1/2.

E [W] = E ln q 0 q 1 = N ln(2) + N =1 ln(1 -π ) + N =1 2 -1 ln π 1 -π = N ln(2) + N =1 ln(1 -π ) + N =1 2 -1 ln(π ) - N =1 2 -1 ln(1 -π ) = N ln(2) + N =1 2 -1 ln(π (1 -π )). Let C = 2π -1, and π (1 -π ) = 1+C 2 × 1-C 2 = 1-C 2 4 . Therefore, E [W] = N ln(2) + N =1 2 -1 ln 1 -C 2 4 = N ln(2) + N =1 2 -1 ln(1 -C 2 ) - N =1 ln(2) = 1 2 N =1 ln(1 -C 2 ).
Using the Taylor series of ln(1 -C 2 ) we can approximate this expression with -C 2 when C 2 is close to 0. Therefore

E [W] ≈ - 1 2 N =1 C 2 .
Next, assuming that w is chosen from D 0 , the average value of w is 1/2 + C /2. Therefore

E [R] = - 1 2 N =1 C 2 + N =1 C 2 ln π 1 -π . Since π /(1 -π ) = 1+C
1-C , we can rewrite the second term as

N =1 C 2 ln π 1 -π = N =1 C 2 ln 1 + C 1 -C = N =1 C 2 (ln(1 + C ) -ln(1 -C )) ≈ N =1 C 2 ,
where we have used again a Taylor approximation of ln(1 + z) for the last step. We conclude that

E [R] ≈ 1 2 N =1 C 2 .
Proposition 4 Let W and R be the LLR statistics when w is chosen from D 1 and D 0 , respectively. Then, the variances Var[W] and Var[R] are estimated as

Var [W] ≈ Var [R] ≈ N =1 C 2 .
Proof In order to compute the variance of ln q0 q1 , for simplicity we treat the term π as a constant. We have experimentally verified that this is reasonable. With this in mind, we can write Var ln

q 0 q 1 ≈ Var N =1 w ln π 1 -π .
Assuming that w is chosen from D 1 , we know that the variance of w is 1/4. As before, since π /(1 -π ) = 1+C 1-C , we obtain

N =1 1 4 ln 1 + C 1 -C 2 = N =1 1 4 (ln(1 + C ) -ln(1 -C )) 2
and using Taylor approximation:

Var [W] ≈ N =1 1 4 (ln(1 + C ) -ln(1 -C )) 2 ≈ N =1 C 2
Similarly, assuming that w is chosen from D 0 , the variance of w is 1/4 -C 2 /4. Therefore, we want to compute

Var [R] ≈ N =1 1 4 1 -C 2 ln 1 + C 1 -C 2
which is approximated with Taylor to

N =1 1 4 1 -C 2 ln 1 + C 1 -C 2 ≈ N =1 C 2 -C 4 .
Therefore, the variance in both cases is approximately

N =1 C 2 .

Distinguishing Between the Distributions

Our experiments indicate that the LLR statistic is normally distributed both in the random and in the real case. While this could potentially be treated theoretically, using e.g. some variant of the central limit theorem, we prefer to back this up by experiments in the applications. For now let N (µ 0 , σ 2 0 ) and

N (µ 1 , σ 2
1 ) be the (assumed) normal distributions for the LLR statistics when the correct and wrong keys are guessed, respectively. The previous computation has shown that

µ 0 = -µ 1 = 1 2 N =1 C 2 = N 2 C, σ 2 0 = σ 2 1 = N =1 C 2 = N C,
where by C we denote the average of the squared correlation, i.e. C :=

1 N N =1 C 2 .
Improved Differential-Linear Attacks with Applications to ARX Ciphers

In order to distinguish between the two distributions, we are interested in the gap between µ 0µ 1 and σ 0 (= σ 1 ).

µ 0 -µ 1 σ 1 = N C √ N C = N C = N =1 C 2 . (6)
Therefore, the larger N =1 C 2 , the bigger the gap is. This implies that in order to maximize this gap, no data should be discarded. That is, there should be no partition with correlation zero. This is different from what happened in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], where the same gap can approximately be represented as

N =1 |C | √ N = √ N c 2 , where c = 1 N N =1 |C |.
In other words, this gap is proportional to the squared value of the average of the (absolute value of the) correlation (c), while for the LLR statistic the same gap is proportional to the average of squared correlations (C). We remark that the latter is always larger than the former, as expected when using the LLR.

WHT-based Key Recovery Technique

We use the LLR statistic to recover the secret key. Recall that the LLR statistic is calculated as

LLR = 1 2 N =1 ln 1 -C 2 + 1 2 N =1 ln 1 -C 1 + C (-1) w ,
where w = y, γ (y P ) ⊕ ỹ, γ (ỹ P ) and (y, ỹ) is the th pair in N pairs. Only ciphertext pair (c, c) can be observed by attackers. Which partition the pair belongs to is determined by y P and ỹP . Therefore, the key denoted by k P is guessed to identify the partition and y P = c P ⊕ k P . After guessing k P , we can get the following 1-bit representation:

w = y, γ (y P ) ⊕ ỹ, γ (ỹ P ) = c, γ (y P ) ⊕ c, γ (ỹ P ) ⊕ k, γ (y P ) ⊕ γ (ỹ P ) .
We need not only k P but also k, γ (y P ) ⊕ γ (ỹ P ) to compute w . Let k R denote involved key bits, and the size is dim W , where a linear subspace W is defined by W := Span{γ (pi) ⊕ γ (pj ) | i, j ∈ {1, . . . , s}}. The trivial procedure would require guessing k P and k R for every pair, for a time complexity of 2N × 2 n P +dim W , where n P is the bit length of k P .

In this section, we introduce a more advanced procedure, where the Fast Walsh-Hadamard Transform (FWHT) is applied instead of guessing k R for every pair. As a result, the time complexity is reduced to 2 n P (2N + dim W • 2 dim W ).

Using the FWHT for Key Recovery

The first step in the key recovery procedure is guessing k P to identify partitions. Once we have guessed these key bits, the first term of the LLR statistic, i.e., α := 1 2 N =1 ln 1 -C 2 , is constant and independent of w . Thus, in order to determine the LLR, we compute LLR = LLRα as

LLR = 1 2 N =1 ln 1 -C 1 + C (-1) w = 1 2 N =1 ln 1 -C 1 + C (-1) c,γ (y P ) ⊕ c,γ ( ỹP )
× (-1) k,γ (y P ) ⊕γ ( ỹP ) .

Then, by using an array β, whose element β(γ) is defined as

β(γ) := 1 2 N =1:γ=γ (y P ) ⊕γ ( ỹP ) ln 1 -C 1 + C (-1) c,γ (y P ) ⊕ c,γ ( ỹP ) , LLR is computed as LLR = γ∈W β(γ) × (-1) k,γ .
Given a real-valued function f : F n 2 → R, the Walsh-Hadamard transform evaluates the function

f : F n 2 → R, x → y∈F n 2 f (y) × (-1) x,y .
A naive computation needs O(2 2n ) steps (additions and evaluations of f ), i.e., for each x ∈ F n 2 , we compute (-1) x,y f (y) for each y ∈ F n 2 . The Fast Walsh-Hadamard transform is a well-known recursive divide-and-conquer algorithm that evaluates the Walsh-Hadamard transform in O(n2 n ) steps. We refer to e.g., [START_REF] Carlet | Boolean Functions for Cryptography and Coding Theory[END_REF]Section 2.3] for the details.

Algorithm 2 shows the attack procedure using the FWHT. We first collect N ciphertext pairs, and therefore, it needs 2N queries to E as the data complexity. We next guess k P and prepare a real number α and the array of real numbers β to compute the LLR statistic. For every stored ciphertext pair, we identify partitions, get corresponding correlation ρ i,j and linear mask γ, and update α and β accordingly. We finally apply the FWHT to β and the LLR statistics are computed as α + β(k L ). The overall running time can be estimated as 2 n P (2N + dim W • 2 dim W ).

Success Probability of Algorithm 2

In the following, we assume that the distributions involved can be well estimated by normal approximations. This significantly simplifies the analysis. Improved Differential-Linear Attacks with Applications to ARX Ciphers Algorithm 2 Key-recovery Require: Cipher E, sample size N , threshold Θ. Ensure: List of key candidates (k P , k L ) for n P + dim W bit of information on k. 1: for ∈ {1, . . . , N } do (c, c) ← (c( ), c( ))

12:

Compute y P = c P ⊕ k P and ỹP = cP ⊕ k P to identify partitions.

13:

Identify T i × T j for (y P , ỹP ) and get corresponding correlation ρ i,j .

14:

γ ← γ (y P ) ⊕ γ (ỹ P ) 15:

α ← α + 1 2 ln(1 -ρ 2 i,j ) 16: β(γ) ← β(γ) + 1 2 ln 1-ρi,j 1+ρi,j (-1) c,γ (y P ) ⊕ c,γ ( ỹP ) 17:
end for 18:

Compute β by using the Fast Walsh-Hadamard Transform.

19:

C(k P , k R ) ← α + β(k R ) 20: if C(k P , k R ) > Θ then 21:
Save (k P , k R ) as a key candidate.

22:

end if 23: end for Note that we opted for a rather simple statistical model ignoring, in particular, the effect of the wrong key distribution by assuming the simple randomization hypothesis and ignoring the way we sample our plaintexts (i.e. known vs. chosen vs. distinct plaintext). Those effects might have major impact on the performance of attacks when the data complexity is close to the full code-book and the success probability and the gain are limited. However, none of this is the case for our parameters. In our concrete applications, we have verified the behavior experimentally wherever possible.

For the statistical model for the right key, this implies that the counter can be expected to approximately follow a normal distribution with parameters

C(k P , k L ) ∼ N N 2 C, N C , where C = 1 N N =1 C 2 .
The wrong key counters (under the simple randomization hypothesis) are approximately normally distributed with parameters With this, we can deduce the following proposition.

C(k P , k L ) ∼ N - N 2 C, N C .
Proposition 5 After running Algorithm 2 for p -1 times, the probability that the correct key is among the key candidates is

psuccess ≥ 1 2 Pr [C(k P , k L ) ≥ Θ] = 1 2 1 -Φ Θ -N 2 C √ N C
.

The expected number of wrong keys is

2 n P +dim W p × 1 -Φ Θ+ N 2 C √ N C
.

Application to Chaskey

Chaskey [START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF] is a lightweight MAC algorithm whose underlying primitive is an ARX-based permutation in an Even-Mansour construction, i.e., Chaskey-EM. The permutation operates on four 32-bit words, i.e., the block size is 128 bits.

In the version proposed in [START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF], the permutation employs 8 rounds of the form depicted in Fig. 7. In [START_REF] Mouha | Chaskey: a MAC algorithm for microcontrollers -status update and proposal of Chaskey-12[END_REF], the author proposed a version with an increased number of rounds (from 8 to 12), and this version is currently standardized in ISO/IEC 29192-6:2019. The designers claim security up to 2 80 computations as long as the data is limited to 2 48 blocks. Let (v r 0 , v r 1 , v r 2 , v r 3 ) be the input of the rth round function, and (w r 0 , w r 1 , w r 2 , w r 3 ) denotes the state after applying the half round for (v r 0 , v r 1 , v r 2 , v r 3 ). Please refer to Fig. 7 for each index of the branches.

Overview of Our Attack

We first show the high-level overview of our attack. Similar to the previous differential-linear attack from [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], we first divide the cipher into three sub ciphers. For the 7-round attack, we use E 1 covering 1.5 rounds, E m covering 4 rounds, and E 2 covering 0.5 rounds, and the key-recovery, i.e., the function F , is covering 1 round. We also present a 7.5-round attack, where E 2 covers 1 round instead of 0.5 rounds.

The differential characteristic and the linear trail are applied to E 1 and E 2 , respectively, while the experimental differential-linear distinguisher is applied to the middle part E m . Note that, since the differential-linear distinguisher over E m is constructed experimentally, its absolute correlation must be high enough [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] to be detectable by using a relatively small sampling space. Moreover, since it is practically infeasible to check all input differences and all output linear masks, we restricted ourselves to the case of an input difference of Hamming weight 1 and linear masks of the form [i] or [i, i + 1], i.e., 1-bit or consecutive 2-bit linear masks. As a result, when there is a non-zero difference only in the 31st bit (msb) of w 1 0 , i.e., ∆ m = (([]), ([]), ( [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]), ([])), we observed the following two differential-linear distinguishers with correlations 2 -5.1 :

γ j = 1 v 0 [8] ⊕ v 1 [8, 13] ⊕ v 2 [29] 4 v 2 [21, 29] ⊕ v 3 [21] v 0 [18, 21, 30] ⊕ v 1 [21, 26, 30] ⊕ v 2 [3, 26] ⊕ v 3 [26, 27] v 2 [15] ⊕ v 3
Aut Em (∆ m , ([], [], [20], []), ([], [], [20], [])) ≈ 2 -5.1 , (7)
Aut Em (∆ m , ([], [], [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF][START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], []), ([], [], [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF][START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], [])) ≈ 2 -5.1 .

These correlations4 are estimated using a set consisting of 2 26 random samples of w 1 . This is significant enough since the standard deviation assuming a normal distribution is 2 13 . Note that we do not focus on the theoretical justification of this 4-round experimental differential-linear distinguisher in this paper and we start the analysis for E 1 and E 2 from the following subsection.

Using Conditional Differentials

Before we discuss the improved basis we have found using the conditional differential technique, we first recall the basis of U introduced in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] (see the first two-row blocks in Table 2). Here, the threshold of the probability is relaxed from 0.95 to 0.93, and v 3 [START_REF] Neyman | On the problem of the most efficient tests of statistical hypotheses[END_REF] (in red) is newly added in the basis. The conditional differential techniques provide us with four other basis elements with probability 1, which cannot be found by Algorithm 1 [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] (see the third-row block in Table 2). A linear subspace U, formed by elements that don't affect the output with probability 1, and whose dimension is 18 + 4 = 22 is finally used to attack 7-round Chaskey. In addition, all, i.e., 18 + 8 + 4 = 30, basis elements are used to attack 7.5-round Chaskey.

In Appendix C, we provide the details on how to obtain these relations. We use the conditional differential framework and Fig. 18 in order to recover for free the value of some keybits and also to find additional bits of information for sampling and increase the dimension of U from 18 as given in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] (and involving exclusively one-bit relations) to 22, or 23 if one-bit relation on the key is known. The new proposed set of freebits (or relations with probability 1) is optimal and no more such relations exist.

Keybits That Are Obtained for Free

If we find a set of inputs that verifies the differential path, we can directly deduce the following linear relations on the keybits, due to the conditions where differences are absorbed during the first modular additions (or the other way round, for each guess of these values, build sets of inputs that verify the 6 related conditions): [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF]. Note that these techniques can be used after mounting concrete attacks shown in Sects. 9.3 and 9.4. Thus, this does not contribute to accelerating our key-recovery attacks.

k 1 [8] ⊕ k 0 [8], k 1 [21] ⊕ k 0 [21], k 1 [30] ⊕ k 0 [30] and k 2 [26] ⊕ k 3 [26], k 2 [21] ⊕ k 3 [21], k 2 [26] ⊕ k 3

Additional Space for Sampling

Compared with the linear subspace U shown in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], the dimension of U increases by 4 by adding vectors listed in the third-row block in Table 2 to the basis. In order to find these relations, we have used the rules presented in Sect. 5.3, and some more detailed explanations can be found in Appendix C for the interested reader using Fig. 18. We summarize this in the following lemma:

Lemma 6 There is a set X ⊆ F 128 2 of size 2 128-17 and a 22-dimensional linear subspace U, such that for any element x ∈ X and any u ∈ U it holds that

E 1 (x ⊕ u) ⊕ E 1 (x ⊕ u ⊕ ∆ in ) = ∆m
, where E 1 denotes 1.5 rounds of Chaskey.

Our improved 7-round attack uses this linear subspace.

One additional probability-one relation can be obtained if we flip the bit v 2 [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF] and at the same time [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF]. The issue with this one is that it depends on the relation of k 2 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF] ⊕ k 3 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF] (guessing this bit of information for instance would allow us to have an extra sampling bit) and it will not be used in the attack.

v 2 [29] = v 2 [29] ⊕ v 2 [28] ⊕ v 3
In addition to the probability-one relations, we can consider a larger linear subspace by adding relations with very high probabilities.

Lemma 7 There is a set X ⊆ F 128 2 whose size is about 2 128-17.28 and a 30dimension linear subspace U, such that for any element x ∈ X and any u ∈ U it holds that E 1 (x⊕u)⊕E 1 (x⊕u⊕∆ in ) = ∆m where E 1 denotes 1.5 rounds of Chaskey. Improved Differential-Linear Attacks with Applications to ARX Ciphers

c 2 c 1 c 3 c 0 k 2 k 1 k 3 k 0 [20] [11,4,3] [27] [] [] [16] [0]
c 2 c 1 c 3 c 0 k 2 k 1 k 3 k 0 [20] [11,10,4] [27,26] [] [] [16,15] [31,0] v 0 v 1 v 3 v 2 v 0 v 1 v 3 v 2 ψ (1)
ψ (0) We can build a 30-dimensional linear subspace such that all its elements verify simultaneously the differential with probability 2 -17.28 . For this, we consider the 22-dimensional linear subspace of Lemma 6 and add to its basis the 7 vectors from [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] and v 3 [START_REF] Neyman | On the problem of the most efficient tests of statistical hypotheses[END_REF]. Our 7.5-round attack uses this linear subspace.

c 2 c 1 c 3 c 0 k 2 k 1 k 3 k 0 [20,19] [11,4] [27] [] [] [16] [0] v 0 v 1 v 3 v 2 v 0 v 1 v 3 v 2 ψ (3) ψ (2)

The 7-Round Attack

List of Differential-Linear Distinguishers

As shown in Equations ( 7) and ( 8), we have two differential-linear distinguishers with correlations 2 -5.1 , where two output linear masks, ([], [], [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF], []) and ([], [], [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF][START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], []) , are available. By extending ([], [], [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF], []) and ([], [], [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF][START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], []) by 0.5 rounds, respectively, we can get four linear masks (see Fig. 8). When both texts in pairs use either of ψ (0) or ψ (1) , the correlation is ±2 -6.42 . Moreover, when both texts in pairs use either of ψ (2) or ψ (3) , the correlation is ±2 -6.42 .

We have other linear masks whose absolute correlation is relatively high but lower than 2 -6.43 . Table 3 summarizes 12 output masks. For any (i, j) ∈ {0, 1} × {0, 1} and (i, j) ∈ {2, 3} × {2, 3}, the correlations of the differentiallinear distinguishers are estimated by the combination of two output masks as follows:

Aut(β

(i) 0 , β (j) 0 ) = δ (i) 0 • δ (j) 0 • 2 -6.42 , Aut(β (i) 0 , β (j) 1 ) = δ (i) 0 • δ (j) 1 • 2 -7.70 , Aut(β (i) 0 , β (j) 2 ) = δ (i) 0 • δ (j) 2 • 2 -8.76 , Aut(β (i) 1 , β (j) 1 ) = δ (i) 1 • δ (j) 1 • 2 -8.95 , Aut(β (i) 1 , β (j) 2 ) = δ (i) 1 • δ (j) 2 • 2 -10.01 , Aut(β (i) 2 , β (j) 2 ) = δ (i) 2 • δ (j) 2 • 2 -11.06 , where Aut(β (i) , β (j) ) = Aut E2•Em (∆ m , β (i) , β (j) ) and δ (i)
h ∈ {1, -1} is defined by the δ column in Table 3. Each correlation is estimated by using 2 35 pairs. = ( [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF], [], [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], []) 1 [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], []) 1

ψ (0) ψ (0) ψ (0) β (0) 1 = ([27], [], [11, 4, 2], []) 1 β (0) 2 = ([27], [],
β
(1) 0

= ( [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF][START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], [], [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF], []) -1 ψ (1) ψ (1) ψ (1) β

(1) 1

= ( [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF][START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], [], [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], []) 1 β

(1) 2 = ( [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF][START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], [], [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], []) 1 [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF][START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], [], [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF]

β (2) 0 = (
, []) 1 ψ (2) ψ (2)
ψ (2) β

(2) 1

= ( [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF][START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], [], [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], []) 1 β

(2) 2

= ( [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF][START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], [], [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], []) 1 [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF], []) 1 ψ (3) ψ (3) ψ (3) β

β (3) 0 = ([27], [],
(3) 1

= ( [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF], [], [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], []) -1 [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], []) -1

β (3) 2 = ([27], [],
Table 4 List of partition points for the attack against 7-round Chaskey.

Choice: (w 6 0 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF], w 6 0 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF])

ζ 1 ζ 1 ζ 1 P 1 p i ∼ = (s R [15], s R [14]) Linear: v 3 [16], v 0 [16], v 0 [15], v 0 [14], v 0 [13] Choice: (v 6 2 [11], v 6 2 [11, 10]) ζ 2 ζ 2 ζ 2 P 2 p i ∼ = (v 3 [18] ⊕ v 2 [9, 17], s L [10], s L [9], s L [18], s L [17]) Linear: v 3 [19], v 1 [11], v 2 [11], v 2 [10], v 2 [9], v 2 [8], v 1 [19], v 2 [19], v 2 [18], v 2 [17], v 2 [16] Choice: (v 6 2 [4], v 6 2 [4, 3]) ζ 3 ζ 3 ζ 3 P 3 p i ∼ = (v 3 [11] ⊕ v 2 [2, 10], s L [3], s L [2], s L [11], s L [10]) Linear: v 3 [12], v 1 [4], v 2 [4], v 2 [3], v 2 [2], v 2 [1], v 1 [12], v 2 [12], v 2 [11], v 2 [10], v 2 [9]
Considering that the lowest correlation is 2 -11.06 , an estimation with 2 35 pairs is reliable enough. These differential-linear distinguishers are finally used to estimate the theoretical correlation by considering the auto-correlation-linear hull.

Theoretical Correlations with Auto-Correlation-Linear Hull

To understand how to estimate the theoretical correlation, we provide an example. We observe a pair of ciphertexts (c, c) and guess key bits to identify the partition. Table 4 summarizes the partition points for the 7-round attack. To identify the partition, we need to know 2 -0.677 × 2 -0.263 × (δ

s R [15], s R [14], v 3 [18] ⊕ v 2 [9, 17], s L [10], s L [9], s L [18], s L [17],
(3) 1 × δ (3) 0 × 2 -7.70 ) = -2 -8.64 .
We estimate 3 × 3 = 9 correlations and sum up these correlations (considering the sign). As a result, when ψ causes the highest absolute correlation on this partition. Remark that once the indicator is given, the best linear mask and corresponding correlation are computed. The complexity is about 2 2k P , which is negligible in comparison to the time complexity of the whole attack.

Experimental Reports

The absolute correlation of each partition is high enough so that we experimentally verify our attack procedure. In our experiments, we used the right pair and the correct key to observe the LLR statistic for the correct case. On the other hand, the right pair is not used for the wrong case.

The LLR statistic depends on the sum of the squared correlation N C = N =1 c 2 . We estimated C ≈ 2 -14.711 , and N C ≈ 39.1 when N = 2 20 pairs are used. The following shows the comparison of the LLR statistics, where the theoretical distribution is drawn by the normal distribution with mean N C/2 (for a correct case) and -N C/2 (for wrong case) and the standard deviation √ N C. By repeating our attack procedure 1024 times, two experimental histograms are drawn (see Fig. 9). A slight gap is observed between the theoretical distribution and experimental histogram in the correct case. Note that the experimental one is more biased than the theoretical estimation. We expect that the reason comes from the additional auto-correlation-linear hull that we do not take into account.

We finally estimate the data and time complexities. To identify the partition, we need to guess the 11-bit secret key. We also enumerated elements of the linear subspace W and computed the basis by using Gaussian elimination. = ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) 1 β (0) 2 = ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) 1 β

1 ψ (0) ψ (0) ψ (0) β (0) 1 = ([
= ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) -1 ψ (1) ψ (1) ψ (1) β

= ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) 1 β

(1) 2 = ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) 1 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF])

β (2) 0 = ([16], [0],
1 ψ (2) ψ (2) ψ (2) β (2) 1
= ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF], [0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) 1 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) -1 β [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) -1 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) 1 ψ (4) ψ (4) ψ (4) β

1 β (2) 2 = ([16], [0],
β (3) 0 = ([16], [0],
1 ψ (3) ψ (3) ψ (3) β (3) 1 = ([16], [0],
(3) 2 = ([16], [0],
β (4) 0 = (
= ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) -1 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) 1 ψ (5) ψ (5) ψ (5) β

β (5) 0 = (
= ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF]0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) 1 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) -1 ψ (6) ψ (6) ψ (6) β

β (6) 0 = ([16], [0],
= ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF], [0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) -1 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF]) -1 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) 1 ψ (7) ψ (7) ψ (7) β

β (6) 2 = ([16], [0],
β (7) 0 = ([16], [0],
= ( [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF], [0], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) -1 β [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF][START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF][START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) -1

(7) 2 = ([16], [0],
As a result, the dimension of W is 10. Because of Lemma 6, 2 17 iterations are required to find the right pair. Thus, we need to remove 2 11+10+17 = 2 38 wrong cases. When 2 21 pairs are used, we have N C ≈ 78.2. With a success probability of 90%, we can construct a 45.5-bit filter, which is enough to remove 2 38 wrong cases. We finally estimate the time complexity by using the formula as follows:

T = p -1 × 2 n P × 2N + dim W 2 dim W = 2 17 × 2 11 × 2 × 2 21 + 10 × 2 10 ≈ 2 50.00 .

The 7.5-Round Attack

We further extend four 0.5-round linear trails to eight 1-round linear trails. For every linear trail, we have two different trails whose absolute correlation is slightly lower. Table 5 shows 24 such output masks. For any (i, j) ∈ {0, 1, 2, 3} × {0, 1, 2, 3} and (i, j) ∈ {4, 5, 6, 7} × {4, 5, 6, 7}, the correlations of the differential-linear distinguishers are estimated by the combination of two output masks as follows: 40 , where Aut(

Aut(β (i) 0 , β (j) 0 ) = δ (i) 0 • δ (j) 0 • 2 -9.72 , Aut (β (i) 0 , β (j) 1 ) = δ
(i) 0 • δ (j) 1 • 2 -10.99 , Aut(β (i) 0 , β (j) 2 ) = δ (i) 0 • δ (j) 2 • 2 -12.04 , Aut(β (i) 1 , β (j) 1 ) = δ (i) 1 • δ (j) 1 • 2 -12.26 , Aut(β (i) 1 , β (j) 2 ) = δ (i) 1 • δ (j) 2 • 2 -13.32 , Aut(β (i) 2 , β (j) 2 ) = δ (i) 2 • δ (j) 2 • 2 -14.
β (i) , β (j) ) = Aut E2•Em (∆ m , β (i) , β (j) ) and δ (i)
h ∈ {1, -1} is defined by the δ column in Table 5. These correlations are estimated by using 2 40 pairs. Considering the lowest absolute correlation is 2 -14.6 , an estimation with 2 40 pairs is reliable enough. We use the same method as the attack against 7-round Chaskey to determine a linear mask and estimate the corresponding correlation.

Table 6 summarizes the partition points for the 7.5-round attack. To identify the partition, we need to know

s R [22], s R [21], s R [20], s R [19], s R [18], s L [24], s L [23], v 3 [28] ⊕ v 0 [27, 14], s L [15], s L [14], s L [28], s L [27], v 1 [25] ⊕ v 2 [8, 1], s R [2], s R [1], s R [9], s R [8], v 1 [18] ⊕ v 2 [26, 1], s R [27], s R [26], (s R [2]), (s R [1]), v 1 [10] ⊕ v 2 [25, 18], (s R [19]), (s R [18]), (s R [26]), s R [25], s L [30], s L [29], (s L [28]), (s L [27])
and 24-bit key guessing is enough, where s L = k 0 ⊕ k 1 and s R = k 2 ⊕ k 3 .

Experimental Reports

Each absolute correlation is relatively lower than for a 7-round attack, but it is still possible to verify our attack procedure experimentally by using about 2 28 pairs. Like the 7-round attack, we used a right pair and the correct key to observe the LLR statistic for the correct case, and a right pair is not used for the wrong case.

We estimated C ≈ 2 -24.37 , and N C ≈ 12.38 when N = 2 28 pairs are used. Figure 10 shows the comparison of the LLR statistics, where the theoretical distribution is drawn by the normal distribution with mean N C/2 (for a correct case) and -N C/2 (for wrong case) and the standard deviation √ N C. By repeating our attack procedure 256 times, two experimental histograms Table 6 List of partition points for the attack against 7.5-round Chaskey.

ζ1 ζ1 ζ1 P1 p i ∼ = (s R [22], s R [21], s R [20], s R [19], s R [18]) (v 7
2 [START_REF] Shi | Improved key recovery attacks on reduced-round Salsa20 and ChaCha[END_REF], v 7 0 [START_REF] Shi | Improved key recovery attacks on reduced-round Salsa20 and ChaCha[END_REF][START_REF] Aumasson | New features of latin dances: Analysis of Salsa, ChaCha, and Rumba[END_REF]) Linear: v3 [START_REF] Shi | Improved key recovery attacks on reduced-round Salsa20 and ChaCha[END_REF], v2 [START_REF] Shi | Improved key recovery attacks on reduced-round Salsa20 and ChaCha[END_REF], v2 [START_REF] Aumasson | New features of latin dances: Analysis of Salsa, ChaCha, and Rumba[END_REF], v2 [START_REF] Dey | Improved analysis for reduced round Salsa and Chacha[END_REF], v2 [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF], v2 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], v2 [START_REF] Langford | Differential-linear cryptanalysis[END_REF], v2 [START_REF] Wallén | Linear approximations of addition modulo 2 n[END_REF] ζ2 ζ2 ζ2 [START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF][START_REF] Maitra | Chosen IV cryptanalysis on reduced round ChaCha and Salsa[END_REF]) Linear: v1 [START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF], v0 [START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF], v0 [START_REF] Maitra | Chosen IV cryptanalysis on reduced round ChaCha and Salsa[END_REF], v0 [START_REF] Shi | Improved key recovery attacks on reduced-round Salsa20 and ChaCha[END_REF], v0 [START_REF] Aumasson | New features of latin dances: Analysis of Salsa, ChaCha, and Rumba[END_REF] ζ3 ζ3 ζ3 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF][START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF]) Linear: v3 [START_REF] Biham | An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[END_REF], v1 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF], v0 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF], v0 [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], v0 [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF], v0 [START_REF] Khovratovich | Rotational cryptanalysis of ARX[END_REF], v1 [START_REF] Biham | An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[END_REF], v0 [START_REF] Biham | An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[END_REF], v0 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], v0 [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF], v0 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF] ζ4 ζ4 ζ4

P2 p i ∼ = (s L [24], s L [23]) (v 7 0 [25], v 7 0
P3 p i ∼ = (v3[28] ⊕ v0[27, 14], s L [15], s L [14], s L [28], s L [27]) (w 6 0 [16], v 7 0
P4 p i ∼ = (v1[25] ⊕ v2[8, 1], s R [2], s R [1], s R [9], s R [8]) (w 6
2 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], v 7 0 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF]) Linear: v1 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], v3 [START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], v2 [START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], v2 [START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], v2 [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF], v3 [START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF], v2 [START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF], v2 [START_REF] Beierle | Lightweight AEAD and hashing using the Sparkle permutation family[END_REF], v2 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF], v2 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF] ζ5 ζ5 ζ5

P5 p i ∼ = (v1[18] ⊕ v2[26, 1], s R [27], s R [26], s R [2], s R [1]) (w 6
2 [START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF], v 7 0 [START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF]) Linear: v1 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], v3 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], v2 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], v2 [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF], v2 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], v2 [START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF], v3 [START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], v2 [START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF], v2 [START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], v2 [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF])

ζ6 ζ6 ζ6 P6 p i ∼ = (v1[10] ⊕ v2[25, 18], s R [19], s R [18], s R [26], s R [25]) (w 6 2 [4], v 7 0 [4, 3]
) Linear: v1 [START_REF] Knudsen | Integral cryptanalysis[END_REF], v3 [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF], v2 [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF], v2 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], v2 [START_REF] Langford | Differential-linear cryptanalysis[END_REF], v2 [START_REF] Wallén | Linear approximations of addition modulo 2 n[END_REF], v3 [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF], v2 [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF], v2 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], v2 [START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF], v2 [START_REF] Maitra | Chosen IV cryptanalysis on reduced round ChaCha and Salsa[END_REF] ζ7 ζ7 ζ7

P7 p i ∼ = (s L [30], s L [29], s L [28], s L [27]) (v 7 0 [31]
) Linear: v1 [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF], v0 [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF], v0 [START_REF] Neyman | On the problem of the most efficient tests of statistical hypotheses[END_REF], v0 [START_REF] Biham | An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[END_REF], v0 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], v0 [START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF], v0 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF] are drawn. Similar to the 7-round attack, a slight gap between the theoretical distribution and experimental histogram is observed in the correct case. We again expect that the reason comes from the other auto-correlation-linear hull that we do not consider. We estimate the data and time complexities. To identify the partition, we need to guess the 25-bit secret key. We also enumerated elements of the linear subspace W and computed the basis by using Gaussian elimination. As a result, the dimension of W is 21. To find a right pair, we need 2 17.28 iterations because of Lemma 7. Thus, we need to remove 2 24+21+17.28 = 2 62.28 wrong cases. Chaskey outputs at most 2 48 data, the number of available pairs is at most 2 48-17.28-1 = 2 29.72 . Then, N C ≈ 40.78. With a success probability of 90%, we can construct a 22.5-bit filter, which is insufficient to remove all wrong cases. Considering 2 17.28 iterations to find a right pair, the performance to filter wrong keys decreases to 5.22 bits. We finally estimate the time complexity as

T = p -1 • 2 n P • 2N + dim W 2 dim W = 2 17.28 • 2 24 • 2 • 2 30 + 21 • 2 21 ≈ 2 72.28 .

Using Multiple Linear Approximations Every Partition

Only filtering 2 5.22 wrong keys is not always enough to attack 7.5-round Chaskey. To recover the unique key under the restriction of 2 48 data, we use an extended attack, where multiple linear approximations are used for every partition. In the 7.5-round attack, there are 2 × 4 × 4 = 32 linear approximations, and we choose only one approximation with the highest absolute correlation. However, why do we not use the other 31 approximations? The use of these approximations allows us to reduce the data complexity significantly. Of course, this is a little controversial technique because we are unlikely to assume that each approximation is independent. Fortunately, since our attack can be verified experimentally, we implemented our attack under this controversial assumption. We estimated C ≈ 2 -22.86 . When N = 2 28 pairs are used, N C ≈ 35.26, which increases from 12.38. Figure 11 shows the comparison of the LLR statistics, where the theoretical distribution is drawn by the normal distribution with mean N C/2 (for a correct case) and -N C/2 (for wrong case) and the standard deviation √ N C. By repeating our attack procedure 256 times, two experimental histograms are drawn. Despite the controversial assumption, our theoretical estimation can simulate the experimental result nicely. Therefore, for the application to 7.5-round Chaskey, we conclude that using multiple linear approximations independently does not have any issue. Improved Differential-Linear Attacks with Applications to ARX Ciphers We estimate the data and time complexities. Again, since only 2 29.72 pairs are available, N C ≈ 116. [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF]. With a success probability of 90%, we can construct a 69.6-bit filter, enough to remove 2 62.28 wrong cases. The number of approximations, 32, is multiplied. We finally estimate the time complexity as

T = p -1 × 2 n P × 2N × 32 + dim W 2 dim W = 2

Application to ChaCha

The internal state of ChaCha is represented by a 4 × 4 matrix whose elements are 32-bit vectors. In this section, the input state for the rth round function is represented as

    v r 0 v r 1 v r 2 v r 3 v r 4 v r 5 v r 6 v r 7 v r 8 v r 9 v r 10 v r 11 v r 12 v r 13 v r 14 v r 15     .
The QR (an abbreviation for quarterround ) function is applied in odd and even rounds on every column and diagonal, respectively. We also introduce the notion of a half round, in which the QR function is divided into two subfunctions depicted in Fig. 12. Let w r be the internal state after applying a half round on v r . Moreover, we use the term branches for a, b, c and d, as shown in Fig. 12.

In the initial state of ChaCha, a 128-bit constant is loaded into the first row, a 128-or 256-bit secret key is loaded into the second and third rows, and a 64-bit counter and 64-bit nonce are loaded into the fourth row. In other words, the first three rows in v 0 are fixed. For r-round ChaCha, the odd and even round functions are iteratively applied, and the feed-forward values v 0 i v r i is given as the key stream for all i. Note that we can compute v r i for i ∈ {0, 1, 2, 3, 12, 13, 14, 15} because corresponding v 0 i is known.

Overview of Our Attack

We use the same attack strategy as for Chaskey. The cipher is divided into the sub ciphers E 1 covering 1 round, E m covering 2.5 rounds, and E 2 covering 1.5 rounds to attack 6 rounds, where the key recovery is applied the last single round (F ). One difference to Chaskey is the domain space that the attacker can control. In particular, we cannot control branches a, b, and c because fixed constants and the fixed secret key are loaded into these states. Thus, only branch d can be varied. It implies that active bit positions for input differences are limited to branch d, and a difference ∆ m with Hamming weight 1 after E 1 will not be available due to the property of the round function. Therefore, we first need to generate consistent ∆ m whose Hamming weight is minimized. ψ (1) ψ (0)

7 7 7 7
Fig. 14 Key recovery for 6-round ChaCha.

Each bit in v to which the secret key is not added can be computed for free. For the other bits, we need to guess some key bits first. We first explain the simple case, i.e., we compute v i [j] from c i . As an example, we focus on v 7 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF], which involves k 7 nonlinearly. We apply the partition technique to compute this bit. By guessing k 7 [START_REF] Aumasson | SHA-3 proposal Blake[END_REF] and k 7 [START_REF] Bernstein | ChaCha, a variant of Salsa20[END_REF] (remember that k 7 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF] cancels out in the differential-linear approximation), (3/4) data is available with correlation ±1, and the remaining (1/4) data 6 is available with correlation -2 -1 . Since v i [0] is linearly computed by c i [0], there are 13 simple partition points in which we need to guess key bits. In total, we need to guess a 26-bit key.

Computing bits in v 5 and t is a bit more complicated than the simple case above. For example, let us consider v 5 9 [START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF], and this bit can be computed as

v 5 9 [12] = (c 9 k 9 c 14 (c 3 ⊕ (v 14 ≫ 8)))[12] = ((c 9 c 14 (c 3 ⊕ (v 14 ≫ 8))) k 9 )[12].
Since we can compute (c 9 c 14 (c 3 ⊕(v 14 ≫ 8))) for free, this case is equivalent to the simple case. We also use this equivalent transformation for t 10 , t 11 , and v 10 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF]. In total, we have 6 such partition points, and some partition points can share the same key, e.g., 2-bit key k 10 [START_REF] Langford | Differential-linear cryptanalysis[END_REF] and k 10 [START_REF] Wallén | Linear approximations of addition modulo 2 n[END_REF] is already guessed to compute v 10 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF]. Guessing 4 bits of additional key is enough to compute each bit. Since we have two linear masks ψ (0) and ψ (1) , we dynamically change an applied linear mask according to the data such that correlations to compute v 5 10 [7]/v 5 10 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF][START_REF] Aumasson | SHA-3 proposal Blake[END_REF] become ±1. We cannot use the equivalent transformation to compute bits in t 0 and t 3 . Then, we further extend this linear mask with correlation 2 -1 . For example, we have the following approximations [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF][START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] ⊕ v 10 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF][START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF], for t 0 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF] with correlation 2 -1 , and we can use preferable approximations depending on the data. Namely, we first guess k 10 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF] and determine which linear approximations are available. Then, we guess k 5 [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] and k 5 [START_REF] Khovratovich | Rotational cryptanalysis of ARX[END_REF] and compute v 5 [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] (resp. v 5 [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF][START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]). In order words, by guessing 3-bit key, 3/4 data is available with correlation ±2 -1 and 1/4 data is available with correlation ±2 -2 . We also use the same technique for t 3 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF]/t 3 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF][START_REF] Aumasson | SHA-3 proposal Blake[END_REF].

t 0 [8] ≈ v 0 [8, 7] ⊕ v 5 [15] ⊕ v 10 [8] ⊕ 1, t 0 [8] ≈ v 0 [8] ⊕ v 5

Estimating the Average of the Squared Correlation

Based on the analysis above, we estimate the average of the squared correlation. We suppose each partitioning point is independent when its indicator uses different bits to calculate the average.

We start evaluating the function involving the 1st diagonal.

• The indicator to compute t 0 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF] is (c 5 ⊕k 5 ) [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF], (c 5 ⊕k 5 ) [START_REF] Khovratovich | Rotational cryptanalysis of ARX[END_REF], and (c 10 ⊕k 10 ) [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF]. As discussed before, the average of the squared correlation is 3/4 × (2 -1 ) 2 + 1/4 × (2 -2 ) 2 . • The indicator to compute v 5 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF] is the 25th and 24th bits in (c 5 ⊕ k 5 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute v 5 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF][START_REF] Aumasson | SHA-3 proposal Blake[END_REF] is the 6th and 5th bits in (c 5 ⊕ k 5 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute v 5 10 [19] is the 18th and 17th bits in ((c 10 c 15 (c 0 ⊕ (c 15 ≫ 8))) ⊕ k 10 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 .

• The indicator to compute v 5 10 [7] (or v 5 10 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF][START_REF] Aumasson | SHA-3 proposal Blake[END_REF]) is the 6th bit in ((c 10 c 15 (c 0 ⊕ (c 15 ≫ 8))) ⊕ k 10 ). Here, we change the applied linear mask according to the observed ciphertext such that correlations become 1. Thus, the average of the squared correlation is 1.

• The indicator to compute t 10 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF] is the 18th and 17th bits in ((c 10 c 15 ) ⊕ k 10 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute t 10 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF] is the 6th and 5th bits in ((c 10 c 15 ) ⊕ k 10 ).

As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 .

• The indicator to compute v 10 [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF] is the 30th and 29th bits in (c 10 ⊕ k 10 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute v 10 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF] is the 18th and 17th bits in (c 10 ⊕ k 10 ).

As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 .

In total, we guess 6 key bits in k 5 and 7 key bits in k 10 . The average of the squared correlation is the product of these nine partitioning points, i.e., about 2 -4.396 . We similarly evaluate the function involving the 2nd, 3rd, and 4th diagonals.

• The indicator to compute v 6 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF] is the 18th and 17th bits in (c 6 ⊕ k 6 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute v 6 [START_REF] Khovratovich | Rotational cryptanalysis of ARX[END_REF] is the 12th and 11th bits in (c 6 ⊕ k 6 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute v 6 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF] is the 6th and 5th bits in (c 6 ⊕ k 6 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute t 11 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF] is the 25th and 24th bits in ((c 11 c 12 ) ⊕ k 11 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute v 11 [START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF] is the 11th and 10th bits in (c 11 ⊕ k 11 ).

As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute v 11 [START_REF] Aumasson | SHA-3 proposal Blake[END_REF] is the 5th and 4th bits in (c 11 ⊕ k 11 ). As discussed before, the average of the squared correlation is 3/4 × (1)

2 + 1/4 × (2 -1 ) 2 .
For the 2nd diagonal, we guess 6 key bits in k 6 and 6 key bits in k 11 . The average of the squared correlation is about 2 -1.797 .

• The indicator to compute v 7 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF] is the 6th and 5th bits in (c 7 ⊕ k 7 ). As discussed before, the average of the squared correlation is 3

/4 × (1) 2 + 1/4 × (2 -1 ) 2 .
For the 3rd diagonal, we guess 2 key bits in k 7 . The average of the squared correlation is about 2 -0.300 .

• The indicator to compute t 3 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF][START_REF] Aumasson | SHA-3 proposal Blake[END_REF] or t 3 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF] is (c 4 ⊕ k 4 ) [START_REF] Khovratovich | Rotational cryptanalysis of ARX[END_REF], (c 4 ⊕ k 4 ) [START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF], and (c 9 ⊕ k 9 ) [START_REF] Aumasson | SHA-3 proposal Blake[END_REF]. As discussed before, the average of the squared correlation is

3/4 × (2 -1 ) 2 + 1/4 × (2 -2 ) 2 .
• The indicator to compute v 4 [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF] is the 18th and 17th bits in (c 4 ⊕ k 4 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 .

• The indicator to compute v 4 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF] is the 6th and 5th bits in (c 4 ⊕ k 4 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 . • The indicator to compute v 5 9 [START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF] is the 11th and 10th bits in ((c 9 c 14 (c 3 ⊕ (c 14 ≫ 8))) ⊕ k 9 ). As discussed before, the average of the squared correlation is 3/4 × (1) 2 + 1/4 × (2 -1 ) 2 .

• The indicator to compute v 9 [START_REF] Todo | Nonlinear invariant attack: Practical attack on full SCREAM, iSCREAM, and Midori64[END_REF] is the 11th and 10th bits in (c 9 ⊕ k 9 ). As discussed before, the average of the squared correlation is 3/4 × (1)

2 + 1/4 × (2 -1 ) 2 .
For the 4th diagonal, we guess 6 key bits in k 4 and 3 key bits in k 9 . The average of the squared correlation is about 2 -3.498 . Therefore, we guess 36 key bits in total, and the average of the squared correlation (for the linear part of one of each pair) is 2 -9.991 . The average of the squared correlation for the whole approximation is estimated by C = (2 -10.3 ) 2 × (2 -9.991 ) × (2 -9.991 ) ≈ 2 -40.582 . Note that, unlike Chaskey, once these key bits are correctly guessed, all linearly involved bits are either determined or canceled out by XORing another text. It implies dim(W ) = 0, and we do not need to proceed with the FWHT.

Data and Time Complexities and Success Probability

Based on the LLR statistic, we estimate the data complexity and the corresponding success probability.

To find a right pair, we repeat Algorithm 2 2 5 times. If we use a right pair and guess the correct key, the LLR statistic follows the normal distribution N ( N 2 C, N C) when the correct key is guessed. On the other hand, we assume that it follows N (-N 2 C, N C) for either using a wrong pair or wrong guess. We need to filter (5 + 36)-bit wrong guess by this difference of the normal distributions. By using Proposition 5, the expected number of wrong keys is less than 1 when

Θ ≥ N C × Φ -1 (1 -2 -41 ) - N 2 C .
When we use N = 2 47 pairs, Θ ≈ 23.303 and7 p success = 0.491. For this success probability, the data complexity is 2 1+47+5 = 2 53 . We guess 2 36 keys for each texts, the required time complexity is 2 53+36 = 2 89 .

Another 6-Round Attack

The aforementioned attack is the straightforward application of our attack framework, and it could be optimal considering the data complexity. Interestingly, we have another strategy where less time complexity is possible, although it increases data complexity.8

In the aforementioned attack, we guessed many key bits for each ciphertext. Now, instead of guessing many key bits, we deduce k P for observed ciphertexts such that the absolute correlations become 1 (except for t 0 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF] and t 3 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF] or t 3 [START_REF] Aumasson | BLAKE2: simpler, smaller, fast as MD5[END_REF][START_REF] Aumasson | SHA-3 proposal Blake[END_REF]). For example, to compute v 5 [START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF], we first check (c 5 [START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF] c 5 [START_REF] Maitra | Chosen IV cryptanalysis on reduced round ChaCha and Salsa[END_REF]). When we guess (k 5 [START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF] k 5 [START_REF] Maitra | Chosen IV cryptanalysis on reduced round ChaCha and Salsa[END_REF]) as 00, the indicator is 11 and the absolute correlation is lower than 1. For another guessing, we have representations whose correlation is ±1. We skip guessing the key as 00 for this ciphertext only to reduce the time complexity.

We have 21 partitioning points, and 3/4 data is available for each point. Only for one point, i.e., v 5 10 [7]/v 5 10 [7, 6], we do not need to reduce the available data by changing the applied linear masks dynamically. In summary, the fraction of available partitions is (3/4) 20 ≈ 2 -8.3 . Both texts in each pair must belong to an available partition, and the fraction of available pairs is 2 -16. 6 . The final correlation is 2 -10.3 × (2 -2 ) × (2 -2 ) = 2 -14.3 , and the average of the squared correlation is estimated by C = 2 -28.6 .

To find a right pair, we repeat Algorithm 2 2 5 times. By using Proposition 5, the expected number of wrong keys is less than 1 when

Θ ≥ N * C × Φ -1 (1 -2 -41 ) - N * 2 C ,
where N * = N × 2 -16.6 . When we use N = 2 52 pairs, N * = 2 35.4 and Θ ≈ 19.693 and9 p success ≈ 0.5. For this success probability, the data complexity is 2 1+52+5 = 2 58 . On this attack, we do not need to guess 2 36 keys for all 2 58 data. On each data, we guess available key bits only. Therefore, the time complexity is estimated as 1/p × (2N + 2N * × 2 n P ) = 2 5 × (2 53 + 2 36.4 × 2 36 ) ≈ 2 77.4 .

The 7-Round Attack

Unfortunately, 7-round ChaCha is too complicated to apply our technique to the linear part. On the other hand, thanks to our contribution for the differential part, we find a new differential-linear distinguisher which is improved by 0.5 rounds. Therefore, to confirm the effect of our contribution for the differential part, we use the known technique, i.e., the probabilistic neutral bits (PNB) approach, for the key-recovery attack against 7-round ChaCha. The PNB-based key recovery is a fully experimental approach. We refer to [START_REF] Aumasson | New features of latin dances: Analysis of Salsa, ChaCha, and Rumba[END_REF] for the details and simply summarize the technique as follows:

• Let the correlation in the forward direction (a.k.a, differential-linear distinguisher) after r rounds be d . • Let n be the number of PNBs given by a correlation γ. Namely, even if we flip one bit in PNBs, we still observe correlation γ. • Let the correlation in the backward direction, where all PNB bits are fixed to 0 and non-PNB bits are fixed to the correct ones, be a .

Then, the time complexity of the attack is estimated as 2 256-n N + 2 256-α , where the data complexity N is given as

N = α log(4) + 3 1 -2 a 2 d a d 2 ,
where α is a parameter that the attacker can choose.

In our case, we use a 4-round differential-linear distinguisher with correlation d = 2 -8.3 . Under pairs generated by the technique shown in 10.2, we experimentally estimated the PNBs. With γ = 0.35, we found 74 PNBs, where non-zero bits of the following bit-vectors represent PNB:

v 4 : 0x00098080 v 5 : 0x8CFFE7FC v 6 : 0xF8087FC0 v 7 : 0x0000403C v 8 : 0x80000100 v 9 : 0xF8198183 v 10 : 0x80700007 v 11 : 0xF8000000.
Then, the correlation is a = 2 -10.6769 . Then, with α = 36, we have N = 2 43.83 and the time complexity is 2 225.86 . Again, since we need to repeat this procedure p -1 times, the data and time complexities are 2 48.83 and 2 230.86 , respectively. 10

Conclusion and Future Work

We presented new ideas for differential-linear attacks and, particularly, the best attacks on ChaCha,11 one of the most widely used ciphers in practice, and Chaskey. We hope that our framework finds more applications. In particular, we think that it is a promising future work to investigate other ARX designs for our ideas.

Besides the direct application of our framework to more primitives, our work raises several more fundamental questions. As explained in the experimental verification, we sometimes observe higher LLR statistics than expected, making the attacks more efficient than estimated. The gap would come from the difficulty of estimating the accurate correlation of all partitions. Our paper does not solve how to estimate these correlations accurately and efficiently.

Another important open question is in the 7-round attack on ChaCha. We applied the partitioning technique to the 6-round attack. Our result outperforms PNB techniques, which is an experiment-based key recovery technique. Unfortunately, using this technique in 7-round ChaCha is too complicated. A more simple and powerful key recovery procedure exploiting the partitioning technique would beat the PNB-based key recovery like the 6-round attack. However, it is still an open question in our paper.

A Summary of Partitioning

We summarize various partition rules for modular addition. Note that we can verify the correlation of each case experimentally because they have a very high absolute correlation.

A.1 Single Modular Addition

k 0 k 1 c 0 c 1 z 0 z 1 y 0 y 1 F b 0 b 1 b 0 b b 0 1 z 0 [i] z 0 [i] z 0 [i] z 0 [i, i -1] z 0 [i, i -1] z 0 [i, i -1] γ γ γ ε ε ε γ γ γ ε ε ε 00 11100 -1 11110 -1 01 11100 -1 11101 -2 -1 10 11010 -1 11000 1 11 11001 -2 -1 11000 1
Fig. 15 Partitions for a single modular addition.

Let us start with the most simple case of a single modular addition. To compute the parity z 0 [i] and z 0 [i] ⊕ z 0 [i -1] (shortly denoted by z 0 [i, i -1]) from c 0 and c 1 (see Fig. 15), we represent each element of P as two-bit values b 0 b 1 , therefore dividing the whole set into four subsets

T b0b1 = {(y 1 , y 0 ) ∈ (F n 2 ) 2 | b 0 b 1 ∼ = s[i -1] s[i -2]}, z 2 z 1 z 3 8 c 2 c 1 c 3 k 2 k 1 k 3 1 v 3 v 2 b 0 b 1 b 2 b 3 b 4 b 0 b 1 b 2 b 3 b 4 b 0 b 1 b 2 b 3 b 4 z 2 [11]
z 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF] z 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF] z 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF] z 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF] z 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF]

γ γ γ ε ε ε γ γ γ ε ε ε 00000 11110111100 -2 -2 11110011100 1 00001 11111011100 -2 -1 11110011100 2 -1 00010 11111011010 -1 11111111010 -2 -2 00011 11111011010 -2 -1 11110011010 -2 -1 00100
Fig. 16 Partition for two consecutive modular additions.

where s = ȳ1 ⊕ y 0 . Note that these partition can be constructed by guessing two bits of key information, i.e., (k 1 ⊕k 0 )[i-1] and (k 1 ⊕k 0 )[i-2]. Linear masks used in the previous partitioning technique involves 4 bits, i.e., y 1 [i], y 0 [i], y 0 [i -1], and y 0 [i -2]. Our new partitioning technique additionally involves y 0 [i -3], and parities z 0 [i] and z 0 [i, i -1] are approximated to

γ, y 1 [i] y 0 [i] y 0 [i -1] y 0 [i -2] y 0 [i -3] ,
where γ and the corresponding correlations are summarized in Fig. 15.

A.2 More Complicated Case

In a similar way, we can extend the technique for the case of two consecutive modular additions. A concrete example, which is used to attack 7-round Chaskey, is shown in Fig. 16.

The goal is to compute the parity z 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF] and z 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF] from c 1 , c 2 , and c 3 (see Fig. 16). We split the ciphertext into 2 5 partitions (this time indexed by where s = v1 ⊕ v 2 . In order for previously discarded partition to be available, our new partitioning technique additionally involves v 2 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF] and v 2 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF], and parities z 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF] and z 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF] are approximated to

γ, v 3 [19] v 1 [11] v 2 [11] v 2 [10] v 2 [9] v 2 [8] v 1 [19] v 2 [19] v 2 [18] v 2 [17] v 2 [16] ,
where γ is appropriately chosen following Fig. [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF]. We remark that this new way of partitoning the ciphertexts allows us to find high-absolute-correlation masks for all the 32 partitions, up from the 24 used with the original [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF].

B Understanding Partition Points B.1 A Simple Toy Example

We transfer the above terminology to the simple toy example given in Fig. 17 and already discussed earlier in Sect. 2.2. In this example, for a fixed i ≥ 2, we want to evaluate z 0 [i] or z 0 [i] ⊕ z 0 [i -1] by using the partitioning rules as expressed in Lemma 2 and Lemma 3. For this, we say that (z 0 [i], z 0 [i]⊕z 0 [i-1]) defines a partition point ζ. This partition point gives rise to a 2-dimensional subspace P which can be defined by two parity check equations, i.e., P is a complement space of the space

R = {(x 1 , x 0 ) ∈ F 2m 2 | x 0 [i -1] ⊕ x1 [i -1] = 0 and x 0 [i -2] ⊕ x1 [i -2] = 0} .

B.3 Analysis for Two Consecutive Modular Additions

To avoid the usage of long linear trails and to reduce the data complexity, we may use the partition technique for the more complicated structure of two consecutive modular additions. Inspired by the round function of Chaskey, we consider the case depicted in Fig. 16. Suppose that we have two partition points, i.e., C Exploiting the Conditions for Finding Chaskey Relations v1 v0 v2 v3

ζ 1 = (z 2 [i], z 2 [i] ⊕ z 2 [i -1]),
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X In Fig. 18, we have depicted the relations and the influence of the input bits on the conditions of the differential path. The bits that stay white (and have no pink color beneath, coming from the carries of the furthest additions) are the bits that do not affect the differential transitions.

It is easy to see how the bits provided in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] as available for sampling with probability one are the only white ones, and therefore not needed for the differential conditions: [START_REF] Baignères | How far can we go beyond linear cryptanalysis?[END_REF][START_REF] Neyman | On the problem of the most efficient tests of statistical hypotheses[END_REF][START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF][START_REF] Maitra | Chosen IV cryptanalysis on reduced round ChaCha and Salsa[END_REF][START_REF] Shi | Improved key recovery attacks on reduced-round Salsa20 and ChaCha[END_REF][START_REF] Aumasson | New features of latin dances: Analysis of Salsa, ChaCha, and Rumba[END_REF][START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF][START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Wallén | Linear approximations of addition modulo 2 n[END_REF][START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF] from v 2 and [START_REF] Shi | Improved key recovery attacks on reduced-round Salsa20 and ChaCha[END_REF][START_REF] Aumasson | New features of latin dances: Analysis of Salsa, ChaCha, and Rumba[END_REF][START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF][START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF][START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Wallén | Linear approximations of addition modulo 2 n[END_REF][START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF]] from v 3 . The differences are represented in grey. Dependencies in colors. A 'g' in the position of a difference means that this difference will go away (be absorbed) after the next addition. An 's' means that the difference stays where it is, while 'm' means that it moves one position to the left. The color of the bits with differences in each transition will be applied to all the bits that might affect this transition. Carries are not directly applied to the involved bits but to the upper row to report the difference this implies.

Please note that for instance bits 28 and 27 from v 2 cannot be included as the carry of the position 29 is needed by the orange bit relations, i.e., the differences after one round at position 29 of v 2 and v 3 , but as said in Sect. 5.3, the bits of previous positions to 26 and 27 will not affect this orange carry anymore due to the particular configuration of 26 and 27. The bits provided in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] that are neutral with very high probability are 20 and 19 from v 1 and 31, 20 and 19 from v 0 and 25 and 24 of v 3 .

Let us now see how can we use the conditional differential ideas and Fig. 18 in order to recover for free the value of some keybits and also to find additional bits of information for sampling and increasing the dimension of U from 18 as given in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] (and involving exclusively one-bit relations) to 22, or 23 if one-bit relation on the key is known.

Additional space for sampling Using Fig. 18 we can try to exploit the conditions to find more evolved relations for increasing the size of U. Let us provide an example: Let us imagine we flip the bit from v 0 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF]. The corresponding difference, marked with a 'g', will have a change of parity. In order for this difference to be absorbed, we need to also flip the other blue difference that will be used for absorbing this one: v 1 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF]. However, if we flip this one, the value of the bit v 1 [START_REF] Khovratovich | Rotational cryptanalysis of ARX[END_REF] after one round, that does not contain a difference, will be flipped also, as to produce it, v 1 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF] is shifted of 5 positions and XORed with the sum of v 0 and v 1 , that has a difference in position 13, marked with an 's': these differences cancel out in both cases, but the value of the resulting bit will change with the parity of v 1 [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF], and the value of this pink will affect the final light-pink transition in the third round, as can be seen in the picture. In order to avoid this, we have to also flip v 1 [START_REF] Khovratovich | Rotational cryptanalysis of ARX[END_REF]: the state v 1 after 1 round will be known the same, but the orange bit v 2 [START_REF] Biham | An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[END_REF] after one round that contains a difference and a 'g' will have the parity changed. In order to make the related transition be satisfied, we need to also change the parity of the other orange bit with a 'g': we flip v 2 [START_REF] Biham | An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[END_REF] from the first round, that does not have a difference, but that will change the parity of v 3 [START_REF] Biham | An improvement of linear cryptanalysis with addition operations with applications to FEAL-8X[END_REF] after the XOR. This bit will not have any more influence in the remaining transitions, so we have found our close relation. In total, we found four new probability-one relations by hand using this same technique. We have verified these relations as well as exhaustively searched all the ones with weight at most 3, and found that no other such relations exist.

  Let a, b ∈ F m and let z = a + b. When i = 0 (lsb), the modular addition for bit i becomes linear, i.e., z[0] = a[0] ⊕ b[0]. Of course, for i > 0, the ith output bit of modular addition is not linear on the inputs. However, by restricting (a, b) to a specific subset, we might obtain other linear relations. In previous work, the following formula on z[i] was derived. Lemma 1 ([19]) Let a, b ∈ F m 2 and z = a + b. For i ≥ 2, we have

Fig. 3

 3 Fig.3Two examples of the partitioning technique. In the first case (left picture), we are interested in an approximation for z 0 [i]. In the second case (right picture), we are interested in an approximation for z 0[i] ⊕ z 0 [i -1].The corresponding partitions and approximations are given in Lemma 2 and Lemma 3, respectively.

Fig. 4

 4 Fig. 4 Representation for z 0 = y 0 + ȳ1 + 1.

Fig. 5

 5 Fig. 5 Two linear trails with correlation 2 -1 .

  ), c( )) ← (E(x), E(x ⊕ ∆ in )) 4: end for 5: for k P ∈ P do for ∈ {1, . . . , N } do 11:

2 Fig. 7

 27 Fig. 7 The round function of Chaskey.

E 2 FFig. 8

 28 Fig. 8 Four 0.5-round linear trails for the 7-round attack.

Fig. 9

 9 Fig. 9 Comparison with LLR statistics to attack 7-Round Chaskey.

  used, the absolute correlation increases to 2 -5.90893 . We similarly estimate correlations when different linear trails are used, but in fact, using ψ

Fig. 10

 10 Fig. 10 Comparison with LLR statistics to attack 7.5-Round Chaskey.

Fig. 11

 11 Fig. 11 Comparison with LLR statistics to attack 7.5-Round Chaskey when multiple linear masks are used every partition.

14 v 0 v 5 v 10 v 15 v 1 v 6 v 11 v 12 v 2 v 7 v 8 v 13 v 3 v 4 v 9 v 14 t 0 t 10 t 11 t 3 c 0 c 5 c 10 c 15 c 1 c 6 c 11 c 12 c 2 c 7 c 8 c 13 c 3 c 4 c 9 c 14

 14314

1 FFig. 17

 117 Fig.17A simple toy example with a single modular addition.

  Fig.17A simple toy example with a single modular addition.

  For example, P can be chosen as{([], []), ([i-1], []), ([i-2], []), ([i-2, i-1], [])}.To demonstrate the attack from the previous section, we split F 2m 2 into the direct sum P ⊕ R. By the isomorphism between P and F 2 2 , we can identify andΓ (001011) out = ([], [ , -1], [], [i, i -1, j]) γ (001011) = ([ ], [ ], [i, j], [i, i -1, i -2, j, j -2]) , ε 001011 = 1 ,which evaluates the parity of five bits of z. Again, several choices for the definition of the tuples in Equation (9) are possible.

ζ 2 =

 2 (z 3 [j], z 3 [j, j -1]),where i, j ≥ 3. We use the same strategy described in Appendix B.2. Namely, we identify the elements p ∈ P by (5 + 2)-bit values, where 5-bit and 2-bit indicators come from the partition point ζ 1 and ζ 2 , respectively. The applied linear mask and corresponding correlation can be computed as depicted in Figs.15 and 16.

Fig. 18

 18 Fig. 18 Conditions on the differential transitions for the 3 first rounds of Chaskey

Table 1 (

 1 Partial) Key-Recovery Attacks on Chaskey and ChaCha.

	Target	Key size Rounds Time Data Ref.
	Chaskey 128	6	2 28.6	2 25	[19]
			7	2 67	2 48	[19]
				2 50	2 40.21 Sect. 9.3
			7.5	2 77	2 48	Sect. 9.4
	ChaCha 256	6	2 139	2 30	[22]
				2 136	2 28	[23]
				2 116	2 116	[20]
				2 89	2 48	Sect. 10.4
				2 77.4	2 58	Sect. 10.5
			7	2 248	2 27	[22]
				2 246.5	2 27	[23]
				2 238.9	2 96	[24]
				2 237.7	2 96	[20]
				2 235.22 -	[21]
				2 230.86 2 48.83 Sect. 10.6
			7.25	2 255.62 2 48.36 [25]

Table 2

 2 Probability that adding one basis element affects the output difference.

	Probability	Basis		Number of indices
	γ j = 1	v 2 : 16,17,18,19,20,22,23,24,25,30,31 v 3 : 16,17,18,19,20,22,23	18
	0.93 ≤ γ j < 1	v 0 : 19,20,31 v 1 : 19,20	v 3 : 24,25,30	8

Table 3

 3 List of output linear masks after 6 rounds.

	Type Linear mask	δ δ δ
	(0) 0 β

Table 5

 5 List of output linear masks after 6.5 rounds.

	Type Linear mask	δ δ δ
	β	(0) 0

  17.28 × 2 24 × 2 × 2 29.72 × 32 + 21 × 2 21 ≈ 2 77.00 .

This article is an extended version of the paper presented at CRYPTO 2020[START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF]. Some further improvements introduced in[START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF] are included.

under the assumption that the sets { Γout, E(x) ⊕ Γout, E(x ⊕ ∆in) | x ∈ X } and { Γout, E(x) ⊕ Γout, E(x ⊕ ∆in) | x ∈ S} are indistinguishable, where S denotes a set of uniformly chosen samples of the same size as X .

Or at least with a cost much lower than p -1 , see Sect. 5.2.

The first case is exactly the one shown in[START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], but its correlation was reported as 2 -6.1 . We are not sure about the reason for this gap, but we think that 2 -6.1 refers to the bias instead of the correlation.

The theoretical justification is discussed in[START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF] after the proposal of our original paper[START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF].

This correlation is estimated originally when the key k7 changes randomly, but k7 is a fixed constant. These correlations are much higher or lower according to the fixed key, but on key average, which is the natural attack assumption for symmetric-key ciphers, the average correlation is -2 -1 .

Note that it means that the success probability is 0.491 × 2 = 0.982 under the condition that the right pair is successfully obtained during 2 5 iterations.

This is the same attack proposed in our original paper[START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF].

Note that it means that the success probability is almost 1 under the condition that the right pair is successfully obtained during 2 5 iterations.

When we estimate a , we used the average correlation. When we used the median instead of the average, a = 2-11.1687 . Then, the data and time complexities are 2 49.7856 and 2 231.823 , respectively.

Some follow-up works[START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF][START_REF] Coutinho | Improved linear approximations to ARX ciphers and attacks against ChaCha[END_REF][START_REF] Dey | Revisiting cryptanalysis on ChaCha from Crypto 2020 and Eurocrypt[END_REF][START_REF] Coutinho | New multi-bit differentials to improve attacks against ChaCha[END_REF] have been proposed after our original proposal[START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF]. Our attack is still the best for 6-round attack in the context of key recovery. Even for 7 rounds, there have not been follow-up works that essentially improve the complexity yet. On the other hand, Coutinho and Neto presented more efficient distinguishing attacks in[START_REF] Coutinho | New multi-bit differentials to improve attacks against ChaCha[END_REF], and Miyashita, Ito, and Miyaji showed the key-recovery attack on 7.25 rounds in[START_REF] Miyashita | Pnb-focused differential cryptanalysis of ChaCha stream cipher[END_REF].

Note that P is not necessarily a direct sum of P1, P2, and P3. In other words, the dimension of P might be smaller than 6, for instance if i = j, i.e., ζ1 = ζ2.

Acknowledgments

We thank the reviewers for their detailed and helpful comments. We further thank Lukas Stennes for checking the application of our framework to ChaCha in a first version of this paper. We also thank Juan del Carmen Grados Vásquez for pointing out the use of the median to evaluate the PNB-based key recovery. This work was partially funded by Deutsche Forschungsgemeinschaft (DFG) under Germany's Excellence Strategy -EXC 2092 CASA -390781972. 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).

v 3 [START_REF] Knudsen | Integral cryptanalysis[END_REF] ⊕ v 2 [START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF], s L [3], s L [START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF], s L [START_REF] Knudsen | Integral cryptanalysis[END_REF], (s L [START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF]), and 11-bit key guessing is enough, where s L = k 1 ⊕ k 2 and s R = k 0 ⊕ k 3 . After we guess the 11-bit key, we assume that ζ 1 p i ∼ = (0, 0), ζ 2 p i ∼ = (0, 0, 0, 1, 0), and ζ 3 p i ∼ = (0, 0, 0, 1, 0) for c. We now consider the case that the linear trail ψ (3) is used for both texts in a pair. When β [START_REF] Shimizu | Fast data encipherment algorithm FEAL[END_REF] 0 is used, available linear masks and corresponding correlation are computed as follows:

• To compute w 6 0 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF], γ = 11100 is used with correlation -1. • To compute v 6 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF], γ = 11111011010 is used with correlation -1. • To compute v 6 2 [START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF], γ = 11111011010 is used with correlation -1. Note that the partition shown in Fig. 16 is directly available to evaluate v 6 2 [START_REF] Knudsen | Integral cryptanalysis[END_REF]. For other bits, e.g., v 6 2 [START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF], corresponding correlations must be reevaluated because the 11th bit and 4th bit provide slightly different correlations. Assuming all partition points are independent, the correlation is

0 ) = -1 × -1 × -1 = -1 due to the piling-up lemma [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF].

We also assume that ζ 1 p i ∼ = (0, 0), ζ 2 p i ∼ = (0, 0, 1, 0, 0), and

0 is used, available linear masks and corresponding correlation are computed as follows:

• To compute w6 0 [START_REF] Lipmaa | Efficient algorithms for computing differential properties of addition[END_REF], γ = 11100 is used with correlation -1.

• To compute ṽ6

2 [START_REF] Knudsen | Integral cryptanalysis[END_REF], γ = 11111011100 is used with correlation 2 -0.263 . • To compute ṽ6

2 [START_REF] Bernstein | The Salsa20 family of stream ciphers[END_REF], γ = 11111011100 is used with correlation -1. Again, assuming all partition points are independent, the correlation is

0 ) = -1 × 2 -0.263 × -1 = 2 -0.263 . Thus, when β

We now take the auto-correlation-linear hull into account. Instead of β and compute the correlation when the same linear mask γ is used.

1 ) = -1 × -1 × 2 -0.677 = 2 -0.677 . Therefore, when ψ

Fig. 12 The odd and even round functions of ChaCha.

The following shows such differential characteristics over one QR function:

The probability that pairs with input difference ∆ in satisfy this characteristic is 2 -5 on average. We discuss the properties of this differential characteristic in Sect. 10.2 in more detail.

We next evaluate an experimental differential-linear distinguisher for the middle part E m . When the Hamming weight of Γ m is 1, and the active bit is in the lsb, it allows the absolute correlation of linear trails for E 2 to be lower. For i = 6, i.e., ∆ m = (( [START_REF] Broll | Further improving differential-linear attacks: Applications to Chaskey and Serpent[END_REF]), ([5, 29, 17, 9]), ( [START_REF] Neyman | On the problem of the most efficient tests of statistical hypotheses[END_REF][START_REF] Aumasson | New features of latin dances: Analysis of Salsa, ChaCha, and Rumba[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF]), ( [START_REF] Neyman | On the problem of the most efficient tests of statistical hypotheses[END_REF][START_REF] Mouha | Chaskey: An efficient MAC algorithm for 32-bit microcontrollers[END_REF])), we find the following four differential-linear distinguishers:

and other branches are constant), and α j is a linear mask such that the lsb of the branch w 3 (j+1) mod 4 is 1 (and the others are 0). When this experimental distinguisher is combined with the differential characteristic for E 1 , it covers 3.5 rounds with a 1-bit output linear mask Γ m . This differential-linear distinguisher is improved by 0.5 rounds from the previous distinguisher with 1-bit output linear mask (see [START_REF] Choudhuri | Significantly improved multi-bit differentials for reduced round Salsa and ChaCha[END_REF][START_REF] Aumasson | New features of latin dances: Analysis of Salsa, ChaCha, and Rumba[END_REF]).

Differential Part

The QR function is independently applied to each column in the first round. Therefore, when the output difference of one QR function is restricted by ∆ m , the input of the other three QR functions are trivially independent of the output difference. It implies that we have 96 independent bits, and we can easily amplify the probability of the differential-linear distinguisher. On the other hand, we face a different problem: the probability of the differential characteristic (∆ in , ∆ m ) highly depends on the value of the secret key. For example, for ∆v 0 12 [START_REF] Aumasson | SHA-3 proposal Blake[END_REF] = 1, we expect that there is a pair (v 0 12 , v 0 12 ⊕0x00000020) satisfying ∆(v 1 0 , v 1 4 , v 1 8 , v 1 12 ) = ∆ m , but it depends on the constant v 0 0 and the key values v 0 4 and v 0 8 . We cannot find such a pair for 292 out of 1024 randomly generated keys in our experiments. On the other hand, when we can find it, i.e., on 732 out of 1024 keys, the average probability satisfying ∆(v 5 . This experiment implies the existence of "strong keys" against our attack 5 . However, note that we can vary the columns in which we put a difference, which involves different key values. Since the fraction of "strong keys" is not so high, i.e., 292/1024, we can assume that there is at least one column in which no "strong key" is chosen with very high probability.

To determine the factor p, for 1024 randomly generated keys, we evaluated p -1 randomly chosen nonces and counters, where the branch in which we induce the difference is also randomly chosen. As a result, we can find a right pair on 587 keys with p -1 = 2 5 iterations. Therefore, with p = 2 -5 , we assume that we can find a right pair with a probability of 1/2 in this stage of the attack.

In the following, we explain our attack for the case that v 0 12 is active,

Note that the analysis for the other three cases follows the same argument.

Linear Part for the 6-Round Attack

To attack 6-round ChaCha, we first construct a 5-round differential-linear distinguisher, where 1.5-round linear trails are appended (i.e. the E 2 part) to the 3.5-round experimental differential-linear distinguisher from the previous section. We have two 1.5-round linear trails given by

where ψ (1) = ψ ⊕ v 5 10 [6] and ψ (0) = ψ ⊕ v 5 14 [START_REF] Aumasson | SHA-3 proposal Blake[END_REF], and

Figure 13 shows the two 1.5-round linear trails. Since their correlations are ±2 -1 , we have 2 × 2 differential-linear distinguishers on 5 rounds whose correlations are ±2 -10.3 . Note that the sign of each correlation is deterministic according to the output linear mask.

Key Recovery for the 6-Round Attack

Our 6-round attack uses these 5-round differential-linear distinguishers, and the 1-round key recovery is shown in Fig. 14. Let c = (c 0 , . . . , c 15 ) be the [0]

[0] corresponding output, and let v = (v 0 , . . . , v 15 ) be the sixteen 32-bit values before the secret key is added. Note that the secret key is only added with half of the state and public values are added with the other state. Therefore, we simply regard v i = c i for i ∈ {0, 15, 1, 12, 2, 13, 3, 14}. First, we partially extend two linear masks for the last round to be linearly computed. Figure 14 summarizes the extended linear masks, where we need to compute the bits labeled by a red color. Moreover, for simplicity, we introduce t 0 , t 10 , t 11 , and t 3 as depicted in Fig. 14.

We then consider the following four tuples (T b0b1 , Γ (b0b1) out , γ (b0b1) ) and corresponding ε b0b1 , whose definition come from the properties presented in Lemma 2 and Lemma 3:

ε 11 = 1 . For example, we give an intuition for the choice of the second tuple when (y 1 , y 0 ) ∈ S 01 . Lemma 2 tells us that ([], [i]), (z

On the other hand, Lemma 3 tells us that there is no linear representation with absolute correlation 1. Thus, if available, we should use Γ (01) out = ([], [i]) for this subset.

We further have

and we could recover the three bits, k 0 [i -1], k 0 [i -2], and k 0 [i -3], by the last step using the fast Walsh-Hadamard transform.

B.2 Toy Example Using Multiple Partition Points

Let us now look at another example which consists of two branches of the structure depicted in Fig. 17 in parallel, i.e., (y 3 , y 2 , y 1 , y 0 ) = (F (z 3 , z 2 ), F (z 1 , z 0 )) and c i = y i ⊕ k i . By using a single partition point as done in the above example, we can only evaluate the parity of at most two (consecutive) bits of z = (z 3 , z 2 , z 1 , z 0 ). Instead of just one single partition point, we can also consider multiple partition points. For example, if we want to evaluate the parity involving three non-consecutive bits of z = (z 3 , z 2 , z 1 , z 0 ), we can use three partition points, i.e.

where i, j, ≥ 3. In a specific attack, the choice of the partition points depends on the definition of the linear trail. Those partition points give rise to three subspaces P 1 , P 2 , and P 3 , defined by two parity-check equations each, i.e., P i is a complement space of R i , where

By defining 12 P = P 1 ⊕ P 2 ⊕ P 3 and R to be a complement space of P, we split F 4m , γ (b0b1...bn P -1) ) (9) by using the properties presented in Lemma 2 and Lemma 3. For example, if n P = 6, we can define We can also use the three partition points to compute the parity of more than three bits of z. For example, if n P = 6, by using Lemma 2 and 3, we can define