Cryptology ePrint Archive: Report 2018/810

Cube-Attack-Like Cryptanalysis of Round-Reduced Keccak Using MILP

Ling Song and Jian Guo

Abstract: Cube-attack-like cryptanalysis on round-reduced Keccak was proposed by Dinur et al. at EUROCRYPT 2015. It recovers the key through two phases: the preprocessing phase for precomputing a look-up table and online phase for querying the output and getting the cube sum with which the right key can be retrieved by looking up the precomputed table. It was shown that such attacks are efficient specifically for Keccak-based constructions with small nonce or message block size. In this paper, we provide a mixed integer linear programming (MILP) model for cube-attack-like cryptanalysis on keyed Keccak, which does not impose any unnecessary constraint on cube variables and finds almost optimal cubes by balancing the two phases of cube-attack-like cryptanalysis. Our model is applied to Ketje Jr, Ketje Sr, a Xoodoo-based authenticated encryption and Keccak-MAC-512, all of which have a relatively small nonce or message block size. As a result, time complexities of 5-round attacks on Ketje Jr and 7-round attacks on Ketje Sr can be improved significantly. Meanwhile, 6-round attacks, one more round than the previous best attack, are possible if the key size of Ketje V1 (V2) is reduced to 72 (80) bits. For Xoodoo-based AE in Ketje style, the attack reaches 6 rounds. Additionally, a 7-round attack of Keccak-MAC-512 is achieved. To verify the correctness of our attacks, a 5-round attack on Ketje V1 is implemented and tested practically. It is noted that this work does not threaten the security of any Keccak-based construction.

Category / Keywords: secret-key cryptography / Ketje, Xoodoo, Keccak-MAC, cube attack, auxiliary variable, MILP

Original Publication (in the same form): ToSC 2018(3)

Date: received 1 Sep 2018

Contact author: songling at ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20180906:192303 (All versions of this report)

Short URL: ia.cr/2018/810


[ Cryptology ePrint archive ]