# Rotational Differential-Linear Attack on Chaskey

Authors: Yuan Qin; Gaoli Wang; Guoyan Zhang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Rotational/Rotational-XOR differential-linear attack is a kind of powerful attack on ARX primitives. In this paper, we analyse the message authentication code algorithm—Chaskey—by using rotational differential-linear attack and using partitioning technique for key recovery. We presentthe results of distinguishing attack under weak-key and related-key settingswith correlation2−55.636 for 9-round Chaskey. This is for the first time rotational differential-linear distinguisher has been used to analyse Chaskey. It is concluded that Chaskey can resist against rotational differential-linear attack.


---

## Body

## 1. Introduction

MAC (Message Authentication Code) is a small piece of information generated by a specific algorithm, which can check the integrity of a certain piece of message and is used for message authentication. It can be used to check whether the content of the message has been changed during message delivery, regardless of whether the reason for the change is accidental or deliberate. In addition, it can be used as the identity verification to confirm the source of message. Specifically, when given a messagem, the MAC algorithm produces a tag τ by processing message m and secret key k. Then, one can send the combination of message and tag as m,τ. It should be difficult for an attacker to forge a tag without knowing the key.MAC algorithm can be constructed from other cryptography primitives. Chaksey[1] is a MAC algorithm, the permutation of which is based on ARX primitives. Since ARX primitives only consist of modular additions, bit rotations, and XORs, they are lightweight and can be implemented easily. The designer of Chaksey thought that it is lightweight and performs well in software as well as hardware. It is natural to think that the security level of MACs mainly depends on its permutation. Therefore, we analyse the permutation of Chaskey, which is presented in Section 4.Rotational cryptanalysis [2–4] was first introduced by Dmitry Khovratovich et al. It is a probabilistic technique which mainly focuses on rotational pair m,m⋘l through the rounds, where m is plaintext and m⋘l is a rotation of m to the left with l bits. This attack is powerful to ARX primitives because the property of rotational pair is preserved by XOR and rotational operations, and also preserved by modular additions with high probability. The only prerequisite for successfully applying a rotation attack is that all constants used in the function maintain their values after rotation. Differential-linear attack [5] combines two most powerful techniques for symmetric-key cryptanalysis, proposed by Langford and Hellman at CRYPTO 1994. At EUROCRYPT 2021, Liu et al. proposed a new attack called rotational/rotational-XOR differential-linear attack [6], which combined the advantages of rotational attack and differential-linear attack.


### 1.1. Our Contributions

Rotational differential-linear attack combines the advantage of rotational attack and differential-linear attack, and it is powerful to analyse ARX primitives. This attack can be divided into two parts. The first part is rotational attack. If there are no constant-xor or there is only rotational-invariable constant in function, the probability of rotational attack is only related to the number of modular additions. However, the conclusion is met when the cipher satisfies Markov cipher assumption, which results in a Markov chain assumption. Since there are some consecutive modular additions in the permutation of Chaksey, the Markov cipher assumption may not hold. In order to get precise results, we should consider the effects of consecutive modular additions. The second part is the linear attack. In this part, we transform the search for linear traces of high correlation into boolean satisfiability problem and use an automatic tool to search the best linear approximations.In order to recover the whitening key, we consider some techniques in differential-linear attack. One of them is the partitioning technique proposed by Beierle et al. [8] at CRYPTO 2020. This technique mainly focuses on multiple linear characteristics rather than one to increase the correlation of linear approximations. We will explain it in detail in Section 3.As a consequence, we get the distinguishing attack under the related-key setting with correlation2−56.636 over 9 rounds of the permutation. Our results with the corresponding complexities are summarized in Tables 1 and 2, together with a comparison to the best attacks published so far. It is the first time to attack Chaskey by using rotational differential-linear attack with partitioning technique.Table 1
Distinguishing attack on Chaskey.
RoundsProbabilityAttack typeRef.122−86Weak-key related-key forgery attack[7]Using rotational attack92−111.272Weak-key related-key distinguisherSection4Using rotational differential-linear attackTable 2
Key recovery attack on Chaskey.
RoundsDataTimeAttack typeRef7240.21251.21Differential-linear key recovery attack[8]With partitioning technique82113.5442124.944Weak-key related-key key recovery attackSection4Using rotational differential-linear attackWith partitioning technique122120Weak-key related-key key recovery attack[7]Using rotational attackThe structure of the remaining paper is as follows: Section2 briefly describes some cryptanalysis methods and techniques for understanding content in this paper. Section 3 gives some examples to introduce the partitioning technique explicitly. Section 4 elaborates on how to attack Chaskey using all the techniques mentioned in the previous section and finally Section 5 is a short conclusion.


## 1.1. Our Contributions

Rotational differential-linear attack combines the advantage of rotational attack and differential-linear attack, and it is powerful to analyse ARX primitives. This attack can be divided into two parts. The first part is rotational attack. If there are no constant-xor or there is only rotational-invariable constant in function, the probability of rotational attack is only related to the number of modular additions. However, the conclusion is met when the cipher satisfies Markov cipher assumption, which results in a Markov chain assumption. Since there are some consecutive modular additions in the permutation of Chaksey, the Markov cipher assumption may not hold. In order to get precise results, we should consider the effects of consecutive modular additions. The second part is the linear attack. In this part, we transform the search for linear traces of high correlation into boolean satisfiability problem and use an automatic tool to search the best linear approximations.In order to recover the whitening key, we consider some techniques in differential-linear attack. One of them is the partitioning technique proposed by Beierle et al. [8] at CRYPTO 2020. This technique mainly focuses on multiple linear characteristics rather than one to increase the correlation of linear approximations. We will explain it in detail in Section 3.As a consequence, we get the distinguishing attack under the related-key setting with correlation2−56.636 over 9 rounds of the permutation. Our results with the corresponding complexities are summarized in Tables 1 and 2, together with a comparison to the best attacks published so far. It is the first time to attack Chaskey by using rotational differential-linear attack with partitioning technique.Table 1
Distinguishing attack on Chaskey.
RoundsProbabilityAttack typeRef.122−86Weak-key related-key forgery attack[7]Using rotational attack92−111.272Weak-key related-key distinguisherSection4Using rotational differential-linear attackTable 2
Key recovery attack on Chaskey.
RoundsDataTimeAttack typeRef7240.21251.21Differential-linear key recovery attack[8]With partitioning technique82113.5442124.944Weak-key related-key key recovery attackSection4Using rotational differential-linear attackWith partitioning technique122120Weak-key related-key key recovery attack[7]Using rotational attackThe structure of the remaining paper is as follows: Section2 briefly describes some cryptanalysis methods and techniques for understanding content in this paper. Section 3 gives some examples to introduce the partitioning technique explicitly. Section 4 elaborates on how to attack Chaskey using all the techniques mentioned in the previous section and finally Section 5 is a short conclusion.


## 2. Preliminaries

We userotx to represent the binary vector x to rotate 1 bit to the left and rot−1x to represent the binary vector x to rotate 1 bit to the right, respectively. For γ,x∈F2n, γ⋅x means the inner product of γ and x. xi is used for denoting the i-th bit of x and x¯ denotes the bitwise complement of x. We denote n dimensional binary vector that all bits are 0 by , the i-th unit vector by i and the xor sum of vectors i1,i2… is by i1,i2,…,is where n is the block size of a cipher. Considering a set S⊆F2n and a Boolean function f: F2n⟶F2n, we define(1)Corx∈Sfx=1S∑x∈S−1fx.In most situations, the correlation offx is estimated by using a subset of F2n due to the limitation of computation resources.


### 2.1. Markov Ciphers and Differential Cryptanalysis

