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

초록

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 2(96.44) time complexity and 2(97) 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 2(66.17) memory complexity and 2(96+epsilon) time complexity, where epsilon is a time complexity for solving SP-box equations. The authors' experiments using CryptoMiniSat SAT solver show that the maximum time complexity for epsilon is about 2(20.57) 9-round GIMLI.

키워드