# Automatic Search for the Linear (Hull) Characteristics of ARX Ciphers: Applied to SPECK, SPARX, Chaskey, and CHAM-64

Authors: Mingjiang Huang; Liming Wang
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Linear cryptanalysis is an important evaluation method for cryptographic primitives against key recovery attack. In this paper, we revisit the Walsh transformation for linear correlation calculation of modular addition, and an efficient algorithm is proposed to construct the input-output mask space of specified correlation weight. By filtering out the impossible large correlation weights in the first round, the search space of the first round can be substantially reduced. We introduce a concept of combinational linear approximation table (cLAT) for modular addition with two inputs. When one input mask is fixed, another input mask and the output mask can be obtained by theSplitting-Lookup-Recombination approach. We first split the n-bit fixed input mask into several subvectors and then find the corresponding bits of other masks, and in the recombination phase, pruning conditions can be used. By this approach, a large number of search branches in the middle rounds can be pruned. With the combination of the optimization strategies and the branch-and-bound search algorithm, we can improve the search efficiency for linear characteristics on ARX ciphers. The linear hulls for SPECK32/48/64 with a higher average linear potential (ALP) than existing results have been obtained. For SPARX variants, an 11-round linear trail and a 10-round linear hull have been found for SPARX-64 and a 10-round linear trail and a 9-round linear hull are obtained for SPARX-128. For Chaskey, a 5-round linear trail with a correlation of 2−61 has been obtained. For CHAM-64, 34/35-round optimal linear characteristics with a correlation of 2−31/2−33 are found.


---

## Body

## 1. Introduction

The three components: modular addition, rotation, and XOR, constitute the basic operations in ARX cryptographic primitives [1]. In ARX ciphers, modular additions provide nonlinearity diffusion with efficient software implementation and low dependencies on computing resources. Compared with S-box-based ciphers, ARX ciphers do not need to store S-box in advance, which can reduce the occupation of storage resources, especially in resource-constrained devices. In addition, ARX ciphers do not need to query S-boxes in the encryption and decryption process, which can reduce a lot of query operations. Therefore, ARX construction is preferred by many designers of lightweight ciphers. At present, there are many primitives used in this construction, such as HIGHT [2], SPECK [3], LEA [4], Chaskey [5], SPARX [6], and CHAM [7].Until now, cryptanalysis on ARX ciphers is still not well understood as S-box-based ciphers, and the security analysis on them are relatively lagging behind [8]. Linear cryptanalysis is very important for evaluating the security margin of symmetric cryptographic primitives [9, 10]. The linear approximation tables of S-box-based ciphers mostly can be constructed and stored directly; however, the full linear approximation table of modular addition will be too large to store when the word length of modular addition is large.For linear cryptanalysis of ARX ciphers, one crucial step is to calculate the linear correlation of modular addition. In [11–14], the linear properties of modular addition have been carefully studied. In [13], a method to calculate the linear correlation of modular addition recursively was proposed, but the calculation process that was based on state transition in bit level leads to high complexity. Based on this method, only the optimal linear characteristics for the variants of SPECK32 [15] and SPECK32/48 [16] were found.In 2013, Schulte-Geers used CCZ equivalence to improve the explicit formula for the calculation of linear correlation of modular addition [17]. Based on the improved formula and SAT solver model, Liu et al. obtained better linear characteristics for SPECK [18], the optimal linear trails for SPECK32/48/64 with correlation close to the security boundary (2−n/2) were obtained, and the 9/10-round linear hull with a potential of 2−29.1/2−32.1 for SPECK32 was obtained.According to the position of the starting round of the search algorithm, there are currently 3 types of automatic search technologies for linear/differential cryptanalysis on ARX primitives. They are bottom-up techniques [15], top-down techniques [19–21], and the method of extending from the middle to the ends [22]. In these methods, the linear correlations are directly calculated based on the input-output masks or by looking up the precomputed partial linear approximation table (pLAT) [23]. For addition modulo 2n with two inputs, the correlations need to be calculated based on the known input-output masks. However, in the search process for linear characteristics of ARX ciphers, due to the existence of three-forked branches, in most case, for the input-output masks v,w⟶u of modular addition, only one input mask v is determined, and another input mask w and the output mask u are unknown. Although all 22n space of w,u can be traversed in a trivial way, it is very time-consuming.High efficiency query operations can be achieved by constructing a linear approximation table of reasonable storage size. The pLAT can store the input-output masks whose linear correlation is greater than a certain threshold [15]. When the branches cannot be queried in pLAT and that need to be calculated by the input-output masks, the calculation process will lead to a significant reduction in search efficiency. Although the heuristic method can speed up the search, it cannot guarantee the results will be the best [24].Therefore, constructing a search model based on the precise correlation calculation formula and realizing an efficient search for linear characteristics on ARX ciphers are still a study worth working on. The motivation of this paper is to investigate how to speed up the search algorithm in order to realize the search for linear (hull) characteristics on typical ARX ciphers.


### 1.1. Our Contributions

In this paper, we first revisit the linear correlation calculation of modular addition and introduce an algorithm to construct the input-output masks of specific correlation weight. Then, we propose a novel concept of combinational linear approximation table (cLAT) and introduce an algorithm to generate the lookup tables. Combining with these two optimization algorithms, we propose an automatic algorithm to search for the optimal linear characteristics on ARX ciphers. In the first round, we can exclude the search space of the nonoptimal linear trails by increasing the correlation weight of each modular addition monotonically. In the middle rounds, the undetermined masks and the corresponding correlation weight of each modular addition can be obtained by querying the cLAT, and a large number of nonoptimal branches can be filtered out during the recombination phase. Also, the algorithm can be appropriately modified for the heuristic search.As applications, for SPECK32/48/64, the 9/11/14-round linear hulls are obtained. For SPARX-64, the 11-round linear trail with a correlation of2−28 and a 10-round linear hull with an ALP of 2−40.92 are found. For SPARX-128, we can experimentally get the optimal linear trails of the first eight rounds, and we get a 10-round linear trail with a correlation of 2−23. For Chaskey, the linear characteristics covering more rounds are updated, and a 5-round linear trail with a correlation of 2−61 is found. For CHAM-64, we find a new 34-round optimal linear trail with a correlation of 2−31. A summary table is shown in Table 1.Table 1
Summary of the linear characteristics on SPECK, SPARX, Chaskey, and CHAM-64, where “s,” “m,” “h,” and “d” represent seconds, minutes, hours, and days, respectively.
Variants
Round
Cor
T
Cor
ALP
T
ALP
Reference
SPECK32
9
2
−
14
N/A
2
−
29.1
N/A
[18]
9
2
−
14
N/A
2
−
28
N/A
[16]
9
2
−
14
9 s
2
−
27.78
25 s
This paper
SPECK48
10
2
−
22
N/A
2
−
44
N/A
[18]
10
2
−
22
N/A
2
−
44
N/A
[16]
10
2
−
22
3.2 h
2
−
43.64
157.3 h
This paper
SPECK64
13
2
−
30
N/A
2
−
60
N/A
[18]
13
2
−
30
N/A
2
−
60
N/A
[16]
13
2
−
30
8.6 h
2
−
55.29
7.3 h
This paper
14
2
−
33
25.6 h
2
−
61.24
5.8 h
This paper
SPARX-64
10
2
−
22
3 d
2
−
40.92
1 h
This paper
11
2
−
28
5 m
2
−
56
—
This paper
SPARX-128
9
2
−
18
27 m
2
−
35.22
6 h
This paper
10
2
−
23
4.4 d
2
−
46
—
This paper
Chaskey
3
2
−
9
N/A
2
−
18
N/A
[18]
4
2
−
29
15.7 m
2
−
58
—
This paper
5
2
−
61
6.6 h
2
−
122
—
This paper
CHAM-64
34
2
−
31
N/A
2
−
62
N/A
[7]
34
2
−
31
1.1 d
2
−
62
—
This paper
35
2
−
33
4.8 d
—
—
This paper


### 1.2. Roadmap

This paper is organized as follows. We first present some preliminaries used in this paper in Section2. In Section 3, we introduce the algorithm for constructing the space of input-output mask tuples, the algorithm for constructing cLAT, and the improved automatic search algorithm for linear cryptanalysis on ARX ciphers. In Section 4, we apply the new tool to several typical ARX ciphers. Finally, we conclude our work in Section 5.


## 1.1. Our Contributions

In this paper, we first revisit the linear correlation calculation of modular addition and introduce an algorithm to construct the input-output masks of specific correlation weight. Then, we propose a novel concept of combinational linear approximation table (cLAT) and introduce an algorithm to generate the lookup tables. Combining with these two optimization algorithms, we propose an automatic algorithm to search for the optimal linear characteristics on ARX ciphers. In the first round, we can exclude the search space of the nonoptimal linear trails by increasing the correlation weight of each modular addition monotonically. In the middle rounds, the undetermined masks and the corresponding correlation weight of each modular addition can be obtained by querying the cLAT, and a large number of nonoptimal branches can be filtered out during the recombination phase. Also, the algorithm can be appropriately modified for the heuristic search.As applications, for SPECK32/48/64, the 9/11/14-round linear hulls are obtained. For SPARX-64, the 11-round linear trail with a correlation of2−28 and a 10-round linear hull with an ALP of 2−40.92 are found. For SPARX-128, we can experimentally get the optimal linear trails of the first eight rounds, and we get a 10-round linear trail with a correlation of 2−23. For Chaskey, the linear characteristics covering more rounds are updated, and a 5-round linear trail with a correlation of 2−61 is found. For CHAM-64, we find a new 34-round optimal linear trail with a correlation of 2−31. A summary table is shown in Table 1.Table 1
Summary of the linear characteristics on SPECK, SPARX, Chaskey, and CHAM-64, where “s,” “m,” “h,” and “d” represent seconds, minutes, hours, and days, respectively.
Variants
Round
Cor
T
Cor
ALP
T
ALP
Reference
SPECK32
9
2
−
14
N/A
2
−
29.1
N/A
[18]
9
2
−
14
N/A
2
−
28
N/A
[16]
9
2
−
14
9 s
2
−
27.78
25 s
This paper
SPECK48
10
2
−
22
N/A
2
−
44
N/A
[18]
10
2
−
22
N/A
2
−
44
N/A
[16]
10
2
−
22
3.2 h
2
−
43.64
157.3 h
This paper
SPECK64
13
2
−
30
N/A
2
−
60
N/A
[18]
13
2
−
30
N/A
2
−
60
N/A
[16]
13
2
−
30
8.6 h
2
−
55.29
7.3 h
This paper
14
2
−
33
25.6 h
2
−
61.24
5.8 h
This paper
SPARX-64
10
2
−
22
3 d
2
−
40.92
1 h
This paper
11
2
−
28
5 m
2
−
56
—
This paper
SPARX-128
9
2
−
18
27 m
2
−
35.22
6 h
This paper
10
2
−
23
4.4 d
2
−
46
—
This paper
Chaskey
3
2
−
9
N/A
2
−
18
N/A
[18]
4
2
−
29
15.7 m
2
−
58
—
This paper
5
2
−
61
6.6 h
2
−
122
—
This paper
CHAM-64
34
2
−
31
N/A
2
−
62
N/A
[7]
34
2
−
31
1.1 d
2
−
62
—
This paper
35
2
−
33
4.8 d
—
—
This paper


## 1.2. Roadmap

This paper is organized as follows. We first present some preliminaries used in this paper in Section2. In Section 3, we introduce the algorithm for constructing the space of input-output mask tuples, the algorithm for constructing cLAT, and the improved automatic search algorithm for linear cryptanalysis on ARX ciphers. In Section 4, we apply the new tool to several typical ARX ciphers. Finally, we conclude our work in Section 5.


## 2. Preliminaries

### 2.1. Notation

For addition modulo2n, i.e., x⊞y=z, we use the symbols ⋘ and ⋙ to indicate rotation to the left and right and ≪ and ≫ to indicate the left and right shift operation, respectively. The binary operator symbols ⊕, ∨, ∧, , and ¬ represent XOR, OR, AND, concatenation, and bitwise NOT, respectively. For a vector x, wtx represents its Hamming weight and xi is the ith bit of it. 0 is a zero vector.


### 2.2. Linear Correlation Calculation for Modular Addition

