Keywords

1 Introduction

Cube attack on tweakable black box polynomials was introduced by Dinur and Shamir [1] at EUROCRYPT 2009 and can be seen as a generalization of higher-order differential attack [2, 3] and chosen IV statistical attacks [4, 5]. The idea of cube attack is to tweak the multivariate master polynomial by assigning chosen values for the public variables, which results in derived polynomials. The set of assigned public variables is denoted as a cube, and the sum of corresponding derived polynomials over all values of the cube, denoted as a superpoly, is evaluated. The target of cube attacks is to find a number of linear superpolys in terms of the common secret variables and recover the secret variables by solving the resultant system of linear equations. The possibility that a cube yields a linear equation depends on both its size and the algebraic properties of the cipher. Since the seminal work of Dinur and Shamir, several variants of cube attacks, including cube tester [6], dynamic cube attack [7], conditional cube attack [8] and correlation cube attack [9] were put forward.

Previous Works on Searching for Cubes. A key step to a successful cube attack is searching for good cubes and the corresponding superpolys during the offline phase. However, how to find favorite cubes is still an intractable problem. In the original paper of the cube attack [1], the cryptosystems were regarded as black-box, and the authors proposed a new technique, which is a variant of the random walk proposed in [5], to search for cubes experimentally. The basic idea is to start from a random subset and iteratively test the linearity of superpoly to decide whether the size of tested subset should be increased or decreased. In this technique, the authors introduced a linearity test to reveal the structure of the superpoly. If the linearity test always passes, the Algebraic Normal Form (ANF) of the superpoly is recovered by assuming that the superpoly is linear. Moreover, a quadraticity test was introduced in [10], and the ANF of the superpoly is similarly recovered. Note that they are experimental cryptanalysis, and it is possible that cube attacks do not actually work. For example, if the superpoly is highly unbalanced function for specific variables, we cannot ignore the probability that the linearity and quadraticity tests fail.

In [11], an simple evolutionary algorithm was proposed by Aumasson et al. to find good cubes. By introducing the well known greedy heuristic, a strategy called Greedy Bit Set Algorithm was presented by Stankovski in [12] to find cubes. The authors of [13] and [14] both used the union of two subcubes to generate larger cube candidates. In all these works, the size of a cube is limited to the experimental range because the attacker has to make \({2^d}\) encryptions under the fixed key to compute the sum over a cube of size d. Thus, searching for large cubes is time consuming, and it is practically infeasible to execute the cube attack when the size of cube exceeds an experimental range, e.g., 50. This restricts the capability of the attacker for better cubes.

Numeric Mapping. Recently two works on cube attacks using large cubes of size greater than 50 were presented in [15, 16]. Both of them treat the cryptosystems as non-blackbox polynomials. One is introducing the bit-based division property into cube attacks on non-blackbox polynomials by Todo et al. [15] at CRYPTO 2017. More recently, Wang et al. [17, 18] further investigated this attack and presented better key recovery attacks on some NFSR-based stream ciphers. Nevertheless, in these two works, the recovered secret variables are generally smaller than 1 bit, while the time complexities are significantly high and the success probabilities of key recovery are difficult to estimate as their attacks are based on some assumptions. Another is exploiting a new technique, called numeric mapping, to present a general framework of iterative estimation of algebraic degree for NFSR-based cryptosystems by Liu [16] at CRYPTO 2017. The key idea of Liu’s work is based on a simple fact. Its advantage is that it has linear time complexity and needs a negligible amount of memory. Furthermore, it is deterministic rather than statistical. As pointed out by Todo et al. [19], Liu’s method is more efficient, since cube attacks based on division property need to ask for the help of solvers, e.g., the MILP solver. The high efficiency of numeric mapping makes it possible to test a large number of large cubes with limited computational resources. It is important to note that numeric mapping can give an upper bound on algebraic degree of the output of a given NFSR-based cryptosystem when the cube is given. However, how to search for cubes using numeric mapping is not explored in [16]. Later, Zhang et al. [20] further investigated Liu’s work, and presented some attacks on two variants of Trivium stream cipher.

