Finding Ordinary Cube Variables for Keccak-MAC with Greedy Algorithm

Abstract

In this paper, we introduce an alternative method to find ordinary cube variables for Keccak-MAC by making full use of the key-independent bit conditions. First, we select some potential candidates for ordinary cube variables by properly adding key-independent bit conditions, which do not multiply with the chosen conditional cube variables in the first two rounds. Then, we carefully determine the ordinary cube variables from the candidates to establish the conditional cube tester. Finally, based on our new method to recover the 128-bit key, the conditional cube attack on 7-round Keccak-MAC-128/256/384 is improved to $2^{71}$ and 6-round Keccak-MAC-512 can be attacked with at most $2^{40}$ calls to 6-round Keccak internal permutation. It should be emphasized that our new approach does not require sophisticated modeling. As far as we know, it is the first time to clearly reveal how to utilize the key-independent bit conditions to select ordinary cube variables for Keccak-MAC.

1 Introduction

In 2007, the U.S. National Institute of Standards and Technology (NIST) announced a public contest aiming at the selection of a new standard for a cryptographic hash function after Wang et al. made a break-through in MD-SHA hash family [14, 15]. After five years of intensive scrutiny, Keccak was selected as the new SHA-3 standard [2].

Due to the low algebraic degree of a Keccak round, algebraic cryptanalysis has been deeply studied for Keccak, including cube attack [5], cube-attack-like cryptanalysis [3, 5, 11], conditional cube attack [8, 9, 12], linear structures for preimage attack [7], one/two/three-round connector for collision attack [4, 10, 13].

Recently, the application of cube attack on Keccak keyed mode has attracted researchers’ interest and several results have been obtained [3, 5, 8, 9, 11, 12]. Cube attack was first proposed by Dinur and Shamir at Eurocrypt 2009 [6], where a primitive is treated as a black-box polynomial in terms of plaintext and secret key. The first application of cube attack to Keccak keyed mode was presented at Eurocrypt 2015 [5]. Two years later, at Eurocrypt 2017, Huang et al. introduced the conditional cube attack [8] on round-reduced Keccak keyed modes based on the pioneer work, i.e. cube attack [5, 6] and cube tester [1]. Cube tester was first proposed by Aumasson et al. [1], aiming at detecting the non-random behaviour e.g. the cube sums are always equal to zero. Conditional cube tester detects a non-random behaviour (the cube sums are zero) only when some conditions hold. Therefore, once the key is involved in the conditions, conditional cube tester can be utilized to mount key-recovery attack. Indeed, conditional cube tester can be viewed as a key-dependent distinguisher.

At Eurocrypt 2017, Huang et al. firstly applied the conditional cube tester to mount key-recovery attack on 5/6/7-round Keccak-MAC-512/384/256 [8]. Later at Asiacrypt 2017, an MILP-based method [9] was proposed to identify good parameters for the conditional cube tester. Therefore, the conditional cube attack on Keccak-MAC-512/384 was extended by one more round. However, it seems that the modelling in [9] did not capture all factors influencing the performance of attack. Consequently, by taking more factors into consideration, Song et al. developed a new general MILP approach for Keccak-based primitives at Asiacrypt 2018 [12] and presented many applications. Despite that Song et al. claimed that 64-dimensional cube variables with only 2 key-dependent bit conditions were found, the details of the 64-dimensional cube variables were not reported in [12]. For the new modeling in [12], it seems sophisticated at the first glance. However, since more factors are taken into account, it is more general and powerful to mount new or improved attack on many Keccak-based constructions.

Due to the limited number of bits of Keccak-MAC-512 that can be controlled for an attacker, it is very difficult to find 64-dimensional cube variables under the conditional cube attack framework proposed by Huang et al. [8]. However, cube-attack-like cryptanalysis works quite well for Keccak-MAC-512 and attack on 7-round Keccak-MAC-512 was first achieved in [3], which was later slightly improved in [11].

Up until now, the improvement for [8] are all based on the MILP approach [9, 12], which sometimes requires sophisticated modeling. This motivates us to consider whether there exist other simple approaches to find sufficient cube variables to establish the conditional cube tester.

Our Contributions. In this paper, we present an alternative method to find ordinary cube variables for Keccak-MAC-512/384. First, we observe that there are many potentially useful key-independent conditions to slow down the propagation of ordinary cube variables, which will help determine the candidates for ordinary cube variables. Then, we introduce a clever way to choose the ordinary cube variables from the candidates by considering their relations in the first round. With such a method, sufficient ordinary cube variables can be discovered to establish the conditional cube tester for 6-round Keccak-MAC-512 and 7-round Keccak-MAC-384. Meanwhile, the number of key-dependent bit conditions is minimum. It should be stressed that we do not use any specific greedy algorithms but use the idea of greedy algorithm. Specifically, we determine a small region of potential candidates at first and then select the final candidates from these potential candidates. As far as we know, it is the first time to clearly reveal how to utilize the key-independent bit conditions to select ordinary cube variables for Keccak-MAC.

