# Algebraic Degree Estimation of ACORN v3 Using Numeric Mapping

Authors: Lin Ding; Lei Wang; Dawu Gu; Chenhui Jin; Jie Guan
Journal: Security and Communication Networks
 (2019)

---

## Abstract

ACORN v3 is a lightweight authenticated encryption cipher, which was selected as one of the seven finalists of CAESAR competition in March 2018. It is intended for lightweight applications (resource-constrained environments). By using the technique numeric mapping proposed at CRYPTO 2017, an efficient algorithm for algebraic degree estimation of ACORN v3 is proposed. As a result, new distinguishing attacks on 647, 649, 670, 704, and 721 initialization rounds of ACORN v3 are obtained, respectively. So far, as we know, all of our distinguishing attacks on ACORN v3 are the best. The effectiveness and accuracy of our algorithm is confirmed by the experimental results.


---

## Body

## 1. Introduction

ACORN, which is known as ACORN v1 [1], is a lightweight authenticated encryption cipher which had been submitted to the CAESAR (Competition for Authenticated Encryption: Security, Applicability, and Robustness) competition [2] in 2014. The structure is based on nonlinear feedback shift register. Later, with minor modifications, it was updated as ACORN v2 [3] and ACORN v3 [4] by enhancing the security. In March 2018, ACORN v3 was selected as one of seven finalists of CAESAR competition. In February 2019, ACORN v3 was listed into the final CAESAR portfolio and recommended for the use case of lightweight applications (resource constrained environments). The state size of ACORN v3 is 293 bits. It uses a 128-bit key and a 128-bit initialization vector. The initialization of ACORN v3 consists of loading the key and IV into the state and running the cipher for 1792 steps.


### 1.1. Previous Attacks on ACORN

In 2014, Wu had submitted an authenticated encryption cipher, known as ACORN v1 to CAESAR competition. After then, some attacks on ACORN v1 and its tweaked version ACORN v2 were presented in [5–11]. Besides these attacks, a cube attack on 477 rounds of ACORN v2 was proposed in [12] to recover the 128-bit key with a total attack complexity of 235, and when the goal is to recover one bit of the secret key, 503 rounds of ACORN v2 were attacked. Later, the authenticated encryption cipher was updated as ACORN v3 with minor modifications by enhancing the security.Until now, several attacks on ACORN v3 have been published in [13–16]. However, there are no attacks better than exhaustive key search on ACORN v3 so far. Based on cube testers and d-monomial test, Ghafari and Hu proposed a new attack framework in [17, 18] and presented a practical distinguishing attack on 676 rounds of ACORN v3 with time complexity of 200×233. This has been the best-known distinguishing attack on the round reduced variants of ACORN v3 so far. Recently, some key recovery attacks on ACORN v3 had been proposed. At CRYPTO 2017, Todo et al. [19] proposed possible key recovery attacks on 647, 649, and 704 rounds of ACORN v3, where no more than one bit of the secret key can be recovered with unknown probability in around 278, 2109, and 2122, respectively. The attack was improved by Wang et al. in [20, 21].


### 1.2. Numeric Mapping

At CRYPTO 2017, Liu [22] exploited a new technique, called numeric mapping, to iteratively estimate the upper bound on the algebraic degree of the internal states of an NFSR. Based on this new technique, he developed an algorithm for estimating the algebraic degree of NFSR-based cryptosystems and gave distinguishing attacks on Trivium-like ciphers, including Trivium, Kreyvium, and TriviA-SC as applications.


### 1.3. Our Contributions

