Improved Cube Attacks on Some Authenticated Encryption Ciphers and Stream Ciphers in the Internet of Things

With technical development and internet popularization, Internet of Things (IoT) technology is gaining a wider application in various fields. Key challenges in the growth of IoT are related to privacy and security. To avoid any possible malicious attacks, employing cryptosystems is widely recognized as one of the most effective approaches to implement confidentiality, integrity, and message authentication for the security of IoT. In this work, we investigate the security of Authenticated Encryption ciphers and stream cipher by using the improved cube attack. Firstly, we introduce a method to identify good cubes, which leads to the largest-round distinguisher. Our idea is based on the greedy algorithm of finding cubes and the numeric mapping method for estimating the algebraic degree of the NFSR-based cryptosystem. By using this method, we can efficiently explore useful cubes from a large search space. Further, we evaluate the security of several cryptographic primitives against the cube attack by using the SAT model of division property and flag technique, which can make the propagation of division property more accurately. Experiments show that we can obtain some new or improved cryptanalysis on MORUS-640-128, TRIAD, Quartet, TriviA-ck-v2, and Enhanced-bivium. The attacks can improve the number of attacking rounds and efficiency, and provide a vital reference for security analysis of other Authenticated Encryption ciphers and lightweight stream ciphers.

SECTION I. Introduction

With the rapid development and the wide use of IoT, there is a huge amount of data transferred over a network in order to communicate and share information. However, the IoT is a network with high dynamic topology, and their connections are vulnerable to attacks. As the benefits of IoT are numerous, the need for ensuring the security and the reliability of the overall system is growing. Nowadays, protecting the overall system against malicious attacks is one of the greatest challenges for deploying IoT technology.

In order to improve cryptographic defenses against cyberattacks, the U.S. National Institute of Standards and Technology (NIST) announced an open competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR) in January 2013 [1] to encourage the design and analysis of AE ciphers. Specifically, authenticated ciphers combine the cryptographic services of confidentiality, integrity, and authentication into one algorithmic construct. Moreover, IoT applications ranging from smart locks to wearable technology to home automation and healthcare, they often require constrained devices, and these innumerable tiny trustworthy devices are required to provide services such as encryption\decryption, authentication, digital signature and so on. To create worthy solutions to the problem of securing data in the IoT-like constrained environments, NIST published the call in August 2018 [2] for proposals for a new lightweight cryptography (LWC) standard process for lightweight applications.

MORUS family [3] is one of the finalists of the CAESAR competition and has received extensive attention. TriviA-ck-v2 [4] is one of the Round 2 candidates in the CAESAR competition. TRIAD [5] and Quartet [6] are two lightweight symmetric-key schemes based on a stream cipher, and both of them are selected as LWC authenticated cipher candidates in April 2019. Cube attack is one of the most powerful techniques in cryptanalysis of cryptographic primitives, and this motivates us to study the security of these above ciphers against the cube attack.

A. Related Work

Cube attack is a powerful technique to analyze symmetric-key ciphers proposed by Dinur and Shamir [7] in 2009. Cube attack can be seen as a generalization of higher-order differential attack [8] and chosen IV statistical attack [9], [10]. The core idea of the cube attack is to simplify the polynomial by summing the output of the cryptosystem over a subset of public variables, so-called cube. The target of the cube attack is to recover secret variables from the simplified polynomial named superpoly. Cube attack has been successfully used to various ciphers, including stream ciphers [11]–​[15], hash functions [16]–​[18], and authenticated encryptions [19], [20]. Originally, stream cipher can be treated as a blackbox polynomial. We can recover the structure of the superpoly with a linearity test [7] or a quadraticity test [21]. Later, cube attacks develop into different types, such as dynamic cube attack [12], conditional cube attack [17], correlation cube attack [15], deterministic cube attack [22], and division property based cube attack.

Todo [23] introduces division property at EUROCRYPT 2015, which is a generalization of integral property. It can be used to construct the integral distinguisher against block ciphers with non-linear components. After that, Todo and Morii [24] present the bit-based division property at FSE 2016, which is a more robust method because it can trace the division property at the bit level. However, it is evident that the memory and computing complexities significantly increase. The complexity of utilizing bit-based division property was roughly equal to $2^{n}$ for ${n}$ -bit primitives, so the considerable complexity restricted the wide applications of bit-based division property. To overcome this limit, at ASIACRYPT 2016, Xiang et al. [25] apply an auxiliary Mixed-Integer Linear Programming (MILP) tool to search integral distinguishers with conventional division property. They innovatively introduce the method to apply inequalities to model the basic bitwise operations COPY, AND, XOR, and an S-box operation. The larger integral distinguishers can be found efficiently through this MILP aided technique. Sun et al. [26] proposed the automatic search method that based on SAT\SMT to search integral distinguishers for ARX-based ciphers.

Further, Todo et al. [27] put cube attacks in the setting of non-blackbox polynomials and apply the division property to the cube attack at CRYPTO 2017. By utilizing this new cube attack technique, they explore cubes with a larger size, and successfully evaluate the involved secret variables on stream ciphers TRIVIUM, Grain128a, and authenticated cipher ACORN. Soon after, Wang et al. [28] present several techniques (flag technique, degree evaluation, and term enumeration) to enhance the performance of division property based cube attack at CRYPTO 2018. With the help of bit-based division property using three subsets, Wang et al. [29] apply their improved cube attack technique on Trivium in practice and propose a theoretical attack that can recover the superpoly of Trivium up to 842 rounds. Very recently, Yang et al. [30] apply a new method of finding cube testers to ACORN, which is based on the greedy algorithm of finding cubes [31], [32] and the numeric mapping technique [33] for iteratively estimating the upper bound of the algebraic degree of the NFSR-based cryptosystem.

Salam et al. [14] recover the key with the cube attack on the initialization of 4-step MORUS-640-128 in 2017. In 2019, Li and Wang [34] apply the MILP tool to analyze its 5.5-step variant by utilizing the technique of cube attacks based on division property. TriviA-ck-v2 [4] is one of the Round 2 candidates in the CAESAR competition. In 2017, Sarkar et al. [35] obtain distinguishers till 950 rounds. Liu [33] provides a distinguishing attack for its 1047-round variant with a cube of size 61 in CRYPTO 2017. It is noted that cube attacks in our paper are key recovery attacks, which aim to guess at least one bit of secret key with complexity less than the brute-force attack. However, cube attack by utilizing such large cube is unfeasible under current limited computing resources. Zhang et al. [36] apply the cube attack on 464-round Enhanced-bivium and claim that the breaking complexity is 2⁵⁵ after 464 rounds. Quartet and TRIAD are Round 1 submissions of the ongoing NIST Lightweight Cryptography Standardization Project in April 2019. To the best of our knowledge, none of the key recovery attacks with the cube technique has been conducted on them.

