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

Abstract

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.

Keywords

• GIMLI
• GIMLI‐HASH
• hash function
• preimage attack