International Association
for Cryptologic Research

Verifiable Delay Functions (VDF) are a class of cryptographic primitives aiming to guarantee a minimum computation time, even for an adversary with massive parallel computational power. They are useful in blockchain protocols, and several practical candidates have been proposed based on exponentiation in a large finite field: Sloth++, Veedo, MinRoot. The underlying assumption of these constructions is that computing an exponentiation x^e requires at least log2(e) sequential multiplications. In this work, we analyze the security of these algebraic VDF candidates. In particular, we show that the latency of exponentiation can be reduced using parallel computation, against the preliminary assumptions.

Differential cryptanalysis is an old and powerful attack against block ciphers. While different techniques have been introduced throughout the years to improve the complexity of this attack, the key recovery phase remains a tedious and error-prone procedure. In this work, we propose a new algorithm and its associated tool that permits, given a distinguisher, to output an efficient key guessing strategy. Our tool can be applied to SPN ciphers whose linear layer consists of a bit-permutation and whose key schedule is linear or almost linear. It can be used not only to help cryptanalysts find the best differential attack on a given cipher but also to assist designers in their security analysis. We applied our tool to four targets: RECTANGLE, PRESENT-80, SPEEDY-7-192 and GIFT-64. We extend the previous best attack on RECTANGLE-128 by one round and the previous best differential attack against PRESENT-80 by 2 rounds. We improve a previous key recovery step in an attack against SPEEDY and present more efficient key recovery strategies for RECTANGLE-80 and GIFT. Our tool outputs the results in only a second for most targets

In this paper, we extend the applicability of differential meet-in-the-middle attacks, proposed at Crypto 2023, to truncated differentials, and in addition, we introduce three new ideas to improve this type of attack: we show how to add longer structures than the original paper, we show how to improve the key recovery steps by introducing some probability in them, and we combine this type of attacks with the state-test technique, that was introduced in the context of impossible differential attacks. Furthermore, we have developed a MILP-based tool to automate the search for a truncated differential-MITM attack with optimized overall complexity, incorporating some of the proposed improvements. Thanks to this, we can build the best known attacks on the cipher CRAFT, reaching 23 rounds against 21 previously; we provide a new attack on 23 round SKINNY-64-192, and we improve the best attacks on SKINNY-128-384.

The impossible boomerang attack, introduced in 2008 by Jiqiang Lu, is an extension of the impossible differential attack that relies on a boomerang distinguisher of probability 0 for discarding incorrect key guesses. In Lu’s work, the considered impossible boomerang distinguishers were built from 4 (different) probability-1 differentials that lead to 4 differences that do not sum to 0 in the middle, in a miss-in-the-middle way.In this article, we study the possibility of extending this notion by looking at finerlevel contradictions that derive from boomerang switch constraints. We start by discussing the case of quadratic Feistel ciphers and in particular of the Simon ciphers. We exploit their very specific boomerang constraints to enforce a contradiction that creates a new type of impossible boomerang distinguisher that we search with an SMT solver. We next switch to word-oriented ciphers and study how to leverage the Boomerang Connectivity Table contradictions. We apply this idea to SKINNYee, a recent tweakable block cipher proposed at Crypto 2022 and obtain a 21-round distinguisher.After detailing the process and the complexities of an impossible boomerang attack in the single (twea)key and related (twea)key model, we extend our distinguishers into attacks and present a 23-round impossible boomerang attack on Simon-32/64 (out of 32 rounds) and a 29-round impossible boomerang attack on SKINNYee (out of 56 rounds). To the best of our knowledge our analysis covers two more rounds than the (so far, only) other third-party analysis of SKINNYee that has been published to date.