LetF2n be the n dimensional vector space over binary field F2=0,1; for Boolean function f:F2n⟶F2 and h:F2n⟶F2, x∈F2n, the linear correlation between f and h can be denoted by(1)Corf,h=2×#x∣fx⊕hx=02n−1.For modular additionx⊞y=z, let (v,w) be the input masks, u be the output mask, and ⋅ be the standard inner product. According to the definition of linear correlation, when v⋅x⊞w⋅y⊕u⋅z=0, the linear approximation probability is defined as(2)Pru,v,w=2−3n×#x,y,zv⋅x⊞w⋅y⊕u⋅z=0.Letμt=−1t, then the linear correlation of modular addition can be denoted by Walsh transformation, and thus,(3)Coru,v,w=2−3n×∑x,y,z∈F2nμv⋅x⊞w⋅y⊕u⋅z.LetPru,v,w=1/2+ε, where ε is the bias. When v⋅x⊞w⋅y⊕u⋅z=1, the linear approximation probability is Pr¯u,v,w=1/2−ε. The linear correlation can be denoted by(4)Coru,v,w=Pru,v,w−Pr¯u,v,w=2Pru,v,w−1.We callCwu,v,w=−log2Coru,v,w as the correlation weight, and the linear square correlation can be denoted by(5)LSCu,v,w=Coru,v,w2=2−2×Cwu,v,w.For additionx⊞y modulo 2n, it can be rewritten as x⊞y=x⊕y⊕carryx,y, in which carryx,yi+1=carryx,yi⊕xi⊕yi and carryx,y0=0 for 0≤i≤n−1. The first-order approximation is carryx,y=x∧y≪1. If all carryx,yj=0 for j≤i, and 0≤i≤n−1, the high-order approximation is(6)carryx,yi+1=12−1xi+−1yi+carryx,yi−−1xi+yicarryx,yi.In [13], Wallén introduced the theorem to calculate the linear correlation by analyzing the carry high-order approximation function recursively. In [12], based on the bit state transformation, the formula to calculate the correlation was given by the following theorem.Theorem 1 (See [12]).
For addition modulo2n, let vandw be the input masks and u be the output mask. Define an auxiliary vector d=dn−1⋯d0, and each di=uiviwi∈F23 is an octal word, 0≤i≤n−1. Then, the linear correlation can be denoted by(7)Coru,v,w=LAdn−1Adn−2⋯Ad1Ad0C,where the row vector L=10, the column vector C=11T, and each 2×2 matrix Adi is defined by(8)A0=122001,A1=A2=−A4=120010,A7=120210,−A3=A5=A6=120001.
In [17], Schulte-Geers extended Theorem 1 and derived a fully explicit formula for the linear correlation calculation, given by Theorem 2.Theorem 2 (See [17]).
For addition modulo2n with input-output mask tuple u,v,w, a vectorial Boolean function M:F2n⟶F2n denotes the partial sum mapping:(9)x=x0,x1,⋯,xn−1⟶Mx=0,x0,x0⊕x1,⋯,x0⊕x1⊕⋯xn−2.
Letz≔MTu⊕v⊕w=0,xn−1,xn−1⊕xn−2,⋯,xn−1⊕xn−2⊕⋯x1, then the linear correlation can be denoted by(10)Coru,v,w=1u⊕v⪯z1u⊕w⪯z−1v⋅w2−wtz,where 1Gf is an indicator function for graph Gf≔x,fxx∈F2n; for n-bit vectors a and b, a⪯b represents ai≤bi for 0≤i≤n−1.
In iterative ciphers, the correlation of a singler-round linear trail is the product of the correlations of each round [25]. Assuming that there are NA additions modulo 2n with two inputs in ith round, Γin and Γout are the input and output masks of the r-round linear trail, and the correlation of it can be denoted by(11)CorΓin,Γout=∏i=1r∏j=1NACorui,j,vi,j,wi,j.
The linear approximation of a linear hull represents the potential of all linear trails with same input-output masks [26]. The averaged linear potential (ALP) can be counted by the following formula:(12)ALPΓin,Γout=1K∑k∈KCorΓin,Γout2.
Assuming that the keyk is selected uniformly from the key space K, the statistics of ALP can be formulated as (13), where TCw is the number of trails with correlation weight of Cw. Let Cmin be the correlation weight of the linear trail whose input-output masks are chosen as the fixed input-output masks of the linear hull. Cmax is the upper bound to be searched, which should be chosen by the trade-off between the search time and the accuracy of ALP:(13)ALPΓin,Γout=∑Cw=CminCmax2−2Cw×TCw.


### 2.3. Linear Properties of SPECK, SPARX, Chaskey, and CHAM

The SPECK family ciphers were designed by NSA in 2013 [3]. The SPARX family ciphers were introduced by Dinu et al. at ASIACRYPT′16 [6]. In SPARX, the nonlinear ARX-box (SPECKEY) is obtained by modifying the round function of SPECK32. The linear mask propagation properties of the round function in SPECK and SPECKEY are shown in Figure 1. The rotation parameters ra,rb=7,2 for SPECK32, while ra,rb=8,3 for other variants.Figure 1
Linear mask propagation properties of SPECK and SPECKEY.If the input-output masks (ui,vi,wi) and (ui+1,vi+1,wi+1) of the modular additions in the two consecutive rounds of SPECK are known, the input and output masks of these two rounds can be denoted by Property 1.Property 1.
If (ui,vi,wi) and (ui+1,vi+1,wi+1) are given, then ΓXi=vi⋘ra, ΓXi+1=vi+1⋘ra, ΓYi+1=vi+1⋘ra⊕ui, ΓYi=ΓYi+1⋙rb⊕wi, ΓYi+2=ΓYi+1⊕wi+1⋘rb, and ΓXi+2=ΓYi+1⊕ui+1.
The linear layer functionsL/ℒ′ [6] for SPARX-64 and SPARX-128 are shown in Figure 2. Due to the existence of the three-forked branches, the masks of the linear transformation layer have the following properties.Figure 2
(a) and (b) represent the linear layer of SPARX-64. (c) and (d) represent the linear layer of SPARX-128.
(a)
(b)
(c)
(d)Property 2.
For SPARX-64, if the masks are transformed by the linear layer functionℒ, let c=ΓX2⊕ΓX3, d=c⋙8, then ΓX0′=ΓX2, ΓX1′=ΓX3, ΓX2′=ΓX0⊕d⊕ΓX2, and ΓX3′=ΓX1⊕d⊕ΓX3.Property 3.
For SPARX-128, if the masks are transformed by the linear layer functionℒ′, let e=ΓX4⊕ΓX5⊕ΓX6⊕ΓX7, f=e⋙8, then ΓX0′=ΓX4, ΓX1′=ΓX5, ΓX2′=ΓX6, ΓX3′=ΓX7, ΓX4′=ΓX0⊕f⊕ΓX6, ΓX5′=ΓX1⊕f⊕ΓX5, ΓX6′=ΓX2⊕f⊕ΓX4, and ΓX7′=ΓX3⊕f⊕ΓX7.
Chaskey is a MAC algorithm introduced by Mouha et al. at SAC′14 [5], and an enhanced variant was proposed in 2015 [27], which increases the number of permutation rounds from 8 to 12. The round function of the permutation v0′,v1′,v2′,v3′=πv0,v1,v2,v3 is shown in Figure 3. The 4 modular additions are labeled by A0,A1,A2,andA3, respectively. The input mask a,b,c,d and the output mask a′,b′,c′,d′ of the first round can be denoted by Property 4.Figure 3
Linear masks in the first round of Chaskey.Property 4.
For the permutation of Chaskey, if the input-output masks of each modular addition in the first round are (ui,vi,wi), 0≤i≤3, the corresponding correlation weight of each modular addition is c0,c1,c2,c3, respectively. Hence, in the first round, a=v0, b=w0⊕u0⊕v3⋙16⋙5, c=v1, d=w1⊕u1⊕v2⋙8, a′=u3⊕u1⊕v2⊕w3⋘13, b′=u0⊕w2⊕w3⋙16⋘7, c′=u2⊕w2⊕u0⊕v3⋙16⋘7, and d′=u1⊕v2⊕w3⋘13. The corresponding correlation weight of the round function is Cw=∑i=03ci.
CHAM is a family of lightweight block ciphers that was proposed by Koo et al. at ICISC′17, which blends the good designs of SIMON and SPECK [7]. 3 variants of CHAM have two kinds of block size, i.e., CHAM-64 and CHAM-128. The linear mask propagation for the 4 consecutive rounds of CHAM is shown in Figure 4. If the input-output mask tuples of each modular addition of the first 4 rounds are given, the input and output masks of the first 4 rounds can be deduced by Property 5.Figure 4
Linear masks in the first 4 rounds of CHAM.Property 5.
For CHAM, if the input-output mask tuples (ui,vi,wi) of each modular addition of the first 4 rounds are given, 1≤i≤4, the input and output masks of the first 4 rounds can be deduced as follows. ΓX00=v1, ΓX10=w1⋘1⊕v2, ΓX20=w2⋘8⊕v3, ΓX30=w3⋘1⊕v4; ΓX01=v2, ΓX11=ΓX20, ΓX21=ΓX30, ΓX31=u1⋘8; ΓX02=v3, ΓX12=ΓX21, ΓX22=ΓX31, ΓX31=u2⋘1; ΓX03=v4, ΓX13=ΓX22, ΓX23=ΓX32, ΓX33=u3⋘8; ΓX04=w4⋘8⊕ΓX13, ΓX14=ΓX23, ΓX24=ΓX33, ΓX34=u4⋘1.


## 2.1. Notation

For addition modulo2n, i.e., x⊞y=z, we use the symbols ⋘ and ⋙ to indicate rotation to the left and right and ≪ and ≫ to indicate the left and right shift operation, respectively. The binary operator symbols ⊕, ∨, ∧, , and ¬ represent XOR, OR, AND, concatenation, and bitwise NOT, respectively. For a vector x, wtx represents its Hamming weight and xi is the ith bit of it. 0 is a zero vector.


## 2.2. Linear Correlation Calculation for Modular Addition

LetF2n be the n dimensional vector space over binary field F2=0,1; for Boolean function f:F2n⟶F2 and h:F2n⟶F2, x∈F2n, the linear correlation between f and h can be denoted by(1)Corf,h=2×#x∣fx⊕hx=02n−1.For modular additionx⊞y=z, let (v,w) be the input masks, u be the output mask, and ⋅ be the standard inner product. According to the definition of linear correlation, when v⋅x⊞w⋅y⊕u⋅z=0, the linear approximation probability is defined as(2)Pru,v,w=2−3n×#x,y,zv⋅x⊞w⋅y⊕u⋅z=0.Letμt=−1t, then the linear correlation of modular addition can be denoted by Walsh transformation, and thus,(3)Coru,v,w=2−3n×∑x,y,z∈F2nμv⋅x⊞w⋅y⊕u⋅z.LetPru,v,w=1/2+ε, where ε is the bias. When v⋅x⊞w⋅y⊕u⋅z=1, the linear approximation probability is Pr¯u,v,w=1/2−ε. The linear correlation can be denoted by(4)Coru,v,w=Pru,v,w−Pr¯u,v,w=2Pru,v,w−1.We callCwu,v,w=−log2Coru,v,w as the correlation weight, and the linear square correlation can be denoted by(5)LSCu,v,w=Coru,v,w2=2−2×Cwu,v,w.For additionx⊞y modulo 2n, it can be rewritten as x⊞y=x⊕y⊕carryx,y, in which carryx,yi+1=carryx,yi⊕xi⊕yi and carryx,y0=0 for 0≤i≤n−1. The first-order approximation is carryx,y=x∧y≪1. If all carryx,yj=0 for j≤i, and 0≤i≤n−1, the high-order approximation is(6)carryx,yi+1=12−1xi+−1yi+carryx,yi−−1xi+yicarryx,yi.In [13], Wallén introduced the theorem to calculate the linear correlation by analyzing the carry high-order approximation function recursively. In [12], based on the bit state transformation, the formula to calculate the correlation was given by the following theorem.Theorem 1 (See [12]).
For addition modulo2n, let vandw be the input masks and u be the output mask. Define an auxiliary vector d=dn−1⋯d0, and each di=uiviwi∈F23 is an octal word, 0≤i≤n−1. Then, the linear correlation can be denoted by(7)Coru,v,w=LAdn−1Adn−2⋯Ad1Ad0C,where the row vector L=10, the column vector C=11T, and each 2×2 matrix Adi is defined by(8)A0=122001,A1=A2=−A4=120010,A7=120210,−A3=A5=A6=120001.
In [17], Schulte-Geers extended Theorem 1 and derived a fully explicit formula for the linear correlation calculation, given by Theorem 2.Theorem 2 (See [17]).
For addition modulo2n with input-output mask tuple u,v,w, a vectorial Boolean function M:F2n⟶F2n denotes the partial sum mapping:(9)x=x0,x1,⋯,xn−1⟶Mx=0,x0,x0⊕x1,⋯,x0⊕x1⊕⋯xn−2.
Letz≔MTu⊕v⊕w=0,xn−1,xn−1⊕xn−2,⋯,xn−1⊕xn−2⊕⋯x1, then the linear correlation can be denoted by(10)Coru,v,w=1u⊕v⪯z1u⊕w⪯z−1v⋅w2−wtz,where 1Gf is an indicator function for graph Gf≔x,fxx∈F2n; for n-bit vectors a and b, a⪯b represents ai≤bi for 0≤i≤n−1.
In iterative ciphers, the correlation of a singler-round linear trail is the product of the correlations of each round [25]. Assuming that there are NA additions modulo 2n with two inputs in ith round, Γin and Γout are the input and output masks of the r-round linear trail, and the correlation of it can be denoted by(11)CorΓin,Γout=∏i=1r∏j=1NACorui,j,vi,j,wi,j.
The linear approximation of a linear hull represents the potential of all linear trails with same input-output masks [26]. The averaged linear potential (ALP) can be counted by the following formula:(12)ALPΓin,Γout=1K∑k∈KCorΓin,Γout2.
Assuming that the keyk is selected uniformly from the key space K, the statistics of ALP can be formulated as (13), where TCw is the number of trails with correlation weight of Cw. Let Cmin be the correlation weight of the linear trail whose input-output masks are chosen as the fixed input-output masks of the linear hull. Cmax is the upper bound to be searched, which should be chosen by the trade-off between the search time and the accuracy of ALP:(13)ALPΓin,Γout=∑Cw=CminCmax2−2Cw×TCw.