Previous Attacks on ACORN v3. ACORN v3 [21] is an authenticated encryption stream cipher, and was selected as one of seven finalists of CAESAR competition [22] at March 2018. Up to now, several attacks on ACORN v3 had been published in [23,24,25,26]. However, there are no attacks better than exhaustive key search on ACORN v3 so far. In [27], Ghafari and Hu proposed a new attack framework based on cube testers and d-monomial test, and gave a distinguishing attack on 676 initialization rounds of ACORN v3 with a time complexity of \(200 \times 2^{33}\).Footnote 1 In [29], Ding et al. proposed distinguishing attacks on 647, 649, 670, 704, and 721 initialization rounds of ACORN v3, which is the best known distinguishing attack on the round reduced variants of ACORN v3 so far. At CRYPTO 2017, Todo et al. [15] 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 \(2^{78}\), \(2^{109}\) and \(2^{122}\), respectively. The attack was improved by Wang et al. [17] at CRYPTO 2018, and possible key recovery attacks on 704 and 750 rounds of ACORN v3 are presented, where no more than one bit of the secret key can be recovered with unknown probability in around \(2^{77.88}\) and \(2^{120.92}\), respectively. Recently, two works [30, 31] on constructing distinguishers on ACORN v3 had been published, which were done independently of our results.

Our Contribution. In this paper, a new general method of searching for cubes in cube attacks, called iterative walk, is proposed. Iterative walk takes the technique numeric mapping as a tool, which is used to test cubes and find out the best cubes among them. It consists of two concrete techniques, called incremental iterative walk and decremental iterative walk, respectively. Both of these two techniques split the process of searching for cubes with large size into several iterative processes, each of which aims at searching for a ‘best’ set of input variables with small size. After each iterative process, the input variables in the obtained ‘best’ set are added to (or dropped from) the cube in incremental (or decremental) iterative walk. As illustrations, we apply it to ACORN v3. Some new distinguishing attacks on round reduced variants of ACORN v3 we have obtained are listed in Table 1, and comparisons with previous works are made. Note that three key recovery attacks on the cipher in [16,17,18] are also listed in Table 1. In these attacks, the recovered secret variables are generally no more than 1 bit, while the time complexities are significantly high. Because of the high time complexities, these attacks are impractical and can not 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.

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 method.

Table 1. Attacks on round reduced variants of ACORN v3
Full size table

This paper is organized as follows. Some preliminaries are introduced in Sect. 2. A new general method of searching for cubes in cube attacks is presented in Sect. 3. In Sect. 4, the method is applied to ACORN v3 to prove the effectiveness of our new method. The paper is concluded in Sect. 5.

2 Preliminaries

2.1 Cube Attacks and Cube Testers

Cube attack, which can be seen as a generalization of higher order differential attacks, was introduced by Dinur and Shamir [1] at EUROCRYPT 2009. It treats the output bit of a cipher as an unknown Boolean polynomial \(f\left( {{k_0}, \cdots ,{k_{n - 1}},{v_0}, \cdots ,{v_{m - 1}}} \right) \) where \({k_0}, \cdots ,{k_{n - 1}}\) are secret input variables and \({v_0}, \cdots ,{v_{m - 1}}\) are public input variables. Given any monomial \({t_I}\) which is the product of variables in \(I = \left\{ {{i_1}, \cdots ,{i_d}} \right\} \), f can be represented as the sum of terms which are supersets of I and terms which are not supersets of I:

$$f\left( {{k_0}, \cdots ,{k_{n - 1}},{v_0}, \cdots ,{v_{m - 1}}} \right) = {t_I} \cdot {p_{S\left( I \right) }} + q\left( {{k_0}, \cdots ,{k_{n - 1}},{v_0}, \cdots ,{v_{m - 1}}} \right) $$

Where \({p_{S\left( I \right) }}\) is called the superpoly of I in f, and the set \(\{{v_{{i_1}}}, \cdots ,{v_{{i_d}}}\}\) is called a cube. The idea behind cube attacks is that the sum of the Boolean polynomial \(f\left( {{k_0}, \cdots ,{k_{n - 1}},{v_0}, \cdots ,{v_{m - 1}}} \right) \) over the cube which contains all possible values for the cube variables is exactly \({p_{S\left( I \right) }}\), 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 work by distinguishing \({p_{S\left( I \right) }}\) from a random function. Especially, the superpoly \({p_{S\left( I \right) }}\) is equal to a zero constant, if the algebraic degree of f in the variables from I is smaller than the size of I.