Moreover, we observe that there are many unnecessary iterations of the conditional cube tester to recover the full key in [8]. Therefore, an optimal procedure to recover the full key for 7-round Keccak-MAC-256/128 based on the conditional cube tester in [8] is proposed and the new key-recovery attack is twice faster. Such an optimal approach is applied to the newly discovered 64-dimensional cube variables for 7-round Keccak-MAC-384. Consequently, conditional cube attack on 7-round Keccak-MAC-384 is improved to $2^{71}$ from $2^{75}$. By carefully choosing the order to recover the full key, we can recover the 128-bit key for 6-round Keccak-MAC-512 with at most $2^{40}$ calls to 6-round Keccak internal permutation, while it costs $\lceil \frac{128}{3}\rceil \times 2^{2^{5}+3}=\lceil \frac{128}{3}\rceil \times 2^{35}\approx 2^{40.4}$ calls in [12]. The results are summarized in Table 1.

Table 1. Related results of Keccak-MAC

Organization. The rest of the paper is organized as follows. The preliminaries of this paper will be presented in Sect. 2. In Sect. 3, our tracing algorithm will be introduced. Then, we will show our method to find enough ordinary cube variables for Keccak-MAC-384 and Keccak-MAC-512 in Sects. 4 and 5 respectively. Next, a slightly improved key-recovery method will be given in Sect. 6. The difference between our work and previous work is explained in Sect. 7. At last, we summarize the paper in Sect. 8.

2 Preliminaries

In this section, we will introduce the details of Keccak-MAC and some related techniques such as cube tester and conditional cube tester.

2.1 Description of Keccak-MAC

Keccak is a family of hash functions and Keccak-MAC is based on Keccak. The Keccak internal permutations denoted by Keccak-p[$b,n_r$] are specified by two parameters, which are the width of permutation in bits b and the number of rounds $n_r$. There are many choices for b, i.e. $b=25\times 2^{l}$ with $l\in \{0,1,2,3,4,5,6\}$. Keccak-p[$b,n_r$] works on a b-bit state A and iterates an identical round function $\mathbf {R}$ for $n_r$ times. The state A can be viewed as a three-dimensional array of bits, namely A[5][5][w] with $w=2^l$. The expression A[x][y][z] represents the bit with (x, y, z) coordinate. At lane level, A[x][y] represents the w-bit word located at the $x^{th}$ column and the $y^{th}$ row. In this paper, the coordinates are considered within modulo 5 for x and y and within modulo w for z. The round function $\mathbf {R}$ consists of five operations $\mathbf {R}=\iota \circ \chi \circ \pi \circ \rho \circ \theta$ as follows.

$$\begin{aligned}&\theta : A[x][y] = A[x][y]\oplus (\bigoplus _{y^{\prime }=0}^{4} A[x-1][y^{\prime }])\oplus (\bigoplus _{y^{\prime }=0}^{4} (A[x+1][y^{\prime }]\lll 1)).\\&\rho : A[x][y]=A[x][y]\lll r[x,y].\\&\pi : A[y][2x+3y] = A[x][y].\\&\chi : A[x][y] = A[x][y]\oplus (\overline{A[x+1][y]}\wedge A[x+2][y]).\\&\iota : A[x][y] = A[x][y]\oplus RC. \end{aligned}$$

According to the above definition of $\theta$ operation, it could be seen that if certain variable in every column of state has even parity, the variable will not diffuse to other columns. In Keccak specification [2], this property is called column parity kernel, CP kernel for short.

The construction of Keccak-MAC-n is illustrated in Fig. 1. For the sake of convenience, we denote the state A after $\theta$, $\rho$, and $\pi$ in round i ($i\ge 0$) by $A_{\theta }^{i}$, $A_{\rho }^{i}$ and $A_{\pi }^{i}$ respectively. The input state of round i is denoted by $A^{i}$. The 128-bit key is denoted by k, where $k_i$ represents the $i^{th}$ bit of k.

Fig. 1.

Construction of Keccak-MAC-n

For Keccak-MAC-n, where $n \in \{128,256,384,512\}$, the size of the internal state is 1600 bits and the 128-bit key is placed at $A^{0}[0][0]$ and $A^{0}[1][0]$. Specifically, $k_i$ is placed at $A^{0}[0][0][i]$ and $k_{i+64}$ is placed at $A^{0}[1][0][i]$, where $0\le i\le 63$. Therefore, we can obtain Observation 1.

Observation 1

Since