Differential cryptanalysis [9] is a probabilistic chosen-plaintext attack introduced by Biham and Shamir. We choose plaintext pair x,x′ with difference Δ and study how it propagates throughout the function. If an input difference Δ can yield an output difference δ whatever the middle differences are, Δ,δ is a differential characteristic. The differential probability Δ,δ is the number of pairs for which plaintext pair x,x′ with difference Δ and ciphertext pair y,y′ with difference δ over the total number of pairs with input difference Δ. However, in practice, it is hard to calculate differential probability. Since the differential characteristics can be regarded as a Markov chain, the differential probability is estimated by the product of intermediate probabilities [10].Theorem 1 (see [7]).
A sequence of discrete random variablesv0,…,vr is a Markov chain, for 0<i<r,(2)Prvi+1=βi+1|vi=βi,vi−1=βi−1,…,v0=β0=Prvi+1=βi+1|vi=βi.


### 2.2. Boolean Satisfiability Problem and Automatic Search

In recent years, a lot of work that focuses on searching differential characteristic and linear characteristic automatically have come out. There are mainly two types of automation tools. One is Mixed Integer Linear Programming (MILP) and the other is boolean satisfiability problem. The aim of MILP is to optimize an objective function under certain constraints. MILP is usually used for searching differential characteristic and linear characteristic of a cipher whose substitution layer is S-box structure. This idea was first proposed by Sun et al. [11] and many methods which can reduce search time or model for large S-box have been proposed recently [12–15].Three or more SAT is NP-complete. But the solution can be found in a reasonable time for most practical problems. There are a large number of heuristic SAT solvers, which output satisfiable or unsatisfiable depending on whether problem can be solved. More specifically, SAT solvers assign initial values to variables, then compute the number of conflicting clauses, and decides the next step to search until a valid or no solution is found.


### 2.3. Rotational Attack and Differential-Linear Attack

Rotational cryptanalysis was first introduced by Dmitry Khovratovich et al. We usex⋘r and x⋙r to represent the variable rotation to the left and right by r bits, respectively. A rotational pair can be denoted by x,x⋘r. It is easy to see that a rotational pair is preserved throughout bitwise XOR and any rotational operations. However, it is not always preserved by modular addition. Therefore, the probability of this attack only depends on the rotational probability of modular additions.For largen and small r, Table 3 is obtained. It is clear to see when r is equal to 1, the probability is the highest, that is why we always choose 1 to be the rotational offset.Table 3
Rotational offsetr and corresponding probability.
rPrlog2pr10.375−1.141520.313−1.67630.281−1.831In Ref. [3], they claimed that when rotation amount r is fixed, the probability of rotational attack depends on the number of modular addition. But the prerequisite of the lemma is that variables in and round can form a Markov chain. When variables are not random and independent, the lemma will not give a precise answer. Due to some consecutive modular addition in the permutation of Chaskey, we realize that the probability of rotational attack may not only rely on the number of modular addition. In Ref. [7], they explored and proposed a lemma, which calculates the rotational probability of k−1 consecutive modular additions precisely. The result shows that when consecutive modular exits, the probability of rotational attack will be much lower.Differential-linear attack [5, 16] was first introduced by Langford and Hellman. As shown in Figure 1, when considering a cipher E, it can be divided into two subparts E1 and E2, which are covered by differential characteristics and linear characteristics, respectively. Assume that input differences δ and output differences Δ for E1 holds with probability(3)Prx⊕x′=δ⟶Fy⊕y′=Δ=p.Figure 1
Differential-linear distinguisher.Assume that input maskγ and output mask Γ for E2 holds with bias(4)ϵγ,Γ=Prγ⋅y⊕Γ⋅E1y=0−12.Assume that the variables inE1 and E2 are random and independent, the overall bias of differential-linear distinguisher is(5)ϵδ,Γ=PrΓ⋅Ex⊕Ex⊕δ=0−12=−1γ⋅Δ⋅2pϵγ,Γ2.The data complexity of differential-linear distinguisher isOp−2ϵγ,Γ−4.In almost all practical ciphers,E1 and E2 are not independent. In recent years, many significant researches have come out to pursue more accurate results. For example, Bar-On et al. proposed Differential-Linear Connectivity Table (DLCT) [17] to deal with the dependencies between the differential and linear parts. Here, cipher E is divided into three parts: E=E2°Em°E1, and the intermediate part Em is evaluated experimentally.


### 2.4. Rotational Differential-Linear Attack

Rotational differential-linear attack is an attack method that combines the advantage of rotational attack and differential-linear attack, the difference between rotational differential-linear distinguisher and differential-linear distinguisher is the differential part, which is replaced by a rotational differential trace. Given a cipherE, it can be described as a cascade of two subparts such that E=E2°E1. E1 is covered by rotational differential with(6)Prx⊕x⋘t=δ⟶FE1x⊕E1x⋘t=Δ=p,and E2 is covered by a linear approximation(7)ϵγ,Γ=Prγ⋅y⊕Γ⋅E2y=0−12ϵrot−1γ,rot−1Γ=Prrot−1γ⋅y⊕rot−1Γ⋅E2y=0−12.Then, the bias of a rotational differential-linear distinguisher can be represented as follows [6]:(8)ϵδ,Γ=PrΓ⋅rotEx⊕Erotx=0−12=−1γ⋅Δ⋅2pϵγ,Γϵrot−1γ,rot−1Γ.Note that if rotational offset is 0, the rotational differential-linear distinguisher will be degenerated to differential-linear distinguisher. It is clear to see that the bias of rotational differential-linear attack depends onp, ϵγ,Γ and ϵrot−1γ,rot−1Γ. pis related to the first part, which is corresponding to rotational differential attack. ϵγ,Γ and ϵrot−1γ,rot−1Γ are the correlations of linear attack. We will explain how to get a higher correlation of the distinguisher in Section 4.


## 2.1. Markov Ciphers and Differential Cryptanalysis

Differential cryptanalysis [9] is a probabilistic chosen-plaintext attack introduced by Biham and Shamir. We choose plaintext pair x,x′ with difference Δ and study how it propagates throughout the function. If an input difference Δ can yield an output difference δ whatever the middle differences are, Δ,δ is a differential characteristic. The differential probability Δ,δ is the number of pairs for which plaintext pair x,x′ with difference Δ and ciphertext pair y,y′ with difference δ over the total number of pairs with input difference Δ. However, in practice, it is hard to calculate differential probability. Since the differential characteristics can be regarded as a Markov chain, the differential probability is estimated by the product of intermediate probabilities [10].Theorem 1 (see [7]).
A sequence of discrete random variablesv0,…,vr is a Markov chain, for 0<i<r,(2)Prvi+1=βi+1|vi=βi,vi−1=βi−1,…,v0=β0=Prvi+1=βi+1|vi=βi.


## 2.2. Boolean Satisfiability Problem and Automatic Search

In recent years, a lot of work that focuses on searching differential characteristic and linear characteristic automatically have come out. There are mainly two types of automation tools. One is Mixed Integer Linear Programming (MILP) and the other is boolean satisfiability problem. The aim of MILP is to optimize an objective function under certain constraints. MILP is usually used for searching differential characteristic and linear characteristic of a cipher whose substitution layer is S-box structure. This idea was first proposed by Sun et al. [11] and many methods which can reduce search time or model for large S-box have been proposed recently [12–15].Three or more SAT is NP-complete. But the solution can be found in a reasonable time for most practical problems. There are a large number of heuristic SAT solvers, which output satisfiable or unsatisfiable depending on whether problem can be solved. More specifically, SAT solvers assign initial values to variables, then compute the number of conflicting clauses, and decides the next step to search until a valid or no solution is found.


## 2.3. Rotational Attack and Differential-Linear Attack

