Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Conditional Cube Attack on Reduced-Round Keccak Sponge Function

Huang, Senyang LU ; Wang, Xiaoyun ; Xu, Guangwu ; Wang, Meiqin and Zhao, Jingyuan (2017) 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2017 In Lecture Notes in Computer Science 10211.
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 cube-attack-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... (More)
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 cube-attack-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 reduced-round Keccak will not threat the security margin of Keccak sponge function.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; and
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Advances in Cryptology – Eurocrypt 2017 : 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part II - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part II
series title
Lecture Notes in Computer Science
volume
10211
publisher
Springer
conference name
36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2017
conference location
Paris, France
conference dates
2017-04-30 - 2017-05-04
external identifiers
  • scopus:85018676686
ISSN
0302-9743
1611-3349
ISBN
978-3-319-56613-9
978-3-319-56614-6
DOI
10.1007/978-3-319-56614-6_9
language
English
LU publication?
no
id
67acfbaa-4a93-4ef1-8335-84ca8eff923d
date added to LUP
2021-12-03 12:49:28
date last changed
2024-06-15 22:05:51
@inproceedings{67acfbaa-4a93-4ef1-8335-84ca8eff923d,
  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 cube-attack-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 reduced-round Keccak will not threat the security margin of Keccak sponge function.<br/><br/>}},
  author       = {{Huang, Senyang and Wang, Xiaoyun and Xu, Guangwu and Wang, Meiqin and Zhao, Jingyuan}},
  booktitle    = {{Advances in Cryptology – Eurocrypt 2017 : 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part II}},
  isbn         = {{978-3-319-56613-9}},
  issn         = {{0302-9743}},
  language     = {{eng}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science}},
  title        = {{Conditional Cube Attack on Reduced-Round Keccak Sponge Function}},
  url          = {{http://dx.doi.org/10.1007/978-3-319-56614-6_9}},
  doi          = {{10.1007/978-3-319-56614-6_9}},
  volume       = {{10211}},
  year         = {{2017}},
}