$$\begin{aligned} A_{\theta }^{0}[3][i]=A^{0}[3][i]\oplus (\bigoplus _{y=0}^{4}A^{0}[2][y]) \oplus (\bigoplus _{y=0}^{4} (A^{0}[4][y]\lll 1)) \end{aligned}$$

for $0\le i\le 4$, $A_{\theta }^{0}[3][i]$ is independent of the 128-bit key. In other words, if we add bit conditions on $A_{\theta }^{0}[3][i]$, all of them are key-independent.

Then, we consider the influence of $\pi \circ \rho$ operation as shown in Fig. 2. Consequently, Observation 2 can be obtained.

Fig. 2.

$\pi \circ \rho$ operation

Observation 2

After $\pi \circ \rho$ operation, $A^{0}_{\theta }[2][i]$ and $A^{0}_{\theta }[4][t]$ are next to $A^{0}_{\theta }[3][j]$ in each row, where $(i,j,t)\in \{(2,3,4),(4,0,1),(1,2,3),(3,4,0),(0,1,2)\}$.

Our approach to determine the candidates for ordinary cube variables is heavily based on the two observations.

2.2 Cube Tester

Cube tester was first proposed by Aumasson et al. at FSE 2009 [1] after Dinur et al. introduced cube attack at Eurocrypt 2009 [6]. Different from standard cube attack, which aims at key extraction, cube tester performs non-randomness detection. In our paper, we only concentrate on a specific non-random behaviour, i.e. the cube sums are zero. To describe cube tester, we first recall the concept of cube attack as follows.

Theorem 1

[6]. Given a polynomial f: $\{0,1\}^{n}\rightarrow \{0,1\}$ of degree d. Suppose $0<k<d$ and t denotes the monomial $x_0 \ldots x_{k-1}$. Then, f can be written as

$$\begin{aligned} f=t\cdot P_t(x_k,\ldots ,x_{n-1})+Q_t(X), \end{aligned}$$

where none of the terms of $Q_t(X)$ is divisible by t. Then the sum of f over all values of the cube (defined by t) is

$$\begin{aligned} \sum _{x^{\prime }\in C_t}f=\sum _{x^{\prime }\in C_t}f(x^{\prime },x_k,\ldots ,x_{n-1})=P_t(x_k,\ldots ,x_{n-1}). \end{aligned}$$

If there exists such a cube $C_t$ that the following equation always hold, then $C_t$ can be viewed as one type of cube tester [1], i.e. the sum over it always equals zero.

$$\begin{aligned} \sum _{x^{\prime }\in C_t}f=\sum _{x^{\prime }\in C_t}f(x^{\prime },x_k,\ldots ,x_{n-1})=P_t(x_k,\ldots ,x_{n-1})=0. \end{aligned}$$

For example, consider the following polynomial f:

$$\begin{aligned} f(x_0,x_1,x_2,x_3)=x_0x_1+x_1x_2+x_2x_4+x_1x_3+x_1x_2x_4. \end{aligned}$$

Then, the following equation always hold:

$$\begin{aligned} \sum _{(x_0,x_3)\in \{0,1\}^{2}}f(x_0,x_1,x_2,x_3)=0. \end{aligned}$$

The reason is that none of the monomial in $f(x_0,x_1,x_2,x_3)$ is divisible by $x_0x_3$. However, if we sum f over all values of $(x_1,x_2)$, then we can obtain the following equation:

$$\begin{aligned} \sum _{(x_1,x_2)\in \{0,1\}^{2}}f(x_0,x_1,x_2,x_3)=1+x_4. \end{aligned}$$

That is, the sum is dependent on the value of $x_4$.

2.3 Conditional Cube Tester

The concept of conditional cube tester was firstly proposed by Huang et al. [8] at Eurocrypt 2017. Their goal is to construct a key-dependent distinguisher. Therefore, they have to overcome the obstacle of how to involve the key information into the distinguisher. Motivated by this, they firstly classify the cube variables into two types: conditional cube variable and ordinary cube variable. The classification is based on the multiplying relations of the cube variables in the first two rounds as follows.

• Conditional cube variables can not multiply with each other after the round.

• Ordinary cube variables can not multiply with each other after the round.

• Ordinary cube variables can not multiply with conditional cube variables after the round.

Then, they develop a theorem to confirm the number of each type of the cube variables in order to establish a conditional cube tester, as specified below, whose proof is based on the relations of the cube variables in the first two rounds as above.

Theorem 2

[8]. For (n+2)-round Keccak sponge function ($n>0$), if there are p conditional cube variables $v_0, v_1, \ldots , v_{p-1}$ and $q=2^{n+1}-2p+1$ ordinary cube variables $v_p, v_{p+1}, \ldots , v_{p+q-1}$, then the term $v_{0}v_{1} \ldots v_{p+q-1}$ will not appear in the output polynomials of $(n+2)$-round Keccak sponge function.