Rotational cryptanalysis was first introduced by Dmitry Khovratovich et al. We usex⋘r and x⋙r to represent the variable rotation to the left and right by r bits, respectively. A rotational pair can be denoted by x,x⋘r. It is easy to see that a rotational pair is preserved throughout bitwise XOR and any rotational operations. However, it is not always preserved by modular addition. Therefore, the probability of this attack only depends on the rotational probability of modular additions.For largen and small r, Table 3 is obtained. It is clear to see when r is equal to 1, the probability is the highest, that is why we always choose 1 to be the rotational offset.Table 3
Rotational offsetr and corresponding probability.
rPrlog2pr10.375−1.141520.313−1.67630.281−1.831In Ref. [3], they claimed that when rotation amount r is fixed, the probability of rotational attack depends on the number of modular addition. But the prerequisite of the lemma is that variables in and round can form a Markov chain. When variables are not random and independent, the lemma will not give a precise answer. Due to some consecutive modular addition in the permutation of Chaskey, we realize that the probability of rotational attack may not only rely on the number of modular addition. In Ref. [7], they explored and proposed a lemma, which calculates the rotational probability of k−1 consecutive modular additions precisely. The result shows that when consecutive modular exits, the probability of rotational attack will be much lower.Differential-linear attack [5, 16] was first introduced by Langford and Hellman. As shown in Figure 1, when considering a cipher E, it can be divided into two subparts E1 and E2, which are covered by differential characteristics and linear characteristics, respectively. Assume that input differences δ and output differences Δ for E1 holds with probability(3)Prx⊕x′=δ⟶Fy⊕y′=Δ=p.Figure 1
Differential-linear distinguisher.Assume that input maskγ and output mask Γ for E2 holds with bias(4)ϵγ,Γ=Prγ⋅y⊕Γ⋅E1y=0−12.Assume that the variables inE1 and E2 are random and independent, the overall bias of differential-linear distinguisher is(5)ϵδ,Γ=PrΓ⋅Ex⊕Ex⊕δ=0−12=−1γ⋅Δ⋅2pϵγ,Γ2.The data complexity of differential-linear distinguisher isOp−2ϵγ,Γ−4.In almost all practical ciphers,E1 and E2 are not independent. In recent years, many significant researches have come out to pursue more accurate results. For example, Bar-On et al. proposed Differential-Linear Connectivity Table (DLCT) [17] to deal with the dependencies between the differential and linear parts. Here, cipher E is divided into three parts: E=E2°Em°E1, and the intermediate part Em is evaluated experimentally.


## 2.4. Rotational Differential-Linear Attack

Rotational differential-linear attack is an attack method that combines the advantage of rotational attack and differential-linear attack, the difference between rotational differential-linear distinguisher and differential-linear distinguisher is the differential part, which is replaced by a rotational differential trace. Given a cipherE, it can be described as a cascade of two subparts such that E=E2°E1. E1 is covered by rotational differential with(6)Prx⊕x⋘t=δ⟶FE1x⊕E1x⋘t=Δ=p,and E2 is covered by a linear approximation(7)ϵγ,Γ=Prγ⋅y⊕Γ⋅E2y=0−12ϵrot−1γ,rot−1Γ=Prrot−1γ⋅y⊕rot−1Γ⋅E2y=0−12.Then, the bias of a rotational differential-linear distinguisher can be represented as follows [6]:(8)ϵδ,Γ=PrΓ⋅rotEx⊕Erotx=0−12=−1γ⋅Δ⋅2pϵγ,Γϵrot−1γ,rot−1Γ.Note that if rotational offset is 0, the rotational differential-linear distinguisher will be degenerated to differential-linear distinguisher. It is clear to see that the bias of rotational differential-linear attack depends onp, ϵγ,Γ and ϵrot−1γ,rot−1Γ. pis related to the first part, which is corresponding to rotational differential attack. ϵγ,Γ and ϵrot−1γ,rot−1Γ are the correlations of linear attack. We will explain how to get a higher correlation of the distinguisher in Section 4.


## 3. Partitioning Technique

In this section, we use some examples in Ref. [8] to explain how to utilize partitioning technique briefly.


### 3.1. An Introduction of Partitioning Technique

Partitioning technique can improve the correlation of differential-linear attack powerfully by yielding linear equations between cipher and key, which was first proposed by Leurent at EUROCRYPT 2016 [18]. For ARX primitives, modular addition is the only nonlinear component. Assume a,b∈F2n, s=a+b, where + means modular addition. For i=0, si=ai⊕bi. But for i>0si is not always equal to ai⊕bi. In order to derive certain linear equation, the following lemma is given.Lemma 1 (see [18]).
Leta,b∈F2nands=a+b. For i≥2, we have(9)si=ai⊕bi⊕ai−1ifai−1=bi−1,ai⊕bi⊕ai−2ifai−1≠bi−1andi−2=bi−2.
Lemma1 shows the way that si can be calculated by a linear equation if some certain conditions are met with a,b. As shown in Figure 2, we want to get specific equations on z0i; the above will not work because the relation between z0 and y0,y1 are not the relation of modular addition but modular subtraction. Formally, it is expressed by z0=y0−y1, here − means modular subtraction. For this case, the following lemma can help solve the problem.Figure 2
Sample for partitioning technique.Lemma 2 (see [8]).
Leti≥2andletS1:=x1,x0∈F22m|x0i−1≠x1i−1andS2:=x1,x0∈F22m|x0i−1=x1i−1andx0i−2≠x1i−2. Then,(10)z0i=y0i⊕y1i⊕y0i−1⊕1ify1,y0∈S1,y0i⊕y1i⊕y0i−2⊕1ify1,y0∈S2.In the later section, we not only care aboutz0i but also z0i,i−1. It is clear that Lemma 2 can be applied to z0i and z0i−1 separately. Then z0i,i−1 is evaluated by the equations which are yielded by applying Lemma 2 on z0i and z0i−1. However, this method requires knowledge of three bits. The following lemma states that z0i,i−1 is evaluated by knowing only two bits. Since y0=c0⊕k0 and y1=c1⊕k1, the following lemma helps us guess less bits to get linear equations.Lemma 3 (see [8]).
Leti≥2and letS3:=x1,x0∈F22m|x0i−1=x1i−1andS4:=x1,x0∈F22m|x0i−1≠x1i−1andx0i−2≠x1i−2. Then,(11)z0i⊕z0i−1=y0i⊕y1iify1,y0∈S3,y0i⊕y1i⊕y0i−1⊕y0i−2⊕1ify1,y0∈S4.Next, we will explain partitioning technique explicitly. The structure of rotational differential-linear attack is shown in Figure3. Note that E1 is the rotational differential part, E2 is the linear part, and F is the part that we use to recover the whitening key. The key idea of partitioning technique is that we want to use multiple linear approximations Γoutpi⋅z=rotΓoutpj⋅z˜ to recover some bits of key. The space of ciphertext F2n can be split into a direct sum R⊕P. We denote the dimension of P by nP and the dimension of R by nR. The specific definition of R and P depends on the attack. Considering some tuples τpi,Γoutpi,γpi, where τpi=R⊕pi is a coset of R⊆F2n,Γoutpi∈F2n and γpi∈R. If we can get a high correlation,(12)ϵi=Cory∈τpiΓoutpi⋅z⊕γpi⋅y=1.The above equation reveals that if the ciphertext belongs to some specific subset (defined byy∈τpi), we yield some linear equation on k because γpi⋅y=γpi⋅c⊕k and c is the ciphertext that can be observed. If the ϵi is not equal to 1 but close to 1, we still obtain the equation on k with high correlation. Since y=c⊕k, we can guess the nP bits of k and split ciphertext into corresponding τpi. After some equations on k are obtained with high correlation, bits on kR will be recovered. The way to recover some bits on kR is introduced as follows. We define(13)qij=Corx∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkPΓoutpi⋅z⊕rot−1rotΓoutpj⋅z˜.We obtain(14)Corx∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkPγpi⋅c⊕rot−1rotγpj⋅c˜⊕γpi⋅k⊕k⋅γpj=Corx∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkPγpi⋅y⊕rot−1rotγpj⋅y˜=ϵiϵjqij.Forr∈R, let us define sgnr=0ifr≥0,1ifr<0.; we define(15)hij=−1sgnϵiϵjqijCorx∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkPγpi⋅c⊕rot−1rotγpj⋅c˜,We havehij=−1γpi⋅k⊕γpj⋅kϵiϵjqij. Let us define,(16)x∈χ|c,c˜∈τpi×rotτpj⊕kP,rotkP,which is of equal size σ for all i,j and consider the scaled version of hij, i.e.,(17)αij=σ⋅hij=−1sgnϵiϵjqij∑x∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkP−1γpi⋅c⊕rot−1rotγpj⋅c˜.For eachγ∈W  = Span γpi⊕γpj|i,j∈1,…,s, we define(18)βγ=∑i,jsuchthatγpi⊕γpj=γαij.We can use this functionβ to recover W bits of information on kR. kR can be expressed as kL⊕kR′, where kL is the key that can be obtained from β. By using Fast Walsh–Hadamard Transform on β. Fast Walsh–Hadamard Transform reduces the time complexity from O22n to On2n.We compute a cumulative counter.(19)CkP,kL=∑γ∈W−1γ⋅kLβγ,for each tuple kP,kL.Note that when counterC is larger than some threshold Θ, we store the tuple kP,kL in the list of key candidates.Figure 3
The structure of overall rotational differential-linear attack with partitioning technique.


