Paper 2019/1080

Preimages and Collisions for Up to 5-Round Gimli-Hash Using Divide-and-Conquer Methods

Fukang Liu, Takanori Isobe, and Willi Meier

Abstract

The Gimli permutation was proposed in CHES 2017 and the hash mode Gimli-Hash is now included in the Round 2 candidate Gimli in NIST's Lightweight Cryptography Standardization process. In the Gimli document, the security of the Gimli permutation has been intensively investigated. However, little is known about the security of Gimli-Hash. The designers of Gimli have claimed $2^{128}$ security against all attacks on Gimli-Hash, whose hash is a 256-bit value. Firstly, we present the trivial generic preimage attack on the structure of Gimli-Hash matching the $2^{128}$ security bound, both, in time and memory complexity. Following such a generic preimage attack framework, we then describe specific preimage attacks on the first 2/3/4/5 rounds and the last 2/3/4 rounds (out of 24) of Gimli-Hash using the divide-and-conquer methods. As will be shown, the application of the divide-and-conquer methods much benefits from the properties of the SP-box and the linear layer of Gimli. Therefore, this work can also be viewed as a first step to exploit specific properties of the SP-box. Finally, the divide-and-conquer method was also applied to a collision attack on up to 5-round Gimli-Hash. Among all the attacks, the preimage attacks on the first and the last 2 rounds of Gimli-Hash are practical. The collision attack on the first 3 rounds of Gimli-Hash is practical. The collision attack and second preimage attack on the last 3 rounds of Gimli-Hash are practical. All practical attacks are experimentally verified. We hope our analysis can advance the understanding of Gimli-Hash.

Note: We imrpoved several attacks in this new version. 1. List two new properties of the SP-box to help improve the corresponding attacks. 2. The preimage attacks on the first and last 2 rounds of Gimli-Hash are now practical. 3. The second preimage attack and collision attack on the last 3 rounds of Gimli-Hash are now practical. 4. All practical attacks have been verified. 5. The paper is reorganized.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
hash functionGimliGimli-Hash(second) preimage attackcollision attackdivide-and-conquer
Contact author(s)
liufukangs @ 163 com
takanori isobe @ ai u-hyogo ac jp
willimeier48 @ gmail com
History
2019-10-14: last of 4 revisions
2019-09-23: received
See all versions
Short URL
https://ia.cr/2019/1080
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1080,
      author = {Fukang Liu and Takanori Isobe and Willi Meier},
      title = {Preimages and Collisions for Up to 5-Round Gimli-Hash Using Divide-and-Conquer Methods},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1080},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1080}},
      url = {https://eprint.iacr.org/2019/1080}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.