## 2.3. Linear Properties of SPECK, SPARX, Chaskey, and CHAM

The SPECK family ciphers were designed by NSA in 2013 [3]. The SPARX family ciphers were introduced by Dinu et al. at ASIACRYPT′16 [6]. In SPARX, the nonlinear ARX-box (SPECKEY) is obtained by modifying the round function of SPECK32. The linear mask propagation properties of the round function in SPECK and SPECKEY are shown in Figure 1. The rotation parameters ra,rb=7,2 for SPECK32, while ra,rb=8,3 for other variants.Figure 1
Linear mask propagation properties of SPECK and SPECKEY.If the input-output masks (ui,vi,wi) and (ui+1,vi+1,wi+1) of the modular additions in the two consecutive rounds of SPECK are known, the input and output masks of these two rounds can be denoted by Property 1.Property 1.
If (ui,vi,wi) and (ui+1,vi+1,wi+1) are given, then ΓXi=vi⋘ra, ΓXi+1=vi+1⋘ra, ΓYi+1=vi+1⋘ra⊕ui, ΓYi=ΓYi+1⋙rb⊕wi, ΓYi+2=ΓYi+1⊕wi+1⋘rb, and ΓXi+2=ΓYi+1⊕ui+1.
The linear layer functionsL/ℒ′ [6] for SPARX-64 and SPARX-128 are shown in Figure 2. Due to the existence of the three-forked branches, the masks of the linear transformation layer have the following properties.Figure 2
(a) and (b) represent the linear layer of SPARX-64. (c) and (d) represent the linear layer of SPARX-128.
(a)
(b)
(c)
(d)Property 2.
For SPARX-64, if the masks are transformed by the linear layer functionℒ, let c=ΓX2⊕ΓX3, d=c⋙8, then ΓX0′=ΓX2, ΓX1′=ΓX3, ΓX2′=ΓX0⊕d⊕ΓX2, and ΓX3′=ΓX1⊕d⊕ΓX3.Property 3.
For SPARX-128, if the masks are transformed by the linear layer functionℒ′, let e=ΓX4⊕ΓX5⊕ΓX6⊕ΓX7, f=e⋙8, then ΓX0′=ΓX4, ΓX1′=ΓX5, ΓX2′=ΓX6, ΓX3′=ΓX7, ΓX4′=ΓX0⊕f⊕ΓX6, ΓX5′=ΓX1⊕f⊕ΓX5, ΓX6′=ΓX2⊕f⊕ΓX4, and ΓX7′=ΓX3⊕f⊕ΓX7.
Chaskey is a MAC algorithm introduced by Mouha et al. at SAC′14 [5], and an enhanced variant was proposed in 2015 [27], which increases the number of permutation rounds from 8 to 12. The round function of the permutation v0′,v1′,v2′,v3′=πv0,v1,v2,v3 is shown in Figure 3. The 4 modular additions are labeled by A0,A1,A2,andA3, respectively. The input mask a,b,c,d and the output mask a′,b′,c′,d′ of the first round can be denoted by Property 4.Figure 3
Linear masks in the first round of Chaskey.Property 4.
For the permutation of Chaskey, if the input-output masks of each modular addition in the first round are (ui,vi,wi), 0≤i≤3, the corresponding correlation weight of each modular addition is c0,c1,c2,c3, respectively. Hence, in the first round, a=v0, b=w0⊕u0⊕v3⋙16⋙5, c=v1, d=w1⊕u1⊕v2⋙8, a′=u3⊕u1⊕v2⊕w3⋘13, b′=u0⊕w2⊕w3⋙16⋘7, c′=u2⊕w2⊕u0⊕v3⋙16⋘7, and d′=u1⊕v2⊕w3⋘13. The corresponding correlation weight of the round function is Cw=∑i=03ci.
CHAM is a family of lightweight block ciphers that was proposed by Koo et al. at ICISC′17, which blends the good designs of SIMON and SPECK [7]. 3 variants of CHAM have two kinds of block size, i.e., CHAM-64 and CHAM-128. The linear mask propagation for the 4 consecutive rounds of CHAM is shown in Figure 4. If the input-output mask tuples of each modular addition of the first 4 rounds are given, the input and output masks of the first 4 rounds can be deduced by Property 5.Figure 4
Linear masks in the first 4 rounds of CHAM.Property 5.
For CHAM, if the input-output mask tuples (ui,vi,wi) of each modular addition of the first 4 rounds are given, 1≤i≤4, the input and output masks of the first 4 rounds can be deduced as follows. ΓX00=v1, ΓX10=w1⋘1⊕v2, ΓX20=w2⋘8⊕v3, ΓX30=w3⋘1⊕v4; ΓX01=v2, ΓX11=ΓX20, ΓX21=ΓX30, ΓX31=u1⋘8; ΓX02=v3, ΓX12=ΓX21, ΓX22=ΓX31, ΓX31=u2⋘1; ΓX03=v4, ΓX13=ΓX22, ΓX23=ΓX32, ΓX33=u3⋘8; ΓX04=w4⋘8⊕ΓX13, ΓX14=ΓX23, ΓX24=ΓX33, ΓX34=u4⋘1.


## 3. Automatic Search for the Linear Characteristics on ARX Ciphers

### 3.1. Input-Output Masks of Specific Correlation Weight

The number of input-output mask tuples in the first round is closely related to the complexity of the branch-and-bound search algorithm, but traversing all possible input masks of the first round will result in high complexity. An alternative approach is to consider the possible correlation weight corresponding to the input-output masks and exclude those tuples that have a large correlation weight. However, for a fixed correlation weight, it may correspond to multiple input-output mask tuples although the correlation can be calculated by Theorem 2 when the input-output masks are fixed for a modular addition.For addition modulo2n, its maximum correlation weight is n−1, and the size of the total space S of all input-output mask tuples is 23n. We can rank the correlation weights Cw from 0 to n−1 and construct the input-output masks subspace SCw corresponding to correlation weight Cw, 0≤Cw≤n−1. Therefore, the total space S can be divided into n subspaces, i.e., S=∪Cw=0n−1SCw.Definition 1.
Letv,w⟶u be the input-output masks for a modular addition with nonzero correlation. Let us define an octal word sequence Φ≔ξn−1⋯ξ0, where ξi=uiviwi∈F23, for 0≤i≤n−1.Definition 2.
Let us define three sets thatξi may belong to, i.e., U0=1,2,4,7, U1=0,3,5,6, and U2=0,7.
In Theorem 2, when the correlation of a modular addition is nonzero, the value distribution of the 3 consecutive bits inz and the 3 consecutive words in Φ has the following relationships, shown in Observation 1.Observation 1.
Letx=u⊕v⊕w and zi=⊕j=i+1n−1xj for 0≤i≤n−2, zn−1=0; hence, zi=zi+1⊕xi+1. For z∈F2n, assuming when zj=0 for n−1≥j>i+1 or zi+2=0, they should have ui⊕vi⪯zi, ui⊕wi⪯zi on bit level, and it is equivalent to ui−1⊕vi−1⪯xi+1⊕xi and ui−1⊕wi−1⪯xi+1⊕xi. Since xi=1 when ξi∈U0 and xi=0 when ξi∈U1,(14)ifzi+1,zi,zi−1=0,0,0,thenξi+1=0,ξi=0,ξi−1=0;ifzi+1,zi,zi−1=0,0,1,thenξi+1=0,ξi=0,ξi−1=7;ifzi+1,zi,zi−1=0,1,0,thenξi+1=0,ξi=7,ξi−1∈U0;ifzi+1,zi,zi−1=0,1,1,thenξi+1=0,ξi=7,ξi−1∈U1;ifzi+1,zi,zi−1=1,0,0,thenξi+1=7,ξi=U0,ξi−1=0;ifzi+1,zi,zi−1=1,0,1,thenξi+1=7,ξi=U0,ξi−1=7;ifzi+1,zi,zi−1=1,1,0,thenξi+1=7,ξi=U1,ξi−1∈U0;ifzi+1,zi,zi−1=1,1,1,thenξi+1=7,ξi=U1,ξi−1∈U1;
Hence, the value ofξi=uiviwi depends on whether the bit positions of zi+1 and zi are active. The last significant bits (u0,v0,w0) of the input-output masks construct the value of ξ0, which is only related to the Hamming weight of z0=⊕j=1n−1xj, i.e., u0⊕v0⪯wtz0 and u0⊕w0⪯wtz0. Therefore, if we get the Hamming weight distribution of z, from the LSB to MSB direction, as z0 is determined, ξ0 can be obtained. Next, x1=z1⊕z0 is determined, and u1⊕v1⪯wtz1 and u1⊕w1⪯wtz1 should be satisfied; hence, the possible values of ξ1 can be obtained. Recursively, all ξi values can be constructed as an octal word sequence from the LSB to MSB direction to subject to the above observation. Hence, the tuples of (u,v,w) can be generated from the elements in Φ. The process to construct the subspace SCw is shown in Algorithm 1, marked as Const (SCw).Algorithm 1:
Const (SCw): constructing the input-output mask tuples with linear correlation weight of Cw for modular addition, 0≤Cw≤n−1.
Input: Cw and Λ=λCw,…,λ1. Each pattern of the Hamming weight distribution of z can be calculated by the combination algorithm in [28], which is the combination pattern of n−1Cw, where ξi=uiviwi for 0≤i≤n−1.
(1)
Func_LSB: i=0 //constructing the LSBs of u,v,andw.
(2)
if Cw=0 then
(3)
Output the tuple of (u,v,w) with (1, 1, 1) or (0, 0, 0);
(4)
end if
(5)
if λ1≠0 then
(6)
For eachξi∈U2, c=1, and Fw=0, call Func_Middle (i+1,c,Fw);
(7)
else
(8)
For eachξi∈F23, c=2, and Fw=1, call Func_Middle (i+1,c,Fw);
(9)
end if
(10)
Func_Middle (i,c,Fw): //constructing the middle bits of u,v,andw.
(11)
if c=Cw then
(12)
call Func_MSB (i,c,Fw);
(13)
end if
(14)
if λc≠i then
(15)
if Fw=0 then //Fw recorded whether the value of λi−1 is 1 or not.
(16)
For eachξi=0 and Fw′=0, call Func_Middle (i+1,c,Fw′);
(17)
else
(18)
For eachξi=7 and Fw′=0, call Func_Middle (i+1,c,Fw′);
(19)
end if
(20)
else //λc=i. The value of Fw determines whether ξi belongs to U0 or U1.
(21)
if Fw=0 then
(22)
For eachξi∈U0 and Fw′=1, call Func_Middle (i+1,c+1,Fw′);
(23)
else
(24)
For eachξi∈U1 and Fw′=1, call Func_Middle (i+1,c+1,Fw′);
(25)
end if
(26)
end if
(27)
Func_MSB (i,c,Fw): //constructing the bits of u,v,w with position higher than λCw.
(28)
if λc≠i then //the value of Fw determines whether ξi equals to 0 or 7.
(29)
if Fw=0 then
(30)
Letξi=0 and Fw′=0, call Func_MSB (i+1,c,Fw′);
(31)
else
(32)
Letξi=7 and Fw′=0, call Func_MSB (i+1,c,Fw′);
(33)
end if
(34)
else //λc=i.
(35)
if Fw=0 then
(36)
For eachξi∈U0 and ξi+1=7, output each tuple of (u,v,w);
(37)
else
(38)
For eachξi∈U1 and ξi+1=7, output each tuple of (u,v,w);
(39)
end if
(40)
end if


### 3.2. Combinational Linear Approximation Table