### 3.2. A Simple Example for Partition Point

As shown in Figure2, we define partition point ξ=z1i,z1i⊕z1i−1. For i≥2, in order to compute z1i or z1i⊕z1i−1 by using Lemmas 2 and 3, we need to know which condition some bits in the ciphertext meets. Considering some definitions in Section 2, a cipher space is split into the direct sum P⊕R, Pis complement space of the space(20)R=x1,x0∈F22m|x0i−1⊕x1i−1=0andx0i−2⊕x1i−2=0.Therefore, the dimension ofP is 2. For each element p∈P, it can be rewritten as b1b0 where b0 indicates the value of x¯0i−1⊕x1i−1 and b1 indicates the value of x¯0i−2⊕x1i−2. To enumerate all possible values of p, we can yield the following four tuples τb0b1,Γoutb0b1,γb0b1 and corresponding ϵb0b1 according to Lemmas 2 and 3:(21)τ00=R⊕00=S4Γout00=,i,i−1γ00=i,i,i−1,i−2ϵ00=−1τ01=R⊕01=S1S4Γout01=,iγ01=i,i,i−1ϵ01=−1τ10=R⊕10=S2Γout10=,iγ10=i,i,i−2ϵ10=−1τ11=R⊕11=S3S2Γout11=,i,i−1γ11=i,iϵ11=1.We take the second tuple to illustrate the principle. When it is observed thaty∈τ01, the linear masks Γout01,γ01 are determined. Therefore, the correlation ϵ01=Cory∈τ01Γout01⋅z⊕γ01⋅y can be deducted by using Lemma 2. Then, we have W = Span γa⊕γb|a,b∈F2n=,,,i−1,,i,,i,i−1. Two bits k0i and k0i−1 will be recovered by using Fast Walsh–Hadamard Transform.


### 3.3. Two Consecutive Modular Additions for Partition Point

In this Section, we introduce some cases of consecutive modular additions. As shown in Figure4, we still define partition point ξ=z1i,z1i⊕z1i−1. Note that z1i and z1i⊕z1i−1 is related to some bits of c0, c1 and c2. Formally,(22)z1=y1−y0⋙b−y1−y0⋙c⊕y2⋙a,where means modular subtraction and c=a+b. Therefore, we get a 5-dimensional subspace P, which is a complement subspace of the subspace:(23)R=x2,x1,x0∈F23m|x2ia−1⊕x1ib−2⊕x1ic−2=0x0ib−1⊕x1ib−1=0,x0ib−2⊕x1ib−2=0,x0ic−1⊕x1ic−1=0,x0ic−2⊕x1ic−2=0,where ia=i+a,ib=i+b and ic=i+a+b. For each element p∈P, it can be rewritten as b4b3b2b1b0, where b4b3b2b1b0=y2ia−1⊕y1ib−2⊕y1ic−2,sib−1,sib−2,sic−1,sic−2 with s=y¯0⊕y1. To enumerate all possible values of p, we can yield 25 tuples τpi,Γoutpi,γpi and the corresponding ϵpi. In these tuples, Γoutpi∈,i,,,i,i−1,, and the corresponding linear mask γpi involves these bits:(24)y2ia,y0ib,y1ib−1,y1ib−2,y0ic,y1ic,y1ic−1,y1ic−2.Figure 4
Case of two consecutive modular additions.For the25 tuples given above, 4 of them correspond to correlation ϵ=±1, 8 of them correspond to correlation ϵ=±2−1, and 12 of them correspond to correlation ϵ=±2−0.263. Therefore, there are 24 tuples with high correlation in total. The tuples with the corresponding correlations are listed in the appendix.


## 3.1. An Introduction of Partitioning Technique

Partitioning technique can improve the correlation of differential-linear attack powerfully by yielding linear equations between cipher and key, which was first proposed by Leurent at EUROCRYPT 2016 [18]. For ARX primitives, modular addition is the only nonlinear component. Assume a,b∈F2n, s=a+b, where + means modular addition. For i=0, si=ai⊕bi. But for i>0si is not always equal to ai⊕bi. In order to derive certain linear equation, the following lemma is given.Lemma 1 (see [18]).
Leta,b∈F2nands=a+b. For i≥2, we have(9)si=ai⊕bi⊕ai−1ifai−1=bi−1,ai⊕bi⊕ai−2ifai−1≠bi−1andi−2=bi−2.
Lemma1 shows the way that si can be calculated by a linear equation if some certain conditions are met with a,b. As shown in Figure 2, we want to get specific equations on z0i; the above will not work because the relation between z0 and y0,y1 are not the relation of modular addition but modular subtraction. Formally, it is expressed by z0=y0−y1, here − means modular subtraction. For this case, the following lemma can help solve the problem.Figure 2
Sample for partitioning technique.Lemma 2 (see [8]).
Leti≥2andletS1:=x1,x0∈F22m|x0i−1≠x1i−1andS2:=x1,x0∈F22m|x0i−1=x1i−1andx0i−2≠x1i−2. Then,(10)z0i=y0i⊕y1i⊕y0i−1⊕1ify1,y0∈S1,y0i⊕y1i⊕y0i−2⊕1ify1,y0∈S2.In the later section, we not only care aboutz0i but also z0i,i−1. It is clear that Lemma 2 can be applied to z0i and z0i−1 separately. Then z0i,i−1 is evaluated by the equations which are yielded by applying Lemma 2 on z0i and z0i−1. However, this method requires knowledge of three bits. The following lemma states that z0i,i−1 is evaluated by knowing only two bits. Since y0=c0⊕k0 and y1=c1⊕k1, the following lemma helps us guess less bits to get linear equations.Lemma 3 (see [8]).
Leti≥2and letS3:=x1,x0∈F22m|x0i−1=x1i−1andS4:=x1,x0∈F22m|x0i−1≠x1i−1andx0i−2≠x1i−2. Then,(11)z0i⊕z0i−1=y0i⊕y1iify1,y0∈S3,y0i⊕y1i⊕y0i−1⊕y0i−2⊕1ify1,y0∈S4.Next, we will explain partitioning technique explicitly. The structure of rotational differential-linear attack is shown in Figure3. Note that E1 is the rotational differential part, E2 is the linear part, and F is the part that we use to recover the whitening key. The key idea of partitioning technique is that we want to use multiple linear approximations Γoutpi⋅z=rotΓoutpj⋅z˜ to recover some bits of key. The space of ciphertext F2n can be split into a direct sum R⊕P. We denote the dimension of P by nP and the dimension of R by nR. The specific definition of R and P depends on the attack. Considering some tuples τpi,Γoutpi,γpi, where τpi=R⊕pi is a coset of R⊆F2n,Γoutpi∈F2n and γpi∈R. If we can get a high correlation,(12)ϵi=Cory∈τpiΓoutpi⋅z⊕γpi⋅y=1.The above equation reveals that if the ciphertext belongs to some specific subset (defined byy∈τpi), we yield some linear equation on k because γpi⋅y=γpi⋅c⊕k and c is the ciphertext that can be observed. If the ϵi is not equal to 1 but close to 1, we still obtain the equation on k with high correlation. Since y=c⊕k, we can guess the nP bits of k and split ciphertext into corresponding τpi. After some equations on k are obtained with high correlation, bits on kR will be recovered. The way to recover some bits on kR is introduced as follows. We define(13)qij=Corx∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkPΓoutpi⋅z⊕rot−1rotΓoutpj⋅z˜.We obtain(14)Corx∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkPγpi⋅c⊕rot−1rotγpj⋅c˜⊕γpi⋅k⊕k⋅γpj=Corx∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkPγpi⋅y⊕rot−1rotγpj⋅y˜=ϵiϵjqij.Forr∈R, let us define sgnr=0ifr≥0,1ifr<0.; we define(15)hij=−1sgnϵiϵjqijCorx∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkPγpi⋅c⊕rot−1rotγpj⋅c˜,We havehij=−1γpi⋅k⊕γpj⋅kϵiϵjqij. Let us define,(16)x∈χ|c,c˜∈τpi×rotτpj⊕kP,rotkP,which is of equal size σ for all i,j and consider the scaled version of hij, i.e.,(17)αij=σ⋅hij=−1sgnϵiϵjqij∑x∈χsuchthatc,c˜∈τpi×rotτpj⊕kP,rotkP−1γpi⋅c⊕rot−1rotγpj⋅c˜.For eachγ∈W  = Span γpi⊕γpj|i,j∈1,…,s, we define(18)βγ=∑i,jsuchthatγpi⊕γpj=γαij.We can use this functionβ to recover W bits of information on kR. kR can be expressed as kL⊕kR′, where kL is the key that can be obtained from β. By using Fast Walsh–Hadamard Transform on β. Fast Walsh–Hadamard Transform reduces the time complexity from O22n to On2n.We compute a cumulative counter.(19)CkP,kL=∑γ∈W−1γ⋅kLβγ,for each tuple kP,kL.Note that when counterC is larger than some threshold Θ, we store the tuple kP,kL in the list of key candidates.Figure 3
The structure of overall rotational differential-linear attack with partitioning technique.