In this paper, we focus on proposing an efficient algorithm for algebraic degree estimation of ACORN v3. By applying our algorithm, we investigate the mixing efficiency of ACORN v3. When taking all the key and IV bits as initial input variables, the result shows that the lower bound on the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is 669 (out of 1792). When taking all the IV bits as input variables, the result shows that the lower bound on the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is 708 (out of 1792). When taking a subset of all the IV bits as initial input variables, we apply our algorithm to ACORN v3 to exploit new distinguishing attacks. Some distinguishing attacks on round reduced variants of ACORN v3 we have obtained are listed in Table1, and comparisons with previous works are made. As shown in Table 1, our results are the best-known distinguishing attacks on the cipher so far. Note that three key recovery attacks on the cipher in [19–21] are also listed in Table 1. In these attacks, the recovered secret variables are generally smaller than 1 bit, while the time complexities are significantly high. Because of the high time complexities, these attacks are impractical and cannot be verified by experiments, and the success probabilities of key recovery are difficult to estimate as they are based on some assumptions. Compared with them, our attacks have significantly better time complexities. Meanwhile, our attacks are deterministic rather than statistical, that is, our attacks hold with probability 1.Table 1
Attacks on ACORN v3.
Cipher
# rounds
Attack
Time complexity
Reference
ACORN v3
647
Key recovery attack
2
78
[19]
647
Distinguishing attack
2
21
Sect. 4.3
649
Key recovery attack
2
109
[19]
649
Distinguishing attack
2
24
Sect. 4.3
676
Distinguishing attack
200
×
2
33
≈
2
40.64
[17]
676
Distinguishing attack
2
36
Sect. 4.3
704
Key recovery attack
2
122
[19]
704
Key recovery attack
2
77.88
[20]
704
Distinguishing attack
2
61
Sect. 4.3
721
Distinguishing attack
2
95
Sect. 4.3
750
Key recovery attack
2
125.71
[21]
750
Key recovery attack
2
120.92
[20]To verify these cryptanalytic results, we make an amount of experiments on round reduced variants of ACORN v3. The experimental results show that our distinguishing attacks are always consistent with our evaluated results. They are strong evidences of high accuracy of our algorithm.This paper is organized as follows. Some notations are defined and the technique numeric mapping is introduced in Section2. In Section 3, algebraic degree estimation of ACORN v3 is presented. The paper is concluded in Section 4.


## 1.1. Previous Attacks on ACORN

In 2014, Wu had submitted an authenticated encryption cipher, known as ACORN v1 to CAESAR competition. After then, some attacks on ACORN v1 and its tweaked version ACORN v2 were presented in [5–11]. Besides these attacks, a cube attack on 477 rounds of ACORN v2 was proposed in [12] to recover the 128-bit key with a total attack complexity of 235, and when the goal is to recover one bit of the secret key, 503 rounds of ACORN v2 were attacked. Later, the authenticated encryption cipher was updated as ACORN v3 with minor modifications by enhancing the security.Until now, several attacks on ACORN v3 have been published in [13–16]. However, there are no attacks better than exhaustive key search on ACORN v3 so far. Based on cube testers and d-monomial test, Ghafari and Hu proposed a new attack framework in [17, 18] and presented a practical distinguishing attack on 676 rounds of ACORN v3 with time complexity of 200×233. This has been the best-known distinguishing attack on the round reduced variants of ACORN v3 so far. Recently, some key recovery attacks on ACORN v3 had been proposed. At CRYPTO 2017, Todo et al. [19] proposed possible key recovery attacks on 647, 649, and 704 rounds of ACORN v3, where no more than one bit of the secret key can be recovered with unknown probability in around 278, 2109, and 2122, respectively. The attack was improved by Wang et al. in [20, 21].


## 1.2. Numeric Mapping

At CRYPTO 2017, Liu [22] exploited a new technique, called numeric mapping, to iteratively estimate the upper bound on the algebraic degree of the internal states of an NFSR. Based on this new technique, he developed an algorithm for estimating the algebraic degree of NFSR-based cryptosystems and gave distinguishing attacks on Trivium-like ciphers, including Trivium, Kreyvium, and TriviA-SC as applications.


## 1.3. Our Contributions

In this paper, we focus on proposing an efficient algorithm for algebraic degree estimation of ACORN v3. By applying our algorithm, we investigate the mixing efficiency of ACORN v3. When taking all the key and IV bits as initial input variables, the result shows that the lower bound on the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is 669 (out of 1792). When taking all the IV bits as input variables, the result shows that the lower bound on the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is 708 (out of 1792). When taking a subset of all the IV bits as initial input variables, we apply our algorithm to ACORN v3 to exploit new distinguishing attacks. Some distinguishing attacks on round reduced variants of ACORN v3 we have obtained are listed in Table1, and comparisons with previous works are made. As shown in Table 1, our results are the best-known distinguishing attacks on the cipher so far. Note that three key recovery attacks on the cipher in [19–21] are also listed in Table 1. In these attacks, the recovered secret variables are generally smaller than 1 bit, while the time complexities are significantly high. Because of the high time complexities, these attacks are impractical and cannot be verified by experiments, and the success probabilities of key recovery are difficult to estimate as they are based on some assumptions. Compared with them, our attacks have significantly better time complexities. Meanwhile, our attacks are deterministic rather than statistical, that is, our attacks hold with probability 1.Table 1
Attacks on ACORN v3.
Cipher
# rounds
Attack
Time complexity
Reference
ACORN v3
647
Key recovery attack
2
78
[19]
647
Distinguishing attack
2
21
Sect. 4.3
649
Key recovery attack
2
109
[19]
649
Distinguishing attack
2
24
Sect. 4.3
676
Distinguishing attack
200
×
2
33
≈
2
40.64
[17]
676
Distinguishing attack
2
36
Sect. 4.3
704
Key recovery attack
2
122
[19]
704
Key recovery attack
2
77.88
[20]
704
Distinguishing attack
2
61
Sect. 4.3
721
Distinguishing attack
2
95
Sect. 4.3
750
Key recovery attack
2
125.71
[21]
750
Key recovery attack
2
120.92
[20]To verify these cryptanalytic results, we make an amount of experiments on round reduced variants of ACORN v3. The experimental results show that our distinguishing attacks are always consistent with our evaluated results. They are strong evidences of high accuracy of our algorithm.This paper is organized as follows. Some notations are defined and the technique numeric mapping is introduced in Section2. In Section 3, algebraic degree estimation of ACORN v3 is presented. The paper is concluded in Section 4.