For addition modulo2n, the full LAT requires a storage size of 23n; when n is too large, it will be very difficult to store. To facilitate the storage, an intuitive approach is to store only a part of the full LAT. For a n-bit vector, we can split it into t subvectors of m bits, where n=mt. When each m-bit subvector is determined, the n-bit vector can be obtained by concatenating. This idea gives birth to the concept of combinatorial LAT (cLAT).Property 6.
Foru⊕v⪯z and u⊕w⪯z, they are equivalent to u⊕v∧¬u⊕v∧z→=0→ and u⊕w∧¬u⊕w∧z→=0→.Corollary 1.
Letu,v,w∈F2n be the input-output masks of the modular addition with nonzero correlation, and let A=u⊕v, B=u⊕w, C=u⊕v⊕w, and z=MTC. Splitting the vectors A=At−1⋯A0, B=Bt−1⋯B0, C=Ct−1⋯C0, and z=zt−1⋯z0 into t subvectors, respectively, n=mt, Ak,Bk,Ck∈F2m, 0≤k≤t−1. Then, the correlation weight of the modular addition can be denoted by(15)−log2Coru,v,w=∑k=0t−1wtzk=∑k=0t−1∑j=0m−1Cmk+j+1⊕zmk+j+1,when(16)Ak∧¬Ak∧zk=0,Bk∧¬Bk∧zk=0.Proof.
w
t
z is the sum of the Hamming weight of each subvector zk, so −log2Coru,v,w=∑k=0t−1wtzk. For C=u⊕v⊕w, the ith bit in z can be denoted by zi=⊕j=i+1n−1Cj=zi+1⊕Ci+1. Let 0≤j<i, 0≤i≤n−1, and the jth bit in zk should be zjk=Cmk+j+1⊕zmk+j+1. Hence, wtzk=∑j=0m−1Cmk+j+1⊕zmk+j+1, when ui⊕vi⪯⊕l=i+1n−1Cl and ui⊕wi⪯⊕l=i+1n−1Cl are satisfied, i.e., Ak∧¬Ak∧zk=0 and Bk∧¬Bk∧zk=0 for 0≤k≤t−1.If them-bit subvector zk+1 adjacent to zk is known, zk can be calculated by subvector tuple (uk, vk, wk) and the lowest bit of zk+1. We call (uk, vk, wk) as a subblock, and we call the bit zk+1m∈0,1 as the connection status when used in the calculation of zk. Splitting the n-bit vector z into t subvectors, there should have t−1 connection status zj, j∈t−1m,⋯,2m,m, and for the highest subvector, its connection status b=0. Hence, for the highest subblock (ut−1, vt−1, and wt−1), the Hamming weight of zt−1 and the bit zt−1m can be obtained, recursively, and the Hamming weight of the remaining subvectors can also be obtained. Therefore, as connection status b∈0,1 and uk,vk,wk∈F2m, we can construct a m-bit lookup table for modular addition in advance and query the tables by indexing input-output masks and the connection status. In addition, the connection status for the next subblock can also be generated.In the top-down search techniques for the ARX ciphers, for the modular additions in the middle rounds, in most cases, only one input mask is fixed (assuming it isv), and another input mask w and the output mask u are unknown. In the lookup tables, we need to lookup all valid subvectors of (u,w) that correspond to nonzero correlation based on v. The lookup table (called as cLAT) is constructed by Algorithm 2, and it takes about 4 seconds on a 2.5 GHz CPU to generate the table with storage size about 1.2 GByte when m=8.Algorithm 2:Constructing the m-bit cLAT for modular addition.
(1)
for each b∈0,1 and input mask v∈F2m
(2)
cLATminvb=m, let MTk=0 and cLATNvbk=0, for 0≤k≤m−1;
(3)
for each input mask w∈F2m and output mask u∈F2m do
(4)
A=u⊕v, B=u⊕w, C=u⊕v⊕w, Cw=0;
(5)
for j=0 to m−1 do
(6)
Cbj=C≫m−1−j∧1;
(7)
end for
(8)
if b=1 then //determining the connection status generated by the upper subblock.
(9)
Cw++, MT0=1, Z=1≪m−1;
(10)
else
(11)
MT0=0, Z=0;
(12)
end if
(13)
for i=1 to m−1 do //determining the correlation weight.
(14)
MTi=Cbi−1+MTi−1∧1;
(15)
if MTi=1 then
(16)
Cw++, Z=Z∨1≪m−1−i;
(17)
end if
(18)
end for
(19)
F1=A∧¬A∧Z, F2=B∧¬B∧Z;
(20)
if F1=0 and F2=0 then //judgment conditions u⊕v⪯z and u⊕w⪯z.
(21)
cLATwvbcLATNvbCw=w;
(22)
cLATuvbcLATNvbCw=u;
(23)
cLATNvbCw++; //the number of tuples correspond to v and b.
(24)
cLATbuvwb=MTm−1+Cbm−1∧1; //connection status.
(25)
if cLATminvb>Cw then
(26)
cLATminvb=Cw; //the minimum correlation weight corresponds to v and b.
(27)
end if
(28)
end if
(29)
end for
(30)
end for.


### 3.3. Splitting-Lookup-Recombination

Algorithm2 constructs a m-bit cLAT for the addition modulo 2n, and this section describes how to use it. When one input mask is fixed, we can get another input mask, the output mask, and the corresponding correlation weight by the Splitting-Lookup-Recombination approach, which contains three steps.


#### 3.3.1. Splitting

For addition modulo2n, n=mt, if one of the two input masks v is fixed, then split v into tm-bit subvectors. The larger the m, the fewer the times to lookup cLAT and the fewer the number of bit concatenation operations, but the more space the memory takes up, and after the trade-offs, we choose m=8.


#### 3.3.2. Lookup

From the MSB to the LSB direction, query the subvectors of (u,w) that correspond to each subvector of v and the corresponding correlation weights. For the highest m-bit subvector vt−1, its connection status b=0, looking up cLAT to get wt−1 and ut−1, the corresponding correlation weight ct−1, and the connection status for the subvector vt−2. Similarly, other subvectors of u and w and the corresponding correlation weights can be obtained.


#### 3.3.3. Recombination

All subvectors ofu and w can be obtained by lookup tables, and the n-bit u and w can be obtained by bit concatenation. The correlation weight of the modular addition is the sum of the weight of each subblock, i.e., Cw=∑k=0t−1ck.When there are multiple modular additions in the round function, i.e.,NA>1, for each modular addition, its undetermined input mask and output mask need to be obtained by the Splitting-Lookup-Recombination approach, respectively. In the lookup phase, a total of tNA lookup operations are required. And the correlation weight of the round function is Cw=∑j=1NA∑k=0t−1cjk.For each subvectorvk, the possible minimum linear correlation weight corresponding to it can be calculated in advance by Algorithm 2, that is,(17)ckmin=mincLATminvk0,cLATminvk1.During theRecombination phase, the correlation boundary can be constructed by the associated weights that have been obtained and the possible minimum correlation weights, shown in Corollary 2.Corollary 2.
For addition modulo2n, one of the input mask v=vt−1⋯v0 is fixed, n=mt, vk∈F2m, and 0≤k≤t−1. For any u,w∈F2n of nonzero correlation, the correlation boundary should have(18)Coru,v,w≤Corut−1⋯uk,vt−1⋯vk,wt−1⋯wk+2−∑j=0k−1cjmin.Proof.
The correlation of modular addition is the product of the correlation of each subblock after splitting, i.e.,Coru,v,w=∏k=0t−1Coruk,vk,wk. Let −log2Corut−1⋯uk,vt−1⋯vk,wt−1⋯wk=∑l=kt−1cl be the correlation weight of the subvector tuples that are obtained by lookup tables. The sum of the correlation weights of the subvector tuples have not been looked up yet, which should s.t. ∑j=0k−1cjmin≤−log2Coru,v,w−∑l=kt−1cl.Assuming the number ofuk,wk corresponding to each subvector vk is Xk, hence, the number of mask branches corresponding to the modular addition is ∏k=0t−1Xk. Corollary 2 can be used to filter out u,w of large correlation weight.


### 3.4. Improved Automatic Search Algorithm

In this section, we adopt a top-down technique [19–21], taking the first round as the starting point of the search process. In the first/second rounds, the input-output mask tuples of each modular addition with correlation weight increasing monotonically can be obtained by Algorithm 1. In the middle rounds, for each modular addition, u and w can be obtained by the Splitting-Lookup-Recombination approach. Algorithm 3 takes SPECK as an example.Algorithm 3:Automatic search for the optimal linear trails of ARX ciphers. Take the application to SPECK as an example, where n=mt.
Input: the cLAT is precomputed and stored by Algorithm 2. Bw1,⋯,Bwr−1 have been recorded
(1)
Program entry:
(2)
LetBcr¯ = Bcr−1−1, and Bcr = null //Bw1 can be derived manually for most ARX ciphers.
(3)
while Bcr¯ ≠ Bcrdo
(4)
Bcr¯++; //the expected r-round correlation weight increases monotonously.
(5)
Call Procedure Round-1;
(6)
end while
(7)
Exit the program.
(8)
Round-1:/exclude the search space with correlation weights larger than Bcr¯−Bcr−1.
(9)
for Cw1=0 to n−1do //Cw1 increases monotonously.
(10)
if Cw1+Bcr−1>Bcr¯ then
(11)
Return to the upper procedure with FALSE state;
(12)
else
(13)
Call Algorithm1 Const (SCw1), and traverse each output tuple u1,v1,w1;
(14)
if call Round-2u1,v1,w1 and the return value is TRUE, then
(15)
Stop Algorithm1 and return TRUE; /record the optimal linear trail be found.
(16)
end if
(17)
end if
(18)
end for
(19)
Return to the upper procedure with FALSE state;
(20)
Round-2u1,v1,w1: /exclude the correlation weights larger than Bcr¯−Bcr−1−Cw1.
(21)
for Cw2=0 to n−1 //Cw2 increases monotonously.
(22)
if Cw1+Cw2+Bcr−2>Bcr¯ then
(23)
Return to the upper procedure with FALSE state;
(24)
else
(25)
Call Algorithm1 Const (SCw2), and traverse each output tuple u2,v2,w2;
(26)
y=u1⊕v2⋘ra⊕w2⋘rb, x=u2⊕y; //ra,rb: rotation parameters.
(27)
if call Round-r (3,x,y) and the return value is TRUE, then
(28)
Stop Algorithm1, compute the masks of the first/second round and return TRUE;
(29)
end if
(30)
end if
(31)
end for
(32)
Return to the upper procedure with FALSE state;
(33)
Round-r (i,x,y): //middle rounds, 3≤i≤r.
(34)
v
=
x
⋙
r
a, and let v=vt−1⋯v0 and vk∈F2m, 0≤k≤t−1; //splitting v.
(35)
CallLRv, traversing each u and w; //where Cwi=Corv,w,u.
(36)
if i=r and Cw1+…+Cwi−1+Cwi=Bcr¯ then //the last round.
(37)
LetBcr=Bcr¯, break from LRv and return TRUE;
(38)
end if //r-round optimal linear trail of expected correlation weight Bcr¯ have been found.
(39)
y
′
=
y
⊕
w
⋘
r
b, x′=y′⊕u;
(40)
if call Round-r (i+1,x′,y′) and the return value is TRUE, then
(41)
Break fromLRv and return TRUE; //record the masks of each round and return.
(42)
end if
(43)
Return to the upper procedure with FALSE state;
(44)
LR
v: //looking up cLAT and recombining another input mask w and the output mask u.
(45)
Letckmin=mincLATminvk0,cLATminvk1, and bk=0, for 0≤k≤t−1;
(46)
for k=t−1 to 0 do //from MSB to LSB direction.
(47)
for cik=cLATminvkbk to cik¯ do //cit−1¯=m−1 and cik¯=m for 0≤k≤t−2.
(48)
if ∑g=1i−1Cwg+∑j=0k−1cjmin + then ∑l=kt−1cil + Bcr−i≤Bcr¯
(49)
for Xk=0 to cLATNvt−1bkcik−1 do
(50)
uk=cLATuvkbkXk; //querying uk and wk.
(51)
wk=cLATwvkbkXk;
(52)
bk−1=cLATbukvkwkbk; //record the next connection status.
(53)
if k=0 then //recombining u and w.
(54)
Output eachu=ut−1⋯u0, w=wt−1⋯w0, and Cwi=∑k=0t−1cik;
(55)
end if
(56)
end for
(57)
end if
(58)
end for
(59)
end forLet the optimal correlation weight of ther−ith round that has been obtained be Bcr−i, 1≤i≤r−1, and let the expected r-round correlation weight be Bcr¯. The correlation weight of the first two rounds should subject to Matsui’s pruning condition, i.e., Cw1+Bcr−1≤Bcr¯ and Cw1+Cw2+Bcr−2≤Bcr¯.Let∑i=1NA′Cwi=Bcr¯−Bcr−1, NA′ is the number of additions in the first two rounds, and then the search space need to be constructed is no more than (19). When the block size of a ARX cipher is large, let n be the word size of the modular addition, the total input-output masks of all NA′ modular additions in the first two round is S′=23n×NA′. Therefore, when the value of Bcr¯−Bcr−1 is small, the search space S will be much smaller than S′ intuitively:(19)S=∏i=1NA′∑c=0Cwi#u,v,w−log2Coru,v,w=c.


### 3.5. Flexible Search Scenario Settings

Combining Algorithm1, cLAT, pruning conditions, and the properties of the target ciphers in Section 2.3, Algorithm 3 can be adapted to the following search scenarios with appropriate modifications:Scenario 1: for some ARX ciphers, such as SPARX and Chaskey, the number of modular additions in the round function is more than 1, NA>1. Hence, the correlation weight of each round is Cwi=∑j=1NACwij, and Cwij is the correlation weight of the jth addition in the ith round. In the first/second round, the input-output masks of each modular addition should be generated by Algorithm 1. In the middle rounds, the tuple (u,w) of each modular addition should be obtained by calling LRv multiple times.Scenario 2: the linear hulls can also be searched by simply modifying Algorithm 3. For an obtained optimal linear trail, fix the input mask of the first round and the output mask of the last round, call round-r (i,x,y) directly, and modify Bcr¯ to the expected maximum statistical correlation weight Cmax. Therefore, for ALP, all linear trails with linear correlation weight between the optimal correlation weight Cmin and Cmax can be counted.Scenario 3: when the number of rounds of a linear trail or the block size is large, the linear correlation tends to be very small, and the search process will be very time-consuming. Hence, good linear characteristic results under certain conditions can be explored by the heuristic search settings. We can exclude a large number of search branches and reduce the search complexity by these methods, such as starting the search from a desired large correlation weight Bcr¯, fixing the input mask of a certain round, and limiting the correlation weight of a round or a certain modular addition.


## 3.1. Input-Output Masks of Specific Correlation Weight

