Paper 2019/392

New Conditional Cube Attack on Keccak Keyed Modes

Zheng Li and Xiaoyang Dong and Wenquan Bi and Keting Jia and Xiaoyun Wang and Willi Meier

Abstract

Conditional cube attack on round-reduced \textsc{Keccak} keyed modes was proposed by Huang et al. at EUROCRYPT 2017. In their attack, a conditional cube variable was introduced, whose diffusion was significantly reduced by certain key bit conditions. Then, a set of cube variables were found, that were not multiplied after the first round, meanwhile, the conditional cube variable was not multiplied with other cube variables (called ordinary cube variables) after the second round. This has an impact on the degree of the output of \textsc{Keccak} and hence gives a distinguisher. Later, MILP method was applied to find ordinary cube variables. However, for some \textsc{Keccak} based versions with low degrees of freedom, one could not find enough ordinary cube variables, which weakens or even invalidates the conditional cube attack. In this paper, a new conditional cube attack on \textsc{Keccak} is proposed. We remove the limitation that no cube variables multiply with each other in the first round. As a result, some quadratic terms may appear after the first round. We make use of some new bit conditions to prevent the quadratic terms from multiplying with other cube variables in the second round, so that there will be no cubic terms after the second round. Furthermore, we introduce the kernel quadratic term and construct a 6-2-2 pattern to reduce the diffusion of quadratic terms significantly, where the $\theta$ operation even in the second round becomes an identity transformation (CP-kernel property) for the kernel quadratic term. Previous conditional cube attacks on \textsc{Keccak} only explored the CP-kernel property of $\theta$ operation in the first round. Therefore, more degrees of freedom are available for ordinary cube variables and fewer bit conditions are used to remove the cubic terms after the second round, which plays a key role in the conditional cube attack on versions with very low degrees of freedom. We also use MILP method in the search of cube variables and give key-recovery attacks on round-reduced \textsc{Keccak} keyed modes. As a result, we reduce the time complexity of key-recovery attacks on 7-round \textsc{Keccak}-MAC-512, and 7-round \textsc{Ketje Sr} v2 from $2^{111}$, $2^{99}$ to $2^{72}$, $2^{77}$, respectively. Additionally, we have reduced the time complexity of attacks on 9-round \texttt{KMAC256} and 7-round \textsc{Ketje Sr} v1. Besides, practical attacks on 6-round \textsc{Ketje Sr} v1 and v2 are also given in this paper for the first time.