## 2. Preliminaries

### 2.1. Notations

LetF2=0,1 be the finite field with two elements. Denote F2n the n-dimension vector space over the binary field F2. Let Bn be the set of all n-variable Boolean functions mapping from F2n into F2, and let f∈Bn. The algebraic normal form (ANF) of the given Boolean function f over n variables x1,x2,…,xn can be uniquely expressed as(1)fx1,x2,…,xn=⊕c=c1,c2,…,cn∈F2nac∏i=1nxici,where the coefficient ac is a constant in F2 and ci denotes the i-th digit of the binary encoding of c (and so the sum spans all monomials in x1,x2,…,xn). The algebraic degree of f, denoted by degf, is defined as maxwtcac=1, where wtc is the Hamming weight of c. Thus, for a multivariate Boolean function, the degree of a term is the sum of the exponents of the variables in the term, and then the algebraic degree of the multivariate Boolean function is the maximum of the degrees of all terms in the Boolean function.


### 2.2. Cube Attack and Cube Tester

Almost any cryptographic scheme can be described by tweakable polynomials over the binary fieldF2, which contain both secret variables (e.g., key bits) and public variables (e.g., IV bits). Cube attack, proposed by Dinur and Shamir [23] at EUROCRYPT 2009, is one of general and powerful cryptanalytic techniques against symmetric-key cryptosystems. It treats the output bit of a stream cipher as an unknown Boolean polynomial fk0,…,kn−1,v0,…,vm−1, where k0,…,kn−1 are secret key variables and v0,…,vm−1 are public IV variables. Given any monomial tI which is the product of variables in I=i1,…,id⊊0,1,…,m−1, f can be represented as the sum of terms which are supersets of I and terms that miss at least one variable from I:(2)fk0,…,kn−1,v0,…,vm−1=tI⋅pSI+qk0,…,kn−1,v0,…,vm−1,where pSI is called the superpoly of I in f and the set vi1,…,vid is called a cube. The idea behind cube attacks is that the sum of the Boolean polynomial fk0,…,kn−1,v0,…,vm−1 over the cube which contains all possible values for the cube variables is exactly pSI, while this is a random function for a random polynomial. In cube attacks, low-degree superpolys in secret variables are exploited to recover the key, while cube testers [24] work by distinguishing pSI from a random function. Especially, the superpoly pSI is equal to a zero constant, if the algebraic degree of f in the variables from I is smaller than the size of I. Thus, from the perspective of cube tester, estimation on algebraic degree of NFSR-based cryptosystems is an efficient way of constructing distinguishing attacks.


### 2.3. Numeric Mapping

At CRYPTO 2017, Liu [22] exploited a new technique, called numeric mapping, to iteratively estimate the upper bound on the algebraic degree of the internal states of an NFSR. Based on this new technique, he developed an algorithm for estimating the algebraic degree of NFSR-based cryptosystems. Let fx1,x2,…,xn=⊕c=c1,c2,…,cn∈F2nac∏i=1nxici. The numeric mapping, denoted by DEG, is defined as(3)DEG:Bn×ℤn⟶ℤ,f,D⟼maxac≠0∑i=1ncidi,where D=d1,d2,…,dn, ac’s are coefficients of algebraic normal form of f as defined previously, and denote ℤn the n-dimension vector space over the integer field ℤ. Let gi1≤i≤m be Boolean functions on n variables and denote degG=degg1,degg2,…,deggm for G=g1,g2,…,gm. We call DEGf,D a numeric degree of h if di≥deggi for all 1≤i≤n, where D=d1,d2,…,dn. The algebraic degree of h is always less than or equal to the numeric degree of h. The algebraic degrees of the output bits with respect to the internal states can be estimated iteratively for NFSR-based cryptosystems by using numeric mapping.