To make conditional cube tester work, it is essential to introduce some conditions which will influence the above multiplying relations between the conditional cube variable and ordinary cube variable in the first two round. Specifically, only when all the introduced conditions hold will their multiplying relations be satisfied, thus making Theorem 2 work. Among the introduced conditions, the key-independent conditions can always be satisfied by controlling the input. For the key-dependent conditions, whether they are satisfied is detected by the conditional cube tester based on Theorem 2. To be more specific, the attack procedure can be briefly divided into three steps.

Step 1::

Except for the cube variables in the input state, the attacker assigns a random value to the remaining part of it, while keeping the key-independent bit conditions satisfied.

Step 2::

The attacker starts to exhaust all possible values of the cube variables and calculates the sum of all outputs.

Step 3::

If the sum is zero, then the attacker knows that the key-dependent bit conditions are satisfied with an overwhelming probability and therefore he can extract some equations for the involved key bits. Otherwise, the attacker knows the key-dependent bit conditions do not hold. For this case, the attacker will flip some bits involved in the key-dependent bit conditions and located in the controllable part of the input state. Then, he goto Step 2 again.

The above procedure is only used to extract a small number of equations for the key bits. To recover the full key, the attacker will repeat the above procedure by changing the parameters of the conditions cube tester to extract more equations for the key bits. Finally, the attacker can solve the obtained equation system to recover some key bits. The remaining key bits can be recovered by brute force.

3 Tracing Algorithm

Several algorithms to determine the relations of cube variables in the first two rounds have been presented in [8]. In this section, we introduce a new method to achieve the same goal. We do not claim that our new method have any advantages over [8]. The purpose to use this new method is only to suit our programming. Before introducing how to determine the candidates for ordinary cube variables, we firstly describe how to trace the propagation of a variable in $A_{\theta }^{0}$ to $A_{\pi }^{1}$.

Since $\theta$, $\rho$, $\pi$ are all linear transformations, an equivalent linear transformation matrix $M\in F_{2}^{1600\times 1600}$ can be derived to express these three consecutive operations $\pi \circ \rho \circ \theta$. From the definitions of the three operations, it can be known that for each row of M, there are only 11 non-zero elements, whose values are all 1. To reduce the size of M, we can only record the positions of M where the corresponding value is 1 in a smaller matrix SM of size $1600\times 11$. Specifically, suppose $M[i][J]=1$ $(J\in \{j_0,\ldots ,j_{10}\})$, then we construct a smaller matrix SM where $SM[i][t]=j_t$ for $0\le t\le 10$. Moreover, since the operation $\pi \circ \rho$ is equivalent to a permutation of bit positions, an equivalent permutation P of size 1600 can be derived to express it.

To make the tracing algorithm more explicit, we should consider the internal state as a boolean vector denoted by V rather than a three-dimensional array. In addition, assume the internal state is an 1600-bit variable. For other sizes of the internal state, the procedure to trace the propagation is similar. For the sake of convenience, we denote the state V after $\theta$, $\rho$, and $\pi$ in round i ($i\ge 0$) by $V_{\theta }^{i}$, $V_{\rho }^{i}$ and $V_{\pi }^{i}$ respectively. The input state of round i is denoted by $V^{i}$.

Now we describe how to trace the propagation of the variable in $A_{\theta }^{0}$ to $A_{\pi }^{1}$.

Step 1.:

Suppose $A_{\theta }^{0}[x][y][z]$ contains a variable, we record $t_0=(5x+y)\times 64+z$.

Step 2.:

Calculate how the variable in $V_{\theta }^{0}[t_0]$ propagates through $\pi \circ \rho$ operation with P. Consequently, we record $t_1=P[t_0]$.

Step 3.:

According to the definition of $\chi$, after $\iota \circ \chi$ operation, three bits of $V^{1}$ will contain the variable from $V_{\pi }^{0}[t_1]$. We denote the corresponding three bit positions by $t_2$, $t_3$ and $t_4$. Among the three bits, one bit will always contain this variable. The other two bits contain this variable depending on bit conditions. We classify these three bits into three types. The first type is the bit that always contains the variable. The second type is the bit that contains the variable depending on a key-independent bit condition. The third type is the bit that contains the variable depending on a key-dependent bit condition. Then, for each of the three bits, we trace how the variable in $V^{1}[pos]$ ($pos\in \{t_2,t_3,t_4\}$) propagates to $V_{\pi }^{1}$ with Algorithm 1. The bit positions of $V_{\pi }^{1}$ containing the variable from $V^{1}[pos]$ are stored in the array finalPosition.

Up until now, the propagation of the variable in $A_{\theta }^{0}$ to $A_{\pi }^{1}$ is known, i.e. the bit positions of $A_{\pi }^{1}$ containing the variable from $A_{\theta }^{0}$ are known and are classified into three types. At last, we only need focus on how the cube variable in $A^{0}$ propagates to $A_{\theta }^{0}$, which can be easily finished by considering the influence of $\theta$ operation.