The number of input-output mask tuples in the first round is closely related to the complexity of the branch-and-bound search algorithm, but traversing all possible input masks of the first round will result in high complexity. An alternative approach is to consider the possible correlation weight corresponding to the input-output masks and exclude those tuples that have a large correlation weight. However, for a fixed correlation weight, it may correspond to multiple input-output mask tuples although the correlation can be calculated by Theorem 2 when the input-output masks are fixed for a modular addition.For addition modulo2n, its maximum correlation weight is n−1, and the size of the total space S of all input-output mask tuples is 23n. We can rank the correlation weights Cw from 0 to n−1 and construct the input-output masks subspace SCw corresponding to correlation weight Cw, 0≤Cw≤n−1. Therefore, the total space S can be divided into n subspaces, i.e., S=∪Cw=0n−1SCw.Definition 1.
Letv,w⟶u be the input-output masks for a modular addition with nonzero correlation. Let us define an octal word sequence Φ≔ξn−1⋯ξ0, where ξi=uiviwi∈F23, for 0≤i≤n−1.Definition 2.
Let us define three sets thatξi may belong to, i.e., U0=1,2,4,7, U1=0,3,5,6, and U2=0,7.
In Theorem 2, when the correlation of a modular addition is nonzero, the value distribution of the 3 consecutive bits inz and the 3 consecutive words in Φ has the following relationships, shown in Observation 1.Observation 1.
Letx=u⊕v⊕w and zi=⊕j=i+1n−1xj for 0≤i≤n−2, zn−1=0; hence, zi=zi+1⊕xi+1. For z∈F2n, assuming when zj=0 for n−1≥j>i+1 or zi+2=0, they should have ui⊕vi⪯zi, ui⊕wi⪯zi on bit level, and it is equivalent to ui−1⊕vi−1⪯xi+1⊕xi and ui−1⊕wi−1⪯xi+1⊕xi. Since xi=1 when ξi∈U0 and xi=0 when ξi∈U1,(14)ifzi+1,zi,zi−1=0,0,0,thenξi+1=0,ξi=0,ξi−1=0;ifzi+1,zi,zi−1=0,0,1,thenξi+1=0,ξi=0,ξi−1=7;ifzi+1,zi,zi−1=0,1,0,thenξi+1=0,ξi=7,ξi−1∈U0;ifzi+1,zi,zi−1=0,1,1,thenξi+1=0,ξi=7,ξi−1∈U1;ifzi+1,zi,zi−1=1,0,0,thenξi+1=7,ξi=U0,ξi−1=0;ifzi+1,zi,zi−1=1,0,1,thenξi+1=7,ξi=U0,ξi−1=7;ifzi+1,zi,zi−1=1,1,0,thenξi+1=7,ξi=U1,ξi−1∈U0;ifzi+1,zi,zi−1=1,1,1,thenξi+1=7,ξi=U1,ξi−1∈U1;
Hence, the value ofξi=uiviwi depends on whether the bit positions of zi+1 and zi are active. The last significant bits (u0,v0,w0) of the input-output masks construct the value of ξ0, which is only related to the Hamming weight of z0=⊕j=1n−1xj, i.e., u0⊕v0⪯wtz0 and u0⊕w0⪯wtz0. Therefore, if we get the Hamming weight distribution of z, from the LSB to MSB direction, as z0 is determined, ξ0 can be obtained. Next, x1=z1⊕z0 is determined, and u1⊕v1⪯wtz1 and u1⊕w1⪯wtz1 should be satisfied; hence, the possible values of ξ1 can be obtained. Recursively, all ξi values can be constructed as an octal word sequence from the LSB to MSB direction to subject to the above observation. Hence, the tuples of (u,v,w) can be generated from the elements in Φ. The process to construct the subspace SCw is shown in Algorithm 1, marked as Const (SCw).Algorithm 1:
Const (SCw): constructing the input-output mask tuples with linear correlation weight of Cw for modular addition, 0≤Cw≤n−1.
Input: Cw and Λ=λCw,…,λ1. Each pattern of the Hamming weight distribution of z can be calculated by the combination algorithm in [28], which is the combination pattern of n−1Cw, where ξi=uiviwi for 0≤i≤n−1.
(1)
Func_LSB: i=0 //constructing the LSBs of u,v,andw.
(2)
if Cw=0 then
(3)
Output the tuple of (u,v,w) with (1, 1, 1) or (0, 0, 0);
(4)
end if
(5)
if λ1≠0 then
(6)
For eachξi∈U2, c=1, and Fw=0, call Func_Middle (i+1,c,Fw);
(7)
else
(8)
For eachξi∈F23, c=2, and Fw=1, call Func_Middle (i+1,c,Fw);
(9)
end if
(10)
Func_Middle (i,c,Fw): //constructing the middle bits of u,v,andw.
(11)
if c=Cw then
(12)
call Func_MSB (i,c,Fw);
(13)
end if
(14)
if λc≠i then
(15)
if Fw=0 then //Fw recorded whether the value of λi−1 is 1 or not.
(16)
For eachξi=0 and Fw′=0, call Func_Middle (i+1,c,Fw′);
(17)
else
(18)
For eachξi=7 and Fw′=0, call Func_Middle (i+1,c,Fw′);
(19)
end if
(20)
else //λc=i. The value of Fw determines whether ξi belongs to U0 or U1.
(21)
if Fw=0 then
(22)
For eachξi∈U0 and Fw′=1, call Func_Middle (i+1,c+1,Fw′);
(23)
else
(24)
For eachξi∈U1 and Fw′=1, call Func_Middle (i+1,c+1,Fw′);
(25)
end if
(26)
end if
(27)
Func_MSB (i,c,Fw): //constructing the bits of u,v,w with position higher than λCw.
(28)
if λc≠i then //the value of Fw determines whether ξi equals to 0 or 7.
(29)
if Fw=0 then
(30)
Letξi=0 and Fw′=0, call Func_MSB (i+1,c,Fw′);
(31)
else
(32)
Letξi=7 and Fw′=0, call Func_MSB (i+1,c,Fw′);
(33)
end if
(34)
else //λc=i.
(35)
if Fw=0 then
(36)
For eachξi∈U0 and ξi+1=7, output each tuple of (u,v,w);
(37)
else
(38)
For eachξi∈U1 and ξi+1=7, output each tuple of (u,v,w);
(39)
end if
(40)
end if


## 3.2. Combinational Linear Approximation Table

For addition modulo2n, the full LAT requires a storage size of 23n; when n is too large, it will be very difficult to store. To facilitate the storage, an intuitive approach is to store only a part of the full LAT. For a n-bit vector, we can split it into t subvectors of m bits, where n=mt. When each m-bit subvector is determined, the n-bit vector can be obtained by concatenating. This idea gives birth to the concept of combinatorial LAT (cLAT).Property 6.
Foru⊕v⪯z and u⊕w⪯z, they are equivalent to u⊕v∧¬u⊕v∧z→=0→ and u⊕w∧¬u⊕w∧z→=0→.Corollary 1.
Letu,v,w∈F2n be the input-output masks of the modular addition with nonzero correlation, and let A=u⊕v, B=u⊕w, C=u⊕v⊕w, and z=MTC. Splitting the vectors A=At−1⋯A0, B=Bt−1⋯B0, C=Ct−1⋯C0, and z=zt−1⋯z0 into t subvectors, respectively, n=mt, Ak,Bk,Ck∈F2m, 0≤k≤t−1. Then, the correlation weight of the modular addition can be denoted by(15)−log2Coru,v,w=∑k=0t−1wtzk=∑k=0t−1∑j=0m−1Cmk+j+1⊕zmk+j+1,when(16)Ak∧¬Ak∧zk=0,Bk∧¬Bk∧zk=0.Proof.
w
t
z is the sum of the Hamming weight of each subvector zk, so −log2Coru,v,w=∑k=0t−1wtzk. For C=u⊕v⊕w, the ith bit in z can be denoted by zi=⊕j=i+1n−1Cj=zi+1⊕Ci+1. Let 0≤j<i, 0≤i≤n−1, and the jth bit in zk should be zjk=Cmk+j+1⊕zmk+j+1. Hence, wtzk=∑j=0m−1Cmk+j+1⊕zmk+j+1, when ui⊕vi⪯⊕l=i+1n−1Cl and ui⊕wi⪯⊕l=i+1n−1Cl are satisfied, i.e., Ak∧¬Ak∧zk=0 and Bk∧¬Bk∧zk=0 for 0≤k≤t−1.If them-bit subvector zk+1 adjacent to zk is known, zk can be calculated by subvector tuple (uk, vk, wk) and the lowest bit of zk+1. We call (uk, vk, wk) as a subblock, and we call the bit zk+1m∈0,1 as the connection status when used in the calculation of zk. Splitting the n-bit vector z into t subvectors, there should have t−1 connection status zj, j∈t−1m,⋯,2m,m, and for the highest subvector, its connection status b=0. Hence, for the highest subblock (ut−1, vt−1, and wt−1), the Hamming weight of zt−1 and the bit zt−1m can be obtained, recursively, and the Hamming weight of the remaining subvectors can also be obtained. Therefore, as connection status b∈0,1 and uk,vk,wk∈F2m, we can construct a m-bit lookup table for modular addition in advance and query the tables by indexing input-output masks and the connection status. In addition, the connection status for the next subblock can also be generated.In the top-down search techniques for the ARX ciphers, for the modular additions in the middle rounds, in most cases, only one input mask is fixed (assuming it isv), and another input mask w and the output mask u are unknown. In the lookup tables, we need to lookup all valid subvectors of (u,w) that correspond to nonzero correlation based on v. The lookup table (called as cLAT) is constructed by Algorithm 2, and it takes about 4 seconds on a 2.5 GHz CPU to generate the table with storage size about 1.2 GByte when m=8.Algorithm 2:Constructing the m-bit cLAT for modular addition.
(1)
for each b∈0,1 and input mask v∈F2m
(2)
cLATminvb=m, let MTk=0 and cLATNvbk=0, for 0≤k≤m−1;
(3)
for each input mask w∈F2m and output mask u∈F2m do
(4)
A=u⊕v, B=u⊕w, C=u⊕v⊕w, Cw=0;
(5)
for j=0 to m−1 do
(6)
Cbj=C≫m−1−j∧1;
(7)
end for
(8)
if b=1 then //determining the connection status generated by the upper subblock.
(9)
Cw++, MT0=1, Z=1≪m−1;
(10)
else
(11)
MT0=0, Z=0;
(12)
end if
(13)
for i=1 to m−1 do //determining the correlation weight.
(14)
MTi=Cbi−1+MTi−1∧1;
(15)
if MTi=1 then
(16)
Cw++, Z=Z∨1≪m−1−i;
(17)
end if
(18)
end for
(19)
F1=A∧¬A∧Z, F2=B∧¬B∧Z;
(20)
if F1=0 and F2=0 then //judgment conditions u⊕v⪯z and u⊕w⪯z.
(21)
cLATwvbcLATNvbCw=w;
(22)
cLATuvbcLATNvbCw=u;
(23)
cLATNvbCw++; //the number of tuples correspond to v and b.
(24)
cLATbuvwb=MTm−1+Cbm−1∧1; //connection status.
(25)
if cLATminvb>Cw then
(26)
cLATminvb=Cw; //the minimum correlation weight corresponds to v and b.
(27)
end if
(28)
end if
(29)
end for
(30)
end for.


## 3.3. Splitting-Lookup-Recombination

Algorithm2 constructs a m-bit cLAT for the addition modulo 2n, and this section describes how to use it. When one input mask is fixed, we can get another input mask, the output mask, and the corresponding correlation weight by the Splitting-Lookup-Recombination approach, which contains three steps.


### 3.3.1. Splitting

For addition modulo2n, n=mt, if one of the two input masks v is fixed, then split v into tm-bit subvectors. The larger the m, the fewer the times to lookup cLAT and the fewer the number of bit concatenation operations, but the more space the memory takes up, and after the trade-offs, we choose m=8.


### 3.3.2. Lookup

From the MSB to the LSB direction, query the subvectors of (u,w) that correspond to each subvector of v and the corresponding correlation weights. For the highest m-bit subvector vt−1, its connection status b=0, looking up cLAT to get wt−1 and ut−1, the corresponding correlation weight ct−1, and the connection status for the subvector vt−2. Similarly, other subvectors of u and w and the corresponding correlation weights can be obtained.


### 3.3.3. Recombination

All subvectors ofu and w can be obtained by lookup tables, and the n-bit u and w can be obtained by bit concatenation. The correlation weight of the modular addition is the sum of the weight of each subblock, i.e., Cw=∑k=0t−1ck.When there are multiple modular additions in the round function, i.e.,NA>1, for each modular addition, its undetermined input mask and output mask need to be obtained by the Splitting-Lookup-Recombination approach, respectively. In the lookup phase, a total of tNA lookup operations are required. And the correlation weight of the round function is Cw=∑j=1NA∑k=0t−1cjk.For each subvectorvk, the possible minimum linear correlation weight corresponding to it can be calculated in advance by Algorithm 2, that is,(17)ckmin=mincLATminvk0,cLATminvk1.During theRecombination phase, the correlation boundary can be constructed by the associated weights that have been obtained and the possible minimum correlation weights, shown in Corollary 2.Corollary 2.
For addition modulo2n, one of the input mask v=vt−1⋯v0 is fixed, n=mt, vk∈F2m, and 0≤k≤t−1. For any u,w∈F2n of nonzero correlation, the correlation boundary should have(18)Coru,v,w≤Corut−1⋯uk,vt−1⋯vk,wt−1⋯wk+2−∑j=0k−1cjmin.Proof.
The correlation of modular addition is the product of the correlation of each subblock after splitting, i.e.,Coru,v,w=∏k=0t−1Coruk,vk,wk. Let −log2Corut−1⋯uk,vt−1⋯vk,wt−1⋯wk=∑l=kt−1cl be the correlation weight of the subvector tuples that are obtained by lookup tables. The sum of the correlation weights of the subvector tuples have not been looked up yet, which should s.t. ∑j=0k−1cjmin≤−log2Coru,v,w−∑l=kt−1cl.Assuming the number ofuk,wk corresponding to each subvector vk is Xk, hence, the number of mask branches corresponding to the modular addition is ∏k=0t−1Xk. Corollary 2 can be used to filter out u,w of large correlation weight.