2.2 Random Walk

As for cube attacks, the basic questions are how to estimate the algebraic degree of the output polynomial f which is only given as a black box, and how to choose appropriate cubes if they exist. In [1], a simple technique was proposed, which is a variant of the random walk proposed in [5]. The basic idea of this technique is briefly described as follows.

The attacker randomly chooses a size k between 1 and m and a subset I of k public variables, and computes the value of the superpoly of I by numerically summing over the cube \({C_I}\) (setting each one of the other public variables to a static value, usually to zero). If his subset I is too large, the sum will be a constant value (regardless of the choice of secret variables), and in this case he has to drop one of the public variables from I and repeat the process. If his subset I is too small, the corresponding \({p_{S\left( I \right) }}\) is likely to be a nonlinear function in the secret variables, and in this case he has to add a public variable to I and repeat the process. The correct choice of I is the borderline between these cases, and if it does not exist the attacker can restart with a different initial I.

2.3 Numeric Mapping

In [16], Liu presented a general framework of iterative estimation of algebraic degree for NFSR-based cryptosystems, by exploiting a technique, called numeric mapping. Denote \(\mathbb {F}_2^n\) the n-dimension vector space over \(\mathbb {F}_2\). Let \({\mathbb {B}_{n}}\) be the set of all functions mapping \(\mathbb {F}_2^n\) to \({\mathbb {F}_2}\), and let \(f \in {\mathbb {B}_{n}}\). The Algebraic Normal Form (ANF) of given Boolean function f over variables \({x_1},{x_2}, \cdots ,{x_n}\) can be uniquely expressed as \(f\left( {{x_1},{x_2}, \cdots ,{x_n}} \right) = \mathop {\oplus }\limits _{c = \left( {{c_1},{c_2}, \cdots ,{c_n}} \right) \in \mathbb {F}_2^n} {a_c}\prod \limits _{i = 1}^n {{x_i}^{{c_i}}} \), where \({a_c}\)’s are coefficients of algebraic normal form of f. The numeric mapping, denoted by \(\mathbf{DEG} \), is defined as

where \(D = \left( {{d_1},{d_2}, \cdots ,{d_n}} \right) \). For the composite function \(h = f \circ G\), it defined the numeric degree of h as \(\mathbf{DEG} \left( {h,\deg \left( G \right) } \right) \), denoted \(\mathbf{DEG} \left( h \right) \) for short. 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 by using numeric mapping. Based on this technique, Liu [16] proposed a concrete and efficient algorithm (described as Algorithm 1 in Appendix for more details) to find an upper bound on the algebraic degree of the output, and then gave a general framework of iterative estimation of algebraic degree of NFSR-Based Cryptosystems.

3 Iterative Walk: A New General Method of Searching for Cubes

In Algorithm 1, an upper bound on algebraic degree of the output of a given NFSR-based cryptosystem after N initialization rounds is obtained as output. Here, we denote \({N_C}\) the maximum number of rounds of not achieving maximum degree (i.e., \(\left| C \right| \)) when taking the variables in the set C as input variables. In this paper, we are more concerned with the value of \({N_C}\), which indicates the maximum number of rounds that efficient distinguishers can be constructed. Inspired by Algorithm 1, a new algorithm is proposed to estimate the maximum attacked number of rounds is depicted as Algorithm 2.

figure a