## 2.1. Notations

LetF2=0,1 be the finite field with two elements. Denote F2n the n-dimension vector space over the binary field F2. Let Bn be the set of all n-variable Boolean functions mapping from F2n into F2, and let f∈Bn. The algebraic normal form (ANF) of the given Boolean function f over n variables x1,x2,…,xn can be uniquely expressed as(1)fx1,x2,…,xn=⊕c=c1,c2,…,cn∈F2nac∏i=1nxici,where the coefficient ac is a constant in F2 and ci denotes the i-th digit of the binary encoding of c (and so the sum spans all monomials in x1,x2,…,xn). The algebraic degree of f, denoted by degf, is defined as maxwtcac=1, where wtc is the Hamming weight of c. Thus, for a multivariate Boolean function, the degree of a term is the sum of the exponents of the variables in the term, and then the algebraic degree of the multivariate Boolean function is the maximum of the degrees of all terms in the Boolean function.


## 2.2. Cube Attack and Cube Tester

Almost any cryptographic scheme can be described by tweakable polynomials over the binary fieldF2, which contain both secret variables (e.g., key bits) and public variables (e.g., IV bits). Cube attack, proposed by Dinur and Shamir [23] at EUROCRYPT 2009, is one of general and powerful cryptanalytic techniques against symmetric-key cryptosystems. It treats the output bit of a stream cipher as an unknown Boolean polynomial fk0,…,kn−1,v0,…,vm−1, where k0,…,kn−1 are secret key variables and v0,…,vm−1 are public IV variables. Given any monomial tI which is the product of variables in I=i1,…,id⊊0,1,…,m−1, f can be represented as the sum of terms which are supersets of I and terms that miss at least one variable from I:(2)fk0,…,kn−1,v0,…,vm−1=tI⋅pSI+qk0,…,kn−1,v0,…,vm−1,where pSI is called the superpoly of I in f and the set vi1,…,vid is called a cube. The idea behind cube attacks is that the sum of the Boolean polynomial fk0,…,kn−1,v0,…,vm−1 over the cube which contains all possible values for the cube variables is exactly pSI, while this is a random function for a random polynomial. In cube attacks, low-degree superpolys in secret variables are exploited to recover the key, while cube testers [24] work by distinguishing pSI from a random function. Especially, the superpoly pSI is equal to a zero constant, if the algebraic degree of f in the variables from I is smaller than the size of I. Thus, from the perspective of cube tester, estimation on algebraic degree of NFSR-based cryptosystems is an efficient way of constructing distinguishing attacks.


## 2.3. Numeric Mapping

At CRYPTO 2017, Liu [22] exploited a new technique, called numeric mapping, to iteratively estimate the upper bound on the algebraic degree of the internal states of an NFSR. Based on this new technique, he developed an algorithm for estimating the algebraic degree of NFSR-based cryptosystems. Let fx1,x2,…,xn=⊕c=c1,c2,…,cn∈F2nac∏i=1nxici. The numeric mapping, denoted by DEG, is defined as(3)DEG:Bn×ℤn⟶ℤ,f,D⟼maxac≠0∑i=1ncidi,where D=d1,d2,…,dn, ac’s are coefficients of algebraic normal form of f as defined previously, and denote ℤn the n-dimension vector space over the integer field ℤ. Let gi1≤i≤m be Boolean functions on n variables and denote degG=degg1,degg2,…,deggm for G=g1,g2,…,gm. We call DEGf,D a numeric degree of h if di≥deggi for all 1≤i≤n, where D=d1,d2,…,dn. The algebraic degree of h is always less than or equal to the numeric degree of h. The algebraic degrees of the output bits with respect to the internal states can be estimated iteratively for NFSR-based cryptosystems by using numeric mapping.


## 3. Algebraic Degree Estimation of ACORN v3

In this section, we first briefly give a description of ACORN v3 and then propose an efficient algorithm for algebraic degree estimation of ACORN v3 to exploit new distinguishing attacks on it.


### 3.1. Brief Description of ACORN v3