## 3.2. A Simple Example for Partition Point

As shown in Figure2, we define partition point ξ=z1i,z1i⊕z1i−1. For i≥2, in order to compute z1i or z1i⊕z1i−1 by using Lemmas 2 and 3, we need to know which condition some bits in the ciphertext meets. Considering some definitions in Section 2, a cipher space is split into the direct sum P⊕R, Pis complement space of the space(20)R=x1,x0∈F22m|x0i−1⊕x1i−1=0andx0i−2⊕x1i−2=0.Therefore, the dimension ofP is 2. For each element p∈P, it can be rewritten as b1b0 where b0 indicates the value of x¯0i−1⊕x1i−1 and b1 indicates the value of x¯0i−2⊕x1i−2. To enumerate all possible values of p, we can yield the following four tuples τb0b1,Γoutb0b1,γb0b1 and corresponding ϵb0b1 according to Lemmas 2 and 3:(21)τ00=R⊕00=S4Γout00=,i,i−1γ00=i,i,i−1,i−2ϵ00=−1τ01=R⊕01=S1S4Γout01=,iγ01=i,i,i−1ϵ01=−1τ10=R⊕10=S2Γout10=,iγ10=i,i,i−2ϵ10=−1τ11=R⊕11=S3S2Γout11=,i,i−1γ11=i,iϵ11=1.We take the second tuple to illustrate the principle. When it is observed thaty∈τ01, the linear masks Γout01,γ01 are determined. Therefore, the correlation ϵ01=Cory∈τ01Γout01⋅z⊕γ01⋅y can be deducted by using Lemma 2. Then, we have W = Span γa⊕γb|a,b∈F2n=,,,i−1,,i,,i,i−1. Two bits k0i and k0i−1 will be recovered by using Fast Walsh–Hadamard Transform.


## 3.3. Two Consecutive Modular Additions for Partition Point

In this Section, we introduce some cases of consecutive modular additions. As shown in Figure4, we still define partition point ξ=z1i,z1i⊕z1i−1. Note that z1i and z1i⊕z1i−1 is related to some bits of c0, c1 and c2. Formally,(22)z1=y1−y0⋙b−y1−y0⋙c⊕y2⋙a,where means modular subtraction and c=a+b. Therefore, we get a 5-dimensional subspace P, which is a complement subspace of the subspace:(23)R=x2,x1,x0∈F23m|x2ia−1⊕x1ib−2⊕x1ic−2=0x0ib−1⊕x1ib−1=0,x0ib−2⊕x1ib−2=0,x0ic−1⊕x1ic−1=0,x0ic−2⊕x1ic−2=0,where ia=i+a,ib=i+b and ic=i+a+b. For each element p∈P, it can be rewritten as b4b3b2b1b0, where b4b3b2b1b0=y2ia−1⊕y1ib−2⊕y1ic−2,sib−1,sib−2,sic−1,sic−2 with s=y¯0⊕y1. To enumerate all possible values of p, we can yield 25 tuples τpi,Γoutpi,γpi and the corresponding ϵpi. In these tuples, Γoutpi∈,i,,,i,i−1,, and the corresponding linear mask γpi involves these bits:(24)y2ia,y0ib,y1ib−1,y1ib−2,y0ic,y1ic,y1ic−1,y1ic−2.Figure 4
Case of two consecutive modular additions.For the25 tuples given above, 4 of them correspond to correlation ϵ=±1, 8 of them correspond to correlation ϵ=±2−1, and 12 of them correspond to correlation ϵ=±2−0.263. Therefore, there are 24 tuples with high correlation in total. The tuples with the corresponding correlations are listed in the appendix.


## 4. Application to Chaskey

### 4.1. Description of Chaskey

Chaskey, proposed by Nicky Mouha et al., is a very efficient Message Authentication Code (MAC) algorithm for 32-bit microcontrollers. Chaskey takes a 128-bit keyk and processes a message m in 128-bit blocks using a 128-bit permutation π. Designers claimed that Chaskey performs well both in software and hardware, and it is an Even-Mansour construction. A message m is processed by n-bit key K into a tag τ. The message m is split into l blocks m1,m2,…,ml of 128-bit each, except for the last block ml which may be incomplete. If the last block ml is not complete, a periodical binary string 10∗ is pushed back until the size of ml is 128-bit. This permutation π is based on the Addition–Rotation–XOR (ARX) design methodology. In practical analysis, we care about the permutation which is shown in Figure 5. When we want to tag a message m with one block of 128 bits, the tag would be τ=πK⊕K1⊕m⊕K1. K1 is generated by K, i.e., K1=xKmodgx, where gx=x128+x7+x2+x+1, as shown in Figure 6.Figure 5
Permutation of Chaskey.Figure 6
Mode of operation for message with single 128 bits block of Chaksey.


### 4.2. Rotational Differential-Linear Distinguishing Attack on Chaskey

In this section, we recall the weak-key class which was introduced in Ref. [7] at first. Then a 9-round rotational differential-linear distinguisher is represented. Finally, an 8-round key recovery attack of Chaskey with partitioning techinique is explained in detail.


#### 4.2.1. Weak Key Class of Rotational Attack