In the algorithm above, \(\left( {s_1^{\left( 0 \right) },s_2^{\left( 0 \right) }, \cdots ,s_L^{\left( 0 \right) }} \right) \) denotes the internal state at clock \(t=0\) with size L, and \(\deg \left( {{s^{\left( 0 \right) }},C} \right) = \left( \deg \left( {s_1^{\left( 0 \right) },C} \right) ,\deg \left( {s_2^{\left( 0 \right) },C} \right) , \cdots ,\right. \left. \deg \left( {s_L^{\left( 0 \right) },C} \right) \right) \), where the notation \(\deg \left( {s_i^{\left( 0 \right) },C} \right) \) denotes the algebraic degree of \(s_i^{\left( 0 \right) }\) with C as input variables. Especially, \(\deg \left( {0,C} \right) = - \infty \) and \(\deg \left( {1,C} \right) = 0\). Note that when Algorithm 2 is utilized to search for cubes, the key is taken as parameter, that is, \(\deg \left( {{k_i},C} \right) = 0\) for any bit \({k_i}\) of the key. This is consistent with a distinguisher in the setting of fixed and unknown key. \(\mathbf{DegEst} \) is a procedure for estimating algebraic degree. For a given NFSR-based cryptosystem, Algorithm 2 outputs the maximum number of rounds of not achieving maximum degree when taking a given cube as input variables. Similar to Algorithm 1, Algorithm 2 has linear time complexity of \(\mathcal {O}(N)\) and needs a negligible amount of memory. Thanks to the high efficiency of Algorithm 2, checking a large amount of cubes with limited computational resources becomes feasible.

Based on Algorithm 2, a new general method of searching for cubes, called iterative walk, is proposed. Iterative walk splits the process of searching for cubes with large size into several iterative processes, each of which aims at searching for a ‘best’ cube of input variables with small size. After each iterative process, the cube varies according to the corresponding result. In this technique, Algorithm 2 is utilized as a tool to test given cubes and find out the best cubes among them. Iterative walk consists of two concrete techniques, called incremental iterative walk and decremental iterative walk, respectively. Different strategies are employed in these two techniques to search for cubes, as described in the following two subsections.

3.1 Incremental Iterative Walk

Incremental iterative walk splits the process of searching for cubes with large size into several iterative processes, each of which aims at searching for a ‘best’ cube of input variables with small size. After each iterative process, the input variables in the obtained ‘best’ set are added to the cube until the cube contains all input variables.

The detailed process of incremental iterative walk is summarized as follows. The attacker first sets the cube C to the empty set and \({N_C}\) to 0. After that, he repeats the followings to search for a good cube with large size. He selects an iterative size r and generates q sets \(\left\{ {\varOmega _1^r,\varOmega _2^r, \cdots ,\varOmega _q^r} \right\} \) which consists of all possible sets by choosing r variables from \(V - C\), where \(q = {{\left| {V - C} \right| }\atopwithdelims ()r }\). For each set \(\varOmega _i^r\), the attacker takes the key K as parameter and the variables in \(C \cup \varOmega _i^r\) as input variables, sets the remaining variables in \(V - \left( {C \cup \varOmega _i^r} \right) \) to be zeros, and then computes \({N_{C \cup \varOmega _i^r}}\) by implementing Algorithm 2. After implementing Algorithm 2 for q times, the attacker finds out the value of \(\beta \) which satisfies \({N_{C \cup \varOmega _\beta ^r}} = \max \left\{ {{N_{C \cup \varOmega _i^r}},i = 1,2, \cdots ,q} \right\} \), sets \({N_C}\) to \({N_{C \cup \varOmega _\beta ^r}}\) and C to \(C \cup \varOmega _\beta ^r\), and then gives \({N_C}\) and C as outputs in this iterative process.

figure b

In Algorithm 3, \({N_C}\) denotes the maximum number of rounds of not achieving maximum degree \(\left| C \right| \) when taking the set C as input variables. \(\alpha \) and \(\beta \) are two intermediate variables and utilized to store necessary calculation results. For a given NFSR-based cryptosystem, Algorithm 3 gives the maximum number of rounds that efficient distinguishers can be constructed and the corresponding cube as outputs for each iterative process.

Complexity. Let \({T_0}\) denotes the time complexity of implementing Algorithm 2 once. Assume that the iterative processes (i.e., Step 4–11 in Algorithm 3) are executed \(\lambda \) times, with the corresponding iterative sizes \({r_1}, \cdots ,{r_\lambda }\), respectively. In the first iterative process, Algorithm 2 is executed \({{\left| {V - C} \right| }\atopwithdelims ()r_1 }\) times with \(C = \emptyset \), which leads to a time complexity of \({T_0} \cdot {{ {m} }\atopwithdelims ()r_1 }\). In the second iterative process, Algorithm 2 is executed \({{\left| {V - C} \right| }\atopwithdelims ()r_2 }\) times with \(\left| C \right| = {r_1}\), which leads to a time complexity of \({T_0} \cdot {{ {m - {r_1}} }\atopwithdelims ()r_2 }\). Similarly, the time complexity of all iterative processes can be calculated easily. Thus, the total time complexity of Algorithm 3 can be obtained as