Once knowing and recording how a variable propagates in the first two rounds with or without bit conditions to slow down this propagation, it is quite easy to determine their multiplying relations in the first two rounds. For example, suppose we know that $A_{\pi }^{0}[x][y][z]$ contains a variable $v^{\prime }$ and $A_{\pi }^{0}[x-1][y][z]$ contains a different variable $v^{\prime \prime }$, then $v^{\prime \prime }$ will multiply with $v^{\prime }$ after the first round. In the same way, suppose we know that $A_{\pi }^{1}[x][y][z]$ contains a variable $v^{\prime }$ and $A_{\pi }^{1}[x-1][y][z]$ contains a different variable $v^{\prime \prime }$, then $v^{\prime \prime }$ will multiply with $v^{\prime }$ after the second round.

4 Finding Ordinary Cube Variables for Keccak-MAC-384

In this section, we will expand on the procedure to find sufficient ordinary cube variables for Keccak-MAC-384. First, the potential candidates for ordinary cube variables will be determined by carefully adding key-independent bit conditions to slow down its propagation. Then, we consider the multiplying relations of these candidates after the first round and deduce some contradictions. As will be shown, from these contradictions, we can efficiently determine how many ordinary cube variables can eventually survive.

4.1 Determining Candidates for Keccak-MAC-384

The initial state of Keccak-MAC-384 is shown in Fig. 3 with 12 lanes set to 0. In the same way as [8, 9, 12], $A[2][0][0]=A[2][1][0]=v_0$ is chosen as the conditional cube variable with four bit conditions ($A_{\theta }^{0}[1][4][60]=1$, $A_{\theta }^{0}[1][0][5]=1$, $A_{\theta }^{0}[3][1][7]=0$, $A_{\theta }^{0}[3][2][45]=0$) to slow down its propagation. Then, the ordinary cube variables are set in the CP kernel. The complete procedure is as follows.

Fig. 3.

Initial state of Keccak-MAC-384

• For the first column, we exhaust all 64 possible variables $A[0][1][i]=A[0][2][i]$ $(0\le i\le 63)$. Based on Observations 1 and 2, if we add bit conditions to slow down the propagation of the variables in this case, all of them are key-dependent bit conditions. Therefore, we do not add bit conditions. For each of these 64 possible variables, the tracing algorithm is applied to determine its multiplying relation with the chosen conditional cube variable in the first two rounds. Only those are selected as candidates that they do not multiply with $v_0$ in the first two rounds.

• For the second column, we exhaust all 64 possible variables $A[1][1][i]=A[1][2][i]$ $(0\le i\le 63)$ and process in the same way as the first column.

• For the third column, we exhaust 63 $\times$ 3 possible variables $A[2][0][i]=A[2][1][i]$, $A[2][0][i]=A[2][2][i]$ and $A[2][1][i]=A[2][2][i]$ $(1\le i\le 63)$. Based on Observations 1 and 2, we can add key-independent bit conditions on $A_{\theta }^{0}[3][t]$ $(0\le t\le 4)$ to slow down the propagation of the variables. To remove the redundant conditions, we add a condition only when it is necessary. In other words, if such a condition is not added and the variable satisfies the required relation with $v_0$ in the first two rounds, this condition is not necessary and redundant. Moreover, if such a condition is added, the variable still does not satisfy the requirement, we filter this variable.

• For the forth column, we exhaust all 64 possible variables $A[3][0][i]=A[3][1][i]$ $(0\le i\le 63)$ and process in the same way as the first column since there are no key-independent bit conditions to slow the propagation of variables.

• For the fifth column, we exhaust 64 possible variables $A[4][0][i]=A[4][1][i]$ $(0\le i\le 63)$. Based on Observations 1 and 2, we can add key-independent bit conditions to slow down the propagation of variables as the third column.

The candidates found with our method are presented in Table 2.

Table 2. Candidates for Keccak-MAC-384, where c is an adjustable constant over GF(2) for each variable.

4.2 Discussion

Adding some bit conditions on $A_{\theta }^{0}[3][t]$ $(0\le t\le 4)$ as described above will cause the following bad cases.

Case 1::

Contradiction of conditions will occur. Specifically, for the third column, the bit condition on a certain bit i of $A^{0}_{\theta }[3][t_{0}]$ is $A^{0}_{\theta }[3][t_{0}][i]=0$. However, for the fifth column, the bit condition on a certain bit j of $A^{0}_{\theta }[3][t_{1}]$ is $A^{0}_{\theta }[3][t_1][j]=1$. If $i=j$ and $t_0=t_1$, the contradiction of conditions is detected. In other words, we can not choose both of their corresponding variables as the final ordinary cube variables. Moreover, if $A_{\theta }^{0}[3][y_0][z_0]$ and $A_{\theta }^{0}[3][y_1][z_0]$ are added on different bit conditions for $y_0>1,y_1>1$, this is also a contradiction since $A[3][y][z_0]$ is set to a constant 0 for Keccak-MAC-384 for $y>1$.