Moreover, in the previous attacks on MORUS-640-128 and Enhanced-bivium, they randomly select a subset of public variables as the cube from a large search space. Aiming to extend the number of attacked rounds and reduce computing complexity, we introduce an algorithm to find expected cubes. Then we apply the improved division property based cube attack on these target ciphers.

B. Our Contributions

In this paper, we introduce a new greedy method to discover cubes from a wide range of initialization vectors efficiently, and we also use the numeric mapping method to iteratively estimate the upper bound of the algebraic at a linear computational complexity. We model the division property propagations of five target ciphers and translate the division trail finding problem into an SAT problem. Further, for the bitwise AND operation, the effect of constant 0 bits is taken into account. We use the algorithm combined with the SAT model of the division property and the flag technique to improve the accuracy of the propagation of division properties. Finally, we evaluate the security of MORUS-640-128, TRIAD, Quartet, Trivia-ck-v2, and Enhanced-bivium by using the improved cube attack based on the division property with the SAT method, and we give some new cryptanalysis results in key recovery attack.

For MORUS-640-128 with keystream generation function, we give the first 5.9-step key recovery attack with a cube of size 24, which achieves 0.4-step (two rounds) more than the previous best work in [34], and the complexity for superpoly recovery is 2^32.06. We also study reduced versions of the initialization of MORUS-640-128 and provide the 6-step key recovery attack with a cube of size 22, which improves two steps comparing with [14]. Also, we find better cubes of the same size as [14], and then we gain one more step key recovery attack with these cubes. For TRIAD, we obtain a zero-sum distinguisher for 559-round with a cube of size 35 and a 568-round distinguisher with a cube of size 45. We find a cube of size 16, which leads to a key recovery attack for its 521 variant, the complexity is 2^24.81. We provide a key recovery attack for 565-round TRIAD with the 30-dimensional cube, the complexity is 2⁴⁸. Also, the theoretical key recovery attack is applied to its 572-round variant. We obtain cubes of size 2 and 18, resulting in key recovery attacks for 3 and 4 rounds of Quartet. We provide cube attacks on TriviA-ck-v2 up to 874 rounds with a cube of size 16. We also provide the first key recovery attack for 502-round Enhanced-bivium with a cube of size 12. Our results are summarized in Table 1, and the comparisons with former key recovery attacks are also included.

TABLE 1 Summarization of Key Recovery Attack Results

C. Organization

The remainder of this paper is organized as follows: Some basic definitions and theories are introduced in Section II. In Section III we briefly describe MORUS-640-128, TRIAD, Quartet, Enhanced-bivium and TriviA-ck-v2. Section IV shows the method of finding good cubes and an algorithm of using the SAT model combined with the flag technique. Section V presents several applications. Section VI provides conclusions and future work.

SECTION II. Preliminaries

A. Cube Attack

Cube attack is an analysis tool to recover the secret key of a cryptosystem, which was proposed by Dinur and Shamir [7].

Almost any cryptosystem can be seen as a Boolean function. For a stream cipher with n secret key bits $x = \left ({x_{0},x_{1},\ldots,x_{n-1}}\right)$ and m public initialization vector (IV) bits $v=\left ({v_{0}, v_{1},\ldots, v_{m-1}}\right)$ , the algebraic normal form (ANF) of the given output bit can be regarded as a Boolean polymonial $f\left ({x,v}\right)$ over the field $GF\left ({2}\right)$ . For a specific subset of indexes $I = \left \lbrace{ i_{1},i_{2},\ldots,i_{|I|} }\right \rbrace \subset \left \lbrace{ 0,1,\ldots,m-1}\right \rbrace$ , the terms $t_{I} = v_{i_{1}}\cdots v_{i_{|I|}}$ in the polynomial, and the $2^{|I|}$ values of indexes are referred as cube $C_{I}$ . Then the ANF of $f\left ({x,v}\right)$ can be decomposed as $$\begin{equation*}f\left ({x,v}\right) = t_{I} \cdot p\left ({x,v }\right) + q\left ({x,v }\right), \tag{1}\end{equation*}$$ where $p\left ({x,v }\right)$ is called the superpoly of $I$ in $f\left ({x,v}\right)$ and it is irrelevant to $\left \lbrace{ v_{i_{1}},v_{i_{2}}\cdots v_{i_{|I|}}}\right \rbrace$ . Obviously, the value of $p\left ({x,v }\right)$ can merely be affected by the secret key bits $x$ and the assignment to the non-cube $IV\text{s}$ . Furthermore, every term in $q\left ({x,v }\right)$ at least misses one variable from the set $I$ . A major observation in cube attacks is that the sum of $f\left ({x,v}\right)$ over all values of the cube $C_{I}$ is $$\begin{equation*}\oplus _{C_{I}}f\left ({x,v}\right) = \oplus _{C_{I}}t_{I}\cdot p\left ({x,v}\right)\! +\! \oplus _{C_{I}}q\left ({x,v}\right)\!=\!p\left ({x,v}\right).\qquad \tag{2}\end{equation*}$$

B. Division Property and Division Trail

Division property is a generalization of integral property, proposed by Todo [23] at EUROCRYPT 2015. In this subsection, we will recall the definitions of bit-based division property [24] and division trail [25].

Definition 1 (Bit-Based Division property[24]):

Let $\mathbb {X}$ be a multiset whose elements take values from $\mathbb {F}_{2}^{n}$ , and let $\mathbb {K}$ be a set of m-dimensional vectors whose i-th element takes 0 or 1. When the multiset $\mathbb {X}$ has the division property $\mathcal {D}_{\mathbb {K}}^{1^{n}}$ , the parity of $\boldsymbol {\pi }_{\textbf {u}} \textbf {(x)}$ over all $x\in \mathbb {X}$ satisfies the following conditions: $$\begin{equation*}\bigoplus \limits _{x\in \mathbb {X}} \boldsymbol {\pi }_{\textbf {u}} \textbf {(x)}= \begin{cases} unknown,&if\; there\; is\; k \in \mathbb {K}, \;\mathit {u \geq k } \\ 0, &otherwise.\end{cases} \tag{3}\end{equation*}$$ There is $u \geq k$ , if $u[j] \geq k[j]$ for all $j$ .