<p> In order to maintain a similar security level in a post-quantum setting, many symmetric primitives should have to double their keys and increase their state sizes. So far, no generic way for doing this is known that would provide convincing quantum security guarantees. In this paper we propose a new generic construction, QuEME, that allows one to double the key and the state size of a block cipher in such a way that a decent level of quantum security is guaranteed. The QuEME design is inspired by the ECB-Mix-ECB (EME) construction, but is defined for a different choice of mixing function than what we have seen before, in order to withstand a new quantum superposition attack that we introduce as a side result: this quantum superposition attack exhibits a periodic property found in collisions and breaks EME and a large class of its variants. We prove that QuEME achieves n-bit security in the classical setting, where n is the block size of the underlying block cipher, and at least (n/6)-bit security in the quantum setting. We finally propose a concrete instantiation of this construction, called Double-AES, that is built with variants of the standardized AES-128 block cipher. </p>

Differential attacks are among the most important families of cryptanalysis against symmetric primitives. Since their introduction in 1990, several improvements to the basic technique as well as many dedicated attacks against symmetric primitives have been proposed. Most of the proposed improvements concern the key-recovery part. However, when designing a new primitive, the security analysis regarding differential attacks is often limited to finding the best trails over a limited number of rounds with branch and bound techniques, and a poor heuristic is then applied to deduce the total number of rounds a differential attack could reach. In this work we analyze the security of the SPEEDY family of block ciphers against differential cryptanalysis and show how to optimize many of the steps of the key-recovery procedure for this type of attacks. For this, we implemented a search for finding optimal trails for this cipher and their associated multiple probabilities under some constraints and applied non-trivial techniques to obtain optimal data and key-sieving. This permitted us to fully break SPEEDY-7-192, the 7-round variant of SPEEDY supposed to provide 192-bit security. Our work demonstrates among others the need to better understand the subtleties of differential cryptanalysis in order to get meaningful estimates on the security offered by a cipher against these attacks.

In this paper we introduce the differential meet-in-the-middle framework, a new cryptanalysis technique for symmetric primitives. Our new cryptanalysis method combines techniques from both meet-in-the-middle and differential cryptanalysis. As such, the introduced technique can be seen as a way of extending meet-in-the-middle attacks and their variants but also as a new way to perform the key recovery part in differential attacks. We apply our approach to SKINNY-128-384 in the single key model and to AES-256 in the related-key model. Our attack on SKINNY-128-384 permits to break 25 out of the 56 rounds of this variant and improves by two rounds the previous best known attacks. For AES-256 we attack 12 rounds by considering two related keys, thus outperforming the previous best related-key attack on AES-256 with only two related keys by 2 rounds.

We present several improvements to the framework of differential-linear attacks with a special focus on ARX ciphers. As a demonstration of their impact, we apply them to Chaskey and ChaCha and we are able to significantly improve upon the best attacks published so far.

We propose a general technique to improve the key-guessing step of several attacks on block ciphers. This is achieved by defining and studying some new properties of the associated S-boxes and by representing them as a special type of decision trees that are crucial for finding fine-grained guessing strategies for various attack vectors. We have proposed and implemented the algorithm that efficiently finds such trees, and use it for providing several applications of this approach, which include the best known attacks on NOKEON, GIFT, and RECTANGLE.

Recent works have shown that quantum period-finding can be used to break many popular constructions (some block ciphers such as Even-Mansour, multiple MACs and AEs...) in the superposition query model. So far, all the constructions broken exhibited a strong algebraic structure, which enables to craft a periodic function of a single input block. The recovery of the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes. In this paper, we introduce the \emph{quantum linearization attack}, a new way of using Simon's algorithm to target MACs in the superposition query model. Specifically, we use inputs of multiple blocks as an interface to a function hiding a linear structure. The recovery of this structure allows to perform forgeries. We also present some variants of this attack that use other quantum algorithms, which are much less common in quantum symmetric cryptanalysis: Deutsch's, Bernstein-Vazirani's, and Shor's. To the best of our knowledge, this is the first time these algorithms have been used in quantum forgery or key-recovery attacks. Our attack breaks many parallelizable MACs such as {\sf LightMac}, {\sf PMAC}, and numerous variants with (classical) beyond-birthday-bound security ({\sf LightMAC+}, {\sf PMAC+}) or using tweakable block ciphers ({\sf ZMAC}). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task.

