Cryptology ePrint Archive: Report 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.

Category / Keywords: Keccak-MAC, Keyak, Ketje, MILP, Cube attack

Date: received 17 Jan 2018, last revised 19 Jan 2018

Contact author: biwenquan at mail sdu edu cn xiaoyangdong@tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20180119:123354 (All versions of this report)

Short URL: ia.cr/2018/075

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]