Definition 2 (Division trail[25]):

Let ${f}$ be the round function of an iterated cipher and $\mathbb {K}_{0}$ be the initial division property state. After r rounds, the division properties denoted by $\mathbb {K}_{r}$ , can be deduced through ${f}$ . Thus, the propagation of the division property from $\mathbb {K}_{0}$ to $\mathbb {K}_{r}$ is evaluated as $\left \{{k}\right \}\,\,\stackrel {def}=\mathbb {K}_{0} \stackrel {f}{\to }\mathbb {K}_{1} \stackrel {f}{\to }\cdots \stackrel {f}{\to }\mathbb {K}_{i}\cdots \stackrel {f}{\to } \mathbb {K}_{r}$ , where $\mathbb {K}_{i}$ denotes the internal states division property after ${i}$ rounds $(0 \leq i \leq r)$ . For any vector $k_{i}\in \mathbb {K}_{i}$ , there must exist a vector $k_{i-1}\in \mathbb {K}_{i-1}$ can propagate to $k_{i}$ for $i\in \left \{{ 1, \cdots, r}\right \}$ , then we call $k_{0} \to k_{1}\to \cdots \to k_{r}$ is a r-round division trail.

Moreover, if there is no division trail ${k}_{0} \stackrel {f}{\to }{k}_{r} = e_{j}$ , where $e_{j}$ is an $n$ -bit unit vector whose $j$ th bit is 1 and others are 0, then the $j$ th output bit after $r$ -round $f$ functions is balanced. Otherwise, the $j$ th bit may be balanced or not.

C. Sat-Aided Bit-Based Division Property

Sun et al. [26] proposed the automatic search method that based on SAT\SMT to search integral distinguishers for ARX-based ciphers. They model the bit-based division property propagations of the three basic operations (COPY, AND, and XOR) in Conjunctive Normal Form (CNF). The concrete equations are depicted as follow.

• Model 1 (SAT Model for COPY [26]):

  Let $a \xrightarrow {COPY} (b_{0},b_{1})$ be a division trail of COPY function. The following CNFs are sufficient to describe the propagation of the division property for COPY. $$\begin{equation*} \begin{cases} \lnot {b_{0}} \lor \lnot {b_{1}} =1 \\ a \lor b_{0} \lor \lnot {b_{1}} =1 \\ a \lor \lnot {b_{0}} \lor b_{1} =1 \\ \lnot {a} \lor b_{0} \lor b_{1} =1 \end{cases} \tag{4}\end{equation*}$$

• Model 2 (SAT Model for XOR [26]):

  Let $(a_{0}, a_{1}) \xrightarrow {XOR} b$ be a division trail of XOR function. The following CNFs are sufficient to describe the propagation of the division property for XOR. $$\begin{equation*} \begin{cases} \lnot {a_{0}} \lor \lnot {a_{1}} =1 \\ a_{0} \lor a_{1} \lor \lnot {b} =1 \\ a_{0} \lor \lnot {a_{1}} \lor b =1 \\ \lnot {a_{0}} \lor a_{1} \lor b =1 \end{cases} \tag{5}\end{equation*}$$

• Model 3 (SAT Model for AND [26]):

  Let $(a_{0}, a_{1}) \xrightarrow {AND} b$ be a division trail of AND function. The following CNFs are sufficient to describe the propagation of the division property for AND. $$\begin{equation*} \begin{cases} \lnot {a_{1}} \lor b =1 \\ a_{0} \lor a_{1} \lor \lnot {b} =1 \\ \lnot {a_{0}} \lor b =1 \\ \end{cases} \tag{6}\end{equation*}$$

D. Cube Attack Based on Division Property

In cube attack, attackers aim to recover the superpoly $p\left ({x,v }\right)$ for a cube and get some secret key bits information. Todo et al. [27] proposed the improved cube attack technique based on division property with MILP. They can identify the secret key bits excluded from the superpoly and explore larger-size cubes. The technique is based on the following proposition.

Proposition 1 (Identify the involved keys by Division Property[27]):

Let $f(x,v)$ be a polynomial over the field $GF\left ({2}\right)$ , where $x$ and $v$ denote the secret and public variables respectively. For a subset of indexes $I = \left \lbrace{ i_{1},i_{2},\ldots,i_{|I|} }\right \rbrace \subset \left \lbrace{ 0,1,\ldots,m-1}\right \rbrace$ , let $C_{ I}$ be a set of $2^{|I|}$ values where the variables in $\left \lbrace{ v_{i_{1}}\cdots v_{i_{|I|}}}\right \rbrace$ are taking all possible combinations of values. Let $k_{I}$ be an n-dimensional vector such that $v^{k_{I}}=t_{I}=v_{i_{1}}v_{i_{2} }\cdots v_{i_{|I|} }$ , i.e. $k_{i}=1$ if $i \in I$ and $k_{i}=0$ otherwise. Assuming there is no division trail such that $\left ({e_{j},k_{I}}\right)\stackrel {f}{\to }1$ , $x_{j}$ is not involved in the superpoly of the cube $C_{I}$ .

Flag Technique: Sun et al. [37] firstly present the MILP model for division property of the bitwise AND operation between a variable and one constant. Later, Todo et al. take into account the impact of constant 0 bits on the propagation of division property, and add several additional constraints in [27]. Afterwards, Wang et al. [28] find out that constant 0 bits could be generated from some XOR operations, which involve an even number of constant 1 bits. For this reason, Wang et al. propose the flag technique to make their MILP model more precisely. The operation $\oplus$ follows the rules: $$\begin{align*} \begin{cases} 1_{c} \oplus 1_{c} = 0_{c}\\ 0_{c} \oplus x = x \oplus 0_{c} = x \\ \delta \oplus x = x \oplus \delta = \delta \end{cases} \quad for~arbitrary~x \in \left \lbrace{ 1_{c}, 0_{c}, \delta }\right \rbrace. \\ {}\tag{7}\end{align*}$$

The operation $\times$ follows the rules: $$\begin{align*} \begin{cases} 1_{c} \times x = x \times 1_{c} = x\\ 0_{c} \times x = x \times 0_{c} = 0_{c} \\ \delta \times \delta = \delta \end{cases}\quad for~arbitrary~x \in \left \lbrace{ 1_{c}, 0_{c}, \delta }\right \rbrace. \\ {}\tag{8}\end{align*}$$