## 3.3.1. Splitting

For addition modulo2n, n=mt, if one of the two input masks v is fixed, then split v into tm-bit subvectors. The larger the m, the fewer the times to lookup cLAT and the fewer the number of bit concatenation operations, but the more space the memory takes up, and after the trade-offs, we choose m=8.


## 3.3.2. Lookup

From the MSB to the LSB direction, query the subvectors of (u,w) that correspond to each subvector of v and the corresponding correlation weights. For the highest m-bit subvector vt−1, its connection status b=0, looking up cLAT to get wt−1 and ut−1, the corresponding correlation weight ct−1, and the connection status for the subvector vt−2. Similarly, other subvectors of u and w and the corresponding correlation weights can be obtained.


## 3.3.3. Recombination

All subvectors ofu and w can be obtained by lookup tables, and the n-bit u and w can be obtained by bit concatenation. The correlation weight of the modular addition is the sum of the weight of each subblock, i.e., Cw=∑k=0t−1ck.When there are multiple modular additions in the round function, i.e.,NA>1, for each modular addition, its undetermined input mask and output mask need to be obtained by the Splitting-Lookup-Recombination approach, respectively. In the lookup phase, a total of tNA lookup operations are required. And the correlation weight of the round function is Cw=∑j=1NA∑k=0t−1cjk.For each subvectorvk, the possible minimum linear correlation weight corresponding to it can be calculated in advance by Algorithm 2, that is,(17)ckmin=mincLATminvk0,cLATminvk1.During theRecombination phase, the correlation boundary can be constructed by the associated weights that have been obtained and the possible minimum correlation weights, shown in Corollary 2.Corollary 2.
For addition modulo2n, one of the input mask v=vt−1⋯v0 is fixed, n=mt, vk∈F2m, and 0≤k≤t−1. For any u,w∈F2n of nonzero correlation, the correlation boundary should have(18)Coru,v,w≤Corut−1⋯uk,vt−1⋯vk,wt−1⋯wk+2−∑j=0k−1cjmin.Proof.
The correlation of modular addition is the product of the correlation of each subblock after splitting, i.e.,Coru,v,w=∏k=0t−1Coruk,vk,wk. Let −log2Corut−1⋯uk,vt−1⋯vk,wt−1⋯wk=∑l=kt−1cl be the correlation weight of the subvector tuples that are obtained by lookup tables. The sum of the correlation weights of the subvector tuples have not been looked up yet, which should s.t. ∑j=0k−1cjmin≤−log2Coru,v,w−∑l=kt−1cl.Assuming the number ofuk,wk corresponding to each subvector vk is Xk, hence, the number of mask branches corresponding to the modular addition is ∏k=0t−1Xk. Corollary 2 can be used to filter out u,w of large correlation weight.


## 3.4. Improved Automatic Search Algorithm

In this section, we adopt a top-down technique [19–21], taking the first round as the starting point of the search process. In the first/second rounds, the input-output mask tuples of each modular addition with correlation weight increasing monotonically can be obtained by Algorithm 1. In the middle rounds, for each modular addition, u and w can be obtained by the Splitting-Lookup-Recombination approach. Algorithm 3 takes SPECK as an example.Algorithm 3:Automatic search for the optimal linear trails of ARX ciphers. Take the application to SPECK as an example, where n=mt.
Input: the cLAT is precomputed and stored by Algorithm 2. Bw1,⋯,Bwr−1 have been recorded
(1)
Program entry:
(2)
LetBcr¯ = Bcr−1−1, and Bcr = null //Bw1 can be derived manually for most ARX ciphers.
(3)
while Bcr¯ ≠ Bcrdo
(4)
Bcr¯++; //the expected r-round correlation weight increases monotonously.
(5)
Call Procedure Round-1;
(6)
end while
(7)
Exit the program.
(8)
Round-1:/exclude the search space with correlation weights larger than Bcr¯−Bcr−1.
(9)
for Cw1=0 to n−1do //Cw1 increases monotonously.
(10)
if Cw1+Bcr−1>Bcr¯ then
(11)
Return to the upper procedure with FALSE state;
(12)
else
(13)
Call Algorithm1 Const (SCw1), and traverse each output tuple u1,v1,w1;
(14)
if call Round-2u1,v1,w1 and the return value is TRUE, then
(15)
Stop Algorithm1 and return TRUE; /record the optimal linear trail be found.
(16)
end if
(17)
end if
(18)
end for
(19)
Return to the upper procedure with FALSE state;
(20)
Round-2u1,v1,w1: /exclude the correlation weights larger than Bcr¯−Bcr−1−Cw1.
(21)
for Cw2=0 to n−1 //Cw2 increases monotonously.
(22)
if Cw1+Cw2+Bcr−2>Bcr¯ then
(23)
Return to the upper procedure with FALSE state;
(24)
else
(25)
Call Algorithm1 Const (SCw2), and traverse each output tuple u2,v2,w2;
(26)
y=u1⊕v2⋘ra⊕w2⋘rb, x=u2⊕y; //ra,rb: rotation parameters.
(27)
if call Round-r (3,x,y) and the return value is TRUE, then
(28)
Stop Algorithm1, compute the masks of the first/second round and return TRUE;
(29)
end if
(30)
end if
(31)
end for
(32)
Return to the upper procedure with FALSE state;
(33)
Round-r (i,x,y): //middle rounds, 3≤i≤r.
(34)
v
=
x
⋙
r
a, and let v=vt−1⋯v0 and vk∈F2m, 0≤k≤t−1; //splitting v.
(35)
CallLRv, traversing each u and w; //where Cwi=Corv,w,u.
(36)
if i=r and Cw1+…+Cwi−1+Cwi=Bcr¯ then //the last round.
(37)
LetBcr=Bcr¯, break from LRv and return TRUE;
(38)
end if //r-round optimal linear trail of expected correlation weight Bcr¯ have been found.
(39)
y
′
=
y
⊕
w
⋘
r
b, x′=y′⊕u;
(40)
if call Round-r (i+1,x′,y′) and the return value is TRUE, then
(41)
Break fromLRv and return TRUE; //record the masks of each round and return.
(42)
end if
(43)
Return to the upper procedure with FALSE state;
(44)
LR
v: //looking up cLAT and recombining another input mask w and the output mask u.
(45)
Letckmin=mincLATminvk0,cLATminvk1, and bk=0, for 0≤k≤t−1;
(46)
for k=t−1 to 0 do //from MSB to LSB direction.
(47)
for cik=cLATminvkbk to cik¯ do //cit−1¯=m−1 and cik¯=m for 0≤k≤t−2.
(48)
if ∑g=1i−1Cwg+∑j=0k−1cjmin + then ∑l=kt−1cil + Bcr−i≤Bcr¯
(49)
for Xk=0 to cLATNvt−1bkcik−1 do
(50)
uk=cLATuvkbkXk; //querying uk and wk.
(51)
wk=cLATwvkbkXk;
(52)
bk−1=cLATbukvkwkbk; //record the next connection status.
(53)
if k=0 then //recombining u and w.
(54)
Output eachu=ut−1⋯u0, w=wt−1⋯w0, and Cwi=∑k=0t−1cik;
(55)
end if
(56)
end for
(57)
end if
(58)
end for
(59)
end forLet the optimal correlation weight of ther−ith round that has been obtained be Bcr−i, 1≤i≤r−1, and let the expected r-round correlation weight be Bcr¯. The correlation weight of the first two rounds should subject to Matsui’s pruning condition, i.e., Cw1+Bcr−1≤Bcr¯ and Cw1+Cw2+Bcr−2≤Bcr¯.Let∑i=1NA′Cwi=Bcr¯−Bcr−1, NA′ is the number of additions in the first two rounds, and then the search space need to be constructed is no more than (19). When the block size of a ARX cipher is large, let n be the word size of the modular addition, the total input-output masks of all NA′ modular additions in the first two round is S′=23n×NA′. Therefore, when the value of Bcr¯−Bcr−1 is small, the search space S will be much smaller than S′ intuitively:(19)S=∏i=1NA′∑c=0Cwi#u,v,w−log2Coru,v,w=c.


## 3.5. Flexible Search Scenario Settings

Combining Algorithm1, cLAT, pruning conditions, and the properties of the target ciphers in Section 2.3, Algorithm 3 can be adapted to the following search scenarios with appropriate modifications:Scenario 1: for some ARX ciphers, such as SPARX and Chaskey, the number of modular additions in the round function is more than 1, NA>1. Hence, the correlation weight of each round is Cwi=∑j=1NACwij, and Cwij is the correlation weight of the jth addition in the ith round. In the first/second round, the input-output masks of each modular addition should be generated by Algorithm 1. In the middle rounds, the tuple (u,w) of each modular addition should be obtained by calling LRv multiple times.Scenario 2: the linear hulls can also be searched by simply modifying Algorithm 3. For an obtained optimal linear trail, fix the input mask of the first round and the output mask of the last round, call round-r (i,x,y) directly, and modify Bcr¯ to the expected maximum statistical correlation weight Cmax. Therefore, for ALP, all linear trails with linear correlation weight between the optimal correlation weight Cmin and Cmax can be counted.Scenario 3: when the number of rounds of a linear trail or the block size is large, the linear correlation tends to be very small, and the search process will be very time-consuming. Hence, good linear characteristic results under certain conditions can be explored by the heuristic search settings. We can exclude a large number of search branches and reduce the search complexity by these methods, such as starting the search from a desired large correlation weight Bcr¯, fixing the input mask of a certain round, and limiting the correlation weight of a round or a certain modular addition.


## 4. Applied to SPECK, SPARX, Chaskey, and CHAM-64

### 4.1. Linear Hulls for SPECK32/48/64

Applying Algorithm3, the optimal linear trails for SPECK32/48/64 with correlation close to 2−n/2 can be obtained, shown in Table 2. Fixing the input and output masks, the ALP of the linear hulls obtained by the cluster experiment are given in Table 3. For SPECK64, new 14-round linear hull with an average linear potential of 2−61.24 has been found.Table 2
The 9/10/13 round optimal linear trails for SPECK32/48/64.
r
SPECK32
SPECK48
SPECK64
Γ
X
r
C
w
r
Γ
X
r
C
w
r
Γ
X
r
C
w
r
0
00A0062 F
1
000180B80001
1
0100012014010021
2
1
78B818B9
4
000000C00001
0
0001810020000101
1
2
00906021
1
00000E00000 E
2
0000010000000001
0
3
60804081
1
7A0070700070
5
0000000100000000
1
4
00800001
0
C2C080829380
6
0D0000000C000000
2
5
00010000
1
D00000108300
2
60610000606C0000
3
6
0B000800
3
800000809800
1
00024D0300620C03
6
7
20402050
2
00000400C004
1
181070141B107358
6
8
008380C3
1
200020260020
2
0013001818031840
3
9
170B130A
—
013100310100
2
1818000000181200
2
10
8800A8880109
—
0018000000001000
1
11
0000100000000000
1
12
0000009800000080
2
13
5000040480000404
—Table 3
Linear hulls for SPECK32/48/64.
2n
r
Γ
in
Γ
out
C
min
C
max
ALP
No. of trails
Time
Reference
32
9
0010, 1400
0B00, 0800
15
25
2
−
29.1
69737
N/A
[18]
9
0380, 5224
066A, 0608
14
14
2
−
28
1
N/A
[16]
9
00A0, 062F
170B, 130A
14
20
2
−
27.78
14
25 s
This paper
48
10
000131, 050021
2484F2, 2480F6
22
N/A
2
−
44
1
N/A
[16]
10
800121, 158021
DE84DC, C684DC
22
N/A
2
−
44
1
N/A
[18]
10
000180, B80001
8800A8, 880109
22
28
2
−
43.64
50
157.3 h
This paper
64
13
18600010, 10724800
00024982, 00420802
30
30
2
−
60
1
N/A
[16]
13
00101800, 00001812
00006065, 00006068
30
30
2
−
60
1
N/A
[18]
13
01000120, 14010021
50000404, 80000404
30
32
2
−
55.29
178
7.3 h
This paper
14
01000120, 14010021
26902000, 20802006
33
35
2
−
61.24
194
5.8 h
This paper
All experiment code in this work are run on a single high-performance server with Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40 GHz. All masks are represented in hexadecimal.When searching for the linear hulls, we need to modify Algorithm3 to adapt to Scenario 2. We use formula (13) to count ALP, where Cmin≤Cw≤Cmax, Cmin is the correlation weight of the linear trail we choose to use to pin the input and output masks, and Cmax is the maximum correlation weight we limit our search. In the middle rounds, we adopt Cmax to instead Bcr¯ for filtering out those trails that contribute less to the ALP.


