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.