After getting the cube index $I$ and index set $J$ of probably involved secret variables by the above-mentioned algorithms, Wang et al. [28] evaluate the algebraic degree and enumerate all possible terms of the superlopy to recover the superpoly efficiently.

Complexity for Superpoly Recovery: With cube indices $I$ , key bits $J$ and degree $d$ , enumerates all $t$ -degree mononials that may appear in the superpoly. Let $J_{i}$ denotes the set contains all possilbe monomials of degree $i$ , for any $i \in (1,2,\cdots,d)$ . The comlexity for superpoly recovery is $$\begin{equation*} 2^{|I|} \times \left({1+ \sum _{t=1}^{d}|J_{t}| }\right). \tag{9}\end{equation*}$$

SECTION III. A Brief Description of Five Target Ciphers

A. The Description of MORUS-640-128

MORUS is an authenticated encryption cipher submitted to the CAESAR competition, and it is of great concern recently.

The design of MORUS is based on the stream cipher, and four parts include: initialization, associated data processing, encryption and finalization. For MORUS-640-128, the internal state is 640 bits and divided into five 128-bit state elements denoted as $S_{0,0}, \cdots, S_{0,4}$ . The initialization starts by loading the 128-bit key $K_{128}$ and the 128-bit initialization vector $IV_{128}$ into the state together with constants $const_{0}$ , $const_{1}$ . The value of above mentioned constants and rotation constants can be referred to [3]. The initial state bits are reprented as follow. $$\begin{align*} S^{-16}_{0,0} =IV_{128}; \\ S^{-16}_{0,1} =K_{128}; \\ S^{-16}_{0,2} =1^{128}; \\ S^{-16}_{0,3} =const_{0}; \\ S^{-16}_{0,4} =const_{1}. \tag{10}\end{align*}$$

The state $S$ is updated by calling the round function StateUpdate for 16 steps. There are 5 rounds with similar bitwise operations at each step as illustrated in Figure 1. The update function StateUpdate$(S^{i}, P_{i})$ is given as follow. $$\begin{align*}&\hspace {-2pc}Round ~0: \\ S^{i}_{1,0}=&Rotl\left ({S^{i}_{0,0}\oplus \left ({S^{i}_{0,1} {\S }^{i}_{0,2}}\right)\oplus S^{i}_{0,3},b_{0} }\right); \\ S^{i}_{1,3}=&S^{i}_{0,3}\lll \omega _{0}; \\ S^{i}_{1,1}=&S^{i}_{0,1}; \\ S^{i}_{1,2}=&S^{i}_{0,2}; \\ S^{i}_{1,4}=&S^{i}_{0,4}; \\&For~1\le j \le ~4, \\&\hspace {-2pc}Round ~j: \\ S^{i}_{j+1,j}=&Rotl\left ({S^{i}_{j,j}\oplus \left ({S^{i}_{j,j+1} {\S }^{i}_{j,j+2}}\right)\oplus S^{i}_{j,j+3} \oplus P_{i},b_{j} }\right); \\ S^{i}_{j+1,j+3}=&S^{i}_{j,j+3}\lll \omega _{j}; \\ S^{i}_{j+1,j+1}=&S^{i}_{j,j+1}; \\ S^{i}_{j+1,j+2}=&S^{i}_{j,j+2}; \\ S^{i}_{j+1,j+4}=&S^{i}_{j,j+4}. \tag{11}\end{align*}$$ Only two of the state elements are updated in every round: one is modified by rotation $\lll$ , and the other by a set of ANDs, XORs, and rotation $Rotl$ . The $Rotl\left ({x,b_{j}}\right)$ for $b \in \left ({0,\cdots,4 }\right)$ indicates that a 128-bit block $x$ is divided into four 32-bit words and each word is rotated left by $b_{j}$ bits, the values of $b_{j}$ can be referred to [3]. The addition between subscripts is actually addition modulo 5.

FIGURE 1.

The state update function of MORUS-640-128.

The plaintext block $P_{i}$ is encrypted to the ciphertext $C_{i}$ by the exclusive OR operation with the key stream $S_{0}\oplus \left ({S_{1} \lll 96 }\right) \oplus \left ({S_{2} \& S_{3}}\right)$ in the encryption phase.

B. The Description of Triad

TRIAD is a family of lightweight symmetric-key schemes based on a stream cipher. The 256-bit internal state of TRIAD denoted by $\boldsymbol {a} =\left ({a_{1} \lVert a_{2} \lVert \cdots \lVert a_{80} }\right)$ , $\boldsymbol {b} = \left ({b_{1} \lVert b_{2} \lVert \cdots \lVert b_{88} }\right)$ and $\boldsymbol {c} = \left ({c_{1} \lVert c_{2} \lVert \cdots \lVert c_{88}}\right)$ . It accepts a 128-bit secret key $K$ and a 96-bit nonce $N$ represented by byte arrays as follow. $$\begin{align*} K=&\left ({K\left [{ 0}\right], K\left [{ 1}\right], K\left [{ 2}\right], \cdots, K\left [{ 15}\right] }\right); \\ N=&\left ({N\left [{ 0}\right], N\left [{ 1}\right], N\left [{ 2}\right], \cdots, N\left [{ 11}\right] }\right). \tag{12}\end{align*}$$

The initialization of TRIAD loads the secret key, nonce, and some constants into the state, and please refer to [5] for more details. The internal state is updated by Algorithm 1 for 1024 rounds. The input is 256-bit internal state $\left ({\boldsymbol {a}, \boldsymbol {b}, \boldsymbol {c} }\right)$ and 1-bit message $msg$ and the output is the updated internal state and 1-bit key stream $z$ . Figure 2 shows the state update function of TRIAD.

FIGURE 2.

The state update function of TRIAD.

Algorithm 1 Update Function of TRIAD

1:

$t_{1} \gets a_{68} \oplus a_{80} \oplus b_{85} \cdot c_{85}$

2:

$t_{2} \gets b_{64} \oplus b_{88}$

3:

$t_{3} \gets c_{68} \oplus c_{88}$

4:

$z \gets t_{1} \oplus t_{2} \oplus t_{3}$

5:

$t_{1} \gets t_{1} \oplus a_{73} \cdot a_{79} \oplus b_{66} \oplus msg$

6:

$t_{2} \gets t_{2} \oplus b_{65} \cdot b_{87} \oplus c_{84} \oplus msg$

7:

$t_{3} \gets t_{3} \oplus c_{77} \cdot c_{87} \oplus a_{74} \oplus msg$

8:

$\left ({a_{1}, a_{2}, \cdots, a_{80} }\right) \gets \left ({t_{3}, a_{1}, \cdots, a_{79} }\right)$

9:

$\left ({b_{1}, b_{2}, \cdots, b_{88} }\right) \gets \left ({t_{1}, b_{1}, \cdots, b_{87} }\right)$

10:

$\left ({c_{1}, c_{2}, \cdots, c_{88} }\right) \gets \left ({t_{2}, c_{1}, \cdots, c_{87} }\right)$

C. The Description of TriviA-ck-v2

TriviA-ck-v2 is an authenticated encryption algorithm submitted to the CAESAR competition.

TriviA-ck-v2 has the 384-bit internal state and uses three Non-linear feedback registers $A$ , $B$ , $C$ of size 132 bit, 105 bit, and 147 bit respectively. It is loaded with the 128-bit key and the 128-bit initialization vector IV. Algorithm 2 describes the state update function of TriviA-ck-v2.

Algorithm 2 Update Function of TriviA-ck-v2

1:

$t_{1} \gets A_{66} \oplus A_{132} \oplus (A_{130} \cdot A_{131}) \oplus B_{96}$

2:

$t_{2} \gets B_{69} \oplus B_{105} \oplus (B_{103} \cdot B_{104}) \oplus C_{120}$

3:

$t_{3} \gets C_{66} \oplus C_{147} \oplus (C_{145} \cdot C_{146})\oplus A_{75}$

4:

$\left ({A_{1},A_{2},\cdots,A_{132}}\right) \gets \left ({t_{3}, A_{1},\cdots,A_{131} }\right)$

5:

$\left ({B_{1},B_{2},\cdots,B_{105}}\right) \gets \left ({t_{1}, B_{1},\cdots,B_{104} }\right)$

6:

$\left ({C_{1},C_{2},\cdots,C_{147}}\right) \gets \left ({t_{2}, C_{1},\cdots,C_{146} }\right)$

After the state updation, keystream bits can be generated. The keystream bit generation function is defined as $$\begin{equation*} A_{66} \!\oplus \! A_{132} \!\oplus \! B_{69} \!\oplus \! B_{105}\! \oplus \! C_{66} \!\oplus \! C_{147} \!\oplus \!(A_{102} \!\cdot \! B_{66}).\qquad \tag{13}\end{equation*}$$

D. The Description of Enhanced-bivium

Enhanced-bivium is an NFSR-based stream cipher [38]. The 174-bit internal state of Enhanced-bivium can be denoted as $s = \left ({s_{0},s_{1},\cdots,s_{173} }\right)$ . The 80-bit key $K$ and the 80-bit intialization vector IV are loaded as follow. It requires 628 cycles in the initialization phase. $$\begin{align*} \left ({s_{0},s_{1},\cdots,s_{89}}\right)=&\left ({K_{0}, K_{1},\cdots,K_{79},0,\cdots,0 }\right); \\ \left ({s_{90},s_{91},\cdots,s_{173}}\right)=&\left ({IV_{0}, IV_{1},\cdots,IV_{79},0,1,1,1 }\right). \qquad \tag{14}\end{align*}$$

The update function is given in Algorithm 3. The internal state is updated for $R$ rounds, then produce the 1-bit keystream denoted as $z$ .

Algorithm 3 Update Function of Enhanced-bivium

1:

for $i=1$ to $R$ do

2:

$t_{1} \gets s_{62} + s_{89}$

3:

$t_{2} \gets s_{92} + s_{173}$

4:

$z_{i} \gets t_{1} + t_{2}$

5:

$t_{1} \gets t_{1} + s_{87} \cdot s_{88} + s_{137}$

6:

$t_{2} \gets t_{2} + s_{171} \cdot s_{172} + s_{74}$

7:

$\left ({s_{0},s_{1},\cdots,s_{89}}\right) \gets \left ({t_{2}, s_{0},\cdots,s_{88} }\right)$

8:

$\left ({s_{90},s_{91},\cdots,s_{173}}\right) \gets \left ({t_{1}, s_{90},\cdots,s_{172} }\right)$

9:

end for

E. The Description of Quartet

Quartet is one of the submissions of the ongoing NIST Lightweight Cryptography Standardization Project. As depicted in Figure 3, there are four 64-bit lanes involved in the algorithm: $x_{0}$ , $x_{1}$ , $x_{2}$ and $x_{3}$ .

FIGURE 3.

Four 64-bit lanes in Quartet.

The state updating of Quartet has four functions. The only non-linear function $\chi$ is defined as $$\begin{equation*} x_{i} \gets x_{i} \oplus (x_{i+2} \oplus 1) \cdot x_{i+1}. \tag{15}\end{equation*}$$ It operates on the 64-bit lanes, which updates $x_{i}$ by taking $x_{i}$ , $x_{i+1}$ and $x_{i+2}$ as inputs with the index addition being the addition modulo 4. The $\rho$ function is a linear function, which divides the 64-bit lane $x_{i}$ into two 32-bit words and rotates each 32-bit word left by the same number of bits $n_{i}$ . The $\lambda$ function is defined as bellow, which operates on one 64-bit lane $x_{i}$ . $$\begin{equation*} x_{i} \gets x_{i} \oplus (x_{i} \ggg _{64} r_{i, 1}) \oplus (x_{i} \ggg _{64} r_{i, 2}). \tag{16}\end{equation*}$$ The $\tau$ function is used to add the round constant $c_{r}$ to the lane $x_{3}$ , for $0 \le r \le 23$ . The round constants $c_{r}$ and the rotation parameters $n_{i}$ , $r_{i,1}$ and $r_{i,2}$ can be referred to [6].

In the initialization phase, one round $R_{ini}$ of the state updating consists of a series of operations done on the four 64-bit lanes, where ° is the composition operation of the different mappings. $$\begin{align*} R_{ini}=&\tau \circ \lambda (x_{2}, r_{2,1}, r_{2,2}) \circ \rho (x_{1}) \circ \chi (x_{3}, x_{0}, x_{1}) \circ \\&\lambda (x_{1}, r_{1,1}, r_{1,2}) \circ \rho (x_{0}) \circ \chi (x_{2}, x_{3}, x_{0}) \circ \\&\lambda (x_{0}, r_{0,1}, r_{0,2}) \circ \rho (x_{3}) \circ \chi (x_{1}, x_{2}, x_{3}) \circ \\&\lambda (x_{3}, r_{3,1}, r_{3,2}) \circ \rho (x_{2}) \circ \chi (x_{0}, x_{1}, x_{2}). \tag{17}\end{align*}$$