### 4.2. Linear Characteristics for SPARX

Searching for the optimal linear trails of SPARX variants, Algorithm3 needs to be modified to fit Scenario 1. There are multiple modular additions in each round, NA=2 for SPARX-64 and NA=4 for SPARX-128. Hence, for all 2NA additions modulo 216 in the first/second rounds, call Algorithm 1 for each addition to generate its input-output mask tuples, and then apply Property 3/4 to obtain the masks of the first two rounds for SPARX-64 and SPARX-128, respectively. In the middle rounds, the Splitting-Lookup-Recombination method is applied to obtain possible input masks and output masks of each addition, as well as correlation weight. The 10-round optimal linear trails for SPARX-64 are listed in Table 4, and the 11-round linear trail is obtained by limiting the correlation weight of each modular addition less than 3 in the first two rounds. Fixing the input and output mask of the 10-round optimal linear trail, a 10-round linear hull with an ALP of 2−40.92 is obtained.Table 4
Linear characteristics for SPARX-64.
r
C
w
T
trail
Γ
in
Γ
out
C
min
C
max
ALP
No. of trails
T
ALP
1
0
0 s
0000
0000
0080
4001
0000
0000
0000
0001
0
0
1
1
0 s
2
0
0 s
0000
0000
0080
4001
0000
0000
0004
0004
0
0
1
1
0 s
3
1
0 s
0000
0000
0080
4001
2C10
2010
2C1C
201C
1
10
2
−
2
1
0 s
4
3
0 s
0090
6021
0000
0000
0000
0000
0B00
0800
3
10
2
−
6
1
0 s
5
5
0 s
00A0
3021
0000
0000
0000
0000
85C2
8442
5
10
2
−
9.98
3
3 s
6
7
0 s
0080
5021
0000
0000
4285
4284
4385
4384
7
15
2
−
13.91
11
22 s
7
11
3.2 m
0090
6021
0000
0000
170B
130A
17CF
130F
11
17
2
−
21.87
5
9 s
8
15
4.6 h
0880
503D
0090
6021
0000
0000
0E81
1EB0
15
20
2
−
29.73
22
2 m
9
19
48.6 h
0080
5021
2000
0058
2058
2040
3858
3840
19
25
2
−
35.97
1215
28.7 h
10
22
3 d
0080
4001
00C0
F001
0205
0204
0205
0204
22
25
2
−
40.92
144
1 h
11
≤
28
5 m
0080
4001
00C0
F001
38A8
2080
2058
2040
28
28
2
−
56
1
—For SPARX-128, the first 8-round optimal linear trails can be derived from the first 8-round optimal linear trails of SPECK32 when considering the minimum active ARX-box. The experiment results in Table5 confirmed the derivation. Based on Scenario 3, we limit the correlation weight of each modular addition in the first/second round to less than 2, then we get the 9/10-round linear trails with a correlation weight of 18/23. Although the 9/10-round linear trail cannot be guaranteed as the best, they can still be used to get the 9/10-round linear hulls with the corresponding ALP of 2−35.22/2−46.Table 5
Linear characteristics for SPARX-128.
r
C
w
T
trail
Γ
in
Γ
out
C
min
C
max
ALP
No. of trails
T
hull
1
0
0 s
0000000000000000
0000000000000000
0000000000804001
0000000000000001
0
0
1
1
0 s
2
0
0 s
0000000000000000
0000000000000000
0000000000804001
0000000000040004
0
0
1
1
0 s
3
1
0 s
0000000000000000
0000000000000000
0000000000804001
000000002C102010
1
3
2
−
2
1
0 s
4
3
0 s
0000000000000000
000000000B000800
0000000000906021
0B03000300030803
3
10
2
−
6
1
0 s
5
5
2 s
0000000000A03021
0000000000000000
0000000000000000
0000000085C28442
5
10
2
−
9.98
3
0 s
6
7
1 s
0000000000805021
0000000000000000
0000000000000000
0000000042854284
7
12
2
−
13.91
3
1 s
7
9
4 s
0000000000906021
0000000000000000
0000000000000000
00000000170B130A
9
15
2
−
17.78
5
13 s
8
12
13 d
0000000000811381
00000000170B130A
0000000000000000
160F01040104120E
12
18
2
−
23.65
11
101 s
9
≥
14
—
0000000000004020
0000000002150012
≤
18
27 m
0000000000000000
081308140A060806
18
22
2
−
35.22
53
6 h
10
≥
18
—
0000000000804001
000000000B810800
≤
23
4.4 d
0000000000000000
09840A0402050204
23
23
2
−
46
1
—The 11/10-round linear trails for SPARX-64/SPARX-128 are given by Table6. cjr represents the correlation weight of the jth modular addition in the rth round, and Cwr represents the correlation weight of the rth round, 0≤j<NA.Table 6
The 11/10-round linear trails for SPARX-64/SPARX-128.
11-round trail for SPARX-64
10-round trail for SPARX-128
r
Γ
X
0
r
⋯
Γ
X
0
r
c
0
r
c
1
r
C
w
r
r
Γ
X
0
r
Γ
X
1
r
⋯
Γ
X
6
r
Γ
X
7
r
c
0
r
c
1
r
c
2
r
c
3
r
C
w
r
1
0080400100C0F001
0
1
1
1
00000000000402000000000000000000
0
0
0
0
0
2
000000010000C001
0
0
0
2
00000000081008100000000000000000
0
1
0
0
1
3
0004000400070007
1
2
3
3
000000000C010E000000000000000000
0
3
0
0
3
ℒ
2C1020102C1C201 C
—
—
—
4
00000000364834500000000000000000
0
5
0
0
5
4
2C1C201C00000000
4
0
4
ℒ
′
00000000008A90E20000000000000000
—
—
—
—
—
5
3140013000000000
3
0
3
5
000000000000000000000000008A90E2
0
0
0
2
2
6
858D05CF00000000
4
0
4
6
000000000000000000000000078F138E
0
0
0
4
4
ℒ
60117B1800000000
—
—
—
7
000000000000000000000000000E1600
0
0
0
2
2
7
0000000060117B18
0
4
4
8
00000000000000000000000000001800
0
0
0
0
0
8
0000000000812261
0
3
3
ℒ
′
00000000000000000000000060006000
—
—
—
—
—
9
0000000080018280
0
1
1
9
00000000600060006000000000006000
0
1
1
0
2
ℒ
0000000000020202
—
—
—
10
00000000828182010280020080018001
0
2
1
1
4
10
0002020200000200
1
0
1
11
0000000002150012081308140A060806
—
—
—
—
—
11
1E08180808000800
3
1
4
12
38A8208020582040
—
—
—


### 4.3. Linear Characteristics for Chaskey

From Table7, the correlation weights of the first 3-round optimal linear trails of Chaskey we have found are 0/2/9. For one-round optimal linear trail with a correlation weight of 0, input-output masks represented in hexadecimal are (1, 1, 0, 0) and (0, 80, 800000, 0). To find the linear trails with longer rounds, we use a heuristic approach in Scenario 3, limiting the correlation weight of each modular additions in the first round to less than 2 and setting the correlation weight to the expected values to start the heuristic search. The 4/5-round linear trails with correlation weights of 29/61 are obtained. The details of the linear trails are listed in Table 8.Table 7
Correlation of the linear trails for Chaskey.
Round
1
2
3
4
5
Reference
Correlation
2
−
1
2
−
2
2
−
9
—
—
[18]
Correlation
1
2
−
2
2
−
9
≥
2
−
29
≥
2
−
61
This paperTable 8
Linear trails for Chaskey.
r
2 rounds withCor=2−2
3 rounds withCor=2−9
a
,
b
,
c
,
d
c
0
r
c
1
r
c
2
r
c
3
r
a
,
b
,
c
,
d
c
0
r
c
1
r
c
2
r
c
3
r
0
2000001, B100001, 1, 1
1
0
0
0
1, 8100001, 201, 303
0
1
0
1
1
0, 1, 0, 0
0
0
0
1
300, 1, 0, 0
5
0
0
0
2
300004, 1000, 10000000, 4
—
—
—
—
0, 10000, 1, 0
0
0
1
1
3
240030, 10008080, 81011000, 240000
—
—
—
—
r
4 rounds withCor=2−29
5 rounds withCor=2−61
a
,
b
,
c
,
d
c
0
r
c
1
r
c
2
r
c
3
r
a
,
b
,
c
,
d
c
0
r
c
1
r
c
2
r
c
3
r
0
0, 800, 90001, 10D0801
0
2
1
0
1, 8100001, 201, 303
0
1
0
1
1
0, 0, 1, 1
0
0
0
0
300, 1, 0, 0
5
0
0
0
2
0, 80, 810000, 0
0
2
3
1
0, 10000, 1, 0
0
0
1
1
3
18001A20, 80880040, 400189, 1A20
5
3
7
5
240030, 10008080, 81011000, 240000
4
4
6
6
4
2D224005, A83F0DA8, 2DA1C86D, 25004107
—
—
—
—
50E73286, 8241A0, 5161469B, 40D436A6
10
12
4
6
5
BAAE7E16, 76224512, 65104022, 3EA61E37
—
—
—
—


### 4.4. Linear Characteristics for CHAM-64

In the first 4 rounds of CHAM, the input-output mask tuples of each modular addition can be constructed by Algorithm1, and all input and output masks for the first 4 rounds are deduced by Property 5. In the forward search process, the Splitting-Lookup-Recombination approach is adopted to determine the possible unknown input masks and output masks for the modular addition in each round. In [7], for CHAM-64, a 34-round linear trail with a bias of ε=2−31 was given. The correlation weights of the optimal linear trails obtained by us are shown in Table 9. The correlation of the 34-round optimal linear trail we find is 2−31, and the details of the 35-round optimal linear trail with a correlation of 2−33 are listed in Table 10.Table 9
Correlation weights of the optimal linear trails for CHAM-64.
Round
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
C
w
0
0
0
0
0
0
0
1
2
3
3
4
5
6
7
9
10
12
14
16
17
18
20
21
22
23
25
26
26
26
27
28
29
31
33Table 10
35-round optimal linear trail for CHAM-64.
r
Γ
X
0
r
⋯
Γ
X
3
r
C
w
r
r
Γ
X
0
r
⋯
Γ
X
3
r
C
w
r
1
0000000000018000
0
19
0007010380C08000
1
2
0000000180000000
0
20
810080C080000700
2
3
0001800000000000
0
21
0001800007000201
0
4
0000000000000100
0
22
0000070002010100
0
5
0000000001000000
0
23
0700020101000000
2
6
0000010000000000
0
24
0001010000000006
0
7
0100000000000000
1
25
0000000000060002
0
8
00C0000000000001
1
26
0000000600020000
0
9
8000000000010100
1
27
0006000200000000
1
10
40000001010000C0
1
28
0000000000000400
0
11
0061010000C08000
1
29
0000000004000000
0
12
812000C080004100
4
30
0000040000000000
0
13
0041800041008201
1
31
0400000000000000
1
14
0030410082014100
3
32
0200000000000006
1
15
6500820141000060
3
33
0002000000060600
1
16
A0C1410000600047
3
34
0001000606000200
0
17
C080006000470103
2
35
0106060002000002
2
18
60000047010380C0
1
36
0682020000028401
—


## 4.1. Linear Hulls for SPECK32/48/64

Applying Algorithm3, the optimal linear trails for SPECK32/48/64 with correlation close to 2−n/2 can be obtained, shown in Table 2. Fixing the input and output masks, the ALP of the linear hulls obtained by the cluster experiment are given in Table 3. For SPECK64, new 14-round linear hull with an average linear potential of 2−61.24 has been found.Table 2
The 9/10/13 round optimal linear trails for SPECK32/48/64.
r
SPECK32
SPECK48
SPECK64
Γ
X
r
C
w
r
Γ
X
r
C
w
r
Γ
X
r
C
w
r
0
00A0062 F
1
000180B80001
1
0100012014010021
2
1
78B818B9
4
000000C00001
0
0001810020000101
1
2
00906021
1
00000E00000 E
2
0000010000000001
0
3
60804081
1
7A0070700070
5
0000000100000000
1
4
00800001
0
C2C080829380
6
0D0000000C000000
2
5
00010000
1
D00000108300
2
60610000606C0000
3
6
0B000800
3
800000809800
1
00024D0300620C03
6
7
20402050
2
00000400C004
1
181070141B107358
6
8
008380C3
1
200020260020
2
0013001818031840
3
9
170B130A
—
013100310100
2
1818000000181200
2
10
8800A8880109
—
0018000000001000
1
11
0000100000000000
1
12
0000009800000080
2
13
5000040480000404
—Table 3
Linear hulls for SPECK32/48/64.
2n
r
Γ
in
Γ
out
C
min
C
max
ALP
No. of trails
Time
Reference
32
9
0010, 1400
0B00, 0800
15
25
2
−
29.1
69737
N/A
[18]
9
0380, 5224
066A, 0608
14
14
2
−
28
1
N/A
[16]
9
00A0, 062F
170B, 130A
14
20
2
−
27.78
14
25 s
This paper
48
10
000131, 050021
2484F2, 2480F6
22
N/A
2
−
44
1
N/A
[16]
10
800121, 158021
DE84DC, C684DC
22
N/A
2
−
44
1
N/A
[18]
10
000180, B80001
8800A8, 880109
22
28
2
−
43.64
50
157.3 h
This paper
64
13
18600010, 10724800
00024982, 00420802
30
30
2
−
60
1
N/A
[16]
13
00101800, 00001812
00006065, 00006068
30
30
2
−
60
1
N/A
[18]
13
01000120, 14010021
50000404, 80000404
30
32
2
−
55.29
178
7.3 h
This paper
14
01000120, 14010021
26902000, 20802006
33
35
2
−
61.24
194
5.8 h
This paper
All experiment code in this work are run on a single high-performance server with Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40 GHz. All masks are represented in hexadecimal.When searching for the linear hulls, we need to modify Algorithm3 to adapt to Scenario 2. We use formula (13) to count ALP, where Cmin≤Cw≤Cmax, Cmin is the correlation weight of the linear trail we choose to use to pin the input and output masks, and Cmax is the maximum correlation weight we limit our search. In the middle rounds, we adopt Cmax to instead Bcr¯ for filtering out those trails that contribute less to the ALP.