This section presents a brief description of the authenticated encryption cipher ACORN v3. The structure of ACORN v3 is shown in Figure1. The state size of ACORN v3 is 293 bits, denoted by St=s0t,s1t,…,s292t at t-th clock. It is constructed by using 6 LFSRs of different lengths 61, 46, 47, 39, 37, and 59 and one additional register of length 4. It supports a 128-bit key and a 128-bit initialization vector. As an authenticated encryption scheme, ACORN v3 passes through 4 procedures: initialization, processing the associated data, encryption, and finalization. In this paper, we only focus on the process of initialization, since the number of rounds we can attack is smaller than the 1792 initialization rounds. For more details about ACORN v3, we refer to [4].Figure 1
The structure of authenticated encryption cipher ACORN v3.The initialization of the authenticated encryption cipher ACORN v3 consists of loading the 128-bit key (k0,k1,…,k127) and 128-bit IV (iv0,iv1,…,iv127) into the state and running the cipher for 1792 steps.(1)
Initialize the stateS−1792 to 0(2)
Letm−1792+t=kt for t=0 to 127Letm−1792+128+t=ivt for t=0 to 127Letm−1792+256=ktmod128⊕1 for t=0Letm−1792+256+t=ktmod128 for t=1 to 1535(3)
Fort=−1792 to t=−1, St+1= StateUpdate128St,mt,cat,cbtAtt-th clock, the cipher executes the state update function: St+1=State−Update128St,mt,cat,cbt, which is given as follows:Step 1. Linear feedback updatest,289⟵st,289⊕st,235⊕st,230st,230⟵st,230⊕st,196⊕st,193st,193⟵st,193⊕st,160⊕st,154st,154⟵st,154⊕st,111⊕st,107st,107⟵st,107⊕st,66⊕st,61st,61⟵st,61⊕st,23⊕st,0Step 2. Generate keystream bitzt⟵st,12⊕st,154⊕st,235⋅st,61⊕st,235⋅st,193⊕st,61⋅st,193⊕st,230⋅st,111⊕st,230⊕1⋅st,66Step 3. Generate the nonlinear feedback bitft⟵st,0⊕st,107⊕1⊕st,244⋅st,23⊕st,244⋅st,160⊕st,23⋅st,160⊕st,230⊕ztStep 4. Shift the 293-bit register with the feedback bit ftst+1,i⟵st,i+1 for i=0,1,…,291st+1,292⟵ft⊕mt


### 3.2. Algorithm for Algebraic Degree Estimation of ACORN v3

In this section, we will propose an efficient algorithm for algebraic degree estimation of ACORN v3 using numeric mapping, as depicted in Algorithm1.Algorithm 1:Algebraic degree estimation of ACORN v3 using numeric mapping.
Require: Given the ANFs of the initial state S0=s0,0,s0,1,…,s0,292, the ANFs of the update function State Update128 and the keystream output function f, and the set of initial input variables X=x1,x2,…,x128.
(1)
SetD0 to degS0,X;
(2)
Fort from 1 to N do:
(3)
Dt⟵DEGState Update128St−1,Dt−1;
(4)
ComputeDEGf,DN;
(5)
ReturnDEGf,DN.Algorithm1 gives a numeric degree DEGf,X of the output function f after N rounds over initial input variables X=x1,x2,…,x128 as output, which gives an upper bound on the algebraic degree of the first output bit after N rounds.The time complexity of Algorithm1 mainly depends on the values of N and the ANFs of the update function State Update128. Since all of the update function State Update128 are shifting operations except one quadratic function and six linear functions, Algorithm 1 has a time complexity of ON. Algorithm 1 requires to store Dt for t=1,2,…,N. Since the number of initial input variables is constant for ACORN v3, it leads to a negligible memory complexity of ON.


### 3.3. Experimental Results

By using Algorithm1, we will investigate the mixing efficiency of ACORN v3 and exploit new distinguishing attacks on the cipher.


#### 3.3.1. When Will the Initial Input Variables Be Sufficiently Mixed?