SECTION IV. Methods to Search Good Cubes and Improved Cube Attack With SAT

The goal of the cube attack is to recover the secret key of a cryptosystem. The main observation of the cube attack is that summing the outputs of the cryptosystem over a cube might cancel out all the higher degree terms except terms associated with the monomials involving the cube variables. Hence, exploring useful cubes are vital to cube attack. However, the number of possible cube choices will increase significantly with the increase of cube sizes during the cube attack. In this section, we will discuss how to find expected cubes more efficiently by utilizing the numeric mapping technique. Moreover, this section describes an algorithm to combine the SAT model of the division property with the flag technique.

A. The Numeric Mapping Technique

The numeric mapping technique is proposed at CRYPTO 2017 to iteratively estimate the upper bound on the algebraic degree of the NFSR-based cryptosystem [33]. In the following, we will shortly review the technique.

Let $f(x)=\bigoplus _{u=(u_{1},\cdots,u_{n})\in \mathbb {F}_{2}^{n}} a_{u}^{f} \prod _{i=1}^{n} x_{i}^{u_{i}}$ , and $\mathbb {B}_{n}$ denotes the set of all $n$ -variable Boolean functions. We denote coefficients of the ANF of $f$ as $a_{u}^{f}$ . The numeric mapping denoted by $DEG$ is defined as below, where $D = (d_{1}, d_{2},\cdots, d_{n})$ . $$\begin{align*}&\hspace {-2pc}DEG:\: \mathbb {B}_{n} \times \mathbb {Z}^{n} \rightarrow \mathbb {Z}, \\ (f,D)\rightarrow&\max _{a_{u}^{f} \ne 0} \left \lbrace{ \sum _{i=1}^{n}u_{i}d_{i}}\right \rbrace. \tag{18}\end{align*}$$

Suppose $g_{i}(1 \le i \le n)$ are Boolean functions on $m$ variables, and denote $deg(G)=(deg(g_{1}), deg(g_{2}),\cdots,deg(g_{n}))$ for $G = (g_{1}, g_{2},\cdots,g_{n})$ . The numeric degreee of the composite function $h = f \circ G$ is defined as $DEG(f,deg(G))$ , denoted by $DEG(h)$ for short. We call $DEG(f,D)$ a super numeric degree of $h$ if $d_{i}\ge deg(g_{i})$ for all $1 \le i \le n$ , where $D = (d_{1}, d_{2},\cdots, d_{n})$ . We can check that the algebraic degree of $h$ is always less than or equal to the numeric degree of $h$ , i.e., $$\begin{equation*}deg\left ({h}\right) \le DEG(h) =\max _{a_{u}^{f} \ne 0} \left \lbrace{ \sum _{i=1}^{n}u_{i}deg(g_{i}) }\right \rbrace. \tag{19}\end{equation*}$$

B. A New Greedy Algorithm to Find Expected Cubes

Before reaching the peak, the number of distinguishable rounds generally becomes bigger as the size of the cube grows larger, then it will turn small gradually. In fact, when the cube has a relatively large size, the number of rounds we can attack becomes larger. Inspired by this, we present a new greedy algorithm to find good cubes by discarding several bits from the candidate list iteratively. In addition, we give the time complexity analysis in this section.

In our greedy algorithm, all of the IV bits are selected as the initial candidate bits, namely $s_{0}$ is equal to the length of IV. We search expected cubes by iteratively discarding $k_{i}$ bits from the previous candidate list. Further, to reduce trivial operations, we set the size of candidates to a fixed value, denoted by $n$ . The main process is as follow:

1. Choose a list of $s_{i-1}$ -bit candidate cubes from an initial starting set, or from the results of the previous iteration. This size of the list is denoted by $n$ .

2. Drop $k_{i}$ bits from each one of the candidate cubes. By using the numeric mapping technique, select the best candidates of size $s_{i-1}-k_{i}$ , which leads to distinguishers or nonrandomness detectors with the largest number of rounds.

3. For all original candidate cubes of size $s_{i-1}$ , their corresponding new best candidates of size $s_{i-1}-k_{i}$ are stored in a new list together. According to the numbers of the distinguishable round, sort the new list from largest to smallest.

4. Reduce the size of the sorted list to $n$ by pruning some of the elements with the smaller distinguishable round.

5. Repeat steps 1 to 4 until the cube of the expected size has been found.

Obviously, the whole complexity of both the accelerated greedy algorithm [30] and our new greedy algorithm mainly depends on the size of IV, discarding or adding size $k_{i}$ , and the complexity of finding the largest distinguishable round. Similarly, we calculate the lower bound of the maximum number of distinguishable rounds by using a degree estimation algorithm. Especially for NFSR-based cryptosystems, we use the numeric mapping technique [33] to estimate the lower bound of the maximum number of distinguishable rounds for the test cube. The time complexity of the degree estimation algorithm is about $O\left ({N }\right)$ , where $N$ is the number of initialization rounds.

C. Combination of SAT Model and Flag Technique

In the previous model of cube attack based on division property, the initial division properties of cube IV bits are set to active, denoted by 1. And the other bits are initialized to constant bits, denoted by 0. Wang et al. [28] introduce the flag technique, which takes the effect of constant bits on the propagation of division property into consideration, then the model can be more precise.

For specific ciphers, the flags of the internal states can be derived from update functions iteratively without the automatic solver SAT. Algorithm 4 shows the combination of the SAT model and the flag technique. Hence the accuracy of the SAT model of the division property propagation will be increased.

Algorithm 4 SAT Model Combined With Flag Technique

1:

Declare $X^{j}$ as the division property of $j$ th round internal state

2:

Declare $operation_{m}^{j}$ as the $m$ th operation in $j$ th round state update function or keystream generation function

3:

Declare $f^{j}$ as the flag of $j$ th round state

4:

while $operation_{m}^{j}$ ($X_{a_{0}}^{j-1},\cdots,X_{a_{n}-1} ^{j-1}$ ) is not NULL do

5:

if $operation_{m}^{j}$ is AND then

6:

if arbitrary $X_{i}^{j-1}$ for any $i \in \left ({a_{0},\cdots,a_{n-1} }\right)$ , the corresponding flag $f_{i}^{j-1}$ is $0_{c}$ then