## 4.2. Linear Characteristics for SPARX

Searching for the optimal linear trails of SPARX variants, Algorithm3 needs to be modified to fit Scenario 1. There are multiple modular additions in each round, NA=2 for SPARX-64 and NA=4 for SPARX-128. Hence, for all 2NA additions modulo 216 in the first/second rounds, call Algorithm 1 for each addition to generate its input-output mask tuples, and then apply Property 3/4 to obtain the masks of the first two rounds for SPARX-64 and SPARX-128, respectively. In the middle rounds, the Splitting-Lookup-Recombination method is applied to obtain possible input masks and output masks of each addition, as well as correlation weight. The 10-round optimal linear trails for SPARX-64 are listed in Table 4, and the 11-round linear trail is obtained by limiting the correlation weight of each modular addition less than 3 in the first two rounds. Fixing the input and output mask of the 10-round optimal linear trail, a 10-round linear hull with an ALP of 2−40.92 is obtained.Table 4
Linear characteristics for SPARX-64.
r
C
w
T
trail
Γ
in
Γ
out
C
min
C
max
ALP
No. of trails
T
ALP
1
0
0 s
0000
0000
0080
4001
0000
0000
0000
0001
0
0
1
1
0 s
2
0
0 s
0000
0000
0080
4001
0000
0000
0004
0004
0
0
1
1
0 s
3
1
0 s
0000
0000
0080
4001
2C10
2010
2C1C
201C
1
10
2
−
2
1
0 s
4
3
0 s
0090
6021
0000
0000
0000
0000
0B00
0800
3
10
2
−
6
1
0 s
5
5
0 s
00A0
3021
0000
0000
0000
0000
85C2
8442
5
10
2
−
9.98
3
3 s
6
7
0 s
0080
5021
0000
0000
4285
4284
4385
4384
7
15
2
−
13.91
11
22 s
7
11
3.2 m
0090
6021
0000
0000
170B
130A
17CF
130F
11
17
2
−
21.87
5
9 s
8
15
4.6 h
0880
503D
0090
6021
0000
0000
0E81
1EB0
15
20
2
−
29.73
22
2 m
9
19
48.6 h
0080
5021
2000
0058
2058
2040
3858
3840
19
25
2
−
35.97
1215
28.7 h
10
22
3 d
0080
4001
00C0
F001
0205
0204
0205
0204
22
25
2
−
40.92
144
1 h
11
≤
28
5 m
0080
4001
00C0
F001
38A8
2080
2058
2040
28
28
2
−
56
1
—For SPARX-128, the first 8-round optimal linear trails can be derived from the first 8-round optimal linear trails of SPECK32 when considering the minimum active ARX-box. The experiment results in Table5 confirmed the derivation. Based on Scenario 3, we limit the correlation weight of each modular addition in the first/second round to less than 2, then we get the 9/10-round linear trails with a correlation weight of 18/23. Although the 9/10-round linear trail cannot be guaranteed as the best, they can still be used to get the 9/10-round linear hulls with the corresponding ALP of 2−35.22/2−46.Table 5
Linear characteristics for SPARX-128.
r
C
w
T
trail
Γ
in
Γ
out
C
min
C
max
ALP
No. of trails
T
hull
1
0
0 s
0000000000000000
0000000000000000
0000000000804001
0000000000000001
0
0
1
1
0 s
2
0
0 s
0000000000000000
0000000000000000
0000000000804001
0000000000040004
0
0
1
1
0 s
3
1
0 s
0000000000000000
0000000000000000
0000000000804001
000000002C102010
1
3
2
−
2
1
0 s
4
3
0 s
0000000000000000
000000000B000800
0000000000906021
0B03000300030803
3
10
2
−
6
1
0 s
5
5
2 s
0000000000A03021
0000000000000000
0000000000000000
0000000085C28442
5
10
2
−
9.98
3
0 s
6
7
1 s
0000000000805021
0000000000000000
0000000000000000
0000000042854284
7
12
2
−
13.91
3
1 s
7
9
4 s
0000000000906021
0000000000000000
0000000000000000
00000000170B130A
9
15
2
−
17.78
5
13 s
8
12
13 d
0000000000811381
00000000170B130A
0000000000000000
160F01040104120E
12
18
2
−
23.65
11
101 s
9
≥
14
—
0000000000004020
0000000002150012
≤
18
27 m
0000000000000000
081308140A060806
18
22
2
−
35.22
53
6 h
10
≥
18
—
0000000000804001
000000000B810800
≤
23
4.4 d
0000000000000000
09840A0402050204
23
23
2
−
46
1
—The 11/10-round linear trails for SPARX-64/SPARX-128 are given by Table6. cjr represents the correlation weight of the jth modular addition in the rth round, and Cwr represents the correlation weight of the rth round, 0≤j<NA.Table 6
The 11/10-round linear trails for SPARX-64/SPARX-128.
11-round trail for SPARX-64
10-round trail for SPARX-128
r
Γ
X
0
r
⋯
Γ
X
0
r
c
0
r
c
1
r
C
w
r
r
Γ
X
0
r
Γ
X
1
r
⋯
Γ
X
6
r
Γ
X
7
r
c
0
r
c
1
r
c
2
r
c
3
r
C
w
r
1
0080400100C0F001
0
1
1
1
00000000000402000000000000000000
0
0
0
0
0
2
000000010000C001
0
0
0
2
00000000081008100000000000000000
0
1
0
0
1
3
0004000400070007
1
2
3
3
000000000C010E000000000000000000
0
3
0
0
3
ℒ
2C1020102C1C201 C
—
—
—
4
00000000364834500000000000000000
0
5
0
0
5
4
2C1C201C00000000
4
0
4
ℒ
′
00000000008A90E20000000000000000
—
—
—
—
—
5
3140013000000000
3
0
3
5
000000000000000000000000008A90E2
0
0
0
2
2
6
858D05CF00000000
4
0
4
6
000000000000000000000000078F138E
0
0
0
4
4
ℒ
60117B1800000000
—
—
—
7
000000000000000000000000000E1600
0
0
0
2
2
7
0000000060117B18
0
4
4
8
00000000000000000000000000001800
0
0
0
0
0
8
0000000000812261
0
3
3
ℒ
′
00000000000000000000000060006000
—
—
—
—
—
9
0000000080018280
0
1
1
9
00000000600060006000000000006000
0
1
1
0
2
ℒ
0000000000020202
—
—
—
10
00000000828182010280020080018001
0
2
1
1
4
10
0002020200000200
1
0
1
11
0000000002150012081308140A060806
—
—
—
—
—
11
1E08180808000800
3
1
4
12
38A8208020582040
—
—
—


## 4.3. Linear Characteristics for Chaskey

From Table7, the correlation weights of the first 3-round optimal linear trails of Chaskey we have found are 0/2/9. For one-round optimal linear trail with a correlation weight of 0, input-output masks represented in hexadecimal are (1, 1, 0, 0) and (0, 80, 800000, 0). To find the linear trails with longer rounds, we use a heuristic approach in Scenario 3, limiting the correlation weight of each modular additions in the first round to less than 2 and setting the correlation weight to the expected values to start the heuristic search. The 4/5-round linear trails with correlation weights of 29/61 are obtained. The details of the linear trails are listed in Table 8.Table 7
Correlation of the linear trails for Chaskey.
Round
1
2
3
4
5
Reference
Correlation
2
−
1
2
−
2
2
−
9
—
—
[18]
Correlation
1
2
−
2
2
−
9
≥
2
−
29
≥
2
−
61
This paperTable 8
Linear trails for Chaskey.
r
2 rounds withCor=2−2
3 rounds withCor=2−9
a
,
b
,
c
,
d
c
0
r
c
1
r
c
2
r
c
3
r
a
,
b
,
c
,
d
c
0
r
c
1
r
c
2
r
c
3
r
0
2000001, B100001, 1, 1
1
0
0
0
1, 8100001, 201, 303
0
1
0
1
1
0, 1, 0, 0
0
0
0
1
300, 1, 0, 0
5
0
0
0
2
300004, 1000, 10000000, 4
—
—
—
—
0, 10000, 1, 0
0
0
1
1
3
240030, 10008080, 81011000, 240000
—
—
—
—
r
4 rounds withCor=2−29
5 rounds withCor=2−61
a
,
b
,
c
,
d
c
0
r
c
1
r
c
2
r
c
3
r
a
,
b
,
c
,
d
c
0
r
c
1
r
c
2
r
c
3
r
0
0, 800, 90001, 10D0801
0
2
1
0
1, 8100001, 201, 303
0
1
0
1
1
0, 0, 1, 1
0
0
0
0
300, 1, 0, 0
5
0
0
0
2
0, 80, 810000, 0
0
2
3
1
0, 10000, 1, 0
0
0
1
1
3
18001A20, 80880040, 400189, 1A20
5
3
7
5
240030, 10008080, 81011000, 240000
4
4
6
6
4
2D224005, A83F0DA8, 2DA1C86D, 25004107
—
—
—
—
50E73286, 8241A0, 5161469B, 40D436A6
10
12
4
6
5
BAAE7E16, 76224512, 65104022, 3EA61E37
—
—
—
—


## 4.4. Linear Characteristics for CHAM-64

In the first 4 rounds of CHAM, the input-output mask tuples of each modular addition can be constructed by Algorithm1, and all input and output masks for the first 4 rounds are deduced by Property 5. In the forward search process, the Splitting-Lookup-Recombination approach is adopted to determine the possible unknown input masks and output masks for the modular addition in each round. In [7], for CHAM-64, a 34-round linear trail with a bias of ε=2−31 was given. The correlation weights of the optimal linear trails obtained by us are shown in Table 9. The correlation of the 34-round optimal linear trail we find is 2−31, and the details of the 35-round optimal linear trail with a correlation of 2−33 are listed in Table 10.Table 9
Correlation weights of the optimal linear trails for CHAM-64.
Round
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
C
w
0
0
0
0
0
0
0
1
2
3
3
4
5
6
7
9
10
12
14
16
17
18
20
21
22
23
25
26
26
26
27
28
29
31
33Table 10
35-round optimal linear trail for CHAM-64.
r
Γ
X
0
r
⋯
Γ
X
3
r
C
w
r
r
Γ
X
0
r
⋯
Γ
X
3
r
C
w
r
1
0000000000018000
0
19
0007010380C08000
1
2
0000000180000000
0
20
810080C080000700
2
3
0001800000000000
0
21
0001800007000201
0
4
0000000000000100
0
22
0000070002010100
0
5
0000000001000000
0
23
0700020101000000
2
6
0000010000000000
0
24
0001010000000006
0
7
0100000000000000
1
25
0000000000060002
0
8
00C0000000000001
1
26
0000000600020000
0
9
8000000000010100
1
27
0006000200000000
1
10
40000001010000C0
1
28
0000000000000400
0
11
0061010000C08000
1
29
0000000004000000
0
12
812000C080004100
4
30
0000040000000000
0
13
0041800041008201
1
31
0400000000000000
1
14
0030410082014100
3
32
0200000000000006
1
15
6500820141000060
3
33
0002000000060600
1
16
A0C1410000600047
3
34
0001000606000200
0
17
C080006000470103
2
35
0106060002000002
2
18
60000047010380C0
1
36
0682020000028401
—


## 5. Conclusions

In this paper, we have improved the automatic search algorithm for the linear characteristics on ARX ciphers. Combining with the optimization strategies of constructing the input-output masks corresponding to specific correlation weight and the novel concept of cLAT, this search tool enables an efficient search for the linear characteristics on typical ARX ciphers. Applying this tool, we get new 9/10/14-round linear hulls for SPECK32/48/64, and theALP is 2−27.78, 2−43.64, and 2−61.24, respectively. For SPARX-64, a 10-round optimal linear trail with a correlation of 2−22 and a 11-round good linear trail with a correlation of 2−28 have been obtained. For SPARX-128, a 10-round linear trail with a correlation of 2−23 is obtained. The linear cryptanalysis results on SPARX are presented for the first time so far. For Chaskey, the linear characteristic results have been updated, which cover more rounds than the existing results. For CHAM-64, the linear characteristics we obtained are the first third-party linear cryptanalysis results. In addition, we believe that these improved optimization strategies can also be achieved by linear cryptanalysis on other ARX ciphers.



---

*Source: 4898612-2020-01-21.xml*