It was long thought that symmetric cryptography was only mildly affected by quantum attacks, and that doubling the key length was sufficient to restore security. However, recent works have shown that Simon's quantum period finding algorithm breaks a large number of MAC and authenticated encryption algorithms when the adversary can query the MAC/encryption oracle with a quantum superposition of messages. In particular, the OCB authenticated encryption mode is broken in this setting, and no quantum-secure mode is known with the same efficiency (rate-one and parallelizable). In this paper we generalize the previous attacks, show that a large class of OCB-like schemes is unsafe against superposition queries, and discuss the quantum security notions for authenticated encryption modes. We propose a new rate-one parallelizable mode named QCB inspired by TAE and OCB and prove its security against quantum superposition queries.

$$\mathsf {Gimli}$$ 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 $$\mathsf {Gimli}$$ Gimli is based on the permutation $$\mathsf {Gimli}$$ 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 $$\mathsf {Gimli}$$ Gimli and its internal symmetries to build, for the first time, a distinguisher on the full permutation of complexity $$2^{64}$$ 2 64 . We also provide a practical distinguisher on 23 out of the full 24 rounds of $$\mathsf {Gimli}$$ Gimli that has been implemented. Next, we give (full state) collision and semi-free start collision attacks on $$\mathsf {Gimli}$$ Gimli -Hash, reaching, respectively, up to 12 and 18 rounds. On the practical side, we compute a collision on 8-round $$\mathsf {Gimli}$$ Gimli -Hash. In the quantum setting, these attacks reach 2 more rounds. Finally, we perform the first study of linear trails in $$\mathsf {Gimli}$$ Gimli , and we find a linear distinguisher on the full permutation.

Spook is one of the 32 candidates that has made it to the second round of the NIST Lightweight Cryptography Standardization process, and is particularly interesting since it proposes differential side channel resistance. In this paper, we present practical distinguishers of the full 6-step version of the underlying permutations of Spook, namely Shadow-512 and Shadow-384, solving challenges proposed by the designers on the permutation. We also propose practical forgeries with 4-step Shadow for the S1P mode of operation in the nonce misuse scenario, which is allowed by the CIML2 security game considered by the authors. All the results presented in this paper have been implemented.

The $k$-xor or Generalized Birthday Problem aims at finding, given $k$ lists of bit-strings, a $k$-tuple among them XORing to 0. If the lists are unbounded, the best classical (exponential) time complexity has withstood since Wagner's CRYPTO 2002 paper. If the lists are bounded (of the same size) and such that there is a single solution, the \emph{dissection algorithms} of Dinur \emph{et al.} (CRYPTO 2012) improve the memory usage over a simple meet-in-the-middle. In this paper, we study quantum algorithms for the $k$-xor problem. With unbounded lists and quantum access, we improve previous work by Grassi \emph{et al.} (ASIACRYPT 2018) for almost all $k$. Next, we extend our study to lists of any size and with classical access only. We define a set of ``merging trees'' which represent the best known strategies for quantum and classical merging in $k$-xor algorithms, and prove that our method is optimal among these. Our complexities are confirmed by a Mixed Integer Linear Program that computes the best strategy for a given $k$-xor problem. All our algorithms apply also when considering modular additions instead of bitwise xors. This framework enables us to give new improved quantum $k$-xor algorithms for all $k$ and list sizes. Applications include the subset-sum problem, LPN with limited memory and the multiple-encryption problem.

Linear cryptanalysis is one of the most important tools in use for the security evaluation of symmetric primitives. Many improvements and refinements have been published since its introduction, and many applications on different ciphers have been found. Among these upgrades, Collard et al. proposed in 2007 an acceleration of the key-recovery part of Algorithm 2 for last-round attacks based on the FFT. In this paper we present a generalized, matrix-based version of the previous algorithm which easily allows to take into consideration an arbitrary number of key-recovery rounds. We also provide efficient variants that exploit the key-schedule relations and that can be combined with multiple linear attacks. Using our algorithms we provide some new cryptanalysis on PRESENT, including, to the best of our knowledge, the first attack on 28 rounds.

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/

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 the permutation, and we propose differential-linear cryptanalysis that reach up to 17 rounds of Gimli.

