International Association
for Cryptologic Research

Motivated by progress in the field of zero-knowledge proofs, so-called Arithmetization-Oriented (AO) symmetric primitives have started to appear in the literature, such as MiMC, Poseidon or Rescue. Due to the design constraints implied by this setting, these algorithms are defined using simple operations over large (possibly prime) fields. In particular, many rely on simple low-degree monomials for their non-linear layers, essentially using x ↦ x3 as an S-box.In this paper, we show that the structure of the material injected in each round (be it subkeys in a block cipher or round constants in a public permutation) could allow a specific pattern, whereby a well-defined affine space is mapped to another by the round function, and then to another, etc. Such chains of one-dimensional subspaces always exist over 2 rounds, and they can be extended to an arbitrary number of rounds, for any linear layer, provided that the round-constants are well chosen.As a consequence, for several ciphers like Rescue, or a variant of AES with a monomial Sbox, there exist some round-key sequences for which the cipher has an abnormally high differential uniformity, exceeding the size of the Sbox alphabet.Well-known security arguments, in particular based on the wide-trail strategy, have been reused in the AO setting by many designers. Unfortunately, our results show that such a traditional study may not be sufficient to guarantee security. To illustrate this, we present two new primitives (the tweakable block cipher Snare and the permutation-based hash function Stir) that are built using state-of-the-art security arguments, but which are actually deeply flawed. Indeed, the key schedule of Snare ensures the presence of a subspace chain that significantly simplifies an algebraic attack against it, and the round constants of Stir force the presence of a subspace chain aligned with the rate and capacity of the permutation. This in turns implies the existence of many easy-to-find solutions to the so-called CICO problem.

Ascon is a sponge-based Authenticated Encryption with Associated Data that was selected as both one of the winners of the CAESAR competition and one of the finalists of the NIST lightweight cryptography standardization effort. As this competition comes to an end, we analyse the security of this algorithm against cube attacks. We present a practical cube attack against the full 6-round encryption in Ascon in the nonce-misuse setting. We note right away that this attack does not violate the security claims made by the designers of Ascon, due to this setting.Our cryptanalysis is a conditional cube attack that is capable of recovering the full capacity in practical time; but for Ascon-128, its extension to a key recovery or a forgery is still an open question. First, a careful analysis of the maximum-degree terms in the algebraic normal form of the Ascon permutation allows us to derive linear equations in half of the capacity bits given enough cube sums of dimension 32. Then, depending on the results of this first phase, we identify smaller-degree cubes that allow us to recover the remaining half of the capacity. Overall, our cryptanalysis has a complexity of about 240 adaptatively chosen plaintexts, and about 240 calls to the permutation. We have implemented the full attack and our experiments confirm our claims.Our results are built on a theoretical framework which allows us to easily identify monomials whose cube-sums provide linear equations in the capacity bits. The coefficients of these monomials have a more general form than those used in the previous attacks against Ascon, and our method enables us to re-frame previous results in a simpler form. Overall, it enables to gain a deeper understanding of the properties of the permutation, and in particular of its S-box, that make such state-recoveries possible.

The security and performance of many integrity proof systems like SNARKs, STARKs and Bulletproofs highly depend on the underlying hash function. For this reason several new proposals have recently been developed. These primitives obviously require an in-depth security evaluation, especially since their implementation constraints have led to less standard design approaches. This work compares the security levels offered by two recent families of such primitives, namely GMiMC and HadesMiMC. We exhibit low-complexity distinguishers against the GMiMC and HadesMiMC permutations for most parameters proposed in recently launched public challenges for STARK-friendly hash functions. In the more concrete setting of the sponge construction corresponding to the practical use in the ZK-STARK protocol, we present a practical collision attack on a round-reduced version of GMiMC and a preimage attack on some instances of HadesMiMC. To achieve those results, we adapt and generalize several cryptographic techniques to fields of odd characteristic.