$$T = {T_0} \cdot \left[ {\left( {\begin{array}{*{20}{c}} m \\ {{r_1}} \\ \end{array}} \right) + \left( {\begin{array}{*{20}{c}} {m - {r_1}} \\ {{r_2}} \\ \end{array}} \right) + \cdots + \left( {\begin{array}{*{20}{c}} {m - \sum \limits _{i = 1}^{\lambda - 1} {{r_i}} } \\ {{r_\lambda }} \\ \end{array}} \right) } \right] $$

The time complexity of Algorithm 3 mainly depends on the time complexity of Algorithm 2 (i.e., \({T_0}\)), the IV size m and the selected iterative sizes \({r_1}, \cdots ,{r_\lambda }\). This algorithm needs a negligible amount of memory.

3.2 Decremental Iterative Walk

Incremental iterative walk searches for a cube with large size, by adding input variables to the cube gradually. The basic idea of decremental iterative walk is similar to incremental iterative walk, while a different strategy is employed to search for cubes in decremental iterative walk. Decremental iterative walk splits the process of searching for cubes into several iterative processes, each of which aims at searching for a ‘best’ cube of input variables with small size. After each iterative process, the input variables in the obtained ‘best’ set are dropped from the cube until the cube contains no input variables, which is different from incremental iterative walk, as depicted in Algorithm 4.

figure c

Similar to Algorithm 3, for a given NFSR-based cryptosystem, Algorithm 4 also gives the maximum number of rounds that efficient distinguishers can be constructed and the corresponding cube as outputs for each iterative process. However, in Algorithm 4, the cube first contains all input variables, and then the input variables are dropped from the cube gradually. Let \({T_0}\) denotes the time complexity of implementing Algorithm 2 once. Assume that the iterative processes (i.e., Step 4–11 in Algorithm 4) are executed \(\lambda \) times, with the corresponding iterative sizes \({r_1}, \cdots ,{r_\lambda }\), respectively. Similar to the complexity calculation of Algorithm 3, the total time complexity of Algorithm 4 can be easily given as

$$T = {T_0} \cdot \left[ {\left( {\begin{array}{*{20}{c}} m \\ {{r_1}} \\ \end{array}} \right) + \left( {\begin{array}{*{20}{c}} {m - {r_1}} \\ {{r_2}} \\ \end{array}} \right) + \cdots + \left( {\begin{array}{*{20}{c}} {m - \sum \limits _{i = 1}^{\lambda - 1} {{r_i}} } \\ {{r_\lambda }} \\ \end{array}} \right) } \right] $$

4 Application to ACORN v3

In this section, we first give a brief description of ACORN v3, and then apply our new method to ACORN v3 to exploit new distinguishing attacks on it.

4.1 A Brief Description of ACORN v3

ACORN v3 is an authenticated encryption stream cipher, and it has been selected as one of the seven algorithms in the final portfolio of the CAESAR competition. The structure of ACORN v3 is shown in Fig. 1. The state size of ACORN v3 is 293 bits, denoted by \(S^{(t)} = ( {{s_0^{(t)}},{s_1^{(t)}}, \cdots ,{s_{292}^{(t)}}} )\) at t-th clock. It is constructed by using 6 LFSRs of different lengths 61, 46, 47, 39, 37, 59 and one additional register of length 4, and uses a 128-bit key and a 128-bit IV. ACORN v3 passes through the key-IV initialization phase, associated data processing phase, encryption/decryption phase and tag generation/verification phase. Since our work is fully based on the key-IV initialization phase, we present a brief description of the cipher during this phase. We refer to the original description of ACORN v3 in [4] for more details.

Fig. 1.
figure 1

The structure of authenticated encryption cipher ACORN v3

Full size image

At t-th clock, the cipher executes the state update function \(S^{(t+1)} = \) \(State-\)

\(Update128\) \((S^{(t)}, m_{t}, ca_{t}, cb_{t})\), which is given as follows.

figure d

4.2 Results on ACORN v3

In this subsection, we will apply our Algorithm 3 and 4 respectively to ACORN v3 to search for cubes. A key step to apply them is choosing the iterative sizes.