Because of the consecutive modular additions in Chaskey, we need to explore the properties in consecutive modular additions to get more accurate formulas. This work has been done in Ref. [7]. Note that in order to preserve the rotational property, we have to consider the pair πK⊕K1⊕m⊕K1 and πrotK⊕K1′⊕rotm⊕K1′, where K1′ is a key generated from rotK, that is, K1′=xrotKmodgx. To ensure K1′ is the word rotation of K1, the first 2 bits of every word is assumed to be zero. The key K must be in the following form with the aim of attacking successfully.(25)K=00∗00∗00∗00∗,K1=0∗00∗00∗00∗0,rotK=00∗00∗00∗00∗,K1′=∗00∗00∗00∗00,where ∗ is 30 bits that we do not care. The set of keys that satisfy such a condition is called the weak key class. It is clear that the size of the weak key class is 2120. The result that we use to calculate the probability precisely is described in Table 4. Note that there are 2 single modular additions in the every round of permutation.Table 4
Table with the expected rotational probabilities for any number of rounds of Chaskey.
RoundsNumber of chains modular additionsExpected probability11−6.43623−13.63635−20.83647−28.03659−35.236611−42.436713−49.636815−56.836917−64.0361019−71.2361121−78.4361223−86.636A 9-round distinguisher is divided into two parts. The first part is covered by rotational attack and the second part is covered by linear attack. We discuss them separately and the detail of attack is represented as follows.


#### 4.2.2. Rotational Differential Part

Here we set 7 rounds for rotational part and the expected probability of this part is2−49.636, which can be seen in Table 4. Mentioned in Section 2, the probability of rotational attack only depends on the number of (consecutive) modular additions. Since our work on key recovery is interested in rotational attack of 6.5 rounds Chaskey, it is easy to calculate the number of (consecutive) modular additions and the probability is 2−45.272.


#### 4.2.3. Linear Part

Sinceϵγ,Γ is close to ϵrot−1γ,rot−1Γ, we cannot use two high-correlation linear characteristics without specific relations directly. Sometimes ϵγ,Γ is the best linear characteristic, but ϵrot−1γ,rot−1Γ has very low correlation. In order to get ϵγ,Γϵrot−1γ,rot−1Γ as high as possible, we should search two linear characteristics simultaneously. This problem can be transformed to a SAT problem [19, 20] and a SAT solver can be used to search. Because more binary variables are needed to add constraints, we may search less round than a single linear characteristic. Therefore, we set 2 rounds for linear part and the correlation of linear part is 2−7. The total correlation is 2−49.636×2−7×2=2−55.636 and the complexity is 2−55.636−2=2111.272.


#### 4.2.4. Experimental Verification

In order to verify the correctness of formula in Section2.4, we use 220 random data to check the correlation of 3-round Chaskey with 1 round for rotational part and 2 rounds for linear part. The expected correlation of 3-round Chaskey is 2−6.436×2−7×2=2−12.436. The experimental result shows the correlation is 2−11.729. We also provide 3 code files, the first one is a python script to generate a smt2 file, which can be solved by the SAT solver. The second one is smt2 file mentioned above. The third one is a c++ file which is used to verify the correlation. The code URL is https://github.com/yuanyuan1024/Chaskey_code.


### 4.3. Partioning Technique for Permutation of Chaskey

Ref. [8] improves the results of differential-linear attack on permutation of Chaskey by using the partitioning technique. Inspired by this, we do a similar research on the rotational differential-linear distinguisher. We want to recover the last whitening key of Chaksey. Since the process of key recovery needs some time, a 9-round distinguisher can no longer be used. Therefore, we set 6.5 rounds for the rotational part, 0.5 rounds for linear part, and 1 round for key recovery. For linear part E2, we consider one trail for mask Γm=,20,,, that is,(26)ψ1=v2611,10,4⊕w1631,0⊕w0616,15,ψ0=v2611,4,3⊕w160⊕w0616,and the other trail for mask rotΓm=,21,,, that is,(27)rotψ1=v2612,11,5⊕w161,0⊕w0617,16,rotψ0=v2612,5,4⊕w161⊕w0617,Partition point and rotational partition point are shown in Figures7 and 8, respectively. Then we begin to compute the correlation. Note that Γoutpi⋅z can be computed by either ψ1 or ψ0 and rot Γoutpj⋅z˜ can be computed by either rotψ1 or rotψ0; the attacker uses one of the highest correlation partition. For example, we assume that ψ1 has a higher correlation than ψ0 and rot ψ1 has a higher correlation than rot ψ0.Figure 7
Partition points.Figure 8
Rotational partition points.The total correlation can be computed in two steps. The first step is computing the correlation ofΓoutpi⋅z=rot−1rotΓoutpj⋅z˜. We experimentally evaluated the correlations of any combination, that is:(28)ψ0,rotψ0,ψ1,rotψ1,ψ1,rotψ0,ψ0,rotψ1,which is the correlation of 2×2 rotational differential-linear distinguishers. We use 230 random data to calculate the empirical correlations. Subsequently, the correlation is 2−6.42. Then, we focus on some partition bits. Partition Γpi is defined as the following 11 bits:(29)sR15,sR14,v318⊕v29,17,sL10,sL9,sL18,sL17,v311⊕v22,10,sL3,sL2,sL11,and partition rotΓpj is defined as the following 11 bits:(30)sR16,sR15,v319⊕v210,18,sL11,sL10,sL19,sL18,v312⊕v23,11,sL4,sL3,sL12,where sL=v¯1⊕v2 and sR=v¯3⊕v0. It is difficult to evaluate the actual correlations of all qij,i,j∈1,…,211 experimentally with a high significance. Therefore, we simply assume that these correlations are the same for each partition, which is qij=2−6.42 for all i and j. The second step is computing the correlation of each partition. We enumerate all possible values of 11 bits for each partition according to Table 5  in the appendix and the results are shown in Table 6.Table 5
Partition for two consecutive modular additions.
pz1iz1i,i−1MaskγCorrelationϵMaskγCorrelationϵ00000—01111101110100001111111110−2−111111011102−100010111111101−1—2−100011111111101−2−1111101101−2−1001001111111102−0.2631111011102−0.26300101—01111011102−0.263001101111111101−2−0.2631111011012−0.263001111111111101−2−0.263—0010001110011101—0010011110011102−11110111102−101010—01110111012−101011111001101−2−11110111012−1011001110011102−0.263111011110−2−0.263011011110011102−0.263—0011101110011012−0.2631110111012−0.26301111—01110111012−0.26310000111111110−1—010001111111110−2−11111011102−110010—01111011011100111111111012−11111011012−110100111111102−0.2631111011102−0.26310101—01111011102−0.2631011011111111012−0.2631111011012−0.2631011111111111012−0.263—011000—01110111101110011110011102−11110111102−1110101110011011—0110111110011012−1111011101−2−1111001110011102−0.2631110111102−0.263111011110011102−0.263—0111101110011012−0.263111011101−2−0.26311111—0111011101−2−0.263Table 6
The distribution of all211 linear characteristics and its correlations.
CorrelationsNumber of linear characteristics204820.26328820.5263682119221.263448221280576In this table, we can see that 1472 partitions have high correlation and Table5 average of the absolute value of those correlations is 2−0.779. Therefore, in this part, we can get the total correlation h=2−6.42−0.779×2=2−7.98. The process of key recovery is the same as Ref. [6]; we will introduce it briefly. First, we choose rotational pair x,x⋘1 and encrypt them to get c,c˜. For every cipher pair we get, we guess all possible values of kP′∈P and identify Γi×Γj for c⊕kP′,c˜⊕rotkP′ and get corresponding γpi and rotγpj, and meanwhile set αijkP′=αijkP′+−1γpi⋅c⊕rot−1rotγpj⋅c˜. Second, for kp′∈P, we compute CkP′,kL by using Fast Walsh–Hadamard Transform. The symbol Θ is used to denote the threshold that we set. If CkP′,kL>Θ, we save kP′,kL as a key candidate.The successful probability of key recovery can be computed by following proposition.Proposition 1 (see [8]).
After running the algorithm of key recoveryp−2 times, the probability that the correct key is among the key candidates is(31)psuccess≥12PrCkP,kL≥Θ=121−ΦΘ−N∗hN∗.where h is the correlation that we compute in linear part and N∗ is available pairs, and Φ is the cumulative distribution function of the standard normal distribution.


