A preimage attack on reduced GIMLI-HASH with unbalanced squeezing phase

Yongseong Lee, Jinkeon Kang, Donghoon Chang, Seokhie Hong

Research output: Contribution to journalArticlepeer-review

Abstract

In Conference on Cryptographic Hardware and Embedded System 2017, Bernstein et al. proposed GIMLI, a 384-bit permutation with 24 rounds, which aims to provide high performance on various platforms. In 2019, the full-round (24 rounds) GIMLI permutation was used as an underlying primitive for building AEAD GIMLI-CIPHER and hash function GIMLI-HASH, which were submitted to the NIST Lightweight Cryptography Standardisation process and selected as one of the second-round candidates. In Transactions on Symmetric Cryptology 2021, Liu et al. presented a preimage attack with a divide-and-conquer method on round-reduced GIMLI-HASH, which uses 5-round GIMLI. In this paper, preimage attacks on a round-reduced variant of GIMLI-HASH is presented, in which the message absorbing phase uses 5-round GIMLI and the squeezing phase uses 9-round GIMLI. This variant is called as 5–9-round GIMLI-HASH. The authors’ preimage attack on 5–9-round GIMLI-HASH requires 296.44 time complexity and 297 memory complexity. Also, this method can be reached up to round shifted 10-round GIMLI in the squeezing phase. The authors’ first attack requires the memory for storing several precomputation tables in GIMLI SP-box operations. In the authors’ second attack, a time-memory trade-off approach is taken, reducing memory requirements for precomputation tables but increasing computing time for solving SP-box equations by using SAT solver. This attack requires 266.17 memory complexity and 296+ϵ time complexity, where ϵ is a time complexity for solving SP-box equations. The authors’ experiments using CryptoMiniSat SAT solver show that the maximum time complexity for ϵ is about 220.57 9-round GIMLI.

Original languageEnglish
Pages (from-to)66-79
Number of pages14
JournalIET Information Security
Volume17
Issue number1
DOIs
Publication statusPublished - 2023 Jan

Bibliographical note

Funding Information:
This work was supported as part of the Military Crypto Research Center (UD210027 XD) funded by the Defense Acquisition Program Administration (DAPA) and the Agency for Defense Development (ADD).

Publisher Copyright:
© 2022 The Authors. IET Information Security published by John Wiley & Sons Ltd on behalf of The Institution of Engineering and Technology.

Keywords

  • GIMLI
  • GIMLI-HASH
  • hash function
  • preimage attack

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'A preimage attack on reduced GIMLI-HASH with unbalanced squeezing phase'. Together they form a unique fingerprint.

Cite this