You are looking at a specific version 20180119:123354 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.