By applying Algorithm1, we investigate the mixing efficiency of ACORN v3. When taking all the key and IV bits as initial input variables, the result shows that the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is at least 669 (out of 1792). When taking all the IV bits as input variables, the result shows that the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is at least 708 (out of 1792). The results are listed in Table 2. Note that both of these two results are lower bounds on the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree. In other words, the true maximum numbers of initialization rounds which do not achieve maximum algebraic degree could be higher.Table 2
Lower bound on the maximum number of rounds of not achieving maximum degree for ACORN v3 with initial input variablesX.
Cipher
X
=
K
,
IV
X
=
IV
#
key
+
#
IV
# rounds
#
IV
# rounds
ACORN v3
256
669
128
708Furthermore, we also take a subset of IV bits as initial input variablesX and apply Algorithm 1 to ACORN v3. Since the IV bits are sequentially loaded into the internal state in the second 128 initialization rounds, it is a natural and reasonable idea that we select the latter IV bits into the cube. We consider an exhaustive search on the subset ivp,ivp+1,…,iv127 of all 128 IV bits for all 1≤p≤127. Some results we have found are listed in Table 3. All these results are obtained on a common PC with 2.5 GHz Intel Pentium 4 processor within one second. In Table 3, the cube size d means that the cube iv128−d,iv128−d−1,…,iv127 is used in our attack. As for 676 rounds of ACORN v3, when d=36, the best result DEGf,X=35 is found, which leads to a practical distinguishing attack on it with time complexity of 236 and improves the previous distinguishing attack [17] by a factor of 24.64. Furthermore, the distinguishing advantage of our attack is 1, while the attack of [17] is based on limited chi-square statistical test and its distinguishing advantage is certainly smaller than 1. As for 721 rounds of ACORN v3, when d=95, the best result DEGf,X=94 is found, which leads to a distinguishing attack on it with time complexity of 295. This is the best result we have found. Clearly, our results are the best distinguishing attacks on round reduced variants of ACORN v3 so far. Note that all our attacks are deterministic rather than statistical, that is, our attacks hold with probability 1.Table 3
Our distinguishing attacks on round reduced variants of ACORN v3.
# rounds
Size of cubed
Cube
Time complexity
647
21
i
v
107
,
i
v
108
,
…
,
i
v
127
2
21
649
24
i
v
104
,
i
v
105
,
…
,
i
v
127
2
24
676
36
i
v
92
,
i
v
93
,
…
,
i
v
127
2
36
704
61
i
v
67
,
i
v
68
,
…
,
i
v
127
2
61
721
95
i
v
33
,
i
v
34
,
…
,
i
v
127
2
95


#### 3.3.2. Experiments

Since221, 224, and 236 in Table 3 are practical, we verify these results by carrying out a test for random 100 keys within half a day on a common PC with 2.5 GHz Intel Pentium 4 processor. All outputs of 647, 649, and 670 rounds of ACORN v3 over the cubes iv107,iv108,…,iv127, iv104,iv105,…,iv127 and iv93,iv94,…,iv127, respectively, always sum to 0. This clearly confirms the effectiveness and accuracy of our algorithm.


## 3.1. Brief Description of ACORN v3

This section presents a brief description of the authenticated encryption cipher ACORN v3. The structure of ACORN v3 is shown in Figure1. The state size of ACORN v3 is 293 bits, denoted by St=s0t,s1t,…,s292t at t-th clock. It is constructed by using 6 LFSRs of different lengths 61, 46, 47, 39, 37, and 59 and one additional register of length 4. It supports a 128-bit key and a 128-bit initialization vector. As an authenticated encryption scheme, ACORN v3 passes through 4 procedures: initialization, processing the associated data, encryption, and finalization. In this paper, we only focus on the process of initialization, since the number of rounds we can attack is smaller than the 1792 initialization rounds. For more details about ACORN v3, we refer to [4].Figure 1
The structure of authenticated encryption cipher ACORN v3.The initialization of the authenticated encryption cipher ACORN v3 consists of loading the 128-bit key (k0,k1,…,k127) and 128-bit IV (iv0,iv1,…,iv127) into the state and running the cipher for 1792 steps.(1)
Initialize the stateS−1792 to 0(2)
Letm−1792+t=kt for t=0 to 127Letm−1792+128+t=ivt for t=0 to 127Letm−1792+256=ktmod128⊕1 for t=0Letm−1792+256+t=ktmod128 for t=1 to 1535(3)
Fort=−1792 to t=−1, St+1= StateUpdate128St,mt,cat,cbtAtt-th clock, the cipher executes the state update function: St+1=State−Update128St,mt,cat,cbt, which is given as follows:Step 1. Linear feedback updatest,289⟵st,289⊕st,235⊕st,230st,230⟵st,230⊕st,196⊕st,193st,193⟵st,193⊕st,160⊕st,154st,154⟵st,154⊕st,111⊕st,107st,107⟵st,107⊕st,66⊕st,61st,61⟵st,61⊕st,23⊕st,0Step 2. Generate keystream bitzt⟵st,12⊕st,154⊕st,235⋅st,61⊕st,235⋅st,193⊕st,61⋅st,193⊕st,230⋅st,111⊕st,230⊕1⋅st,66Step 3. Generate the nonlinear feedback bitft⟵st,0⊕st,107⊕1⊕st,244⋅st,23⊕st,244⋅st,160⊕st,23⋅st,160⊕st,230⊕ztStep 4. Shift the 293-bit register with the feedback bit ftst+1,i⟵st,i+1 for i=0,1,…,291st+1,292⟵ft⊕mt