The Results of Applying Algorithm. 3 to ACORN v3. When applying Algorithm 3 to ACORN v3, the chosen iterative sizes in the whole iterative process and the corresponding experimental results are listed in Table 2. In the i-th iterative process, the iterative size \(r_i\) is choosed, and then Algorithm 3 gives \(N_C\) and C as outputs, where C is obtained by adding the \(r_i\) input variables listed in the third column of Table 2 to the outputted cube in the \((i-1)\)-th iterative process. \({N_C}\) denotes the maximum number of rounds of not achieving maximum degree \(\left| C \right| \) when taking the variables in the set C as input variables. As shown in Table 2, the best result is found in the 19-th iterative process, which results into a distinguishing attack on 732 rounds of ACORN v3 with a time complexity of \(2^{103}\). All these results are obtained on a common PC with 2.5 GHz Intel Pentium 4 processor within about two days.

Table 2. The results of applying Algorithm 3 to ACORN v3
Full size table

The Results of Applying Algorithm  4 to ACORN v3. When applying Algorithm 4 to ACORN v3, the chosen iterative sizes in the whole iterative process and the corresponding experimental results are listed in Table 3. In the i-th iterative process, the iterative size \(r_i\) is choosed, and then Algorithm 4 gives \(N_C\) and C as outputs, where C is obtained by dropping the \(r_i\) input variables listed in the third column of Table 2 from the outputted cube in the \((i-1)\)-th iterative process. \({N_C}\) denotes the maximum number of rounds of not achieving maximum degree \(\left| C \right| \) when taking the variables in the set C as input variables. In our experiments, it should be noted that \(N_{V} = 708\) when taking all IV bits as input variables. As shown in Table 3, the best result is found in the 1-th iterative process, which results into a distinguishing attack on 731 rounds of ACORN v3 with a time complexity of \(2^{123}\). All these results are obtained on a common PC with 2.5 GHz Intel Pentium 4 processor within about two days.

Table 3. The results of applying Algorithm 4 to ACORN v3
Full size table

The Improved Results. Since the IV bits of ACORN v3 are sequentially loaded into the internal state in the second 128 initialization rounds, it is a nature and reasonable idea that we select the latter IV variables into the cube. To reduce the search space, we fix the first p IV variables to be zeros, i.e., \(iv_{i}=0, i=0, \cdots , p-1\), and put the last \(q (\ge 0)\) IV variables into the cube. We consider applying Algorithm 4 when the V is dropped from \(\left( {{v_0}, \cdots ,{v_{127}}} \right) \) to \(\left( {{v_p}, \cdots ,{v_{127 - q}}} \right) \). Some better results we have found are listed in Table 4, and the corresponding cubes are given in Appendix. As for 676 rounds of ACORN v3, the best result we have found implies \(\mathbf{DEG} \left( {f,X} \right) = 29\), which leads to a practical distinguishing attack on it with a time complexity of \(2^{30}\) and improves the previous distinguishing attack [29] by a factor of \(2^{6}\). As for 736 rounds of ACORN v3, the best result we have found implies \(\mathbf{DEG} \left( {f,X} \right) = 94\), which leads to a distinguishing attack on it with a time complexity of \(2^{95}\). This is the best result we have found.

Table 4. The improved results on ACORN v3
Full size table

Experiments. Since \(2^{18}\) and \(2^{30}\) in Table 4 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 676 rounds of ACORN v3 always sum to 0. This clearly confirms the effectiveness and accuracy of our method.

5 Conclusions

In this paper, we focus on proposing a new general method of searching for cubes in cube attacks. The new method is called iterative walk, which takes the technique numeric mapping as a tool. It consists of two concrete techniques, called incremental iterative walk and decremental iterative walk, respectively. Both of them split the process of searching for cubes with large size into several iterative processes, each of which aims at searching for a ‘best’ set of input variables with small size. After each iterative process, the input variables in the obtained ‘best’ set are added to (or dropped from) the cube in incremental (or decremental) iterative walk. The effectiveness and accuracy of our new method is confirmed by applying it to the authenticated encryption cipher ACORN v3. Hopefully, our new method can provide a new perspective to search for cubes in cube attacks.