Case 2::

Contradiction between conditions and ordinary cube variables will occur. Specifically, for the forth column, some of $A[3][0][i]=A[3][1][i]$ $(0\le i\le 63)$ will be chosen as candidates. The bad case is that $A[3][0][t]=A[3][1][t]$ is chosen as a candidate and $A_{\theta }^{0}[3][0][t]$ or $A_{\theta }^{0}[3][1][t]$ is added on a condition.

Indeed, the second case can be processed in a simple way. After the candidates are determined, if a contradiction in the second case is detected, it implies that two ordinary variables multiplies with each other in the first round. For example, supposing $A_{\theta }^{0}[3][0][t]$ is added on a condition and $A[3][0][t]=A[3][1][t]$ is chosen as a candidate, it implies a variables set in A[2][4] or A[4][1] is chosen as a candidate, which will multiply with the variable set to A[3][0][t] after the first round. This can be seen from the $\pi \circ \rho$ operation in Fig. 2. Thus, the second case is equivalent to the case that two ordinary cube variables multiply with each other in the first round. Benefiting from this new property, we do not have to process the second bad case and only need concentrate on the relation of the candidates in the first round as well as the contradiction caused by conditions.

4.3 Deducing Contradictions

The contradictions of candidates are deduced from two cases. The first case is that variables multiply with each other in the first round. The second case is that there is contradiction of conditions. The contradictions deduced are displayed in Table 3. In this table, $v_{i}\{v_{j_0}, \ldots ,v_{j_n}\}$ means $v_i$ can not be chosen with any of $\{v_{j_0}, \ldots ,v_{j_n}\}$ as the final candidates at the same time. We count the times that each variable appears in these contradictions and do not choose the one which appears more than one time as marked in red and blue. However, although some variables appear two times as marked in green in this table, we can still choose them. Therefore, for the obtained contradictions, at most 28 variables can be derived. Moreover, there are 56 fully free variables, i.e. there are no contradictions on them.

Table 3. Contradictions of candidates

Observe that we consider the third column under three cases, which will cause two problems. Specifically, if $A[2][0][t]=A[2][1][t]+c$, $A[2][0][t]=A[2][2][t]+c$ and $A[2][1][t]=A[2][2][t]+c$ are chosen simultaneously, only two variables rather than three variables can be obtained. In this case, we should change the variables as $A[2][0][t]=v_{x_0}, A[2][1][t]=v_{x_1}, A[2][2][t]=v_{x_0}+v_{x_1}+c$. This is due to that the ordinary cube variables are set in the CP kernel. According to Table 2, there are 8 possible values for t and they are $\{1,14,15,20,41,52,61,62\}$. Therefore, for the worst case, we can finally obtain $28+56-8=76$ ordinary cube variables, which is much larger than the required number (63) to mount key-recovery attack on 7-round Keccak-MAC-384.

On the other hand, if two of $A[2][0][t]=A[2][1][t]+c$, $A[2][0][t]=A[2][2][t]+c$, $A[2][1][t]=A[2][2][t]+c$ are chosen simultaneously, we should change the variables as $A[2][0][t]=v_{x_0}, A[2][1][t]=v_{x_1}, A[2][2][t]=v_{x_0}+v_{x_1}+c$.

One choice of the 64-dimensional cube variables to establish the conditional cube tester is displayed in Table 4.

Table 4. One choice of ordinary cube variables for Keccak-MAC-384

5 Finding Ordinary Cube Variables for Keccak-MAC-512

Although 32-dimensional cube variables have been found with MILP to establish the 6-round conditional cube tester for Keccak-MAC-512 and the time complexity is practical, we want to explain how to apply our method to achieve the same goal. This is for a better understanding of the differences between our method and others based on MILP. Now, we expand on how to find sufficient cube variables for Keccak-MAC-512.

In a similar way for Keccak-MAC-384, 32 candidates for ordinary cube variables are discovered as displayed in Table 5. The corresponding contradictions are as follows.

$$\begin{aligned} v_2\{v_{24}\}, \ v_7\{v_{26}\}, \ v_9\{v_{27}\}, \ v_{14}\{v_{32}\}, \ v_{17}\{v_{21}\}. \end{aligned}$$

Table 5. Candidates for Keccak-MAC-512, where c is an adjustable constant over GF(2) for each variable.