## 3.2. Algorithm for Algebraic Degree Estimation of ACORN v3

In this section, we will propose an efficient algorithm for algebraic degree estimation of ACORN v3 using numeric mapping, as depicted in Algorithm1.Algorithm 1:Algebraic degree estimation of ACORN v3 using numeric mapping.
Require: Given the ANFs of the initial state S0=s0,0,s0,1,…,s0,292, the ANFs of the update function State Update128 and the keystream output function f, and the set of initial input variables X=x1,x2,…,x128.
(1)
SetD0 to degS0,X;
(2)
Fort from 1 to N do:
(3)
Dt⟵DEGState Update128St−1,Dt−1;
(4)
ComputeDEGf,DN;
(5)
ReturnDEGf,DN.Algorithm1 gives a numeric degree DEGf,X of the output function f after N rounds over initial input variables X=x1,x2,…,x128 as output, which gives an upper bound on the algebraic degree of the first output bit after N rounds.The time complexity of Algorithm1 mainly depends on the values of N and the ANFs of the update function State Update128. Since all of the update function State Update128 are shifting operations except one quadratic function and six linear functions, Algorithm 1 has a time complexity of ON. Algorithm 1 requires to store Dt for t=1,2,…,N. Since the number of initial input variables is constant for ACORN v3, it leads to a negligible memory complexity of ON.


## 3.3. Experimental Results

By using Algorithm1, we will investigate the mixing efficiency of ACORN v3 and exploit new distinguishing attacks on the cipher.


### 3.3.1. When Will the Initial Input Variables Be Sufficiently Mixed?

By applying Algorithm1, we investigate the mixing efficiency of ACORN v3. When taking all the key and IV bits as initial input variables, the result shows that the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is at least 669 (out of 1792). When taking all the IV bits as input variables, the result shows that the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is at least 708 (out of 1792). The results are listed in Table 2. Note that both of these two results are lower bounds on the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree. In other words, the true maximum numbers of initialization rounds which do not achieve maximum algebraic degree could be higher.Table 2
Lower bound on the maximum number of rounds of not achieving maximum degree for ACORN v3 with initial input variablesX.
Cipher
X
=
K
,
IV
X
=
IV
#
key
+
#
IV
# rounds
#
IV
# rounds
ACORN v3
256
669
128
708Furthermore, we also take a subset of IV bits as initial input variablesX and apply Algorithm 1 to ACORN v3. Since the IV bits are sequentially loaded into the internal state in the second 128 initialization rounds, it is a natural and reasonable idea that we select the latter IV bits into the cube. We consider an exhaustive search on the subset ivp,ivp+1,…,iv127 of all 128 IV bits for all 1≤p≤127. Some results we have found are listed in Table 3. All these results are obtained on a common PC with 2.5 GHz Intel Pentium 4 processor within one second. In Table 3, the cube size d means that the cube iv128−d,iv128−d−1,…,iv127 is used in our attack. As for 676 rounds of ACORN v3, when d=36, the best result DEGf,X=35 is found, which leads to a practical distinguishing attack on it with time complexity of 236 and improves the previous distinguishing attack [17] by a factor of 24.64. Furthermore, the distinguishing advantage of our attack is 1, while the attack of [17] is based on limited chi-square statistical test and its distinguishing advantage is certainly smaller than 1. As for 721 rounds of ACORN v3, when d=95, the best result DEGf,X=94 is found, which leads to a distinguishing attack on it with time complexity of 295. This is the best result we have found. Clearly, our results are the best distinguishing attacks on round reduced variants of ACORN v3 so far. Note that all our attacks are deterministic rather than statistical, that is, our attacks hold with probability 1.Table 3
Our distinguishing attacks on round reduced variants of ACORN v3.
# rounds
Size of cubed
Cube
Time complexity
647
21
i
v
107
,
i
v
108
,
…
,
i
v
127
2
21
649
24
i
v
104
,
i
v
105
,
…
,
i
v
127
2
24
676
36
i
v
92
,
i
v
93
,
…
,
i
v
127
2
36
704
61
i
v
67
,
i
v
68
,
…
,
i
v
127
2
61
721
95
i
v
33
,
i
v
34
,
…
,
i
v
127
2
95