The cryptographic algorithms needed to ensure the security of our communications have a cost. For devices with little computing power, whose number is expected to grow significantly with the spread of the Internet of Things (IoT), this cost can be a problem. A simple answer to this problem is a compromise on the security level: through a weaker round function or a smaller number of rounds, the security level can be decreased in order to cheapen the implementation of the cipher. At the same time, quantum computers are expected to disrupt the state of the art in cryptography in the near future. For public-key cryptography, the NIST has organized a dedicated process to standardize new algorithms. The impact of quantum computing is harder to assess in the symmetric case but its study is an active research area.In this paper, we specify a new block cipher, Saturnin, and its usage in different modes to provide hashing and authenticated encryption in such a way that we can rigorously argue its security in the post-quantum setting. Its security analysis follows naturally from that of the AES, while our use of components that are easily implemented in a bitsliced fashion ensures a low cost for our primitives. Our aim is to provide a new lightweight suite of algorithms that performs well on small devices, in particular micro-controllers, while providing a high security level even in the presence of quantum computers. Saturnin is a 256-bit block cipher with a 256-bit key and an additional 9-bit parameter for domain separation. Using it, we built two authenticated ciphers and a hash function.• Saturnin-CTR-Cascade is an authenticated cipher using the counter mode and a separate MAC. It requires two passes over the data but its implementation does not require the inverse block cipher.• Saturnin-Short is an authenticated cipher intended for messages with a length strictly smaller than 128 bits which uses only one call to Saturnin to providenconfidentiality and integrity.• Saturnin-Hash is a 256-bit hash function. In this paper, we specify this suite of algorithms and argue about their security in both the classical and the post-quantum setting. https://project.inria.fr/saturnin/

We give the first practical instance – bison – of the Whitened Swap-Or-Not construction. After clarifying inherent limitations of the construction, we point out that this way of building block ciphers allows easy and very strong arguments against differential attacks.

In this paper, a new framework is developed for proving and adapting the recently proposed multiple-of-8 property and mixture-differential distinguishers. The above properties are formulated as immediate consequences of an equivalence relation on the input pairs, under which the difference at the output of the round function is invariant. This approach provides a further understanding of these newly developed distinguishers. For example, it clearly shows that the branch number of the linear layer does not influence the validity of the property, on the contrary of what was previously believed. We further provide an extension of the mixture-differential distinguishers and multiple-of-8 property to any SPN and to a larger class of subspaces. These adapted properties can then be exhibited in a systematic way for other ciphers than the AES. We illustrate this with the examples of Midori, Klein, LED and Skinny.

The boomerang attack is a cryptanalysis technique against block ciphers which combines two differentials for the upper part and the lower part of the cipher. The dependency between these two differentials then highly affects the complexity of the attack and all its variants. Recently, Cid et al. introduced at Eurocrypt’18 a new tool, called the Boomerang Connectivity Table (BCT) that permits to simplify this complexity analysis, by storing and unifying the different switching probabilities of the cipher’s Sbox in one table. In this seminal paper a brief analysis of the properties of these tables is provided and some open questions are raised. It is being asked in particular whether Sboxes with optimal BCTs exist for even dimensions, where optimal means that the maximal value in the BCT equals the lowest known differential uniformity. When the dimension is even and differs from 6, such optimal Sboxes correspond to permutations such that the maximal value in their DDT and in their BCT equals 4 (unless APN permutations for such dimensions exist). We provide in this work a more in-depth analysis of boomerang connectivity tables, by studying more closely differentially 4-uniform Sboxes. We first completely characterize the BCT of all differentially 4-uniform permutations of 4 bits and then study these objects for some cryptographically relevant families of Sboxes, as the inverse function and quadratic permutations. These two families provide us with the first examples of differentially 4-uniform Sboxes optimal against boomerang attacks for an even number of variables, answering the above open question.

This work studies deterministic and non-deterministic nonlinear approximations for cryptanalysis of block ciphers and cryptographic permutations and embeds it into the well-understood framework of linear cryptanalysis. For a deterministic (i.e., with correlation ±1) nonlinear approximation we show that in many cases, such a nonlinear approximation implies the existence of a highly-biased linear approximation. For non-deterministic nonlinear approximations, by transforming the cipher under consideration by conjugating each keyed instance with a fixed permutation, we are able to transfer many methods from linear cryptanalysis to the nonlinear case. Using this framework we in particular show that there exist ciphers for which some transformed versions are significantly weaker with regard to linear cryptanalysis than their original counterparts.

The current paper studies the probability of differential characteristics for an unkeyed (or with a fixed key) construction. Most notably, it focuses on the gap between two probabilities of differential characteristics: probability with independent S-box assumption, pind, and exact probability, pexact. It turns out that pexact is larger than pind in Feistel network with some S-box based inner function. The mechanism of this gap is then theoretically analyzed. The gap is derived from interaction of S-boxes in three rounds, and the gap depends on the size and choice of the S-box. In particular the gap can never be zero when the S-box is bigger than six bits. To demonstrate the power of this improvement, a related-key differential characteristic is proposed against a lightweight block cipher RoadRunneR. For the 128-bit key version, pind of 2−48 is improved to pexact of 2−43. For the 80-bit key version, pind of 2−68 is improved to pexact of 2−62. The analysis is further extended to SPN with an almost-MDS binary matrix in the core primitive of the authenticated encryption scheme Minalpher: pind of 2−128 is improved to pexact of 2−96, which allows to extend the attack by two rounds.