Cryptology ePrint Archive: Report 2016/790
Conditional Cube Attack on Reduced-Round Keccak Sponge Function
Senyang Huang, Xiaoyun Wang, Guangwu Xu, Meiqin Wang, Jingyuan Zhao
Abstract: The security analysis of Keccak, the winner of SHA-3, has
attracted considerable interest. Recently, some attention has been paid
to the analysis of keyed modes of Keccak sponge function. As a notable
example, the most efficient key recovery attacks on Keccak-MAC and
Keyak were reported at EUROCRYPT'15 where cube attacks and cubeattack-
like cryptanalysis have been applied. In this paper, we develop
a new type of cube distinguisher, the conditional cube tester, for Keccak
sponge function. By imposing some bit conditions for certain cube
variables, we are able to construct cube testers with smaller dimensions.
Our conditional cube testers are used to analyse Keccak in keyed modes.
For reduced-round Keccak-MAC and Keyak, our attacks greatly improve
the best known attacks in key recovery in terms of the number of rounds
or the complexity. Moreover, our new model can also be applied to
keyless setting to distinguish Keccak sponge function from random permutation.We provide a searching algorithm to produce the most efficient
conditional cube tester by modeling it as an MILP (mixed integer linear
programming) problem. As a result, we improve the previous distinguishing
attacks on Keccak sponge function significantly. Most of our attacks
have been implemented and verified by desktop computers. Finally we
remark that our attacks on the the reduced-round Keccak will not threat
the security margin of Keccak sponge function.
Category / Keywords: Keccak-MAC, Keyak, cube tester, conditional cube variable, ordinary cube variable
Original Publication (with minor differences): IACR-EUROCRYPT-2017
Date: received 18 Aug 2016, last revised 25 Jan 2017
Contact author: xiaoyunwang at mail tsinghua edu cn
Available format(s): PDF | BibTeX Citation
Version: 20190217:224315 (All versions of this report)
Short URL: ia.cr/2016/790
[ Cryptology ePrint archive ]