### 3.3.2. Experiments

Since221, 224, and 236 in Table 3 are practical, we verify these results by carrying out a test for random 100 keys within half a day on a common PC with 2.5 GHz Intel Pentium 4 processor. All outputs of 647, 649, and 670 rounds of ACORN v3 over the cubes iv107,iv108,…,iv127, iv104,iv105,…,iv127 and iv93,iv94,…,iv127, respectively, always sum to 0. This clearly confirms the effectiveness and accuracy of our algorithm.


## 3.3.1. When Will the Initial Input Variables Be Sufficiently Mixed?

By applying Algorithm1, we investigate the mixing efficiency of ACORN v3. When taking all the key and IV bits as initial input variables, the result shows that the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is at least 669 (out of 1792). When taking all the IV bits as input variables, the result shows that the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree is at least 708 (out of 1792). The results are listed in Table 2. Note that both of these two results are lower bounds on the maximum number of initialization rounds of ACORN v3 such that the generated keystream bit does not achieve maximum algebraic degree. In other words, the true maximum numbers of initialization rounds which do not achieve maximum algebraic degree could be higher.Table 2
Lower bound on the maximum number of rounds of not achieving maximum degree for ACORN v3 with initial input variablesX.
Cipher
X
=
K
,
IV
X
=
IV
#
key
+
#
IV
# rounds
#
IV
# rounds
ACORN v3
256
669
128
708Furthermore, we also take a subset of IV bits as initial input variablesX and apply Algorithm 1 to ACORN v3. Since the IV bits are sequentially loaded into the internal state in the second 128 initialization rounds, it is a natural and reasonable idea that we select the latter IV bits into the cube. We consider an exhaustive search on the subset ivp,ivp+1,…,iv127 of all 128 IV bits for all 1≤p≤127. Some results we have found are listed in Table 3. All these results are obtained on a common PC with 2.5 GHz Intel Pentium 4 processor within one second. In Table 3, the cube size d means that the cube iv128−d,iv128−d−1,…,iv127 is used in our attack. As for 676 rounds of ACORN v3, when d=36, the best result DEGf,X=35 is found, which leads to a practical distinguishing attack on it with time complexity of 236 and improves the previous distinguishing attack [17] by a factor of 24.64. Furthermore, the distinguishing advantage of our attack is 1, while the attack of [17] is based on limited chi-square statistical test and its distinguishing advantage is certainly smaller than 1. As for 721 rounds of ACORN v3, when d=95, the best result DEGf,X=94 is found, which leads to a distinguishing attack on it with time complexity of 295. This is the best result we have found. Clearly, our results are the best distinguishing attacks on round reduced variants of ACORN v3 so far. Note that all our attacks are deterministic rather than statistical, that is, our attacks hold with probability 1.Table 3
Our distinguishing attacks on round reduced variants of ACORN v3.
# rounds
Size of cubed
Cube
Time complexity
647
21
i
v
107
,
i
v
108
,
…
,
i
v
127
2
21
649
24
i
v
104
,
i
v
105
,
…
,
i
v
127
2
24
676
36
i
v
92
,
i
v
93
,
…
,
i
v
127
2
36
704
61
i
v
67
,
i
v
68
,
…
,
i
v
127
2
61
721
95
i
v
33
,
i
v
34
,
…
,
i
v
127
2
95


## 3.3.2. Experiments

Since221, 224, and 236 in Table 3 are practical, we verify these results by carrying out a test for random 100 keys within half a day on a common PC with 2.5 GHz Intel Pentium 4 processor. All outputs of 647, 649, and 670 rounds of ACORN v3 over the cubes iv107,iv108,…,iv127, iv104,iv105,…,iv127 and iv93,iv94,…,iv127, respectively, always sum to 0. This clearly confirms the effectiveness and accuracy of our algorithm.


## 4. Conclusions

In this paper, we focus on proposing an efficient algorithm for algebraic degree estimation of ACORN v3. By applying our algorithm, we investigate the mixing efficiency of ACORN v3 and exploit distinguishing attacks on it. As a result, new distinguishing attacks on 647, 649, 670, 704, and 721 initialization rounds of ACORN v3 are obtained, respectively. So far as we know, all of our distinguishing attacks on ACORN v3 are the best. The effectiveness and accuracy of our algorithm is confirmed by the experimental results.



---

*Source: 7429320-2019-11-20.xml*