Therefore, there will be $32-5=27$ possible ordinary cube variables in total if the ordinary cube variables are set only in the CP kernel. As a result, we can not mount key-recovery attack on 6-round Keccak-MAC-512, which requires 31 ordinary cube variables if only $v_0$ is chosen to be the conditional cube variable.

Based on [12], the variables which multiply with $v_0$ only in the second round can be leveraged as well. For an intuitive example, suppose one variable $v_{x_0}$ multiplies with $v_0$ only in the second round and the multiplying bit position is $p_0$. If another variable $v_{x_{1}}$ multiplies with $v_0$ only in the second round and the multiplying bit position is $p_0$ as well, then setting $v_{x_0}=v_{x_1}$ will cause the already filtered two variables become one possible variable. Then, the goal becomes how to find these possible variables.

Suppose $A_{\theta }^{0}[i][j][k]$ contains a variable, then after $\chi$ operation, three bits will contain this variable. Based on the definition of $\chi$ operation, among the three bits, one bit will always contain this variable and the other two bits contain this variable depending on the conditions. We classify the three bits into three types.

Type-1: :

It always contains this variable.

Type-2: :

It contains this variable depending on a key-independent bit condition.

Type-3: :

It contains this variable depending on a key-dependent bit condition.

Then, we trace how the three bits propagate to the second round with the tracing algorithm. Specifically, we trace the Type-1 bit and record the influenced bits of $A_{\pi }^{1}$ multiplying with $v_0$ in the second round. For the Type-2 and Type-3 bits, we process in the same way. The recorded bits for Type-1, Type-2 and Type-3 are defined as core bits, independent-key bits and key-dependent bits. Since our focus is the minimal key-dependent conditions, once the key-dependent bits are detected, the corresponding variable should not be chosen as a candidate.

With the above method, we reconsider the filtered ordinary cube variables set in the CP kernel. Besides, the variables set to a single bit are also considered. The final result obtained is displayed in Table 6.

For a better understanding of this table, we take the variable A[3][1][8] as instance. For the first column, it means A[3][1][8] is set to be a variable. For the second column, it means 5 bits of $A^{1}_{\pi }$ will multiply with $v_0$ only in the second round. For the third column, {656,1003} means the two bits of $A^{1}_{\pi }$, i.e. $A^{1}_{\pi }[0][2][16]$ and $A^{1}_{\pi }[0][3][43]$, will multiply with $v_0$ only in the second round depending on the same key-independent bit condition. The last column means A[3][1][8] can not be chosen as a variable with any of $v_{1}$ and $v_{31}$ in Table 5 simultaneously.

According to Table 6, at most three more possible ordinary cube variables can be obtained. One choice is as follows:

$$\begin{aligned}&A[3][0][58]=A[3][1][58]=A[2][0][24]=A[2][1][24]=v_{e_0},\\&A[3][0][61]=v_{e_1},A[3][1][61]=v_{e_2},\\&A[2][0][26]=A[2][1][26]=v_{e_3}, v_{e_3}=v_{e_2}+v_{e_1}\\&A[2][0][46]=A[2][1][46]=v_{e_2}.\\&\mathrm{Condition}: A_{\theta }^{0}[3][3][20]=0, A_{\theta }^{0}[3][4][21]=0, A_{\theta }^{0}[3][1][53]=0. \end{aligned}$$

According to Table 6, adding $A[2][0][37]=A[2][1][37]=v_{e_2}$ to the above variables and converting the bit condition $A_{\theta }^{0}[3][1][53]=0$ into $A_{\theta }^{0}[3][1][53]=1$ is also possible. However, it can not help improve the number of possible variables. In fact, there are many interesting cases. For example, if $A[3][0][60]=A[3][1][60]$ does not multiply with $v_{16}$ in the first round, we can obtain one more candidate. For the third row, if {652, 1109} does not depend on the same condition, then we can add one key-independent bit condition to prevent the propagation to the 652-nd bit and another key-independent bit condition to allow the propagation to the 1109-th bit of $A^{1}_{\pi }$.

Table 6. Possible candidates for Keccak-MAC-512

Then we test whether $v_{e_i}$ ($0\le i\le 3$) multiplies with each other in the first round and check whether the three bit conditions to slow down the propagation of $v_{e_1}$ and $v_{e_2}$ are contradict with the conditions in Table 5. It is shown that the three variables are all valid. Therefore, we can obtain at most $32-5+3=30$ ordinary cube variables without key-dependent bit conditions. It reveals in a way why [12] can only discover the same number of such ordinary variables with a solver. However, to mount key-recovery attack on 6-round Keccak-MAC-512, we need 31 ordinary cube variables. Thus, we try to search ordinary cube variables set in the CP kernel with only one key-dependent bit condition, which satisfy the required relation with $v_0$ and the chosen $32+4=36$ candidates for ordinary cube variables. Our searching result is displayed in Table 7. Thus, there are many possible choices for 31 ordinary cube variables, i.e. at least $2^{5}\,\times \,12$. The verification can be found at https://github.com/Crypt-CNS/Keccak_ConditionalCubeAttack.git.

