Paper 2018/075
MILP-aided Cube-attack-like Cryptanalysis on Keccak Keyed Modes
Wenquan Bi and Xiaoyang Dong and Zheng Li and Rui Zong and Xiaoyun Wang
Abstract
Cube-attack-like cryptanalysis was proposed by Dinur et al. at EUROCRYPT 2015, which recovers the key of Keccak keyed modes in a divide-and-conquer manner. In their attack, one selects cube variables that are not multiplied with each other (denoted as linear-cube) with the method of construction. The chosen cube variables are consecutive bits in one lane and the key bits they multiply with are still too many, which leads to that one can attack less rounds sometimes. In this paper, we introduce a new MILP model to solve the above problem. Using this new MILP tool, we find the optimal linear-cubes for Keccak-MAC, Keyak and Ketje that multiply with a minimum number of key bits in the first round. For example, when the capacity is 256, we find a new 32-dimension linear-cube for Keccak-MAC that only multiply with 18 key bits instead of Dinur et al.'s 64 bits and the complexity of the 6-round attack is reduced to $2^{42}$ from $2^{66}$. More impressively, using this new tool, we give the very first 7-round key-recovery attack on Keccak-MAC-512. We get the 8-round key-recovery attacks on Lake Keyak in nonce-respecting setting. In addition, we get the best attacks on Ketje Major/Minor. For Ketje Major, when nonce is 9 lanes, we could improve the best previous 6-round attack to 7-round. When comparing with Huang et al.'s conditional cube attack, the MILP-aided cube-attack-like cryptanalysis have larger effective range and get the best results on the Keccak keyed variants with relatively smaller degrees of freedom.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- Keccak-MACKeyakKetjeMILPCube attack
- Contact author(s)
- biwenquan @ mail sdu edu cn xiaoyangdong @ tsinghua edu cn
- History
- 2018-07-27: last of 3 revisions
- 2018-01-18: received
- See all versions
- Short URL
- https://ia.cr/2018/075
- License
-
CC BY