Cryptology ePrint Archive: Report 2017/1030

New MILP Modeling: Improved Conditional Cube Attacks to Keccak-based Constructions

Ling Song and Jian Guo and Danping Shi and San Ling

Abstract: In this paper, we propose a new MILP modeling to find better or even optimal choices of conditional cubes, under the general framework of conditional cube attacks. These choices generally find new or improved attacks against the keyed constructions based on Keccak permutation and its variants, including Keccak-MAC, KMAC, Keyak, and Ketje, in terms of attack complexities or the number of attacked rounds. Interestingly, conditional cube attacks were applied to round-reduced Keccak-MAC, but not KMAC despite the great similarity between Keccak-MAC and KMAC, and the fact that KMAC is the NIST standard way of constructing MAC from SHA-3. As examples to demonstrate the effectiveness of our new modeling, we report key recovery attacks against KMAC128 and KMAC256 reduced to 7 and 9 rounds, respectively; the best attack against Lake Keyak with 128-bit keys is improved from 6 to 8 rounds in the nonce-respected setting and 9 rounds of Lake Keyak can be attacked if the key size is of 256 bits; attack complexity improvements are found generally on other constructions. Our new model is also applied to Keccak-based full-state keyed sponge and gives a positive answer to the open question proposed by Bertoni et al. that whether cube attacks can be extended to more rounds by exploiting full-state absorbing. To verify the correctness of our attacks, reduced-variants of the attacks are implemented and verified on a PC practically. It is remarked that this work does not threaten the security of any instance analyzed in this paper.

Category / Keywords: Keccak, SHA-3, KMAC, Keyak, Ketje, Full-state, Conditional cube attack, MILP

Date: received 18 Oct 2017, last revised 13 May 2018

Contact author: songling at ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20180514:010547 (All versions of this report)

Short URL: ia.cr/2017/1030


[ Cryptology ePrint archive ]