Limited birthday distinguishers (LBDs) are widely used tools for the cryptanalysis of cryptographic permutations. In this paper we propose LBDs on several variants of the sLiSCP permutation family that are building blocks of two round 2 candidates of the NIST lightweight standardization process: Spix and SpoC. We improve the number of steps with respect to the previously known best results, that used rebound attack. We improve the techniques used for solving the middle part, called inbound, and we relax the external conditions in order to extend the previous attacks. The lower bound of the complexity of LBDs has been proved only against functions. In this paper, we prove for the first time the bound against permutations, which shows that the known upper bounds are tight.

In this paper we analyze for the first time the post-quantum security of AES. AES is the most popular and widely used block cipher, established as the encryption standard by the NIST in 2001. We consider the secret key setting and, in particular, AES-256, the recommended primitive and one of the few existing ones that aims at providing a post-quantum security of 128 bits. In order to determine the new security margin, i.e., the lowest number of non-attacked rounds in time less than 2128 encryptions, we first provide generalized and quantized versions of the best known cryptanalysis on reduced-round AES, as well as a discussion on attacks that don’t seem to benefit from a significant quantum speed-up. We propose a new framework for structured search that encompasses both the classical and quantum attacks we present, and allows to efficiently compute their complexity. We believe this framework will be useful for future analysis.Our best attack is a quantum Demirci-Selçuk meet-in-the-middle attack. Unexpectedly, using the ideas underlying its design principle also enables us to obtain new, counter-intuitive classical TMD trade-offs. In particular, we can reduce the memory in some attacks against AES-256 and AES-128.One of the building blocks of our attacks is solving efficiently the AES S-Box differential equation, with respect to the quantum cost of a reversible S-Box. We believe that this generic quantum tool will be useful for future quantum differential attacks. Judging by the results obtained so far, AES seems a resistant primitive in the post-quantum world as well as in the classical one, with a bigger security margin with respect to quantum generic attacks.

In symmetric cryptanalysis, the model of superposition queries has led to surprising results, with many constructions being broken in polynomial time thanks to Simon’s period-finding algorithm. But the practical implications of these attacks remain blurry. In contrast, the results obtained so far for a quantum adversary making classical queries only are less impressive.In this paper, we introduce a new quantum algorithm which uses Simon’s subroutines in a novel way. We manage to leverage the algebraic structure of cryptosystems in the context of a quantum attacker limited to classical queries and offline quantum computations. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature, while using only as much hardware requirements (quantum and classical) as a standard exhaustive search with Grover’s algorithm. In particular, we are able to break the Even-Mansour construction in quantum time $$\tilde{O}(2^{n/3})$$, with $$O(2^{n/3})$$ classical queries and $$O(n^2)$$ qubits only. In addition, we improve some previous superposition attacks by reducing the data complexity from exponential to polynomial, with the same time complexity.Our approach can be seen in two complementary ways: reusing superposition queries during the iteration of a search using Grover’s algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure.We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.

In this article we study the security of the authenticated encryption algorithm Ketje against divide-and-conquer attacks. Ketje is a third-round candidate in the ongoing CAESAR competition, which shares most of its design principles with the SHA-3 hash function. Several versions of Ketje have been submitted, with different sizes for its internal state. We describe several state-recovery attacks on the smaller variant, called Ketje Jr. We show that if one increases the amount of keystream output after each round from 16 bits to 40 bits, Ketje Jr becomes vulnerable to divide-and-conquer attacks with time complexities 271.5 for the original version and 282.3 for the current tweaked version, both with a key of 96 bits. We also propose a similar attack when considering rates of 32 bits for the non-tweaked version. Our findings do not threaten the security of Ketje, but should be taken as a warning against potential future modifications that would aim at increasing the performance of the algorithm.

Preface