7:

$0 \gets operation_{m}\left ({X_{a_{0}}^{j-1},\cdots,X_{a_{n}-1} ^{j-1}}\right)$

8:

else

9:

follow the traditional SAT propagation rules

10:

end if

11:

else

12:

follow the traditional SAT propagation rules

13:

end if

14:

end while

15:

return $X^{j}$

SECTION V. Applications

With the methods proposed in Section 4, we are able to find good cubes from a large search space efficiently. As an illustration, we apply our greedy algorithm to explore expected cubes for MORUS-640-128, TRIAD, Quartet, TriviA-ck-v2, and Enhanced-bivium, then we apply SAT-aided bit-based division property to conduct cube attacks in this section. As authenticated encryption primitives, we only focus on the process of the initialization phase because the number of rounds we can attack is smaller than the whole initialization rounds.

In the experiments, the numeric mapping technique is used to estimate the algebraic degree of the output key bit more precisely. Note that, regardless of the dimension of the cube, the estimation can give an upper bound of the real algebraic degree of the output key bit. If the estimated degree of the output bits is smaller than the size of the cube, then we obtain a zero-sum distinguisher. Finally, several key recovery attacks with suitable cubes are implemented in this section. We implement the attacks on the Linux system with 8 GB RAM and use Cyptominisat solver with Python interface to solve SAT problems.

A. Applications to MORUS-640-128

In this section, we practically evaluate the performance of the cube attack against reduced versions of MORUS-640-128. There are 5 rounds with similar operations at each step in the state update function, so one of five rounds will be called 0.2-step in this paper. Besides, the keystream generation function is named 0.5-step.

To conduct the practical attack, we use an SAT-based algorithm, which is a division property based cube attack framework. According to Proposition 1, for a polynomial $f\left ({x,y}\right)$ , if there is no division trail such that $\left ({e_{j},k_{I}}\right)\stackrel {f}{\to }1$ , then the observed bit $x_{j}$ does not belong to the set $J$ , whose elements are indexes of secret variables may be involved to the superpoly. Consequently, we can evaluate which secret variables may be involved in the superpoly of a given cube based on this algorithm. The specific progress is shown in Algorithm 5. And this algorithm is supported by the SAT solver. The input $\mathcal {M}$ is an SAT model, where the target stream cipher is represented by using the division property.

Algorithm 5 Evaluate Secret Variables by SAT Method

1:

Declare cube indexes $I$

2:

Let $x$ be n SAT variables of $\mathcal {M}$ corresponding to secret variables.

3:

Let $v$ be m SAT variables of $\mathcal {M}$ corresponding to public variables.

4:

$v_{i} = 1$ for all $i \in I$ .

5:

$v_{i} = 0$ for all $i \in \left \lbrace{ 0,1,\cdots,m-1}\right \rbrace -I$ .

6:

$x_{i} = 0$ for all $i \in \left \lbrace{ 0,1,\cdots,n-1}\right \rbrace$ .

7:

for $j$ in range$\left ({m}\right)$ do

8:

$x_{j} = 1$

9:

solve SAT model $\mathcal {M}$

10:

if $\mathcal {M}$ is satisfied then

11:

$J=J \cup \left \lbrace{ j}\right \rbrace$

12:

end if

13:

$x_{j} = 0$

14:

end for

15:

return $J$

During the attack, we implement the SAT model for the propagation of the division property on MORUS-640-128 for the first step. Then we evaluate involved secret variables by using Algorithm 5. To verify our attack and implementation, cubes identical to [34] are directly used in our testing experiments for 2.5-step to 5.5-step, and the results we obtained are consistent with the previous results. Then, we find some better cubes of the same size as [14], as shown in Table 2, and with these cubes we gain one more step key recovery attack on MORUS-640-128 in the initialization phase.

TABLE 2 Example of Cubes for 5-Step MORUS-640-128 With 3-Dimensional Cubes

Further, we find better cubes with the greedy algorithm and select different output keystream bits for 5.7-step and 5.9-step. Moreover, we find a cube of a practical size 24, which can lead to the first 5.9-step key recovery attack, and we gain 0.4-step (two rounds) more than the previous best work in [34]. For example, if the cube index is $I = \{ 1, 11, 14, 19, 31, 35, 37, 40, 50, 51, 56, 60, 63, 67, 76, 82, 90, 95, 107, 112, 115, 116, 117, 126 \}$ , then the key variables with index in {2, 8, 10, 16, 17, 20, 24, 25, 28, 29, 30, 39, 43, 49, 75, 90, 93, 96, 99, 100, 104, 113, 119, 121} may be involved in the corresponding superpoly, and the complexity of recovering the superpoly is 2^32.06. Also, we find some good cubes of size 22 for 6-step MORUS-640-128 in the initialization phase, which improves two more steps comparing with [14]. We provide some selected cubes and summarize the corresponding key recovery attack results in Table 3.

TABLE 3 Some of Cube Attacks on MORUS-640-128 With Various Cubes

B. Applications to TRIAD

The security of TRIAD in the initialization process is evaluated using the same approach as before.

Firstly, we conduct the algebraic degree estimation algorithm to calculate the lower bound of the largest distinguishable round for TRIAD. To compare the performance between the accelerated greedy algorithm and our new greedy algorithm, we explore cube testers using the accelerated greedy algorithm and our new greedy algorithm, respectively. During the experiments with the accelerated greedy algorithm, we exhaust all possible cubes of size 4 at the first iteration. After that, we add 4 to 6 new bits at each iteration. As for our greedy algorithm, we exhaust all possible cubes of size 92 at the first iteration and drop 4 to 6 bits at each iteration. Experiments show that both methods can find the same good cube tester efficiently. For example, we find the same cube tester with size of 30, and the cube index set is $I= \left ({0,1,2,3,4,5,6,7,8,\!9,10,11,12,\!13,14,17,21,22,\!23,24,25,26,27,28,29,30,37,46,56,72}\right)$ , which can lead to a 561-round zero-sum distinguisher. We also obtain the 568-round distinguisher with the cube of size 45. We summarize the results in Table 4.

TABLE 4 Some Cubes of TRIAD Found by Our Greedy Algorithm