#### 4.3.1. Data and Time Complexities and Success Probability

In order to get the right pair, we repeat the process of key recoveryp−2=290.544 times. For each iteration, we use N=222 pairs and available pairs N∗=N×1472/211=221.047. By using the threshold Θ=N∗×Φ−11−p2/2n, we can get a success probability of 0.972 under the condition that the right pair is successfully obtained during 290.544 iterations. On this success probability, the data complexity is 21+22+90.544=2113.544 and the time complexity is 290.544×211×2×222+10×210=2124.944.


## 4.1. Description of Chaskey

Chaskey, proposed by Nicky Mouha et al., is a very efficient Message Authentication Code (MAC) algorithm for 32-bit microcontrollers. Chaskey takes a 128-bit keyk and processes a message m in 128-bit blocks using a 128-bit permutation π. Designers claimed that Chaskey performs well both in software and hardware, and it is an Even-Mansour construction. A message m is processed by n-bit key K into a tag τ. The message m is split into l blocks m1,m2,…,ml of 128-bit each, except for the last block ml which may be incomplete. If the last block ml is not complete, a periodical binary string 10∗ is pushed back until the size of ml is 128-bit. This permutation π is based on the Addition–Rotation–XOR (ARX) design methodology. In practical analysis, we care about the permutation which is shown in Figure 5. When we want to tag a message m with one block of 128 bits, the tag would be τ=πK⊕K1⊕m⊕K1. K1 is generated by K, i.e., K1=xKmodgx, where gx=x128+x7+x2+x+1, as shown in Figure 6.Figure 5
Permutation of Chaskey.Figure 6
Mode of operation for message with single 128 bits block of Chaksey.


## 4.2. Rotational Differential-Linear Distinguishing Attack on Chaskey

In this section, we recall the weak-key class which was introduced in Ref. [7] at first. Then a 9-round rotational differential-linear distinguisher is represented. Finally, an 8-round key recovery attack of Chaskey with partitioning techinique is explained in detail.


### 4.2.1. Weak Key Class of Rotational Attack

Because of the consecutive modular additions in Chaskey, we need to explore the properties in consecutive modular additions to get more accurate formulas. This work has been done in Ref. [7]. Note that in order to preserve the rotational property, we have to consider the pair πK⊕K1⊕m⊕K1 and πrotK⊕K1′⊕rotm⊕K1′, where K1′ is a key generated from rotK, that is, K1′=xrotKmodgx. To ensure K1′ is the word rotation of K1, the first 2 bits of every word is assumed to be zero. The key K must be in the following form with the aim of attacking successfully.(25)K=00∗00∗00∗00∗,K1=0∗00∗00∗00∗0,rotK=00∗00∗00∗00∗,K1′=∗00∗00∗00∗00,where ∗ is 30 bits that we do not care. The set of keys that satisfy such a condition is called the weak key class. It is clear that the size of the weak key class is 2120. The result that we use to calculate the probability precisely is described in Table 4. Note that there are 2 single modular additions in the every round of permutation.Table 4
Table with the expected rotational probabilities for any number of rounds of Chaskey.
RoundsNumber of chains modular additionsExpected probability11−6.43623−13.63635−20.83647−28.03659−35.236611−42.436713−49.636815−56.836917−64.0361019−71.2361121−78.4361223−86.636A 9-round distinguisher is divided into two parts. The first part is covered by rotational attack and the second part is covered by linear attack. We discuss them separately and the detail of attack is represented as follows.


### 4.2.2. Rotational Differential Part

Here we set 7 rounds for rotational part and the expected probability of this part is2−49.636, which can be seen in Table 4. Mentioned in Section 2, the probability of rotational attack only depends on the number of (consecutive) modular additions. Since our work on key recovery is interested in rotational attack of 6.5 rounds Chaskey, it is easy to calculate the number of (consecutive) modular additions and the probability is 2−45.272.


### 4.2.3. Linear Part

Sinceϵγ,Γ is close to ϵrot−1γ,rot−1Γ, we cannot use two high-correlation linear characteristics without specific relations directly. Sometimes ϵγ,Γ is the best linear characteristic, but ϵrot−1γ,rot−1Γ has very low correlation. In order to get ϵγ,Γϵrot−1γ,rot−1Γ as high as possible, we should search two linear characteristics simultaneously. This problem can be transformed to a SAT problem [19, 20] and a SAT solver can be used to search. Because more binary variables are needed to add constraints, we may search less round than a single linear characteristic. Therefore, we set 2 rounds for linear part and the correlation of linear part is 2−7. The total correlation is 2−49.636×2−7×2=2−55.636 and the complexity is 2−55.636−2=2111.272.


### 4.2.4. Experimental Verification

In order to verify the correctness of formula in Section2.4, we use 220 random data to check the correlation of 3-round Chaskey with 1 round for rotational part and 2 rounds for linear part. The expected correlation of 3-round Chaskey is 2−6.436×2−7×2=2−12.436. The experimental result shows the correlation is 2−11.729. We also provide 3 code files, the first one is a python script to generate a smt2 file, which can be solved by the SAT solver. The second one is smt2 file mentioned above. The third one is a c++ file which is used to verify the correlation. The code URL is https://github.com/yuanyuan1024/Chaskey_code.


## 4.2.1. Weak Key Class of Rotational Attack

Because of the consecutive modular additions in Chaskey, we need to explore the properties in consecutive modular additions to get more accurate formulas. This work has been done in Ref. [7]. Note that in order to preserve the rotational property, we have to consider the pair πK⊕K1⊕m⊕K1 and πrotK⊕K1′⊕rotm⊕K1′, where K1′ is a key generated from rotK, that is, K1′=xrotKmodgx. To ensure K1′ is the word rotation of K1, the first 2 bits of every word is assumed to be zero. The key K must be in the following form with the aim of attacking successfully.(25)K=00∗00∗00∗00∗,K1=0∗00∗00∗00∗0,rotK=00∗00∗00∗00∗,K1′=∗00∗00∗00∗00,where ∗ is 30 bits that we do not care. The set of keys that satisfy such a condition is called the weak key class. It is clear that the size of the weak key class is 2120. The result that we use to calculate the probability precisely is described in Table 4. Note that there are 2 single modular additions in the every round of permutation.Table 4
Table with the expected rotational probabilities for any number of rounds of Chaskey.
RoundsNumber of chains modular additionsExpected probability11−6.43623−13.63635−20.83647−28.03659−35.236611−42.436713−49.636815−56.836917−64.0361019−71.2361121−78.4361223−86.636A 9-round distinguisher is divided into two parts. The first part is covered by rotational attack and the second part is covered by linear attack. We discuss them separately and the detail of attack is represented as follows.


## 4.2.2. Rotational Differential Part

Here we set 7 rounds for rotational part and the expected probability of this part is2−49.636, which can be seen in Table 4. Mentioned in Section 2, the probability of rotational attack only depends on the number of (consecutive) modular additions. Since our work on key recovery is interested in rotational attack of 6.5 rounds Chaskey, it is easy to calculate the number of (consecutive) modular additions and the probability is 2−45.272.


## 4.2.3. Linear Part