The $$k$$-xor (or generalized birthday) problem is a widely studied question with many applications in cryptography. It aims at finding k elements of n bits, drawn at random, such that the xor of all of them is 0. The algorithms proposed by Wagner more than fifteen years ago remain the best known classical algorithms for solving them, when disregarding logarithmic factors.In this paper we study these problems in the quantum setting, when considering that the elements are created by querying a random function (or k random functions) $$H~: \{0,1\}^n \rightarrow \{0,1\}^n$$. We consider two scenarios: in one we are able to use a limited amount of quantum memory (i.e. a number O(n) of qubits, the same as the one needed by Grover’s search algorithm), and in the other we consider that the algorithm can use an exponential amount of qubits. Our newly proposed algorithms are of general interest. In both settings, they provide the best known quantum time complexities.In particular, we are able to considerately improve the $$3$$-xor algorithm: with limited qubits, we reach a complexity considerably better than what is currently possible for quantum collision search. Furthermore, when having access to exponential amounts of quantum memory, we can take this complexity below $$O(2^{n/3})$$, the well-known lower bound of quantum collision search, clearly improving the best known quantum time complexity also in this setting.We illustrate the importance of these results with some cryptographic applications.

At Eurocrypt 2017 a tweak to counter Simon’s quantum attack was proposed: replace the common bitwise addition with other operations, as a modular addition. The starting point of our paper is a follow up of these previous results:First, we have developed new algorithms that improves and generalizes Kuperberg’s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005, widely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the hidden problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes.In order to verify our theoretical analysis, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak. We concluded that the tweak does not seem to be efficient.

Preface to Volume 2017, Issue 1

Quantum computers, that may become available one day, would impact many scientific fields, most notably cryptography since many asymmetric primitives are insecure against an adversary with quantum capabilities. Cryptographers are already anticipating this threat by proposing and studying a number of potentially quantum-safe alternatives for those primitives. On the other hand, symmetric primitives seem less vulnerable against quantum computing: the main known applicable result is Grover’s algorithm that gives a quadratic speed-up for exhaustive search. In this work, we examine more closely the security of symmetric ciphers against quantum attacks. Since our trust in symmetric ciphers relies mostly on their ability to resist cryptanalysis techniques, we investigate quantum cryptanalysis techniques. More specifically, we consider quantum versions of differential and linear cryptanalysis. We show that it is usually possible to use quantum computations to obtain a quadratic speed-up for these attack techniques, but the situation must be nuanced: we don’t get a quadratic speed-up for all variants of the attacks. This allows us to demonstrate the following non-intuitive result: the best attack in the classical world does not necessarily lead to the best quantum one. We give some examples of application on ciphers LAC and KLEIN. We also discuss the important difference between an adversary that can only perform quantum computations, and an adversary that can also make quantum queries to a keyed primitive.

The need for lightweight (that is, compact, low-power, low-energy) cryptographic hash functions has been repeatedly expressed by professionals, notably to implement cryptographic protocols in RFID technology. At the time of writing, however, no algorithm exists that provides satisfactory security and performance. The ongoing SHA-3 Competition will not help, as it concerns general-purpose designs and focuses on software performance. This paper thus proposes a novel design philosophy for lightweight hash functions, based on the sponge construction in order to minimize memory requirements. Inspired by the stream cipher Grain and by the block cipher KATAN (amongst the lightest secure ciphers), we present the hash function family Quark, composed of three instances: u-Quark, d-Quark, and s-Quark. As a sponge construction, Quark can be used for message authentication, stream encryption, or authenticated encryption. Our hardware evaluation shows that Quark compares well to previous tentative lightweight hash functions. For example, our lightest instance u-Quark conjecturally provides at least 64-bit security against all attacks (collisions, multicollisions, distinguishers, etc.), fits in 1379 gate-equivalents, and consumes on average 2.44 μW at 100 kHz in 0.18 μm ASIC. For 112-bit security, we propose s-Quark, which can be implemented with 2296 gate-equivalents with a power consumption of 4.35 μW.