Therefore, to reduce computational complexity, our new algorithm is recommended when the size of the cube is larger than half the length of IV; the accelerated greedy algorithm is recommended when the size of the cube is smaller than half the length of IV. Moreover, we construct the SAT model of division property for TRIAD. In the initial input of the division property, the division properties of constant bits are fixed to 0. Set the division properties of cube IV bits to 1, and non-cube IVs to 0. In our experiments, we set the non-cube IV bits to be zeros, so let the flags of non-cube IV bits equal to $0_{c}$ .

We obtain a cube of size 16, which leads to a key recovery attack for 521-round TRIAD. The cube index set is $I = \left \lbrace{ 0,1,5,6,7,8,9,10,11,24,25,26,27,28,29,30 }\right \rbrace$ , only 12 secret key bits with index in {39, 43, 47, 48, 51, 57, 58,67,72, 119,121, 122} may exist in the superpoly corresponding to this cube. The complexity of recovering the superpoly is 2^24.81. With the cube of size 30 and the cube index in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 37, 46, 56, 72}, we provide a key recovery attack for its 565-round variant. The key bits with index in {6, 14, 15, 18, 40, 41, 43, 51, 53, 54, 55, 56, 60, 72, 74, 118, 120, 124} may be involved in the corresponding superpoly. For 572-round TRIAD, then the following secrect bits with index in $J = \left \lbrace{ 0,1,2, \cdots,127 }\right \rbrace \backslash \left \lbrace{ 2, 3, 6, 32, 33, 34, 36, 39, \cdots, 42,\! 48, 49, 62,\! 81, 100, 101,\! 104, 105, 106, 109, \cdots,127 }\right \rbrace$ may be involved in the corresponding superpoly of the output key.

C. Applications to TriviA-ck-v2

We conduct experiments searching for cubes on the reduced version of TriviA-ck-v2 to find the existence of lower dimension cubes.

We initialize the algebraic degrees of cube variables to 1, and set the degrees of any non-zero constant bits are 0. Since secret key bits are constant with respect to cube variables, the degrees of secret key bits are set to 0, too. We set non-cube IV bits to constant 0, so the degrees of both non-cube IV bits and other constant 0 bits are set to $-\infty$ . When evaluating the degree of $A_{130}A_{131}$ , $B_{103}B_{104}$ , and $C_{145}C_{146}$ , we make further improvement of the degree evaluation by utilizing the numeric mapping technique in [33]. We can make the algebraic degree estimation tending towards real value due to its NFSR-based structure.

We apply the model described in Section 4, and we obtain cubes resulting in key recovery attacks up to 874 rounds of TriviA-ck-v2, as shown in Table 5. For TriviA-ck-v2, an 874-round key recovery attack can be performed with 16 cube variables. If the cube index set is $I = \left \lbrace{ 1, 3, 5, 6, 11, 18, 20, 22, 26, 35, 36, 41, 50, 66, 71, 86}\right \rbrace$ , then the secret key bits with index set in {13, 19, 20, 21, 30, 51, 60, 73, 115, 116, 117} may be involved in the corresponding superpoly of the output key bit, and the complexity of superpoly recovery is 2^22.48.

TABLE 5 Some of Cube Attacks on TriviA-ck-v2 With Various Cubes

D. Applications to Enhanced-bivium

For Enhanced-bivium, we obtain some better cryptanalytic results at a lower computational complexity. Combining the method to select cube variables for key recovery attack, we can find some good cubes, shown in Table 6.

TABLE 6 Some Cubes of Enhanced-Bivium Found by Our Greedy Algorithm

We obtain a cube with a size 68, and the number of the round we can attack theoretically is 575. The cube index set is $I = \left \lbrace{ 0,1,2,\cdots,79}\right \rbrace \backslash \left \lbrace{ 0, 1, 2, 31, 42, 44, 46, 54, 56, 58, 66, 75}\right \rbrace$ . Also, we find a cube of size 35, and we can get a 559-round practical zero-sum distinguisher. We also propose a key recovery attack by using cube attack based on division property with the SAT method on reduced Enhanced-bivium. For 502-round Enhanced-bivium in initialization phase, if the cube index set of size 12 is $I = \left \lbrace{ 3,5,9,12,15,18,20,25,48,51,53,69 }\right \rbrace$ , the secret key bits with index in {7, 21, 23, 24, 25, 30, 46, 47, 48, 71, 72, 73} may be involved in the corresponding superpoly of output key bit. The time complexity of recovering the superpoly is 2^18.19. So far, all of the attacks on Enhanced-bivium are the best attacks in terms of the number of attacked rounds and the feasibility of attack.

E. Applications to Quartet

We use the technique illustrated in Section 4 on the modified version of Quartet to find good cubes. We take the first keystream bit as the output bit. The appropriate cubes found for the 3-step and 4-step Quartet are of size 2 and 18, respectively.

We denote the 256-bit state of Quartet by $s$ , where $s[i]$ represents the $i$ -th bit of $s$ . For 3-step Quartet in the initialization process, if the cube index set is $I = \left \lbrace{ 180,181}\right \rbrace$ , then the secret key bits with index set in {201, 240, 243} may be involved in the corresponding superpoly of the output bit $z_{0}$ , and the complexity of superpoly recovery is 2⁴. We do similar experiments on Quartet with an initialization phase of 4 steps, the attack on 4-step Quartet sequentially utilizes several 18-dimensional cubes, as shown in Table 7. For example, if the cube index set is $I = \left \lbrace{ 65, 71, 74, 81, 82,94, 97,104, 110, 111, 116, 118,158, 160, 163, 164, 188, 191 }\right \rbrace$ , then the secret key variables with index in {38, 39, 43, 44, 45, 205, 208, 230} may be involved in the corresponding superpoly of the output key bit $z_{0}$ , and the complexity to recover the superpoly is 2^23.81. However, the degree of the output function grows significantly with the increase in the number of steps. Our further experiments reveal that cube attacks failed when the number of attack step is increased from 4 to 5.

TABLE 7 Some of Cube Attacks on Quartet With Various Cubes

SECTION VI. Conclusion and Future Work

In this paper, we present a new method for finding good cubes for cryptographic primitives with optimal complexity. In our division property based cube attacks, the operations with a constant are considered, and we use the flag technique on our SAT model to propagate the division property more precisely. We give some new or improved cube cryptanalysis on MORUS-640-128, TRIAD, Quartet, TriviA-ck-v2, and Enhanced-bivium. As an important type of cryptanalysis, the cube attack is flexible in applying in the IoT since the attacking rounds are improved.

In the future, we will study how to estimate the algebraic degree of non-NFSR based cryptosystems more precisely.