Table 7. Candidates for Keccak-MAC-512 with one key-dependent bit condition

6 Recovering Full Key

In this section, a new slightly improved way to recover 128-bit key for Keccak-MAC is presented by removing unnecessary iterations of conditional cube tester. In [8], 64 iterations of the conditional cube tester were used to recover the 128-bit key for Keccak-MAC-256. For each iteration, it costs $2^{64+2}=2^{66}$ to recover 2-bit key. Observe that once there are only a few key bits to be recovered, there is no need to iterate the conditional cube tester since each iteration is costly and only 2 bits are recovered.

Taking Keccak-MAC-128/256 for instance, for the 64-dimensional cube variable [8], after 31 iterations in z-axis of the conditional cube tester, 62 bits of key can be recovered. Then, the remaining 66 bits can be recovered by brute force. Therefore, the time complexity is improved to $2^{66}\times 31+2^{66}=2^{71}$ from $2^{72}$. Similarly, for the 64-dimensional cube variables in Table 4, we can recover the 128-bit key for 7-round Keccak-MAC-384 with time complexity $2^{71}$.

For the conditional cube attack on 6-round Keccak-MAC-512, we choose $A[2][0][11]=A[2][1][11]$ in Table 7 as the ordinary cube variable with one key-dependent bit condition $A_{\theta }^{0}[1][4][7]=1$, while $A[2][0][19]=A[2][1][19]$ is chosen in [12]. For our choice, only 31 iterations in z-axis is enough. Then, $3\times 31=93$ bits can be recovered with time complexity $2^{32+3}\times 31=2^{35}\times 31$. The remaining $128-93=35$ bits can be recovered by brute force. The order to recover 93 bits of key with conditional cube tester is shown in Table 8. Therefore, the total time complexity becomes $2^{35}\times 31+2^{35}=2^{40}$. However, the time complexity is estimated as $\lceil \frac{128}{3}\rceil \times 2^{2^{5}+3}=\lceil \frac{128}{3}\rceil \times 2^{35}=2^{40.4}$ in [12], which implies 64 iterations of the conditional cube tester are used to recover the 128-bit key.

Table 8. The order to recover 93 bits of key with conditional cube tester

7 Comparison with Previous Work

Our work is heavily based on [8]. However, Huang et al. did not consider the potentially useful key-independent bit conditions to slow down the propagation of ordinary cube variables [8].

As for [9], it seems that the key-independent bit conditions have been considered. However, it is strange that Li et al. found 63 ordinary cube variables with 6 key-dependent bit conditions for Keccak-MAC-384, while we can find much more ordinary cube variables without key-dependent bit conditions, i.e. at least 76 variables. Besides, Li et al. only found 25 ordinary cube variables set in the CP kernel for Keccak-MAC-512, while we can find $32-5=27$ ordinary cube variables set in the CP kernel. Therefore, we guess that the key-independent bit conditions were not fully leveraged in [9].

As for [12], minimum key-dependent bit conditions is considered in the model. In that paper, one instance of 31 ordinary cube variables for Keccak-MAC-512 was presented, which is almost the same with what we found. However, it is strange that there are 18 key-independent bit conditions to slow down the propagation of the ordinary cube variables. With our approach, there are at most $10+3+1=14$ key-independent bit conditions for ordinary cube variables. If we choose the same cube variables as [12], only $9+3=12$ key-independent bit conditions are sufficient. Indeed, we can reach the minimum key-independent bit conditions, which is $8+3=11$. Thus, we guess the redundancy in key-independent bit conditions are not well processed in the modeling in [12]. It should be noted that the redundancy of key-independent bit conditions will not affect the time complexity to recover the key. However, from the scientific point, if there is a more accurate answer, why not choose it?

In addition, a new slightly improved approach to recover the 128-bit key is introduced. This is based on the observation that many iterations of the conditional cube tester are costly once a few bits of key are left. Consequently, we improve the conditional cube attack on 7-round Keccak-MAC-128/256/384 and 6-round Keccak-MAC-512.

8 Conclusion

An algorithm to search ordinary cube variables for Keccak-MAC is developed. The first step is to identify a small region of potential candidates by making full use of the key-independent bit conditions. Then, these candidates are further filtered according to their relations after the first round with an efficient approach. In this way, sufficient ordinary cube variables can be discovered to establish the conditional cube tester. Combined with the new slightly improved way to recover the key, the time complexity of the conditional cube attack on 7-round Keccak-MAC-128/256/384 and 6-round Keccak-MAC-512 are improved to $2^{71}$ and $2^{40}$ respectively.