Antonio Flórez Gutiérrez

Gaëtan Leurent

María Naya-Plasencia

Léo Perrin

André Schrottenloher

Ferdinand Sibleyras

Internal Symmetries and Linear Properties: Full-permutation Distinguishers and Improved Collisions on Gimli *

Keywords: Gimli, symmetries, symmetric cryptanalysis, full-round distinguisher, collision attacks, linear approximations recovery Linear Differential-linear Internal symmetry

Gimli is a family of cryptographic primitives (both a hash function and an AEAD scheme) that has been selected for the second round of the NIST competition for standardizing new lightweight designs. The candidate Gimli is based on the permutation Gimli, which was presented at CHES 2017. In this paper, we study the security of both the permutation and the constructions that are based on it. We exploit the slow diffusion in Gimli and its internal symmetries to build, for the first time, a distinguisher on the full permutation of complexity 2 64 . We also provide a practical distinguisher on 23 out of the full 24 rounds of Gimli that has been implemented.

Next, we give (full state) collision and semi-free-start collision attacks on

Gimli-Hash, reaching respectively up to 12 and 18 rounds. On the practical side, we compute a collision on 8-round Gimli-Hash. In the quantum setting, these attacks reach 2 more rounds. Finally, we perform the first study of linear trails in Gimli, and we find a linear distinguisher on the full permutation.

Introduction

Gimli is a cryptographic permutation that was published at CHES 2017 [START_REF] Bernstein | Gimli : A crossplatform permutation[END_REF]. It is also the core primitive of a submission to the NIST lightweight cryptography project [START_REF] Bernstein | Gimli. Submission to the NIST Lightweight Cryptography project[END_REF] which is part of the 32 candidates that made it to the second round. It is intended to run well on a vast variety of platforms and contexts, from powerful processors supporting vector instructions to side-channel protected hardware.

A cryptographic permutation is a versatile primitive which is easily used to construct a hash function (as originally intended for this type of object [START_REF] Bertoni | ECRYPT hash workshop[END_REF]). It was later shown that they can also be used to build authenticated ciphers [START_REF] Bertoni | Duplexing the sponge: Singlepass authenticated encryption and other applications[END_REF],

pseudo-random number generators [START_REF] Bertoni | Sponge-based pseudorandom number generators[END_REF], etc. In all such structures, the security of the cryptographic function relies on the properties of the permutation. In particular, it is assumed in the underlying security proofs that the permutation used behaves like a permutation picked uniformly at random-apart of course from the existence of a compact implementation, a property which should not be expected from a random object.

By definition, a cryptographic permutation does not have a key. Thus, we cannot define its security level using a game that relies on distinguishing a random permutation from a keyed instance with a random key. Still, since it should behave like a permutation picked uniformly at random, we can assess its security level by trying to identify properties that hold for the permutation studied but which should not be expected for one picked uniformly at random. In this context, cryptanalysts can re-use approaches originally intended for block cipher cryptanalysis (e.g. differential attacks [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]). In fact, given that no key material is involved, we can also borrow techniques from hash function cryptanalysis such as rebound attacks [START_REF] Lamberger | The rebound attack and subspace distinguishers: Application to Whirlpool[END_REF].

The aim is usually then to obtain inputs of the permutation satisfying a certain property using an algorithm which is more efficient than the generic one, i.e. the one that would work on a random permutation.

Our Contributions. In this paper, we complete the original security analysis of the designers of Gimli by targeting both the permutation on its own, and the NIST candidate Gimli-Hash. Our results on the permutation are summarized in Figure 1 (plain lines). In order to account for the different costs of the generic attacks, we divided the logarithm of the time complexity of our distinguishers by the logarithm of the time complexity of the corresponding generic distinguisher.

In Figure 1, a distinguisher is valid if the ratio is under 1.0. Previous attacks from the literature are represented with dotted lines. The complexities of all our attacks (included those against the hash function) are given in Table 1, along with all the results from the literature we are aware of.

Our main result is a distinguisher of the full 24-round permutation with a cost of 2 64 , while a similar generic distinguisher has a cost of 2 96 . We also propose a distinguisher on 23 rounds that is practical, with a cost of 2 32 , and has been successfully implemented. These distinguishers exploit internal symmetries that are encouraged by the round function. The 23-round distinguisher could be extended by 1 round for free if the rounds were shifted.

Fig. 1. Comparison of various cryptanalysis techniques. Note that we may consider "shifted" variants of Gimli that do not start at round 24. Dotted lines correspond to results from the literature.

This attack is more efficient than a generic one for 18 rounds classically, and up to 20 quantumly. As a side note, these results provide a new example where quantum attacks reach more rounds than classical ones, much like in [START_REF] Hosoyamada | Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound[END_REF]. We also find a state-recovery attack on the authenticated encryption Gimli-Cipher

(which leads to a key-recovery) up to 12 rounds, with only 3 blocks of data.

In addition, we provide the first extensive study of the linear properties of the round function of Gimli. We design a full-round linear distinguisher and study faster differential-linear distinguishers on reduced-round variants.

Our implementations (23-round distinguisher, reduced-round collision attack, search for linear trails) are available at this URL 4 .

Differences with [START_REF] Flórez-Gutiérrez | New results on Gimli: full-permutation distinguishers and improved collisions[END_REF]. This article is an extended version of the paper "New Results on Gimli: Full-Permutation Distinguishers and Improved Collisions" which appeared in the proceedings of ASIACRYPT 2020 [START_REF] Flórez-Gutiérrez | New results on Gimli: full-permutation distinguishers and improved collisions[END_REF]. Our new contributions are the state-recovery attacks explored in Section 6 and the full-round linear distinguisher on Gimli in Section 7. The rest of the paper (e.g., the distinguishers of Section 3 and the collision attacks of Section 4) is unchanged with respect to the ASIACRYPT version.

Organization of the paper. The organization of the paper is as follows. In Section 2 we provide the description of the Gimli permutation and primitive, as well as previous known results. Section 3 provides the new distinguishers exploiting the internal symmetries that allow to distinguish the full permutation, and 4 https://project.inria.fr/quasymodo/files/2020/05/gimli_ cryptanalysis_eprint.tar.gz

Gimli-Hash

Divide-andconquer 2 42.4 32 [START_REF] Liu | Exploiting weak diffusion of Gimli: A full-round distinguisher and reduced-round preimage attacks[END_REF] 5 96 65.6 [START_REF] Liu | Exploiting weak diffusion of Gimli: A full-round distinguisher and reduced-round preimage attacks[END_REF] Preimages on

Gimli-XOF-128 9 104 70 [START_REF] Liu | Exploiting weak diffusion of Gimli: A full-round distinguisher and reduced-round preimage attacks[END_REF] Collisions on

Gimli-Hash

Divide-and- to build practical distinguishers up to 23 rounds. Section 4 presents improved collision and semi-free start collision attacks, and Section 5 their quantum counterpart. In Section 6, we use similar methods to perform state-recovery attacks on reduced-round versions of the AE scheme Gimli-Cipher. Section 7 presents our new results regarding statistical distinguishers, with new linear trails and differential-linear attacks. We conclude the paper in Section 8 with a summary, a discussion on the impact of our results and a proposal of tweak that would mitigate their reach.

Preliminaries

In this section we describe the Gimli permutation and we provide an overview of previous cryptanalysis results. The Gimli-Hash function is described directly in Section 4.

We adopt the following notations in this paper: ≪, ≫, ≪, ≫ represent respectively shift left, shift right, rotate left and rotate right operations. 𝑥, 𝑦, 𝑧 will denote elements of F 32 2 . SP is the 96-bit SP-Box. We denote 𝑥 𝑖 the (𝑖 mod 32) 𝑡ℎ bit of 𝑥 (𝑥 33 = 𝑥 1 ) with 𝑥 0 least significant (right-most). We denote the output of the SP box as SP(𝑥, 𝑦, 𝑧) = (𝑥 ′ , 𝑦 ′ , 𝑧 ′ ) and SP 2 (𝑥, 𝑦, 𝑧) = (𝑥 ′′ , 𝑦 ′′ , 𝑧 ′′ ).

The Gimli Permutation

State Structure. We denote by 𝑆 the 384-bit Gimli state, which is the concatenation of 4 columns of 96-bit, that we denote 𝐴, 𝐵, 𝐶, 𝐷, where 𝐴 is column number 0, and 𝐷 is column number 3. Each column is cut into three 32-bit words 𝑥, 𝑦, 𝑧 which are denoted e.g. 𝐴 𝑥 , 𝐴 𝑦 , 𝐴 𝑧 . Thus, the state is a 4 × 3 × 32 parallelepiped. We will speak of the 𝑥 lane to denote the sequence or concatenation of words 𝐴 𝑥 , 𝐵 𝑥 , 𝐶 𝑥 , 𝐷 𝑥 . SP-Box. The only non-linear operation in Gimli is the SP-Box, which is applied columnwise. On input 𝑥, 𝑦, 𝑧, it updates the three words as follows:

1. Rotate 𝑥 and 𝑦: 𝑥 ← 𝑥 ≪ 24, 𝑦 ← 𝑦 ≪ 9.

2. Perform the following non-linear operations in parallel (shifts are used rather than rotations): Rounds. Gimli applies a sequence of 24 rounds numbered from 24 downto 1 inclusively. Each round applies an SP-Box layer, then performs a swap (every two rounds, either a "big swap" or a small "small swap" as shown in Algorithm 1) and a constant addition (every four rounds). The constant at round 𝑖, if there is one, will be denoted rc 𝑖 in what follows. In Gimli we have: rc 𝑖 = 0x9e377900 ⊕ 𝑖.

𝑥 ← 𝑥 ⊕ (𝑧 ≪ 1) ⊕ ((𝑦 ∧ 𝑧) ≪ 2), 𝑦 ← 𝑦 ⊕ 𝑥 ⊕ ((𝑥 ∨ 𝑧) ≪ 1), 𝑧 ← 𝑧 ⊕ 𝑦 ⊕ ((𝑥 ∧ 𝑦) ≪ 3).
Note that all the attacks studied in this paper are independent of the choice of round constants.

An algorithmic depiction of full Gimli is given in Algorithm 1and it is depicted in Figure 10, where each wire represents a word.

Boolean Description of the SP-Box Now we give a full description of the SP box using Boolean functions:

for 𝑥 ′ :

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ 𝑥 ′ 0 = 𝑦 23 + 𝑧 0 𝑥 ′ 1 = 𝑦 24 + 𝑧 1 𝑥 ′ 2 = 𝑦 25 + 𝑧 2 𝑥 ′ 𝑖 = 𝑦 𝑖-9 + 𝑧 𝑖 + 𝑥 𝑖+5 𝑦 𝑖-12 , 3 ≤ 𝑖 ≤ 32 , (1)
Algorithm 1 The full Gimli permutation.

Input: State 𝑆 = 𝐴, 𝐵, 𝐶, 𝐷 Output: Gimli(𝑆)