Sinceϵγ,Γ is close to ϵrot−1γ,rot−1Γ, we cannot use two high-correlation linear characteristics without specific relations directly. Sometimes ϵγ,Γ is the best linear characteristic, but ϵrot−1γ,rot−1Γ has very low correlation. In order to get ϵγ,Γϵrot−1γ,rot−1Γ as high as possible, we should search two linear characteristics simultaneously. This problem can be transformed to a SAT problem [19, 20] and a SAT solver can be used to search. Because more binary variables are needed to add constraints, we may search less round than a single linear characteristic. Therefore, we set 2 rounds for linear part and the correlation of linear part is 2−7. The total correlation is 2−49.636×2−7×2=2−55.636 and the complexity is 2−55.636−2=2111.272.


## 4.2.4. Experimental Verification

In order to verify the correctness of formula in Section2.4, we use 220 random data to check the correlation of 3-round Chaskey with 1 round for rotational part and 2 rounds for linear part. The expected correlation of 3-round Chaskey is 2−6.436×2−7×2=2−12.436. The experimental result shows the correlation is 2−11.729. We also provide 3 code files, the first one is a python script to generate a smt2 file, which can be solved by the SAT solver. The second one is smt2 file mentioned above. The third one is a c++ file which is used to verify the correlation. The code URL is https://github.com/yuanyuan1024/Chaskey_code.


## 4.3. Partioning Technique for Permutation of Chaskey

Ref. [8] improves the results of differential-linear attack on permutation of Chaskey by using the partitioning technique. Inspired by this, we do a similar research on the rotational differential-linear distinguisher. We want to recover the last whitening key of Chaksey. Since the process of key recovery needs some time, a 9-round distinguisher can no longer be used. Therefore, we set 6.5 rounds for the rotational part, 0.5 rounds for linear part, and 1 round for key recovery. For linear part E2, we consider one trail for mask Γm=,20,,, that is,(26)ψ1=v2611,10,4⊕w1631,0⊕w0616,15,ψ0=v2611,4,3⊕w160⊕w0616,and the other trail for mask rotΓm=,21,,, that is,(27)rotψ1=v2612,11,5⊕w161,0⊕w0617,16,rotψ0=v2612,5,4⊕w161⊕w0617,Partition point and rotational partition point are shown in Figures7 and 8, respectively. Then we begin to compute the correlation. Note that Γoutpi⋅z can be computed by either ψ1 or ψ0 and rot Γoutpj⋅z˜ can be computed by either rotψ1 or rotψ0; the attacker uses one of the highest correlation partition. For example, we assume that ψ1 has a higher correlation than ψ0 and rot ψ1 has a higher correlation than rot ψ0.Figure 7
Partition points.Figure 8
Rotational partition points.The total correlation can be computed in two steps. The first step is computing the correlation ofΓoutpi⋅z=rot−1rotΓoutpj⋅z˜. We experimentally evaluated the correlations of any combination, that is:(28)ψ0,rotψ0,ψ1,rotψ1,ψ1,rotψ0,ψ0,rotψ1,which is the correlation of 2×2 rotational differential-linear distinguishers. We use 230 random data to calculate the empirical correlations. Subsequently, the correlation is 2−6.42. Then, we focus on some partition bits. Partition Γpi is defined as the following 11 bits:(29)sR15,sR14,v318⊕v29,17,sL10,sL9,sL18,sL17,v311⊕v22,10,sL3,sL2,sL11,and partition rotΓpj is defined as the following 11 bits:(30)sR16,sR15,v319⊕v210,18,sL11,sL10,sL19,sL18,v312⊕v23,11,sL4,sL3,sL12,where sL=v¯1⊕v2 and sR=v¯3⊕v0. It is difficult to evaluate the actual correlations of all qij,i,j∈1,…,211 experimentally with a high significance. Therefore, we simply assume that these correlations are the same for each partition, which is qij=2−6.42 for all i and j. The second step is computing the correlation of each partition. We enumerate all possible values of 11 bits for each partition according to Table 5  in the appendix and the results are shown in Table 6.Table 5
Partition for two consecutive modular additions.
pz1iz1i,i−1MaskγCorrelationϵMaskγCorrelationϵ00000—01111101110100001111111110−2−111111011102−100010111111101−1—2−100011111111101−2−1111101101−2−1001001111111102−0.2631111011102−0.26300101—01111011102−0.263001101111111101−2−0.2631111011012−0.263001111111111101−2−0.263—0010001110011101—0010011110011102−11110111102−101010—01110111012−101011111001101−2−11110111012−1011001110011102−0.263111011110−2−0.263011011110011102−0.263—0011101110011012−0.2631110111012−0.26301111—01110111012−0.26310000111111110−1—010001111111110−2−11111011102−110010—01111011011100111111111012−11111011012−110100111111102−0.2631111011102−0.26310101—01111011102−0.2631011011111111012−0.2631111011012−0.2631011111111111012−0.263—011000—01110111101110011110011102−11110111102−1110101110011011—0110111110011012−1111011101−2−1111001110011102−0.2631110111102−0.263111011110011102−0.263—0111101110011012−0.263111011101−2−0.26311111—0111011101−2−0.263Table 6
The distribution of all211 linear characteristics and its correlations.
CorrelationsNumber of linear characteristics204820.26328820.5263682119221.263448221280576In this table, we can see that 1472 partitions have high correlation and Table5 average of the absolute value of those correlations is 2−0.779. Therefore, in this part, we can get the total correlation h=2−6.42−0.779×2=2−7.98. The process of key recovery is the same as Ref. [6]; we will introduce it briefly. First, we choose rotational pair x,x⋘1 and encrypt them to get c,c˜. For every cipher pair we get, we guess all possible values of kP′∈P and identify Γi×Γj for c⊕kP′,c˜⊕rotkP′ and get corresponding γpi and rotγpj, and meanwhile set αijkP′=αijkP′+−1γpi⋅c⊕rot−1rotγpj⋅c˜. Second, for kp′∈P, we compute CkP′,kL by using Fast Walsh–Hadamard Transform. The symbol Θ is used to denote the threshold that we set. If CkP′,kL>Θ, we save kP′,kL as a key candidate.The successful probability of key recovery can be computed by following proposition.Proposition 1 (see [8]).
After running the algorithm of key recoveryp−2 times, the probability that the correct key is among the key candidates is(31)psuccess≥12PrCkP,kL≥Θ=121−ΦΘ−N∗hN∗.where h is the correlation that we compute in linear part and N∗ is available pairs, and Φ is the cumulative distribution function of the standard normal distribution.


### 4.3.1. Data and Time Complexities and Success Probability

In order to get the right pair, we repeat the process of key recoveryp−2=290.544 times. For each iteration, we use N=222 pairs and available pairs N∗=N×1472/211=221.047. By using the threshold Θ=N∗×Φ−11−p2/2n, we can get a success probability of 0.972 under the condition that the right pair is successfully obtained during 290.544 iterations. On this success probability, the data complexity is 21+22+90.544=2113.544 and the time complexity is 290.544×211×2×222+10×210=2124.944.


## 4.3.1. Data and Time Complexities and Success Probability

In order to get the right pair, we repeat the process of key recoveryp−2=290.544 times. For each iteration, we use N=222 pairs and available pairs N∗=N×1472/211=221.047. By using the threshold Θ=N∗×Φ−11−p2/2n, we can get a success probability of 0.972 under the condition that the right pair is successfully obtained during 290.544 iterations. On this success probability, the data complexity is 21+22+90.544=2113.544 and the time complexity is 290.544×211×2×222+10×210=2124.944.


## 5. Conclusion

In this paper, we study the rotational differential-linear distinguisher of Chaskey’s permutation and partitioning technique for the linear part [21]. For the linear part, we use an automatic tool to search for the linear characteristic to get the highest correlation. As a consequence, we give a distinguishing attack over 9 rounds of Chaskey with complexity 2111.272, and a key recovery attack over 8 rounds of Chaskey with complexity 2124.944.



---

*Source: 4186874-2022-08-25.xml*