{ 𝑦 ′ 0 = 𝑥 8 + 𝑦 23 𝑦 ′ 𝑖 = 𝑥 𝑖+8 + 𝑦 𝑖-9 + 𝑥 𝑖+7 + 𝑧 𝑖-1 + 𝑥 𝑖+7 𝑧 𝑖-1 , 1 ≤ 𝑖 ≤ 32 , (2)
and for 𝑧 ′ :

⎧ ⎪ ⎨ ⎪ ⎩ 𝑧 ′ 0 = 𝑥 8 𝑧 ′ 1 = 𝑥 9 + 𝑧 0 𝑧 ′ 𝑖 = 𝑥 𝑖+8 + 𝑧 𝑖-1 + 𝑦 𝑖-11 𝑧 𝑖-2 , 2 ≤ 𝑖 ≤ 32 . (3)
Description of the SP 2 Box. If 𝑥 ′ 0 = 𝑦 23 + 𝑧 0 as in Equation (1) then it naturally holds that 𝑥 ′′ 0 = 𝑦 ′ 23 + 𝑧 ′ 0 and thus we can use Equations ( 2) and (3) to get the full formula. Here we write some of them:

𝑥 ′′ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 𝑥 ′′ 0 = 𝑥 8 +
The 2-round probability 1 linear relation 𝑥 ′′ 0 + 𝑦 ′′ 0 + 𝑧 ′′ 0 = 𝑥 8 follows.

Previous work

We provide here a brief overview of the main previous third-party results of cryptanalysis against either the permutation or the NIST candidate Gimli. Notice that all the cryptanalysis previously considered were classical attacks, while in this paper, we will also give quantum attacks on reduced-round Gimli-Hash. Let us point out that no search of linear trails was done prior to our work.

Zero-sum permutation distinguishers on 14 rounds. In [START_REF] Cai | Zero-sum distinguishers for roundreduced Gimli permutation[END_REF], Cai, Wei, Zhang, Sun and Hu present a zero-sum distinguisher on 14 rounds of Gimli. This distinguisher uses the inside-out technique and improves by one round the integral distinguishers given by the designers.

Structural permutation distinguisher on 22.5 rounds. In [START_REF] Hamburg | Cryptanalysis of 22 1/2 rounds of Gimli[END_REF], Hamburg proposed the first third-party cryptanalysis of the Gimli permutation, providing distinguishers on reduced-round versions of the permutation. This analysis does not depend on the details of the SP-Box, and is based only on the slow diffusion of

Gimli. Thus, it follows a similar path as the distinguishers of Section we call an internal symmetry distinguisher, where states with symmetries are produced in the input and in the output of a reduced-round variant of Gimli.

A "hybrid" one adds a limited birthday-like property (which is absent from our distinguishers). The steps that they take are however different from ours, as this distinguisher only spans 14 rounds. Compared with our analysis in Section 3, they will actually start from a much more constrained middle state, which limits the number of rounds by which one can extend the distinguisher afterwards (or significantly increases the complexity). In contrast, we complete the middle state in multiple successive steps, each step ensuring that more rounds will be later covered. The ZID distinguisher targets 18 rounds of Gimli with a negligible complexity. After the publication of our results, and personal communications, the authors updated their ePrint report [START_REF] Liu | Exploiting weak diffusion of Gimli: A full-round distinguisher and reduced-round preimage attacks[END_REF]. They proposed to modify our distinguisher of Section 3 to reduce the complexity from 2 64 to 2 52 .

Collisions and Preimages on Gimli-Hash. In [START_REF] Zong | Collision attacks on round-reduced Gimli-Hash/Ascon-Xof/Ascon-Hash[END_REF], Zong, Dong and Wang study

Gimli among other candidates of the competition. They present a 6-round collision attack on Gimli-Hash of complexity 2 113 , using a 6-round differential characteristic where the input and output differences are active only in the rate. This differential characteristic was invalidated in [START_REF] Liu | Automatic verification of differential characteristics: Application to reduced Gimli[END_REF].

In [START_REF] Liu | Preimages and collisions for up to 5-round Gimli-Hash using divide-and-conquer methods[END_REF], [START_REF] Liu | Exploiting weak diffusion of Gimli: A full-round distinguisher and reduced-round preimage attacks[END_REF] and [START_REF] Liu | Automatic verification of differential characteristics: Application to reduced Gimli[END_REF] Liu, Isobe and Meier give collision and preimage attacks on reduced-round Gimli-Hash. Their attacks rely on divide-and-conquer methods, exploiting the lack of diffusion between the columns, as did Hamburg, but they also rely on SP-Box equations in order to attack the hash function itself. These equations are different from those that we will solve in Section 4, and they mostly relate the input and outputs of a single SP-Box, whereas we study directly two SP-Boxes. Their analysis is also much more precise, since they prove running times of solving these equations.

After giving a meet-in-the-middle generic preimage attack of time and memory complexity 2 128 , which sets a bound against the sponge construction used in Gimli-Hash, they give practical preimage attacks on 2-round Gimli-Hash and practical collision attacks on 3-round Gimli-Hash. They give a collision attack on 5-round Gimli-Hash with a time complexity 2 65 and a second preimage attack with time complexity 2 96 . They give in [START_REF] Liu | Exploiting weak diffusion of Gimli: A full-round distinguisher and reduced-round preimage attacks[END_REF] a preimage attack on 5-round Gimli-Hash. In [START_REF] Liu | Automatic verification of differential characteristics: Application to reduced Gimli[END_REF], they give a semi-free start collision attack on 8 rounds and a state-recovery attack on the AE scheme for 9 rounds.

On the Notion of Distinguisher

Some of our results are "distinguishers" targeting the Gimli permutation itself.

However, as there is a unique instance of this permutation, what is the meaning of "distinguishing" it from a random permutation?

As far as primitives are concerned, distinguishers are normally defined for keyed algorithms, and work as follows (in the case of a block cipher). First, an 𝑛-bit block cipher 𝐸 𝑘 is instantiated with a key 𝑘 picked uniformly at random from the relevant set, and a permutation 𝑃 of F 𝑛 2 is picked uniformly at random from the set of such permutations. Then, the attacker is given black-box access to both algorithms and their task is to figure out which is which with a success probability greater than 1/2.

This notion of distinguisher breaks down when we look at cryptographic permutations. Indeed, since there is no key, the permutation 𝜋 used is picked from a set of size 1, and thus the attacker could simply query for instance 𝑃 (0) and, if it is equal to 𝜋(0), win the game with overwhelming probability.

At the same time, it is also obvious that cryptographic permutations must satisfy specific requirements in order for them to be valid building blocks for secure hashing or AEAD. To take a trivial example: using the notion of distinguisher outlined above, it is not much harder to distinguish the Keccak permutations from random than it is to distinguish the identity from random. And yet, instantiating a sponge with each of these permutations yields hash functions with vastly different security levels.

As we can see, the problem of defining a distinguisher for a fixed permutation is in fact close to that of defining one for an open key cipher, i.e. a block cipher instantiation for which the key is known. A first notion to capture the meaning of "distinguisher" in this context was proposed by Gilbert in [START_REF] Gilbert | A simplified representation of AES[END_REF], namely that of T-intractable relation. Informally, a T-intractable relation ℛ is such that it is infeasible to find a set 𝑋 = (𝑥 0 , . . . , 𝑥 𝑖 ) of inputs and a corresponding set 𝑌 = (𝑃 (𝑥 0 ), . . . , 𝑃 (𝑥 𝑖 )) of outputs such that 𝑋 ℛ 𝑌 in time less than 𝑇 if 𝑃 is a permutation picked uniformly at random. Of course, the definition of ℛ cannot be chosen arbitrarily-otherwise, we could simply define ℛ to be such that 𝑥 ℛ 𝐸 𝑘 (𝑥). For a keyed primitive, the relation should not depend on the key.

As a consequence, it is natural to rely on linear structures to define a relationship ℛ that may be of interest when assessing the security level of a cryptographic permutation. The limited birthday [START_REF] Gilbert | Super-sbox cryptanalysis: Improved attacks for AES-like permutations[END_REF][START_REF] Iwamoto | Limited-birthday distinguishers for hash functions -collisions beyond the birthday bound can be meaningful[END_REF], originally intended for hash functions, is an approach in this direction. The idea is to find pairs of inputs (𝑥, 𝑥 ′ ) such that the pair (𝑥 ⊕ 𝑥 ′ , 𝐻(𝑥) ⊕ 𝐻(𝑥)) lives in a vector space of a high dimension.

If these pairs can be found faster than with a classical birthday search, then it is a distinguisher.

In this paper, we propose another type of distinguisher whereby we generate an input 𝑥 such that (𝑥, 𝑃 (𝑥)) lives in a specific affine space. As with the limited birthday, if this can be done faster than with a brute-force approach, then it can be seen as a distinguisher.

More generally, we consider that a distinguisher for a permutation is an algorithm that can return (tuples of ) input/output pairs in a specific affine space that is more efficient than the generic algorithm. As the aim of a cryptographic permutation is to yield complex and non-linear relations between its input and output, we claim that this approach is the correct one to assess the security of a keyless cryptographic permutation.

Internal Symmetry Distinguishers against Gimli

In this section we present new distinguishers on the Gimli permutation. Our distinguishers improve upon the best previously known ones, reaching the full 24round permutation. They are practical on 23 rounds and have been implemented.

The results presented in this section do not exploit the specifics of the SP-Box: they would work equally well if the SP-Box was replaced with a permutation picked uniformly at random. Like all the other analyses presented in this paper, they do not depend on the values of the round constants.

Our distinguishers rely on internal symmetries. The general idea consists in identifying a specific form of symmetry (formally, a vector space) that is preserved by the round function under some circumstances, and then trying to craft an input for the permutation such that this symmetry traverses all the rounds so that the output has the same type of property.

In our case, we formalize the symmetry using the notion of 2-identical states.

Definition 1 (2-identical states). A state 𝑆 is 2-identical if 𝐵 = 𝐷, if 𝐴 = 𝐶, or if one of these properties holds up to a swap and a constant addition.

Our internal symmetries distinguisher aims at finding a 2-identical input that is mapped to a 2-identical output. Since there are 96 bits of constraint, a generic algorithm returning such an input should run in time 2 96 by evaluating the permutation on a set of inputs satisfying the property until the output matches it by chance. Our aim is to find more efficient algorithms in the case of Gimli.

This definition is similar to the one used in [START_REF] Derbez | Cryptanalysis results on Spook -bringing full-round Shadow-512 to the light[END_REF]. In fact, an internal symmetry distinguisher can be seen as a stronger variant of a limited birthday distinguisher of the type used in [START_REF] Derbez | Cryptanalysis results on Spook -bringing full-round Shadow-512 to the light[END_REF]. Indeed, we can build a limited birthday pair using our distinguisher: by producing a pair of inputs 𝑆, 𝑆 ′ satisfying the internal symmetry property, we obtain 𝑆 ⊕ 𝑆 ′ ∈ 𝑉 𝑖𝑛 and 𝛱(𝑆) ⊕ 𝛱(𝑆 ′ ) ∈ 𝑉 𝑜𝑢𝑡 . Further, since the converse is not true, an internal symmetry distinguisher is strictly stronger.

From now on, 𝑆 𝑖 denotes the Gimli state before round 𝑖.

23-round Practical Distinguisher

We design an internal symmetry distinguisher on 23 rounds of Gimli, that is represented in Figure 2, running in time equivalent to 2 32 evaluations of Gimli on average. Algorithm 2 starts from a symmetric state in the middle and completes the state 𝑆 11 in three steps. Each step assigns a value to more words of the state, and ensures that the 2-identical symmetry property traverses more rounds.

Each step of Algorithm 2 requires to evaluate a few SP-Boxes 2 32 times (we do not even need to evaluate the inverse SP-Box). The total amount of computations is smaller than 2 32 evaluations of 23-round Gimli. Notice also that the algorithm uses only a small amount of memory. Our implementation of Algorithm 2 ran in less than one hour on a regular laptop.

The time complexity of the algorithm can be computed as follows: 8 × 2 32 SP-Box evaluations for the first step, 8 × 2 32 for the second and 16 × 2 32 for the third, meaning a total of 8 × 2 32 + 8 × 2 32 + 16 × 2 32 = 40 × 2 32 which is less than 2 32 evaluations of 23-round Gimli (each of them consisting essentially of 92 SP-Box evaluations). This complexity is to be compared to that of the generic algorithm for obtaining our internal symmetry property, which costs 2 96 . Below, we provide an example of input-output pair that we obtained, with a 2-identical input 𝑆 that remains 2-identical after Gimli(23, 1):

7f9fcf70 6aedf7e6 7f9fcf70 cb2f0e6a Input:
0ba2f1f9 f339b619 0ba2f1f9 f70cf15c b2ee8259 df0b4801 b2ee8259 3856106d a8ef848d 8c17b743 9615b3bc 8c17b743 Output: 541122c5 30530879 8d9d5d30 30530879 74b6dbe6 18885a6e 744b55c1 18885a6e

Distinguisher on full Gimli and Extensions

Here we will describe how to extend the 23-round distinguisher to the full Gimli permutation, and even to more rounds. All these results are summarized in Step 1

⊕ rc20 ⊕ rc16 ⊕ rc12 9
Step 2

Step 3

Fig. By repeating the previous procedure 2 32 times, we should find an input value that verifies the output property. The generic complexity of finding a 2-identical input that generates a 2-identical output is still 2 96 . Thus, full Gimli can be distinguished in time less than 2 32+32 = 2 64 full Gimli evaluations, and constant memory.

An interesting question is: how many rounds of a Gimli-like permutation can we target? The distinguisher works mainly because the diffusion in Gimli is somewhat slow. Thus, a possible fix would be to increase the number of swaps, for example by having one in each round instead of every two rounds. An attack exploiting this behaviour that worked previously for 𝑟 rounds would now a priori work for 𝑟/2 rounds only. Of course, the details of the SP-box could allow further improvement of these results given that a single iteration would now separate the swaps rather than a double.

Extending to 28 Rounds. It is trivial to adapt this distinguisher to an extended version of Gimli with more rounds. The 2-identicality of 𝑆 0 is preserved after one round since the next round would apply only an SP-Box layer and a small swap.

Similarly, the 2-identicality of 𝑆 24 is preserved after 3 more inverse rounds since the next swap operation is a big swap which exchanges data between 𝐴 and In this section, we describe collision attacks on Gimli-Hash when it is instantiated with a round-reduced variant of Gimli. Table 2 summarizes our results.

The Gimli-Hash Function

This function is built using the Gimli permutation in a sponge construction [START_REF] Bertoni | On the indifferentiability of the sponge construction[END_REF],

represented in Figure 3.

Gimli-Hash (Algorithm 5) initializes the Gimli state to the all-zero value. The message is padded and separated into blocks of size 𝑟 = 128, which corresponds to the rate 𝑟, introducing message blocks of 128 bits between two permutation applications by XORing them to the first 128 bits of the state. Once all the padded message blocks are processed, a 32-byte hash is generated by outputting 16 bytes of the internal state, applying once more the permutation, and outputting 16 additional ones. In Gimli-Hash, the rate part is formed of the words 𝐴 𝑥 , 𝐵 𝑥 , 𝐶 𝑥 , 𝐷 𝑥 and the capacity part of 𝐴 𝑦,𝑧 , 𝐵 𝑦,𝑧 , 𝐶 𝑦,𝑧 , 𝐷 𝑦,𝑧 .

We will consider two kinds of collision attacks:

-Full-state collision attacks: we will build pairs of two-block messages 𝑀 0 , 𝑀 1 and 𝑀 0 , 𝑀 ′ 1 such that the state after absorbing these pairs becomes again equal. Thus, one can append any sequence of message blocks after this and obtain the same hash.

-Semi-freestart collision attacks: we will build pairs of (384-bit) states 𝑆, 𝑆 ′ such that 𝑆 differs from 𝑆 ′ only in a single 𝑥, and after 𝑟 rounds of Gimli, 𝜋(𝑆) and 𝜋(𝑆 ′ ) differ only in a single 𝑥 as well. This does not yield a collision on the hash function as we would need to choose the value of the same initial state; however, it represents a vulnerability that may be used in the context of the Gimli modes of operation. For example, in Gimli-cipher, the initial state contains a key of 256 bits and a nonce of 128 bits which is put in the 𝑥 values. Then each block of plaintext is handled in the same way as Gimli-hash. Thus, by XORing the right values before and after 𝜋, one can create a key, a nonce and a pair of messages which yield the same tags.

SP-Box Equations and How to Solve Them

All collision attacks in this section exploit the slow diffusion of Gimli and the simplicity of the SP-Box (contrary to the distinguishers on the permutation, which worked regardless of the SP-Box used). In this section, we describe a series of "double SP-Box equations"; solving them will be the main building block of our attacks. We define the following equations.

Given 𝑦, 𝑧, find 𝑥 ̸ = 𝑥 ′ such that 𝑆𝑃 2 (𝑥, 𝑦, 𝑧) 𝑥 = 𝑆𝑃 2 (𝑥 ′ , 𝑦, 𝑧) 𝑥 . [START_REF] Bertoni | ECRYPT hash workshop[END_REF] Given 𝑦, 𝑧, 𝑦 ′ , 𝑧 ′ , find 𝑥 such that 𝑆𝑃 2 (𝑥, 𝑦, 𝑧) 𝑥 = 𝑆𝑃 2 (𝑥, 𝑦 ′ , 𝑧 ′ ) 𝑥 . [START_REF] Bertoni | On the indifferentiability of the sponge construction[END_REF] Given 𝑦, 𝑧, 𝑦 ′ , 𝑧 ′ , find 𝑥 such that 𝑆𝑃 2 (𝑥, 𝑦, 𝑧) 𝑧 = 𝑆𝑃 2 (𝑥, 𝑦 ′ , 𝑧 ′ ) 𝑧 . [START_REF] Bertoni | Sponge-based pseudorandom number generators[END_REF] Given 𝑦, 𝑧, 𝑥 ′ , find 𝑥 such that 𝑆𝑃 2 (𝑥, 𝑦, 𝑧) 𝑥 = 𝑥 ′ . [START_REF] Bertoni | Duplexing the sponge: Singlepass authenticated encryption and other applications[END_REF] Number of Solutions. Except Equation [START_REF] Bertoni | ECRYPT hash workshop[END_REF], all these equations have on average, when the inputs are drawn uniformly at random, a single solution. However, the variance on the number of solutions depends on the equation considered.

For example, only approx. 6.2% of inputs to Equation ( 8) have a solution, and they have on average 82.4 solutions each. Equation [START_REF] Bertoni | Duplexing the sponge: Singlepass authenticated encryption and other applications[END_REF] gives a little more than 1.5 solutions. This variance is not a problem for us, as long as we can produce efficiently all solutions of the equations, which remains the case. In order to simplify our presentation, we will do as if equations ( 8), ( 9) and (10) always gave exactly a single solution for each input.

Solving the Equations. We use an off-the-shelf SAT solver [START_REF] Soos | Extending SAT solvers to cryptographic problems[END_REF]. In some cases, more time seems spent building the SAT instance rather than solving it, and we believe that our current implementation is highly unoptimized.

The solver allows us to retrieve all solutions of a given equation (we treat Equation [START_REF] Bertoni | ECRYPT hash workshop[END_REF] differently because it has on average 2 32 of them). Let us consider the average time to produce a solution when random inputs are given. On a standard laptop, this time varies between approximately 0.1 milliseconds (Equation ( 8)) and 1 millisecond (Equation ( 10)). This difference mainly stems from the fact that Equation ( 8) often has no solutions, and that the solver quickly finds a counterexample, while Equation [START_REF] Bertoni | Duplexing the sponge: Singlepass authenticated encryption and other applications[END_REF] practically always has solutions that must be found.

On the same computer, an evaluation of the full Gimli permutation (not reduced-round) takes about 1 microsecond, so there is approximately a factor 1000 between computing Gimli and solving a double SP-Box equation.

We consider that all equations have approximately the same complexity and introduce a factor 𝑡 𝑒 that expresses the time taken to solve them in number of evaluations of Gimli or a reduced-round version (depending on the studied case).

Practical 8-round Collision Attack

We consider 8 rounds of Gimli, e.g. rounds 21 to 14 included, and name Gimli [START_REF] Gleixner | The SCIP Optimization Suite 6.0[END_REF][START_REF] Brassard | Quantum cryptanalysis of hash and claw-free functions[END_REF] this reduced-round permutation. We omit the last swap, because it has no incidence (it only swaps 𝑥 values). The situation is represented on Figure 4. As before, we name 𝑆 𝑖 the partial state immediately before round 𝑖.

Algorithm 3 finds on average a single solution, with any input state. There is some variance on the number of solutions, that is induced by the SP-Box equations, but it is small in practice. Furthermore, we can eliminate the memory requirement by solving Equation [START_REF] Bertoni | ECRYPT hash workshop[END_REF] for many input random states. Starting from a given state, it suffices to apply one more Gimli permutation with a random message block, in order to re-randomize the input.

Remark that if we omit the second step then we already have a semi-free-start collision attack, because we can reconstruct the inputs 𝐶 21 and 𝐷 21 immediately from the middle.

Practical Application: first step. In our practical computations, we considered rounds 21 to 14 included. We solved step 1, starting from 0, 0, 0, 0 and using a random message 𝑚 1 , 0, 0, 0 to randomize the first block. We also solved at the same time the two Equations ( 10) that enabled us to go back to 𝐴 17 𝑥 , 𝐵 17 𝑥 .

We had to produce 15582838652 ≃ 2 33.86 solutions for Equation ( 7) until we found a solution for Step 1 and for both equations. We verified experimentally that each solution for Equation ( 7) yielded on average a solution for the final equation. We obtained in total 5 solutions (Table 3). There are two different solutions for 𝐴 15 𝑥 ⊕ rc 16 , which yield two and three solutions respectively for 𝐵 17

𝑥 .

The total computation ran in less than 5000 core-hours. It was easy to run on many concurrent processes as this algorithm is trivial to parallelize.

Practical Application: second step. We solved step 2, that is, looking for 𝐶 𝑥 (in red on Figure 4). We expect on average a single solution, and little variation on the number of solutions, as only Equation ( 10) is involved.

Step 2: find 𝐵 21 𝑥 , 𝐶 21 𝑥 , 𝐷

Semi-free Start Collisions on Reduced-round Gimli

We will now design semi-free start collision attacks based on the same principle.

This time, our goal is to obtain two input states 𝑆, 𝑆 ′ that differ only in the rate (in practice, only in 𝐴 𝑥 ) and such that after applying a reduced-round Gimli, the output states differ only in the rate (the 𝑥 values). They can also be seen as finding one state and two pairs of 2-block messages such that after inserting both messages we obtain a collision. The previous "first step" remains the same, with an extension to whichever number of rounds we are targeting. The "second step" is changed, because we can now choose completely the columns 𝐵, 𝐶, 𝐷, e.g. by starting from the middle instead of having to choose only the input rate. dc84bf38 00000000 00000000 00000000 dc84bf38 00000000 00000000 00000000

Second message block bbdb41f3 4333192c bc17e444 8a9d06c7 1b1da6e4 4333192c bc17e444 8a9d06c7

Third message block 00000000 00000000 00000000 00000000 00000000 00000000 afad801e 00000000

Starting state (first message block)

dc84bf38 00000000 00000000 00000000 dc84bf38 00000000 00000000 00000000

Second message block bbdb41f3 4333192c 971398fb 2fbe55ce 1b1da6e4 4333192c 971398fb 2fbe55ce

Third message block 00000000 00000000 00000000 00000000 00000000 00000000 afad801e 00000000 Doing this allows us to reach 4 rounds more for the same cost as before, as outlined on Figure 5 and Algorithm 4. We can then append new rounds as before, reaching 16 rounds classically in time 2 96 × 10 × 𝑡 𝑒 .

Another Improvement using Precomputations. We are going to win a factor 2 is slightly below 2 96 evaluations of Gimli, since fewer SP-Boxes are evaluated in each step than in the full primitive.

Better Quantum Collision Attacks

In this section, we explain how our attacks can be extended in the quantum setting, where even more rounds can be broken. We want to emphasize that, as our goal is simply to determine a security margin, we will not go into the details of the implementation of these attacks as quantum algorithms. We will only show how to use well-known building blocks of quantum computing in order to build these new attacks, and show why they perform better than the corresponding generic quantum attacks. At this point, we assume that the reader is familiar with the basics of quantum computing that are covered in textbooks such as [START_REF] Nielsen | Quantum information and quantum computation[END_REF].

We define quantum algorithms in the quantum circuit model. The circuit starts with a set of qubits (elementary quantum systems) initialized to a basis state and applies quantum operations. The state of the system lies in a Hilbert space of dimension 2 𝑛 if there are 𝑛 qubits. Quantum operations are linear operators of this space, and a quantum circuit is built from such elementary operators Algorithm 4 12-round semi-free start collision attack (see Figure 5).

Input: an initial 𝐴 (can be given) Output 𝐴𝑥, 𝐴 ′ 𝑥 , 𝐵, 𝐶, 𝐷 such that after Gimli [START_REF] Gleixner | The SCIP Optimization Suite 6.0[END_REF][START_REF] Bertoni | Duplexing the sponge: Singlepass authenticated encryption and other applications[END_REF], only the rate differs.

As before, we don't write the last swapping step.

Step 1: Same step as in Algorithm 3, extended to 12 rounds. It gives a total of 10 32-bit branches (input values) that are required, that are represented in red on Figure 5.

Step 2: we will start from the middle.

1. We take an arbitrary value for 𝐵 𝑥 that must be met, we obtain the whole state by solving another simple SP-Box equation (which is not Equation ( 10), but has a similar form).

4. Having deduced 𝐶 15 , we have only 2 -32 chances of obtaining the right 𝐶 17 𝑥 , so we have to repeat all of this 2 32 times.

In total, we have to solve 5 SP-Box equations, 2 32 times, in both steps, so the time complexity is 2 32 × 10 × 𝑡𝑒. coined quantum gates. The result of a quantum computation is accessed through measurement of the qubits, which destroys their state.

The cryptanalytic algorithms that we consider in this section do not require any form of query to a black-box, since we want only to build a collision on the hash function. Thus, they do not require any more specific model (e.g. the Q2 model used in some works in quantum cryptanalysis).

Tools, Model and Complexity Estimates

Most of the collision attacks presented in this section rely on an exhaustive search. For example, consider the 8-round attack of Algorithm 3. Both steps are exhaustive searches in spaces of size 2 32 that contain on average a single solution:

-In the first step, we find 𝐴 21 𝑥 such that, after solving a sequence of SP-Box equations, a 32-bit condition is met: the first equation finds 𝐴 ′21 𝑥 such that there is a collision in 𝑥 after two SP-Boxes, the second equation finds 𝐴 19 𝑥 such that there is a collision in 𝑥 after two SP-Boxes, etc., and the final 32-bit condition is that 𝐴 ′13 𝑧 and 𝐴 13 𝑧 must collide.

-In the second step, we find the good 𝐶 21

𝑥 by guessing it and trying to match with a 32-bit condition.

Quantumly, Grover's algorithm [START_REF] Grover | A fast quantum mechanical algorithm for database search[END_REF] speeds up exhaustive search quadratically. Amplitude Amplification [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF] is a powerful generalization which applies to any pair 𝒜, 𝜒 such that:

-𝒜 is a quantum algorithm without measurements (a unitary and reversible operation), that takes no input and produces an output 𝑥 ∈ 𝑋.

-𝜒 : 𝑋 → {0, 1} is a function that decides whether 𝑥 ∈ 𝑋 is a "good" output of 𝒜 (𝜒(𝑥) = 1) or a "failure" of 𝒜, such that 𝜒 can also be implemented as a quantum algorithm.

Theorem 1 (Amplitude Amplification [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF], informal). Let 𝒜 be a quantum algorithm without measurements that succeeds with probability 𝑝 and 𝑂 𝜒 be a quantum algorithm that tests whether an output of 𝒜 is a failure or not. Then there exists a quantum algorithm that finds a good output of 𝒜 using 𝑂(

√ 1/𝑝)
calls to 𝒜 and 𝑂 𝜒 .

Quantum Embeddings. Any classical algorithm admits a quantum embedding, that is, a quantum algorithm that returns the same results. Note that this is not a trivial fact, because a quantum algorithm without measurement is reversible.

Definition 2. Let 𝒜 be a randomized algorithm with no input. A quantum embedding for 𝒜 is a quantum algorithm 𝒜 ′ that has no input, and the distribution over the possible outcomes of 𝒜 ′ (after measurement) is the same as the distribution over possible outcomes of 𝒜.

This quantum embedding admits similar time and space complexities, where classical elementary operations (logic gates) are replaced by quantum gates and classical bits by qubits. Generic time-space trade-offs have been studied

in [START_REF] Bennett | Time/space trade-offs for reversible computation[END_REF][START_REF] Levin | A note on Bennett's time-space tradeoff for reversible computation[END_REF][START_REF] Knill | An analysis of Bennett's pebble game[END_REF], but precise optimizations are required in practice, where the bulk of the work comes from making the computation reversible. As we just want to compare costs with quantum generic attacks, the following fact will be useful.

Remark 1. The ratio in time complexities is approximately preserved when embedding classical algorithms into quantum algorithms.

For example, if a classical algorithm has a time complexity equivalent to 1000 evaluations of Gimli, we can consider that the corresponding quantum embedding has a time complexity equivalent to 1000 quantum evaluations of Gimli. In all quantum attacks, we will give quantum time complexities relatively to quantumly evaluating Gimli. In order to use Amplitude Amplification (Theorem 1 above), we simply need to define classical randomized algorithms for 𝒜 and 𝑂 𝜒 .

Example

We take the example of the classical 8-round collision attack. Both steps run in classical time 2 32 ×4×𝑡 𝑒 by running 2 32 iterates of a randomized algorithm of time complexity 4 × 𝑡 𝑒 . Using Amplitude Amplification, we obtain a corresponding quantum algorithm with time complexity approximately 2 16 × 4 × 𝑡 𝑞𝑒 , where 𝑡 𝑞𝑒 is the time to solve quantumly an SP-Box equation, relative to the cost of a quantum implementation of Gimli. As we remarked above, we can approximate 𝑡 𝑞𝑒 ≃ 𝑡 𝑒 . This approximation comes from different factors:

a small constant factor 𝜋 2 which is inherent to quantum search.

the trade-offs between time and space in the detailed implementations of the primitive and its components. Let us simply notice that Gimli, compared to other primitives that have been studied in this setting, e.g. AES [START_REF] Jaques | Implementing grover oracles for quantum key search on AES and LowMC[END_REF], seems fairly easy to implement using basic quantum computing operations. In the example of AES, the most costly component is the S-Box [START_REF] Jaques | Implementing grover oracles for quantum key search on AES and LowMC[END_REF], and Gimli does not have such.

We are mainly interested in the security margin, and these approximations will be sufficient for us to determine whether a given algorithm runs faster or slower than the corresponding quantum generic attack. Thus, we will write that the quantum 8-round attack on Gimli-Hash runs in time ≃ 2 16 × 4 × 𝑡 𝑒 .

Quantum Collision Bounds and Quantum Attacks

The best quantum generic attack for finding collisions depends on the computational model, more precisely, on the cost assigned to quantum-accessible memory. Different choices are possible, which are detailed e.g. in [START_REF] Hosoyamada | Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound[END_REF]. In short, the overall cost of quantum collision search depends on the cost that is assigned to quantum hardware.

In this paper, we will simply consider the most conservative setting, where quantum memory is free. Note that this actually makes our attacks overall less efficient, since the generic algorithm is the most efficient possible (and they'll also work in the other settings). In this situation, the best collision search algorithm is by Brassard, Høyer and Tapp [START_REF] Brassard | Quantum cryptanalysis of hash and claw-free functions[END_REF]. It will find a collision on Gimli-Hash in approximately 2 256/3 ≃ 2 85.3 quantum evaluations of Gimli, using a quantumaccessible memory of size 2 85.3 .

Quantum collision attacks reaching more rounds than classical ones. In [START_REF] Hosoyamada | Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound[END_REF], Hosoyamada and Sasaki initiated the study of dedicated quantum attacks on hash functions. They remarked that quantum collision search does not benefit from a square-root speedup (it goes from roughly 2 𝑛/2 to 2 𝑛/3 with the BHT algorithm, and the gain is even smaller in more constrained models of quantum hardware), while some collision-finding procedures may have a better speedup, say, quadratic. Thus:

there may exist quantum collision attacks such that the corresponding classical algorithm is not an attack (it gets worse than the generic bound); the quantum security margin of hash functions for collision attacks is likely to be smaller than the classical one.

Hosoyamada and Sasaki studied differential trails in the hash functions AES-MMO and Whirlpool. Although our attacks are based on a different framework, we show that similar findings apply for Gimli.

Quantum Collision Attacks on Gimli

We assume that 𝑡 𝑒 < 2 20 , hence solving an equation costs less than evaluating reduced-round Gimli 2 20 times, which is suggested by our computations, and should hold in the quantum setting as well.

Full-state collisions. By adding another 32-bit condition in the classical 12round collision attack, we obtain a procedure which runs classically in time 4 × 2 128 × 𝑡 𝑒 , which is too high. However, using Amplitude Amplification, we obtain a procedure that runs in quantum time ≃ 4 × 2 64 × 𝑡 𝑒 and reaches 14 rounds, with less complexity than the quantum collision bound.

Semi-free start collisions. We can extend the 18-round semi-free start collision attack in the same way. Building the 6

State-recovery Attacks on Gimli-Cipher

In this section, we study state-recovery attacks on Gimli-Cipher. Gimli-Cipher uses the Duplex mode, where message blocks are XORed in the same place as in Gimli-Hash. The goal of a state-recovery attack is to recover the complete internal state, including the capacity. Once this is done, the Duplex is invertible and the key can also be recovered.

Since there are 256 bits of key in Gimli-Cipher, a meaningful state-recovery attack can have a complexity up to 2 256 , although it will not necessarily contradict the security claims of [START_REF] Bernstein | Gimli. Submission to the NIST Lightweight Cryptography project[END_REF], which go only up to 128 bits of security.

The current best attack is from [START_REF] Liu | Automatic verification of differential characteristics: Application to reduced Gimli[END_REF], targeting 9 rounds in time 2 192 and memory 2 190 . Generic Principle. We will target reduced-round variants of the permutation, starting, as before, from an intermediate round in order to leverage the rounddependent linear layer. Due to the Duplex mode, the value of the rate (the 𝑥 words 𝐴 𝑥 , 𝐵 𝑥 , 𝐶 𝑥 , 𝐷 𝑥 ) is known before and after each call to the permutation. Starting from any nonce, we inject zero messages and observe the results. Let 𝑆 = (𝐴, 𝐵, 𝐶, 𝐷) be the current state. Let 𝛱 be the reduced-round permutation. Let 𝑆 ′ = 𝛱(𝑆) and 𝑆 ′′ = 𝛱(𝑆 ′ ). This means that we know 𝑆 𝑥 = (𝐴 𝑥 , 𝐵 𝑥 , 𝐶 𝑥 , 𝐷 𝑥 ), 𝑆 ′ 𝑥 and 𝑆 ′′ 𝑥 .

Given 𝑆 𝑥 and 𝑆 ′ 𝑥 , there are on average 2 128 possibilities for 𝑆 ′ . Given 𝑆 ′ 𝑥 and 𝑆 ′′ 𝑥 , there are also 2 128 possibilities for 𝑆 ′′ . Thus our goal is to produce these two lists of (at least) 2 128 values and to find a collision between them. We expect a single collision to occur.

𝐴

𝐵 𝐶 𝐷 We write 8 rounds of Gimli as on Figure 6, where single-word constraints are put on the beginning and the end. Since each double SP-Box takes at most 2 96 values, we can start by writing down a list of these values for each double SP-Box. We will then merge these lists together progressively. If we merge two lists of size 2 ℓ and 2 ℓ ′ , and if the double SP-Boxes have 2 words in common, then we obtain a list of size 2 ℓ+ℓ ′ -2×32 .

The goal is to obtain a list of states that will match all the input and output constraints. This is graphically intuitive: on Figure 6, we will progressively merge the nodes. When we merge two nodes of labels 𝑖 and 𝑗, we obtain a node of label max(𝑖 + 𝑗 -𝑚, 0) where 𝑚 is the number of edges between them. All outgoing edges of 𝑖 and 𝑗 are copied to the new node. We will end with a single node, that represents a list of possible states. The time and memory complexities of this procedure are roughly equal to the biggest list size encountered, that is, in log 2 , 32 times the biggest label that was put on a node during the process.

Starting from Figure 6, our strategy for 8 rounds is to first merge the nodes pairwise, obtaining Figure 7.

𝐴 𝐵 𝐶 𝐷 Next, we merge 𝐴, 𝐵, 𝐶, 𝐷 into single nodes, and obtain a label 4. That is, thanks to the input and output constraints, we have only 2 128 choices for each column separately. Next, there are 4 edges between 𝐴 abd 𝐵, 4 edges between 𝐶 and 𝐷, so we merge into 2 128 choices for 𝐴, 𝐵 and 𝐶, 𝐷 separately. There are 4 edges between the remaining two nodes, so we merge into a list of 2 128 possible states.

This gives a state-recovery attack of time and memory complexity 2 128 (up to a small constant factor). Note that at this point, we can assume that the double SP-Box has been tabulated, and so, we don't need to solve equations anymore.

More Rounds. The complexity rapidly increases with the number of rounds.

Once we represent them as on Figure 6 and Figure 7, we find that our merging strategies are rather limited.

As soon as we move to 10 rounds, the merging process produces nodes of label 6, that is, lists of size 2 192 (see Figure 8). This seems to correspond to the 9-round attack of [START_REF] Liu | Automatic verification of differential characteristics: Application to reduced Gimli[END_REF], written differently (note that [START_REF] Liu | Automatic verification of differential characteristics: Application to reduced Gimli[END_REF] starts from the first round of Gimli, and thus, there is a swap immediately after the first SP-box).

With a minor modification in the merging process, we obtain the same complexity for 12 rounds, where the final step gives Figure 9.

With more rounds, that is, adding another layer of double SP-Boxes, all the merging strategies that we tried produced nodes of label at least 8 (that is, a complexity 2 256 ). We conjecture that this method cannot perform better.

7

Statistical Analyses of Gimli

Linear cryptanalysis

This section aims to provide the first analysis of the linear properties of the Gimli permutation and its components. For this purpose, we used a bit-oriented Mixed Integer Linear Programming (MILP) modelization of the state transformations of Gimli constructed according to [START_REF] Abdelkhalek | MILP modeling for (large) s-boxes to optimize probability of differential characteristics[END_REF]. The resulting optimization problems were then solved with the SCIP solver [START_REF] Gleixner | The SCIP Optimization Suite 6.0[END_REF][START_REF] Gleixner | The SCIP Optimization Suite 6.0[END_REF] to search for linear trails with optimal correlation.

Using this tool, we provide a rudimentary analysis of the linear approximation table of the double Gimli SP-box, as well as constructing effective linear distinguishers for up to the full 24 rounds of the Gimli permutation.

𝐴 𝐵

𝐶 𝐷 Let us consider that we apply the double SP-box to 𝐴 = (𝑥, 𝑦, 𝑧) to obtain 𝐴 ′′ = (𝑥 ′′ , 𝑦 ′′ , 𝑧 ′′ ) = 𝑆𝑃 2 (𝑥, 𝑦, 𝑧). We are interested in correlated linear approximations, that is, masks 𝛼 = (𝛼 𝑥 , 𝛼 𝑦 , 𝛼 𝑧 ) and 𝛽 = (𝛽 𝑥 , 𝛽 𝑦 , 𝛽 𝑧 ) for which

𝑐(𝑆𝑃 2 , 𝛼, 𝛽) = 2 -96 ( ⃒ ⃒ {𝐴 : 𝛼 • 𝐴 ⊕ 𝛽 • 𝐴 ′′ = 0} ⃒ ⃒ - ⃒ ⃒ {𝐴 : 𝛼 • 𝐴 ⊕ 𝛽 • 𝐴 ′′ = 1} ⃒ ⃒ )
is as large (in absolute value) as possible. From Section 2.1 we already know that the relationship 𝑥 8 + 𝑥 ′′ 0 + 𝑦 ′′ 0 + 𝑧 ′′ 0 = 0 always holds. This is a linear trail of the double SP-box with correlation 1, and it is the only one.

An automated MILP-based search for linear trails of correlation 2 -1 and 2 -2

shows that there exist at least 41 trails of the former kind and 572 of the latter, but this is not an exhaustive count. Although these approximations probably only account for a very small fraction of the possible ones, a more thorough study of the distribution of the different correlation values among all the trails would be of interest.

We have found no signs of significant linear-hull effects (that is, of different highly-biased linear trails with the same input and output masks, as shown in [START_REF] Nyberg | Linear approximation of block ciphers (rump session)[END_REF]) within these linear approximations of the double SP-box, although since we have not considered every interesting linear trail, they might still exist for trails of lower correlation.

Some linear trails of round-reduced Gimli. In order to provide some linear trails for reduced-round Gimli, we first focus on trails with only one active SP-Box in each round, or more specifically, with masks which only cover one column in each round. They do not provide an upper bound on the correlation of more general trails, but we still think they could be of interest, and this restriction greatly limits the search space.

More specifically, we consider linear trails on powers of the SP-box such that the mask for the 𝑥 word is zero every two rounds. This means that the mask is unaffected by the big and small swaps, and these trails easily translate into trails for the reduced-round Gimli construction with the same correlation.

We first look at iterative linear trails for the double SP-box so that both the input and output masks have the 𝑥 word set to zero, which means they can be easily extended and the correlation is computed using the piling-up lemma from [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF]. We find that the optimal correlation is 2 -26 , and this is the (maybe not unique) associated trail:

𝛤 1 : 00000000 0a064e03 0c08e406 SP -→ 2 -14 0c8b0507 01040322 00054302 SP -→ 2 -12 00000000 0a064e03 0c08e406
.

As this trail is iterative, we can construct 2𝑙-round trails with correlation 2 -26𝑙 .

Next, we provide a similar iterative trail for four rounds with correlation .

With this, we can construct trails of 4𝑙 rounds with correlation 2 -47𝑙 .

We have also been able to construct an eight-round iterative trail with correlation 2 -67 , which allows to construct trails of 8𝑙 rounds with correlation 2 .

We also performed some additional experiments to see whether there linear hull of the linear approximation based on these input and output masks has a larger linear potential than the one suggested by this single linear trail. We found that, in fact, there are 8 trails with correlation 2 -67 , 32 trails with correlation 2 -68 , 128 trails with correlation 2 -69 , 466 trails with correlation 2 -70 , and 1527 trails with correlation 2 -71 . This gives the linear approximation an Estimated Linear Potential (ELP, see [START_REF] Nyberg | Linear approximation of block ciphers (rump session)[END_REF]) of at least

8 • 2 -67•2 + 32 • 2 -68•2 + 128 • 2 -69•2 + 466 • 2 -70•2 + 1527 • 2 -71•2 ≃ 2 -128.8 .
For comparison, the ELP if we consider a single trail would be 2 -67•2 = 2 -134 .

Additionally, when we consider iterations of this approximation, it is possible that even more trails appear.

For a small number of rounds, iterative trails are far from optimal. We now construct some nice trails for up to six rounds. We start with an optimal fourround trail with correlation 2 -16 : .

We attempt to extend this trail at the top. There are no approximations for the double SP-box for which the output mask is the input mask of 𝛤 4 and so .

This gives us a six round linear trail with correlation 2 -32 .

We now aim to construct an effective 24-round distinguisher for the full permutation based on the 8-round iterative linear trail. To this end, we find a prolongation of this linear trail by seven rounds at the top, which includes a swap. We obtain a 24-round linear trail with correlation 2 -189 . Furthermore, because of the linear hull properties of the iterative linear trail, we know that the ELP of the linear approximation using the same input and output linear masks is at least 2 -367. .

In general, we provide the linear trails for up to 24 rounds of Gimli shown in Table 5. We should note that we have not proven the optimality of these trails (in fact we consider it quite likely that they are not), as we have focused on a very specific subfamily of trails and we haven't even shown optimality within that family for more than four rounds.

Our 24-round linear approximation can be used to mount a distinguishing attack on the Gimli permutation, which also works for the block cipher built with the Even-Mansour construction. It is possible to reduce the complexity slightly by using multiple linear cryptanalysis, as in [START_REF] Biryukov | On multiple linear approximations[END_REF]. The time complexity is equal to the data complexity, which is a number of known plaintext-ciphertext pairs inversely proportional to the ELP of 2 -367. 6 . By considering the same approximation but in the four columns we can mount a multiple attack with an increase in the capacity by a factor of four.

The problem of finding a linear approximation whose input and output masks lie on the 𝑥 lane (that is, on the rate of the Gimli-Hash and Gimli-Cipher constructions) remains open.

Differential-Linear Cryptanalysis

We now consider differential-linear cryptanalysis, a technique that combines a differential trail and a linear trail built independently. The differential-linear distinguishers of this section have the advantage of smaller complexities than the linear distinguishers presented above.

We use the approach of Leurent [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF] where we actually split the cipher in three parts 𝐸 = 𝐸 ⊥ ∘𝐸 ⊥ ⊤ ∘𝐸 ⊤ , with a differential trail in 𝐸 ⊤ , a linear trail in 𝐸 ⊥ , and an experimental evaluation of the bias in 𝐸 ⊥ ⊤ . This gives a more accurate evaluation of the complexity. More precisely, we consider Therefore, the complexity of the distinguisher is about 2/𝑝 2 𝑏 2 𝑐 4 . In Gimli, there are no keys, so the assumption of independence does not hold, but experiments show that the computed bias is close to the reality. In practice, the best results are obtained when 𝛿 out and 𝛼 have a low hamming weight [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF].

Differential Trail. We start by picking a trail that mainly follows the one given by the designers [START_REF] Bernstein | Gimli : A crossplatform permutation[END_REF] with slight changes to optimize it for for our number of rounds. We chose a trail with a difference pattern 𝛿 out with two active bits. A differential trail over 5 rounds with probability 𝑝 = 2 -28 is given in Table 6.

We considered trade-offs between the different phases, and it never seems to be worth it to propagate the trail any further.

Though our results do not pose a direct threat to the Gimli NIST candidate, low-complexity full-round distinguishers on the permutation or reduced-round attacks for a high proportion of the rounds (specially when not predicted by the designers) have been considered in some cases as an issue worth countering by proposing a tweak, as can be seen for instance in the modification proposed by the Spook team [START_REF] Bellizia | Spook: Sponge-based leakage-resistant authenticated encryption with a masked tweakable block cipher[END_REF] to protect against the cryptanalysis results from [START_REF] Derbez | Cryptanalysis results on Spook -bringing full-round Shadow-512 to the light[END_REF]. In September 2020, after the results of [START_REF] Flórez-Gutiérrez | New results on Gimli: full-permutation distinguishers and improved collisions[END_REF] were made public, the NIST offered the submitters of second-round algorithms to propose status updates. In their document [START_REF] Bernstein | Gimli: NIST LWC second-round candidate status update[END_REF], the designers of Gimli acknowledged the collision attacks of Section 4 but dismissed the distinguishers of Section 3, and did not introduce any change to their specification. Later on, Gimli was not accepted among the finalists of the competition.

The Gimli designers studied other linear layers instead of the swaps, like using an MDS or the linear transformation from SPARX [START_REF] Dinu | Design strategies for ARX with provable bounds: Sparx and LAX[END_REF], and they found some advantages in proving security against various types of attacks. On the other hand, they also found it unclear whether these advantages would outweight the costs. We believe our results show some light in this direction: the other variants that were considered seem a priori to be stronger regarding our analysis, though an extensive study should be performed.

We believe the symmetry distinguishers might still be improved by exploiting the properties of the SP-Box, which we have not done yet.

In order to mitigate the attacks based on internal symmetries and guess-anddetermine methods (including our distinguishers on the permutation) a simple fix would be to perform a swap at each round instead of every second round.

This would however imply a renewed cryptanalysis effort.

3 .

 3 Swap 𝑥 and 𝑧: (𝑥, 𝑧) ← (𝑧, 𝑥).

4 Classical

 4 Collisions on Reduced-Round Gimli-Hash

Fig. 3 .

 3 Fig.3. Gimli-Hash (𝑃 stands for the Gimli permutation). The rate part is formed of the words 𝐴𝑥, 𝐵𝑥, 𝐶𝑥, 𝐷𝑥 and the capacity part of 𝐴𝑦,𝑧, 𝐵𝑦,𝑧, 𝐶𝑦,𝑧, 𝐷𝑦,𝑧.

Fig. 5 .

 5 Fig. 5. Semi-free start collision attack on 12 rounds of Gimli (see Algorithm 4).

Fig. 6 .

 6 Fig. 6. Synthesis of 8 rounds of Gimli, with 4 double SP-Boxes. We write in each double SP-Box the number of word-degrees of freedom.

Fig. 7 . 8 -

 78 Fig. 7. 8-round merging process, step 2.

Fig. 8 .Fig. 9 .

 89 Fig. 8. 10-round merging process. Nodes merged at the next step are displayed with the same colors.

-

  a differential trail 𝛿 in → 𝛿 out for 𝐸 ⊤ with probability 𝑝 = Pr 𝑋 ( 𝐸 ⊤ (𝑋) ⊕ 𝐸 ⊤ (𝑋 ⊕ 𝛿 in ) = 𝛿 out ).an experimental bias 𝑏 from 𝛿 out to 𝛽 for 𝐸 ⊥ ⊤ :𝑏 = 𝑐(𝛼 • 𝐸 ⊥ ⊤ (𝑊 ), 𝛼 • 𝐸 ⊥ ⊤ (𝑊 ⊕ 𝛿 out )) = 2 Pr 𝑊 (𝛼 • 𝐸 ⊥ ⊤ (𝑊 ) = 𝛼 • 𝐸 ⊥ ⊤ (𝑊 ⊕ 𝛿 out )) -1 a linear trail 𝛼 → 𝛽 for 𝐸 ⊥ with correlation 𝑐 = 2 Pr 𝑌 (𝛼•𝑌 = 𝛽 •𝐸 ⊥ (𝑌 ))-1.If the three parts are independent then we can estimate the bias of the differentiallinear distinguisher as:𝑐(𝛽 • 𝐸(𝑋), 𝛽 • 𝐸(𝑋 ⊕ 𝛿 in )) = 2 Pr 𝑋 (𝛽 • 𝐸(𝑋) = 𝛽 • 𝐸(𝑋 ⊕ 𝛿 in )) -1 ≈ 𝑝𝑏𝑐 2

A. 3 1 Fig. 10 .

 3110 Fig. 10. A representation of full Gimli.

Table 1 .

 1 Results against algorithms of the Gimli family (including quantum attacks). Time is counted in evaluations of Gimli, and memory in 128-bit blocks. Attacks that were actually implemented are written in bold. 𝜖 is a term that we only estimated experimentally (𝜖 ≈ 10, see Section 4). In rounds attacked, 𝑟1 → 𝑟2 means rounds 𝑟1 to 𝑟2 included.

		Technique	Rounds	Time	Memory Generic Reference
		Key-recovery	25 → 2.5 138.5	128		[24]
		on Gimli-PRF	15.5	64	64		[24]
		Zero-sum	14	351	negl.		[15]
	Distinguishers	ZID	18	2	negl.	4	[34]
	on the	Linear	16	238.8	negl.		Sec. 7.1
	permutation	Linear	24	367.6	negl.		Sec. 7.1
	(real rounds:	Differential-Linear	15	87.4	negl.		Sec. 7.2
	24 → 1)	Differential-Linear	16	110.8	negl.		Sec. 7.2
		Differential-Linear	17	154.8	negl.		Sec. 7.2
		Symmetry	23 → 0	32	negl.	96	Sec. 3
		Symmetry	27 → 0	64	negl.	96	Sec. 3
	Preimages on

  1: for 𝑟 = 24 downto 1 inclusive do

	2:	𝐴, 𝐵, 𝐶, 𝐷 ← 𝑆𝑃 (𝐴), 𝑆𝑃 (𝐵), 𝑆𝑃 (𝐶), 𝑆𝑃 (𝐷)	◁ SP-Box layer
	3:	if 𝑟 mod 4 = 0 then
	4:	Swap 𝐴𝑥 and 𝐵𝑥, swap 𝐶𝑥 and 𝐷𝑥	◁ small swap
	5:	𝐴𝑥 ← 𝐴𝑥 ⊕ rc𝑟	◁ Constant addition
	6:	else if 𝑟 mod 2 = 0 then
	7:	Swap 𝐴𝑥 and 𝐶𝑥, swap 𝐵𝑥 and 𝐷𝑥	◁ big swap
	8:	end if
	9: end for
		Return 𝑆
	-

for 𝑦 ′ :

  𝑥 30 + 𝑥 31 + 𝑦 14 + 𝑧 22 + 𝑥 30 𝑧 22 𝑥 ′′ 1 = 𝑥 9 + 𝑥 31 + 𝑥 0 + 𝑦 15 + 𝑧 0 + 𝑧 23 + 𝑥 31 𝑧 23 𝑥 ′′ 2 = 𝑥 10 + 𝑥 0 + 𝑥 1 + 𝑦 16 + 𝑧 1 + 𝑧 24 + 𝑦 23 𝑧 0 + 𝑥 0 𝑧 24 𝑥 ′′ +𝑦 𝑖-4 𝑧 𝑖-13 + 𝑧 𝑖-13 𝑧 𝑖+5 + 𝑥 𝑖-4 𝑥 𝑖+10 𝑦 𝑖-7 + 𝑥 𝑖+10 𝑦 𝑖-7 𝑦 𝑖+11 +𝑥 𝑖-5 𝑦 𝑖-4 𝑧 𝑖-13 + 𝑥 𝑖-5 𝑧 𝑖-13 𝑧 𝑖+5 + 𝑥 𝑖-5 𝑥 𝑖+10 𝑦 𝑖-7 + 𝑥 𝑖+10 𝑦 𝑖-7 𝑧 𝑖-13 +𝑥 𝑖-5 𝑥 𝑖+10 𝑦 𝑖-7 𝑧 𝑖-13 , 𝑖 ̸ = 0, 1, 2, 9, 12, 27, 28, 29 mod 32 𝑥 30 + 𝑥 31 + 𝑦 14 + 𝑦 31 + 𝑧 8 + 𝑧 22 + 𝑥 13 𝑦 28 + 𝑥 30 𝑧 22 𝑦 31 + 𝑧 8 + 𝑥 13 𝑦 28 𝑧 ′′ 1 = 𝑥 8 + 𝑦 0 + 𝑧 9 + 𝑥 14 𝑦 29

			(4)
	𝑦 ′′	{ 𝑦 ′′ 0 = (5)
	𝑧 ′′	{	𝑧 ′′ 0 =

𝑖 = 𝑥 𝑖-2 + 𝑥 𝑖-1 + 𝑥 𝑖+8 + 𝑦 𝑖-18 + 𝑧 𝑖-10 + 𝑧 𝑖-1 + 𝑥 𝑖-2 𝑧 𝑖-10 + 𝑦 𝑖-11 𝑧 𝑖-2 +𝑥 𝑖-4 𝑦 𝑖-4 + 𝑥 𝑖-4 𝑧 𝑖+5 + 𝑦 𝑖-4 𝑦 𝑖+11 + 𝑦 𝑖+11 𝑧 𝑖+5 + 𝑥 𝑖-5 𝑧 𝑖+5 + 𝑥 𝑖-5 𝑦 𝑖-4

  3. In his work, Hamburg defines a PRF with 192-bit input 𝑥 and 192-bit key 𝑘 that computes 𝐹 (𝑘, 𝑥) = trunc 192 (Gimli(𝑘‖𝑥)). He gives a distinguishing attack in time 2 64 for 15.5 rounds (omitting the final swap), and a key-recovery attack on 𝐹 when using 22.5 rounds of Gimli, precisely rounds 25 to 2.5 (omitting again the final swap). This attack runs in time 2 138.5 with a memory requirement of 2 129 , which is faster than the expected 2 192 , and thus shows that 22.5-round Gimli

	behaves differently than what could be expected from a random permutation.
	Hamburg's attacks are based on a meet-in-the-middle approach, exploiting
	the slow diffusion by tabulating some of the values that are passed from an SP-
	Box to another. The 15.5-round distinguisher relies on a table of size 2 64 , and
	the 22.5-round attack on a table of size 2 128 . None of these attacks are practical.
	ZID Permutation Distinguishers. In an independent and simultaneous work
	posted on ePrint [34], Liu, Isobe, and Meier present a "hybrid zero-internal dif-
	ferential" (ZID) distinguisher on full Gimli, which extends a ZID distinguisher
	of previous unpublished work. The basic ZID distinguisher happens to be what

  2. Distinguisher on 23 rounds. The same color for symmetric branches or columns at a given round means that they are equal. Algorithm 2 23-round internal symmetry distinguisher.Output: a 2-identical state 𝑆 such that Gimli(23, 1)(𝑆) is 2-identical We start from the middle. We will be interested in the state 𝑆11 .Notice that due to the small swap operation, the values 𝐵11 𝑥 and 𝐷 11 𝑥 actually come from 𝐴 and 𝐶 and depend only on 𝐴 15 and 𝐶 15 . At this point, we have ensured that for any values of 𝐵 15 = 𝐷 15 : -𝑆 23 is 2-identical: indeed, 𝐴 and 𝐶 will remain identical from rounds 16 to 19 backwards. Then, the small swap backwards injects the same value in 𝐴 and 𝐶 since 𝐵 and 𝐷 are also identical. Thus, 𝐴 23 = 𝐶 23 . -𝑆 7 is 2-identical: indeed, since 𝐵 11 𝑥 = 𝐷 11 𝑥 , 𝐵 and 𝐷 remain equal until the SP-Box layer of round 8, and the 2-identical property remains after the small swap of round 8. Once good values have been found, we can compute part of the state 𝑆 11 : 𝐴 11

	1. Select 𝐴 15 𝑥 , 𝐴 15 𝑦 , 𝐴 15 𝑧 and 𝐶 15 𝑥	= 𝐴 15 𝑥 ⊕ rc16, 𝐶 15 𝑦	= 𝐴 15 𝑦 , 𝐶 15 𝑧	= 𝐴 15 𝑧 such that
	𝐵 11 𝑥 = 𝐷 11 𝑥 .
				𝑦,𝑧 ,

𝐶

11

𝑦,𝑧 , and 𝐵 11 𝑥 = 𝐷 11 𝑥 are fixed. The rest remains free. 2. Select 𝐴 11 𝑥 = 𝐶 11 𝑥 ⊕ rc12 such that 𝐵 7 𝑥 = 𝐶 7 𝑥 . At this point, the two-identicality of the output state is preserved through 4 more rounds (until round 4 included): 𝑆 3 is 2-identical. In the state 𝑆 11 , 𝐵 11 𝑦,𝑧 = 𝐷 11 𝑦,𝑧 remain free. 3. Select 𝐵 11 𝑦,𝑧 = 𝐷 11 𝑦,𝑧 such that 𝐵 3 𝑥 = 𝐶 3 𝑥 . Thus, the output 𝑆 0 is 2-identical. Figure 1 from Section 1. An extension of our distinguisher to the full Gimli is a trivial matter. Indeed, after running Algorithm 2, we obtain a 2-identical input state 𝑆 23 = 𝐴 23 , 𝐵 23 , 𝐶 23 , 𝐷 23 with 𝐴 23 = 𝐶 23 . Then, if 𝐵 23 𝑥 = 𝐷 23 𝑥 , which is a 32-bit condition, the state remains 2-identical after the inverse round 24.

Table 2 .

 2 Collision attacks on round-reduced Gimli

	Type	Nbr of rounds Time complexity	Memory complexity
	Standard	8	8 × 2 32 × 𝑡𝑒 (practical) negl.
	Standard	12	8 × 2 96 × 𝑡𝑒	negl.
	Quantum	14	≃ 8 × 2 64 × 𝑡𝑒	negl.
	Semi-free start	12	10 × 2 32 × 𝑡𝑒	negl.
	Semi-free start	16	10 × 2 96 × 𝑡𝑒	negl.
	Semi-free start	18	7 × 2 96 × 𝑡𝑒	2 64
	Semi-free start	18	2 96	2 96
	Semi-free start, quantum 20	≃ 2 64 × 10 × 𝑡𝑒	2 64

𝐶 only. Thus, our practical distinguisher works against Gimli(23, 0) (a 24-round version of Gimli shifted by one round), and our extended distinguisher works against Gimli(27, 0) (a 28-round version of Gimli).

Table 4 .

 4 Collision attack on 8 rounds of Gimli, extended to 12 rounds. The first step fixes the branches in red, which have equal values for the two inputs 𝐴21 𝑥 , 𝐴 ′21 We start from 𝑚 1 , 0, 0, 0, then after one round, we inject the values 𝐴21 𝑥 , 𝐵 21 𝑥 , 𝐶 21 𝑥 , 𝐷 21 𝑥 and 𝐴 ′21 𝑥 , 𝐵 21 𝑥 , 𝐶 21 𝑥 , 𝐷 21 𝑥 respectively in the rate; then we obtain two states that differ only on the 𝑥-coordinate of the third column (not the first, due to a big swap), and we inject two different blocks to cancel out this difference, obtaining the same state. The full state then collides, and we can append any message block that we want. The two collisions are given in Extending the Attack. Remark that the first step can be extended to span any number of 𝑆𝑃 2 -boxes. However, each time we add two more rounds, there is one more branch coming from the 𝐵, 𝐶, 𝐷 states which has to match an expected value, so we add a factor 2 32 in complexity. Since 𝑡 𝑒 ≪ 2 32 , we can do that twice before meeting the bound 2 128 . Thus, a collision on 12-round Gimli-Hash can be built in time 2 96 × 4 × 𝑡 𝑒 . : an input state 𝐴 21 , 𝐵 21 , 𝐶 21 , 𝐷 21 . : 7 × 2 32 × 𝑡𝑒 time and 2 32 memory or 8 × 2 32 × 𝑡𝑒 and negligible memory. The attack runs in two main steps, both of which must solve 2 32 times a sequence of SP-Box equations.

	21 𝑥 ,

𝑥

Fig.

4

.

𝑥 that will conform to these branches. Then, the whole states are deduced. The branches 𝐴

13

𝑥 and 𝐴 11 𝑥 remain to match. in step 2 we benefited from having 5 different possible solutions. We found two solutions: 𝐶 21 𝑥 , 𝐷 21 𝑥 = 819b1392, 9f4d3233 and 𝐶 21 𝑥 , 𝐷 21 𝑥 = aa9f6f2d, 3a6e613a.

Putting both Steps Together. With these solutions, we built two collisions on 8round Gimli

[START_REF] Gleixner | The SCIP Optimization Suite 6.0[END_REF][START_REF] Brassard | Quantum cryptanalysis of hash and claw-free functions[END_REF]

.

InputComplexity

Since we do that 2 32 times, we expect on average a single solution such that 𝐴 13 𝑦 and 𝐴 ′13 𝑦 also collide. Now that we have found 𝐴 21 𝑥 , 𝐴 ′21 𝑥 , it remains to find 𝐵 21 𝑥 , 𝐶 21 𝑥 , 𝐷 21 𝑥 that give the wanted 𝐴 19 𝑥 , 𝐴 17 𝑥 , 𝐴 15

Table 3 .

 3 Results of the first step

	𝑚1	𝐴 21 𝑥	𝐴 ′21 𝑥	𝐴 19 𝑥 ⊕ rc20 𝐴 17 𝑥	𝐵 21 𝑥
	dc84bf38 bbdb41f3 1b1da6e4 07f25303 f793fb5f aae48b72
	𝐴 15 𝑥 ⊕ rc16 𝐵 17 𝑥		𝐴 15 𝑥 ⊕ rc16 𝐵 17 𝑥
	ddfbc88b 92f536b6		ddfbc803 f72044db
	ddfbc88b 0d9605fe		ddfbc803 b1c91a60
				ddfbc803 55d2252a

Table 4 .

 4 Two 8-round collisions on Gimli-Hash

	Starting state (first message block)

  Thus, we repeat step 1 in Algorithm 4 a total of 2 64 times in order to have 𝐶17 𝑥 = 𝐴 13 𝑥 = 0.Step 1 now costs 2 96 × 𝑡 𝑒 . The table that we precompute shall contain: for each 𝑥 ′ , 𝑥 ′′ , all values (on average 1) of 𝑦 ′ , 𝑧 ′ such that 𝑆𝑃 2 (0, *, *) = 𝑥 ′ , 𝑦 ′ , 𝑧 ′ and 𝑆𝑃 2 (𝑥 ′′ , 𝑦 ′ , 𝑧 ′ ) = 0, *, *. Now, in Algorithm 4, for each guess of 𝐵 19 𝑦,𝑧 , and for each guess of 𝐷 19 𝑦,𝑧 , we can find the value of 𝐶 that matches all the fixed branches in time 1, using this table. Thus, we can repeat this 2 96 times, extending the attack by 6 rounds. -Step 1 costs 2 × 2 96 × 𝑡 𝑒 (we solve only 2 equations most of the time, before aborting if the wanted "0" do not appear). -The table costs 2 64 × 𝑡 𝑒 , which is negligible -Step 2 costs 2 96 × 5 × 𝑡 𝑒 , since it is the same as before, and we only need forwards computation of SP-Boxes to check if the full path is correct. Note that we can get rid of the term 𝑡 𝑒 if we use a memory of size 2 96 to store the solutions of the SP-Box equations. In that case, the overall time complexity

			Step 1
			fix branches
	rc20	⊕	Step 2.1:
			guess 𝐵 19 𝑦 , 𝐵 19 𝑧 ,
			find all 𝐵 𝑖
			Step 2.2:
			guess 𝐷 19 𝑦 , 𝐷 19 𝑧 ,
			find all 𝐷 𝑖
	rc16	⊕
			Step 2.3:
			guess 𝐶 15 𝑧
			deduce all
	rc12	⊕

32

using 2 64 × 𝑡 𝑒 precomputations and a table of size 2 64 . This way, we can attack two more rounds. Indeed, once we have computed the first step, the two branches 𝐶

17

𝑥 and 𝐴 13

𝑥 contain arbitrary fixed values. Then, when we try to find the right 𝐶, we could have a table that for all 𝐶 15 𝑦 , 𝐶 15 𝑧 , gives all input-output values for 𝐶 17 and 𝐶 14 , and we could directly use this table to match the values 𝐶 15 𝑥 and 𝐷 15 𝑥 that come from 𝐷 (instead of having to make a guess of 𝐶 15 𝑧 . Let us fix 𝐶 17 𝑥 = 𝐴 13 𝑥 = 0.

  19 𝑦,𝑧 . This guess enables to deduce all values of the column 𝐵, from 𝐵 21 to 𝐵 10 , either by simply computing the SP-Box, or by solving Equation (10) (given two input branches 𝑦, 𝑧, given the output 𝑥, deduce the input 𝑥). From this, we deduce the value in all branches that go from 𝐵 to 𝐷 on the figure, hence 4 branches. They are represented in orange on Figure5.2. We take an arbitrary value for 𝐷 19 𝑦,𝑧 . Again, this enables to deduce the whole sequence of states from 𝐷 20 to 𝐷 10 , either by computing the SP-Box when possible, or by finding the input 𝑥 value corresponding to a given output. We also obtain the values of branches that are transmitted from 𝐷 to 𝐶. 3. We now guess 𝐶15 𝑧 . Given this, and 𝐶 15 𝑥 , and the output 𝐴13

Table 5 .

 5 Linear trails for Gimli. Some of them apply to shifted versions of the algorithm starting with two consective SP-box substitutions instead of one.No that the input mask has the 𝑥 word set to zero. However, by removing the last condition we can add two rounds with a 2 -16 correlation:

	# Rounds Correlation Construction		Shift
	2	1	Probability 1 trail from 2.1 Yes
	6	2 -32	𝛤5, 𝛤4			Yes
	8	2 -55	Rounds 24 to 17 of 𝛤6	No
	16	2 -122	Rounds 24 to 9 of 𝛤6	No
	24	2 -189	𝛤6 (ELP ≥ 2 -367.6 )
		68009800	SP	40211090	SP	00000000
	𝛤 5 :	40202088 403510d4	-→ 2 -10	00480010 00200088	-→ 2 -6	90002000 00400110

  6 .

	80860280	SP	00000000
	01404060	-→	80808003	Swap
	00000200	2 -6	00000601	↘	00000201	SP	00000600	SP
	𝛤6 :				80808003	-→	01000101	-→
	00004000	SP	00000201	↗	00000601	2 -3	00000103	2 -5
	00800001	-→	00000000
	00000201	2 -1	00000000
	00000000	SP	00000006	SP	00000000	SP	00000000	SP
	00020203	-→	04040404	-→	0c080808	-→	10101010	-→
	00020205	2 -8	04040404	2 -8	08080808	2 -8	10101010	2 -8

Acknowledgments. The authors would like to thank all the members of the cryptanalysis party meetings, for many useful comments and discussions, in particular many thanks to Anne Canteaut, Virginie Lallemand and Thomas Fuhr for many interesting discussions over previous versions of this work. Thanks to Donghoon Chang for finding some mistakes and inaccuracies, including an error in a 32-round version of our distinguisher. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 714294acronym QUASYModo).

40418080 02010000 00000000 00000000 𝛿in 40400010 00000000 00000000 00000000 80002080 80010080 00000000 00000000 80010080 00000000 00000000 00000000

Round 24 00402000 00000000 00000000 00000000 𝑝 = 2 -18 80400080 00000000 00000000 00000000 00000080 00000000 00000000 00000000

Round 23 00400000 00000000 00000000 00000000 𝑝 = 2 -8 80000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 Round 22 00000000 00000000 00000000 00000000 𝑝 = 1 80000000 00000000 00000000 00000000 80000000 00000000 00000000 00000000

Round 21 00000000 00000000 00000000 00000000 𝑝 = 1 00000000 00000000 00000000 00000000 𝛿out 00000000 00000000 00000000 00000000

Round 20 00800000 00000000 00000000 00000000 𝑝 = 2 -2 00800000 00000000 00000000 00000000

Experimental Bias. Starting from the target difference pattern 𝛿 out at round 19, we experimentally evaluate the bias after a few rounds with all possible masks 𝛼 with a single active bit. Concretely, we choose the state at random, build the second state by adding 𝛿 out and observe the bias a few rounds later.

The most useful results are on the least significant bit 𝑧 0 of the last word, where the probability of having a difference is smaller than 1/2. After computing 8 round, the probability of having an active difference on this bit in round 12 is 1 2 -2 -6.2 , a correlation of 𝑏 = -2 -5.2 . After 9 rounds, at the end of round 11, there is a correlation of 𝑏 = -2 -16.9 . These probabilities are large enough to be experimentally significant after the 2 40 trials we have made.

Linear Trail. We use assisted tools to find good linear trails, starting from the mask corresponding to 𝑧 0 . The diffusion is not the same depending whether we start after round 12 or 11 so we show the best 3 rounds linear approximation for both case. We find a correlation 𝑐 of 2 -17 and 2 -16 respectively, see Table 7.

Complexity of the distinguishers. We can combine the trails in different way to obtain distinguishers on 15, 16 or 17 rounds (starting from round 24).

rounds We use 5 rounds for 𝐸

16 rounds We use 5 rounds for 𝐸 ⊤ , 9 rounds for 𝐸 ⊥ ⊤ , 2 rounds for 𝐸 ⊥ . The corresponding complexity is 2/𝑝𝑏𝑐 2 = 2 × 2 2×28 × 2 2×16.9 × 2 4×5 = 2 110.8 . 17 rounds We use 5 rounds for 𝐸 ⊤ , 9 rounds for 𝐸 ⊥ ⊤ , 3 rounds for 𝐸 ⊥ . The corresponding complexity is 2/𝑝𝑏𝑐 2 = 2 × 2 2×28 × 2 2×16.9 × 2 4×16 = 2 154.8 . Those distinguishers can be used when the Gimli permutation is used to build a block cipher with the Even-Mansour construction. Such a cipher should ensure Table 7. Diffusion of 𝑧0 starting at the end of round 12.

Round 12 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001 Round 11 00000000 00000000 00000000 00000001 corr = 2 -0 00000000 00000000 00000000 00000001 00000000 00000000 00000000 00000001

Round 10 00000000 00800001 00000000 00000000 corr = 2 -5 00000000 00000000 00000000 00800201 00000000 00000000 00000000 01c00201

Round 9

00000000 00880000 00000000 01000201 corr = 2 -12 00000000 00f10000 00000000 01040000 00000000 01e00000 00000000 01840000

Table 8. Diffusion of 𝑧0 starting at the end of round 11.

Round 11 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001 00000000 00000000 00000000

Round 10 00000000 00000000 00000001 00000000 corr = 2 -0 00000001 00000000 00000000 00000000 00000001 00000000 00000000 00000000

Round 9

00000001 00000000 00800000 00000000 corr = 2 -5 00000201 00000000 00800000 00000000 00000201 00000000 01c00000 00000000

Round 8 00000000 00200201 00000000 01004000 corr = 2 -11 00000001 00000000 01004001 00000000 01000001 00000000 0180e001 00000000 a birthday bound security of up to 2 192 query, which is less efficient than our differential-linear distinguisher if the number of rounds Gimli is reduced to 17 (or fewer). Further improvement should be possible with the partitioning technique of [START_REF] Leurent | Improved differential-linear cryptanalysis of 7-round Chaskey with partitioning[END_REF], but we leave this to future work.

Conclusion

A common point of the results presented in this paper is that they exploit the relatively slow diffusion between the columns of the Gimli state. This issue has trivial causes: swaps are effectively the identity for 256 out of the 384 bits of the internal state, and occur only every second round. Thus, the Gimli SP-Box is always applied twice, except at the first and last rounds. This means that the permutation can be viewed as an SPN with only 12 rounds, and with very simple linear layers. Meanwhile, the double SP-Box is a rather simple function, and some of our attacks rely crucially on solving efficiently equations that relate its inputs and outputs.

A Appendix

A.1 SP-Box Inverse

The SP-Box is a bijective operation, but its inverse is difficult to write (and it is never used).

1. Swap 𝑥 and 𝑧 2. Perform: 5


Annie Bollie

Sandrine Grouard

Christine Lefevre

Noémie Tomadini

Emmanuel Moizan

Annie Bolle

The 25 th IACA Congress Noémie Tomadini • Emmanuel Moizan •

Keywords: Bone artefacts, Martinique, Historical Period, Daily life, trade, local crafts. Résumé Mobilier en os, Martinique, Période historique, Vie quotidienne, Commerce, Artisanat local. Resumen artefactos de huesos, Martinica, Periodo histórico, Vida cotidiana, Comercio, Artesanía local

For fifteen years, French archaeological investigations in Martinique allow a fresh look at daily life in the past, from French settlement to the years that followed the abolition of slavery. The study of bone artefacts from the sites of Cour d'Appel-Rue Schoelcher (Fort-de-France), Allée Pécoul (Saint-Pierre), Habitation Perinelle (Saint-Pierre) and Maison Coloniale de Santé (Saint-Pierre) help us to better understand the close connection between France and its colonies, through society and customs. People maintained this "savoir-vivre à la française" though they lived 6000 kilometers from mainland France. Besides the bone artefact trade, the discovery of more than 500 fragment from button debris manufacturing together with finished buttons at the Habitation Perinelle site (Saint-Pierre; 1645-1763) confirm the presence of local bone working.

Introduction

Barely studied until now, bone artefacts found in Colonial contexts on the island of Martinique invite us to reexamine the habits and customs of historic populations from European colonization to the post-abolition period . Whether ornamental elements, toilet accessories, game pieces or, kitchen utensils, these objects bear witness to everyday in the past, and are also cultural markers of this multicultural society (French settlers, Religious community members, Enslaved peoples ...) under construction. In this article, we will attempt, thanks to the analysis of bone objects coming from four historical sites, to learn more about the lives of historic populations and the links between France and this colony.

Study context, sites and material

This study presents over 650 worked bone remains from four archaeological sites. These sites are divided between the city of Saint-Pierre and the city of Fort-de-France: l'Habitation Perrinelle (1645 -1902), la Cour d'Appel-Rue Schoelcher (1726early 20th century), l'Allée Pécoul (late 18th/early 19 th century -1902) and la Maison Coloniale de Santé (1839Santé ( -1902)). The two towns, located on the west coast of Martinique, were established in the first decades of French colonization and played economic, military and politic roles throughout the colonial period. Saint-Pierre, called "le Petit Paris des Antilles" (the little Paris from West Indies) was indeed a major Antillean trade centre until the early twentieth century [START_REF] Veuve | Saint-Pierre de la Martinique, 17 e document d'évaluation du patrimoine archéologique des villes de France[END_REF][START_REF] Butel | Histoire des Antilles françaises (XVIIe-XXe siècles)[END_REF]. As for Fort-de-France, it housed the military fort and became, during the late seventeenth century, the administrative capital of the island [START_REF] Contour | Fort-de-France au début du siècle[END_REF]. . The slave quarters and the gardens of the plantation were also discovered [START_REF] Veuve | Habitation Perrinelle, Ancienne maison des Jésuites, Saint-Pierre de la Martinique[END_REF][START_REF] Veuve | Habitation Perrinelle, Ancienne maison des Jésuites, Saint-Pierre de la Martinique[END_REF][START_REF] Veuve | Centre de découverte de la Terre, Saint-Pierre de la Martinique, Rapport de diagnostic archéologique[END_REF][START_REF] Veuve | Habitation Perrinelle, Saint-Pierre de la Martinique[END_REF] The excavation of l'Allée Pécoul site, carried out by INRAP in 2013 has uncovered three housing units located in a rich urban residential area. One of these houses, almost entirely excavated, included a main house, associated domestic buildings and a courtyard with a well and pond. The buildings' evolution was documented up until the eruption of Montagne Pelée, which buried all the structures under a thick layer of pumice. Besides the 8011 remains of vertebrate fauna, this site has contained 14 bone artefacts related to various functions.

Finally, we studied material culture remains from the site of La Maison Coloniale de Santé, the first psychiatric hospital in the French West Indies built in 1839. The site, excavated in the early 90's by Serge Veuve, contained 9 bones objects including clothing items and toilet accessories [START_REF] Veuve | Maison Coloniale de Santé[END_REF].

Crafts import: the "French etiquette"

After buttons, toiletry products are the best represented crafts in these collections, especially toothbrushes. The five examples recovered in these sites are simply carved and without decorations. Despite the fact that they are broken at their most useful part, the toothbrushes from Habitation Perrinelle (fig. 1a), la Cour-d'Appel (fig. 1b) and la Maison Coloniale de Santé (fig. 1c) have preserved parts of their heads intact. They were all perforated to threequarters depth, and then perforated longitudinally. Then, a linen thread was used to sew the pig bristles into each hole. The thread was inserted into a hole then emerged in the last drill hole, closest to the handle, and so on. The frames were generally made from mammalian long bones. Two of them, recovered from deposits dating from the second half of the nineteenth century, have the inscriptions: "SUPERFINE PARIS" from la Cour-d'Appel (fig. 1b) and "EXTRA-FINE GARANTIE" on the toothbrush discovered at la Maison Coloniale de Santé (fig. 1c). These inscriptions don't concern their brand but rather their qualities, their manufacturing sites, their place of origin place or their wholesaler. This type of inscription does not appear before 1850, confirming the dates obtained for these deposits. We find the same type of inscription on copies fabricated in the Oise department, north of Paris. Indeed, in the 19th century, numerous orders were taken on by Parisian wholesalers for department workshops, which were specialized in toiletry brushes and they manufactured this kind of product in large quantities. Therefore, it seems that these two copies were imported from Paris and manufactured in the workshops of the Oise department.

Two parasol handles were discovered at the Allée Pécoul site. The first is embossed with a rose and its two leaves. This was made in one piece, from a diaphysis of a radius or tibia of a large mammal. The second example is also carved (fig. 2). On its upper part, the decoration is composed of geometric motifs. The lower part has a zoomorphic figure, a greyhound with lowered ears. The handle consists of two parts joined at the second inferior "bead". The quality of the workmanship on this handle is fantastic, but it is not a unique piece. Indeed, the pattern of the greyhound was very fashionable in Paris from 1840 to 1855 (comm. Pers. Michel Hertault). Made in Parisian art workshops, this type of figurine was also available in ivory as seen in a similar copy at the Galliera museum. In the nineteenth century, parasols were fashionable and an important element for sun protection. Indeed, at that time, it was important for a lady of high society to have a pale complexion without recourse, if possible, to make up to stand out from the lower social classes who, from working outside were tanned.

Local craft: private factory or a testimony of bones and horns workshop in Martinique?

Similar to parasols, fans were an important element of dress in the West Indies, as represented in an engraving showing "the Creole suit" (LeClerc & Dupin, 1779). The discovery of a hand fan on the Cour-d'Appel site confirms this (fig. 3). Many streak marks were observed on the back of this artifact suggesting that it could have been broken during manufacture or sold and used as a fan, even if was unpolished.

Although the status of this artifact is still uncertain, the presence of beef horn cores in the same stratigraphic unit and a second bone artifact could support the hypothesis of a bone and horn workshop on this site in the eighteenth century.

Besides, at the Perrinelle plantation, more than 600 remains (between waste and worked bones; fig. 4) from the button industry were recovered, certifying that the entire chaîne opératoire for their production was local. All artefacts are from surveys, excavated in 1996 and 1997, in the south wing of the plantation and in the garden. These buttons were almost exclusively taken from ribs of large mammals. Regarding the general form of the rib fragments, they were likely cattle ribs as those of horses are too narrow, and almost cylindrical in shape and therefore not appropriate for button production [START_REF] Barone | Anatomie comparée des mammifères domestiques[END_REF]. It is possible to observe that only the proximal part was not exploited. The raw materials were likely provided by a butcher who had cut the rib into two or three fragments to separate individual cuts of meat. Then, the sections were split longitudinally with a cleaver. It is easier to work rib fragments when the inner and outer parts are not in one piece, avoiding uncontrollable "breaks". At this site, the artisan chose the best use of raw materials: The edges were not removed and small-sized cuts were made in staggered rows. The discs were produced with a wick in three points, set on a brace. The central spike pierced the bone in one side while the other two points traced the contour to cut the disc. As soon as the disk surface was considered satisfactory, the worker returned the bones and worked on the other face of the disk by focusing in a central perforation. The buttons were covered with fabric and set in an embossed metal sheath and laced.

A study of the diameter's show predominantly medium-sized buttons and especially between 12 and 14 mm diameter, generally used for trousers or shirts. The same type of reinforcement was recovered during the excavation of the tomb 115 of the Anse Sainte Marguerite cemetery in Guadeloupe found on the chest and pelvis of a man [START_REF] Courtaud | -Le site d'Anse Sainte-Marguerite (Guadeloupe, Grande-Terre) présentation d'un cimetière d'époque coloniale[END_REF] and are often found in the West Indian colonial sites (Tomadini, data from PhD thesis in progress).

Button production in Perrinelle was not unique, five more colonial sites revealed this type of production in the West Indies. Located in Antigua, St Kitts, St Eustatius and Guadeloupe, all these sites, dated from late 18th until middle of 19th centuries, had military functions [START_REF] Klippel | Bone Disc Manufacturing Debris from Newfoundland to Antigua During the Historic Period[END_REF][START_REF] Jégouzo | Fort Delgrès, Basse-Terre (971[END_REF]. At Perrinelle, contexts where these remains were discovered are not chronologically defined, and it is impossible to accurately identify the social context in which this button factory was situated. Indeed, during these three centuries of occupation, this site was occupied successively by the Jesuits (1645-1763), a military barracks (1766-1770) and finally by M. Perrinelle . If one refers to the dates of other West Indian sites, this factory may have existed for one of these occupations. However, regarding of the function of these sites, the military occupation at Perrinelle seems to be favored.

Conclusion

Concerning craft imports, it appears that France and Martinique maintained close commercial and cultural relationships. Imported manufactured objects are from Besides this trade of manufactured objects, the discovery of significant worked bone waste in Perrinelle appears to attest to local craft activities during the historic period. Nonetheless, without ceramics to date these contexts, the social framework of these sites remains unknown. The status of the hand fan from the site of la Courd'Appel also remains uncertain and we cannot confirm that this was locally produced on Martinique in the colonial period. Does this suggest manufacturing exclusively developed within the private sphere on island and reserved for the site's inhabitants? Or does it represent the knowledge and techniques of European craftsmanship and was an item imported from Europe? Only ongoing archaeological investigations in historical contexts and continued archival research will allow us to answer these questions and better understand the social and economic status of these bone objects.

  L'Habitation Perrinelle, one of the rare stone buildings dating to Martinique's colonization, was occupied from 1645 until May 8th 1902 when the eruption of Montagne Pelée volcano destroyed the whole town. Excavations carried by Serge Veuve between 1996 and 2001 led to the discovery of the Jesuit castle (1645-1763) that became, in the late eighteenth century, l'Habitation Perrinelle

Figure 1

 1 Figure 1: a) Toothbrush from Habitation Perrinelle (South Wing); b) Toothbrush « SUPERFINE PARIS » from la Cour d'Appel -Rue Schoelcher (US 181-post. 1850); c) Toothbrush "EXTRA-FINE GARANTIE" from La Maison Coloniale de Santé (East dormitories -1902).

Figure

  Figure 2: Parasol handle, 1840-1855 (US 532, Allée Pécoul).

Figure 4 :

 4 Figure 4: Habitation Perrinelle, waste and worked bones (Surveys S1/S2) .

Acknowledgments

Our thanks go to Anne Hoguet (master fan maker) and Michel Hertault (art master parasols and umbrellas) for their availability and the many information they have shared. Our thanks go furthermore to Muriel Rousseau (responsible for communication with the FFB), Patrick Lhoyer (GBS Mouny) as well as Dominique Leroy and Daniele for valuable information about the toothbrush history and to have opened doors of the brush museum in Saint-Félix (Oise). We also thank warmly Pr . Allison Bain (Laval University) for proofreading of English.