Publications

Here is a full list of my publications:

Bibliographical data is also available from DBLP and from my Google Scholar profile.

Conference and journal papers

Cryptanalysis of Algebraic Verifiable Delay Functions

Crypto 2024, Alex Biryukov, Ben Fisch, Gottfried Herold, Dmitry Khovratovich, Gaëtan Leurent, Maria Naya-Plasencia, Benjamin Wesolowski (©IACR)

Keywords:

Verifiable Delay Functions, MinRoot, Veedo, Sloth++, cryptanalysis, smoothness

To appear

Abstract:

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 xe 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.

Improving Generic Attacks Using Exceptional Functions

Crypto 2024, Xavier Bonnetain, Rachelle Heim Boissier, Gaëtan Leurent, André Schrottenloher (©IACR)

Keywords:

Cryptanalysis, Generic attack, Duplex-based modes, Hash Combiners, Random Functions

See also:

Preprint

To appear

Abstract:

Over the past ten years, the statistical properties of random functions have been particularly fruitful for generic attacks. Initially, these attacks targeted iterated hash constructions and their combiners, developing a wide array of methods based on internal collisions and on the average behavior of iterated random functions. More recently, Gilbert et al. (EUROCRYPT 2023) introduced a forgery attack on so-called duplex-based Authenticated Encryption modes which was based on exceptional random functions, i.e., functions whose graph admits a large component with an exceptionally small cycle.
In this paper, we expand the use of such functions in generic cryptanalysis with several new attacks. First, we improve the attack of Gilbert et al. from O(23c/4) to O(22c/3), where c is the capacity. This new attack uses a nested pair of functions with exceptional behavior, where the second function is defined over the cycle of the first one. Next, we introduce several new generic attacks against hash combiners, notably using small cycles to improve the complexities of the best existing attacks on the XOR combiner, Zipper Hash and Hash-Twice. Last but not least, we propose the first quantum second preimage attack against Hash-Twice, reaching a quantum complexity O(23n/7).

[article]

Partial Sums Meet FFT: Improved Attack on 6-Round AES

Eurocrypt 2024, Orr Dunkelman, Shibam Ghosh, Nathan Keller, Gaëtan Leurent, Avichai Marmor, Victor Mollimard (©IACR)

Download:

paper

Keywords:

AES, partial sum, FFT

Abstract:

The partial sums cryptanalytic technique was introduced in 2000 by Ferguson et al., who used it to break 6-round AES with time complexity of 252 S-box computations — a record that has not been beaten ever since. In 2014, Todo and Aoki showed that for 6-round AES, partial sums can be replaced by a technique based on the Fast Fourier Transform (FFT), leading to an attack with a comparable complexity.
In this paper we show that the partial sums technique can be combined with an FFT-based technique, to get the best of the two worlds. Using our combined technique, we obtain an attack on 6-round AES with complexity of about 246.4 additions. We fully implemented the attack experimentally, along with the partial sums attack and the Todo-Aoki attack, and confirmed that our attack improves the best known attack on 6-round AES by a factor of more than 32.
We expect that our technique can be used to significantly enhance numerous attacks that exploit the partial sums technique. To demonstrate this, we use our technique to improve the best known attack on 7-round Kuznyechik by a factor of more than 80, and to reduce the complexity of the best known attack on the full MISTY1 from 269.5 to 267.

[article]

Design of a Linear Layer Optimised for Bitsliced 32-bit Implementation

IACR Transactions on Symmetric Cryptology, 2024, Gaëtan Leurent, Clara Pernot

Download:

paper

Keywords:

Bitsliced cipher, Linear layer, Branch number

Abstract:

The linear layer of block ciphers plays an important role in their security. In particular, ciphers designed following the wide-trail strategy use the branch number of the linear layer to derive bounds on the probability of linear and differential trails.
At FSE 2014, the LS-design construction was introduced as a simple and regular structure to design bitsliced block ciphers. It considers the internal state as a bit matrix, and applies alternatively an identical S-Box on all the columns, and an identical L-Box on all the lines. Security bounds are derived from the branch number of the L-Box.
In this paper, we focus on bitsliced linear layers inspired by the LS-design construction and the Spook AEAD algorithm. We study the construction of bitsliced linear transformations with efficient implementations using XORs and rotations (optimized for bitsliced ciphers implemented on 32-bit processors), and a high branch number. In order to increase the density of the activity patterns, the linear layer is designed on the whole state, rather than using multiple parallel copies of an L-Box.
Our main result is a linear layer for 128-bit ciphers with branch number 21, improving upon the best 32-bit transformation with branch number 12, and the one of Spook with branch number 16.

[article] [slides]

Truncated Boomerang Attacks and Application to AES-Based Ciphers

Eurocrypt 2023, Augustin Bariant, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Truncated differential, boomerang attack, AES, KIASU, Deoxys, TNT-AES

Abstract:

The boomerang attack is a cryptanalysis technique that combines two short differentials instead of using a single long differential. It has been applied to many primitives, and results in the best known attacks against several AES-based ciphers (Kiasu-BC, Deoxys-BC). In this paper, we introduce a general framework for boomerang attacks with truncated differentials.
While the underlying ideas are already known, we show that a careful analysis provides a significant improvement over the best boomerang attacks in the literature. In particular, we take into account structures on the plaintext and ciphertext sides, and include an analysis of the key recovery step. On 6-round AES, we obtain a structural distinguisher with complexity 297 and a key recovery attack with complexity 261.
The truncated boomerang attacks is particularly effective against tweakable AES variants. We apply it to 8-round Kiasu-BC, resulting in the best known attack with complexity 283(rather than 2103). We also show an interesting use of the 6-round distinguisher on TNT-AES, a tweakable block-cipher using 6-round AES as a building block. Finally, we apply this framework to Deoxys-BC, using a MILP model to find optimal trails automatically. We obtain the best attacks against round-reduced versions of all variants of Deoxys-BC.

[article]

Algebraic Attacks against Some Arithmetization-Oriented Primitives

IACR Transactions on Symmetric Cryptology, 2022, Augustin Bariant, Clémence Bouvier, Gaëtan Leurent, Léo Perrin

Download:

paper

Keywords:

Arithmetization-oriented hash functions, Poseidon, Feistel–MiMC, Rescue–Prime, Ciminion, algebraic cryptanalysis

Abstract:

Recent advanced Zero-Knowledge protocols, along with other high-level constructions such as Multi-Party Computations (MPC), have highlighted the need for a new type of symmetric primitives that are not optimized for speed on the usual platforms (desktop computers, servers, microcontrollers, RFID tags...), but for their ability to be implemented using arithmetic circuits.
Several primitives have already been proposed to satisfy this need. In order to enable an efficient arithmetization, they operate over large finite fields, and use round functions that can be modelled using low degree equations. The impact of these properties on their security remains to be completely assessed. In particular, algebraic attacks relying on polynomial root-finding become extremely relevant. Such attacks work by writing the cryptanalysis as systems of polynomial equations over the large field, and solving them with off-the-shelf tools (SageMath, NTL, Magma, …).
The need for further analysis of these new designs has been recently highlighted by the Ethereum Foundation, as it issued bounties for successful attacks against round-reduced versions of several of them.
In this paper, we show that the security analysis performed by the designers (or challenge authors) of four such primitives is too optimistic, and that it is possible to improve algebraic attacks using insights gathered from a careful study of the round function.
First, we show that univariate polynomial root-finding can be of great relevance in practice, as it allows us to solve many of the Ethereum Foundation's challenges on Feistel–MiMC. Second, we introduce a trick to essentially shave off two full rounds at little to no cost for Substitution-Permutation Networks (SPN). This can be combined with univariate (resp. multivariate) root-finding, which allowed to solve some challenges for Poseidon (resp. Rescue–Prime). Finally, we also find an alternative way to set up a system of equations to attack Ciminion, leading to much faster attacks than expected by the designers.

[article]

Practical key recovery attacks on FlexAEAD

Designs, Codes and Cryptography, 2022, Orr Dunkelman, Maria Eichlseder, Daniel Kales, Nathan Keller, Gaëtan Leurent, Markus Schofnegger

Download:

paper

Keywords:

Keywords Authenticated encryption, NIST LWC, Practical key recovery, Truncated differential

Abstract:

FlexAEAD is a block cipher candidate submitted to the NIST Lightweight Cryptography standardization project, based on repeated application of an Even-Mansour construction. In order to optimize performance, the designers chose a relatively small number of rounds, using properties of the mode and bounds on differential and linear characteristics to substantiate their security claims. Due to a forgery attack with complexity of 246, FlexAEAD was not selected to the second round of evaluation in the NIST project. In this paper we present a practical key recovery attack on FlexAEAD, using clusters of differentials for the internal permutation and the interplay between different parts of the mode. Our attack, that was fully verified in practice, allows recovering the secret subkeys of FlexAEAD-64 with time complexity of less than 231 encryptions (with experimental success rate of 75%). This is the first practical key recovery attack on a candidate of the NIST standartization project.

[article]

Quantum Linearization Attacks

Asiacrypt 2021, Xavier Bonnetain, Gaëtan Leurent, María Naya-Plasencia, André Schrottenloher (©IACR)

Download:

paper

Keywords:

Quantum cryptanalysis, MACs, superposition query model, Deutsch's algorithm, Bernstein-Vazirani algorithm, Simon's algorithm, Shor's algorithm

Abstract:

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. Recovering the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes.
In this paper, we introduce the 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. Recovering 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 LightMac, PMAC, and numerous variants with (classical) beyond-birthday-bound security (LightMAC+, PMAC) or using tweakable block ciphers (ZMAC). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task.

[article]

Clustering Effect in Simon and Simeck

Asiacrypt 2021, Gaëtan Leurent, Clara Pernot, André Schrottenloher (©IACR)

Download:

paper

Keywords:

Lightweight cipher, Simon, Simeck, differential cryptanalysis, linear cryptanalysis, clustering effect

Abstract:

Simon and Simeck are two lightweight block ciphers with a simple round function using only word rotations and a bit-wise AND operation. Previous work has shown a strong clustering effect for differential and linear cryptanalysis, due to the existence of many trails with the same inputs and outputs.
In this paper, we explore this clustering effect by exhibiting a class of high probability differential and linear trails where the active bits stay in a fixed window of w bits. Instead of enumerating a set of good trails contributing to a differential or a linear approximation, we compute the probability distribution over this space, including all trails in the class.
This results in stronger distinguishers than previously proposed, and we describe key recovery attacks against Simon and Simeck improving the previous results by up to 7 rounds. In particular, we obtain an attack against 42-round Simeck64, leaving only two rounds of security margin, and an attack against 45-round Simon96/144, reducing the security margin from 16 rounds to 9 rounds.

[article]

QCB: Efficient Quantum-secure Authenticated Encryption

Asiacrypt 2021, Ritam Bhaumik, Xavier Bonnetain, André Chailloux, Gaëtan Leurent, María Naya-Plasencia, André Schrottenloher, Yannick Seurin (©IACR)

Download:

paper

Keywords:

authenticated encryption, lightweight cryptography, QCB, post-quantum cryptography, provable security, tweakable block ciphers

Abstract:

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.

[article]

Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2

Eurocrypt 2021, Christof Beierle, Patrick Derbez, Gregor Leander, Gaëtan Leurent, Håvard Raddum, Yann Rotella, David Rupprecht, Lukas Stennes (©IACR)

Download:

paper

Keywords:

GPRS Encryption, Stream Cipher, Algebraic attacks, GEA.

Abstract:

This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms. Instead of providing full 64-bit security, we show that the initial state of GEA-1 can be recovered from as little as 65 bits of known keystream (with at least 24 bits coming from one frame) in time 240 GEA-1 evaluations and using 44.5 GiB of memory.
The attack on GEA-1 is based on an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance. This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design.
In contrast, for GEA-2 we did not discover the same intentional weakness. However, using a combination of algebraic techniques and list merging algorithms we are still able to break GEA-2 in time 245.1 GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.

[article]

New Representations of the AES Key Schedule

Eurocrypt 2021, Gaëtan Leurent, Clara Pernot (©IACR)

Download:

paper

Keywords:

AES, Key schedule, mixFeed, ALE, Impossible differential attack

Abstract:

In this paper we present a new representation of the AES key schedule, with some implications to the security of AES-based schemes. In particular, we show that the AES-128 key schedule can be split into four independent parallel computations operating on 32 bits chunks, up to linear transformation. Surprisingly, this property has not been described in the literature after more than 20 years of analysis of AES. We show two consequences of our new representation, improving previous cryptanalysis results of AES-based schemes.
First, we observe that iterating an odd number of key schedule rounds results in a function with short cycles. This explains an observation of Khairallah on mixFeed, a second-round candidate in the NIST lightweight competition. Our analysis actually shows that his forgery attack on mixFeed succeeds with probability 0.44 (with data complexity 220 GB), breaking the scheme in practice. The same observation also leads to a novel attack on ALE, another AES-based AEAD scheme.
Our new representation also gives efficient ways to combine information from the first subkeys and information from the last subkeys, in order to reconstruct the corresponding master keys. In particular we improve previous impossible differential attacks against AES-128.

[article]

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

Journal of Cryptology, 2021, Antonio Flórez-Gutiérrez, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, André Schrottenloher, Ferdinand Sibleyras (©IACR)

Download:

paper

Keywords:

Gimli, symmetries, symmetric cryptanalysis, full-round distinguisher,

Abstract:

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 264. 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.

[article]

On the Cost of ASIC Hardware Crackers: A SHA-1 Case Study

CT-RSA 2021, Anupam Chattopadhyay, Mustafa Khairallah, Gaëtan Leurent, Zakaria Najm, Thomas Peyrin, Vesselin Velichkov

Download:

paper

Keywords:

SHA-1, Cryptanalysis, ASIC, Birthday Problem, Hash Functions

Abstract:

In February 2017, the SHA-1 hashing algorithm was practically broken using an identical-prefix collision attack implemented on a GPU cluster, and in January 2020 a chosen-prefix collision was first computed with practical implications on various security protocols. These advances opened the door for several research questions, such as the minimal cost to perform these attacks in practice. In particular, one may wonder what is the best technology for software/hardware cryptanalysis of such primitives. In this paper, we address some of these questions by studying the challenges and costs of building an ASIC cluster for performing attacks against a hash function. Our study takes into account different scenarios and includes two cryptanalytic strategies that can be used to find such collisions: a classical generic birthday search, and a state-of-the-art differential attack using neutral bits for SHA-1.
We show that for generic attacks, GPU and ASIC poses a serious practical threat to primitives with security level ∼64 bits, with rented GPU a good solution for a one-off attack, and ASICs more efficient if the attack has to be run a few times. ASICs also pose a non-negligible security risk for primitives with 80-bit security. For differential attacks, GPUs (purchased or rented) are often a very cost-effective choice, but ASIC provides an alternative for organizations that can afford the initial cost and look for a compact, energy-efficient, reusable solution. In the case of SHA-1, we show that an ASIC cluster costing a few millions would be able to generate chosen-prefix collisions in a day or even in a minute. This extends the attack surface to TLS and SSH, for which the chosen-prefix collision would need to be generated very quickly.

[article]

Generic Attacks on Hash Combiners

Journal of Cryptology, Zhenzhen Bao, Itai Dinur, Jian Guo, Gaëtan Leurent, Lei Wang (©IACR)

Download:

paper

Keywords:

Hash function, Generic attack, Hash combiner, XOR combiner, Concatenation combiner, Zipper hash, Hash-Twice, (Second) Preimage attack

Abstract:

Hash combiners are a practical way to make cryptographic hash functions more tolerant to future attacks and compatible with existing infrastructure. A combiner combines two or more hash functions in a way that is hopefully more secure than each of the underlying hash functions, or at least remains secure as long as one of them is secure. Two classical hash combiners are the exclusive-or (XOR) com- biner H1(M)⊕H2(M) and the concatenation combiner H1(M)‖H2(M). Both of them process the same message using the two underlying hash functions in parallel. Apart from parallel combiners, there are also cascade constructions sequentially calling the underlying hash functions to process the message repeatedly, such as Hash-Twice H2(H1(IV,M,M) and the Zipper hash H2(H1(IV,M),M̄), where M̄ is the reverse of the message M. In this work, we study the security of these hash combiners by devising the best-known generic attacks. The results show that the security of most of the combiners is not as high as commonly believed.

[article]

New Results on Gimli: Full-Permutation Distinguishers and Improved Collisions

Asiacrypt 2020, Antonio Flórez-Gutiérrez, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, André Schrottenloher, Ferdinand Sibleyra (©IACR)

Download:

paper

Keywords:

Gimli, symmetries, symmetric cryptanalysis, full-round distinguisher, collision attacks, linear approximations

Abstract:

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 264. 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.

[article]

Out of Oddity — New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems

Crypto 2020, Tim Beyne, Anne Canteaut, Itai Dinur, Maria Eichlseder, Gregor Leander, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, Yu Sasaki, Yosuke Todo, Friedrich Wiemer (©IACR)

Download:

paper

Keywords:

Hash functions, integrity proof systems, Integral attacks, GMiMC, HadesMiMC.

Abstract:

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.

[article]

Spook: Sponge-based leakage-resistant authenticated encryption with a masked tweakable block cipher

IACR Transactions on Symmetric Cryptology, 2020, Special Issue 1, Davide Bellizia, Francesco Berti, Olivier Bronchain, Gaëtan Cassiers, Sébastien Duval, Chun Guo, Gregor Leander, Gaëtan Leurent, Itamar Levi, Charles Momin, Olivier Pereira, Thomas Peters, François-Xavier Standaert, Balazs Udvarhelyi, Friedrich Wiemer

Download:

paper

Keywords:

Authenticated encryption, NIST lightweight cryptography standardization effort, leakage-resistance, bitslice ciphers, masking countermeasure, low energy

Abstract:

This paper defines Spook: a sponge-based authenticated encryption with associated data algorithm. It is primarily designed to provide security against side-channel attacks at a low energy cost. For this purpose, Spook is mixing a leakageresistant mode of operation with bitslice ciphers enabling efficient and low latency implementations. The leakage-resistant mode of operation leverages a re-keying function to prevent differential side-channel analysis, a duplex sponge construction to efficiently process the data, and a tag verification based on a Tweakable Block Cipher (TBC) providing strong data integrity guarantees in the presence of leakages. The underlying bitslice ciphers are optimized for the masking countermeasures against side-channel attacks. Spook is an efficient single-pass algorithm. It ensures state-of-the-art black box security with several prominent features: (i) nonce misuse-resilience, (ii) beyond-birthday security with respect to the TBC block size, and (iii) multiuser security at minimum cost with a public tweak. Besides the specifications and design rationale, we provide first software and hardware implementation results of (unprotected) Spook which confirm the limited overheads that the use of two primitives sharing internal components imply. We also show that the integrity of Spook with leakage, so far analyzed with unbounded leakages for the duplex sponge and a strongly protected TBC modeled as leak-free, can be proven with a much weaker unpredictability assumption for the TBC. We finally discuss external cryptanalysis results and tweaks to improve both the security margins and efficiency of Spook.

[article]

Saturnin: a suite of lightweight symmetric algorithms for post-quantum security

IACR Transactions on Symmetric Cryptology, 2020, Special Issue 1, Anne Canteaut, Sébastien Duval, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, Thomas Pornin, André Schrottenloher

Download:

paper

Keywords:

lightweight cryptography, post-quantum security, block cipher, authenticated encryption, hash function, AES, duck

Abstract:

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.

[article]

SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust

Usenix Security 2020, Gaëtan Leurent, Thomas Peyrin

Download:

paper

Keywords:

SHA-1, Cryptanalysis, Chosen-prefix collision, HPC, GPU, PGP, GnuPG

Abstract:

The SHA-1 hash function was designed in 1995 and has been widely used during two decades. A theoretical collision attack was first proposed in 2004, but due to its high complexity it was only implemented in practice in 2017, using a large GPU cluster. More recently, an almost practical chosen-prefix collision attack against SHA-1 has been proposed. This more powerful attack allows to build colliding messages with two arbitrary prefixes, which is much more threatening for real protocols. In this paper, we report the first practical implementation of this attack, and its impact on real-world security with a PGP/GnuPG impersonation attack. We managed to significantly reduce the complexity of collision attacks against SHA-1: on an Nvidia GTX 970, identical-prefix collisions can now be computed with a complexity (expressed in terms of SHA-1 equivalents on this GPU) of 261.2 rather than 264.7, and chosen-prefix collisions with a complexity of 263.4 rather than 267.1. When renting cheap GPUs, this translates to a cost of US$11k for a collision and USD$45k for a chosen-prefix collision, within the means of academic researchers. Our actual attack required two months of computations using 900 Nvidia GTX 1060 GPUs (we paid US$ 75k because GPU prices were higher, and we wasted some time preparing the attack).
Therefore, the same attacks that have been practical on MD5 since 2009 are now practical on SHA-1. In particular, chosen-prefix collisions can break signature schemes and handshake security in secure channel protocols (TLS, SSH), if generated extremely quickly. We strongly advise to remove SHA-1 from those type of applications as soon as possible.
We exemplify our cryptanalysis by creating a pair of PGP/GnuPG keys with different identities, but colliding SHA-1 certificates. A SHA-1 certification of the first key can therefore be transferred to the second key, leading to an impersonation attack. This proves that SHA-1 signatures now offer virtually no security in practice. The legacy branch of GnuPG still uses SHA-1 by default for identity certifications, but after notifying the authors, the modern branch now rejects SHA-1 signatures (the issue is tracked as CVE-2019-14855).

[article]

Cryptanalysis of Forkciphers

IACR Transactions on Symmetric Cryptology, 2020, Augustin Bariant, Nicolas David, Gaëtan Leurent

Download:

paper

Keywords:

Forkciphers, TWEAKEY, ForkAES, ForkSkinny, Cryptanalysis, NIST Lightweight Standardisation

Abstract:

The forkcipher framework was designed in 2018 by Andreeva et al. for authenticated encryption of short messages. Two dedicated ciphers were proposed in this framework: ForkAES based on the AES (and its tweakable variant Kiasu-BC), and ForkSkinny based on Skinny. The main motivation is that the forked ciphers should keep the same security as the underlying ciphers, but offer better performances thanks to the larger output. Recent cryptanalysis results at ACNS'19 have shown that ForkAES actually offers a reduced security margin compared to the AES with an 8-round attack, and this was taken into account in the design of ForkSkinny.
In this paper, we present new cryptanalysis results on forkciphers. First we improve the previous attack on ForkAES in order to attack the full 10 rounds. This is the first attack challenging the security of full ForkAES. Then we present the first analysis of ForkSkinny, showing that the best attacks on Skinny can be extended to one round for most ForkSkinny variants, and up to three rounds for ForkSkinny-128-256. This allows to evaluate the security degradation between ForkSkinny and the underlying block cipher.
Our analysis shows that all components of a forkcipher must be carefully designed: the attack against ForkAES uses the weak diffusion of the middle rounds in reconstruction queries (going from one ciphertext to the other), but the attack against ForkSkinny uses a weakness of the tweakey schedule in encryption queries (when one branch of the tweakey schedule is skipped).

[article]

Universal Forgery Attack against GCM-RUP

CT-RSA 2020, Yanbin Li, Gaëtan Leurent, Meiqin Wang, Wei Wang, Guoyan Zhang, Yu Liu

Download:

paper

Keywords:

GCM-RUP, partial key recovery, universal forgery, birthday bound

Abstract:

Authenticated encryption (AE) schemes are widely used to secure communications because they can guarantee both confidentiality and authenticity of a message. In addition to the standard AE security notion, some recent schemes offer extra robustness, i.e. they maintain security in some misuse scenarios. In particular, Ashur, Dunkelman and Luykx proposed a generic AE construction at CRYPTO'17 that is secure even when releasing unverified plaintext (the RUP setting), and a concrete instantiation, GCM-RUP. The designers proved that GCM-RUP is secure up to the birthday bound in the nonce-respecting model. In this paper, we perform a birthday-bound universal forgery attack against GCM-RUP, matching the bound of the proof. While there are simple distinguishing attacks with birthday complexity on GCM-RUP, our attack is much stronger: we have a partial key recovery leading to universal forgeries. For reference, the best known universal forgery attack against GCM requires 22n/3 operations, and many schemes do not have any known universal forgery attacks faster than 2n. This suggests that GCM-RUP offers a different security trade-off than GCM: stronger protection in the RUP setting, but more fragile when the data complexity reaches the birthday bound. In order to avoid this attack, we suggest a minor modification of GCM-RUP that seems to offer better robustness at the birthday bound.

[article]

Lightweight MACs from Universal Hash Functions

CARDIS 2019, Sébastien Duval, Gaëtan Leurent

Download:

paper

Keywords:

Lightweight cryptography, Micro-controller, MAC, Almost Universal hash functions, Beyond-birthday-bound security

Abstract:

Lightweight cryptography is a topic of growing importance, with the goal to secure the communication of low-end devices that are not powerful enough to use conventional cryptography. There have been many recent proposals of lightweight block ciphers, but comparatively few results on lightweight Message Authentication Codes (MACs).
Therefore, this paper focuses on lightweight MACs. We review some existing constructions, and revisit the choices made in mainstream MACs with a focus on lightweight cryptography. We consider MACs based on universal hash functions, because they offer information theoretic security, can be implemented efficiently and are widely used in conventional cryptography. However, many constructions used in practice (such as GMAC or Poly1305-AES) follow the Wegman-Carter-Shoup construction, which is only secure up to 264 queries with a 128-bit state.
We point out that there are simple solutions to reach security beyond the birthday bound, and we propose a concrete instantiation, MAC611, reaching 61-bit security with a 61-bit universal hash function. We wrote an optimized implementation on two ARM micro-controllers, and we obtain very good performances on the Cortex-M4, at only 3.7 c/B for long messages, and less than one thousand cycles for short messages.

[article]

Low-Memory Attacks against Two-Round Even-Mansour using the 3-XOR Problem

Crypto 2019, Gaëtan Leurent, Ferdinand Sibleyras (©IACR)

Download:

paper

Keywords:

Even-Mansour, Cryptanalysis, 3-XOR

Abstract:

The iterated Even-Mansour construction is an elegant construction that idealizes block cipher designs such as the AES. In this work we focus on the simplest variant, the 2-round Even-Mansour construction with a single key. This is the most minimal construction that offers security beyond the birthday bound: there is a security proof up to 22n/3 evaluations of the underlying permutations and encryption, and the best known attacks have a complexity of roughly 2n/n operations. We show that attacking this scheme with block size n is related to the 3-XOR problem with element size =2n, an important algorithmic problem that has been studied since the nineties. In particular the 3-XOR problem is known to require at least 2/3 queries, and the best known algorithms require around 2/2/ operations: this roughly matches the known bounds for the 2-round Even-Mansour scheme.
Using this link we describe new attacks against the 2-round Even-Mansour scheme. In particular, we obtain the first algorithms where both the data and the memory complexity are significantly lower than 2n. From a practical standpoint, previous works with a data and/or memory complexity close to 2n are unlikely to be more efficient than a simple brute-force search over the key. Our best algorithm requires just λn known plaintext/ciphertext pairs, for some constant 0<λ<1, 2nn time, and 2λn memory. For instance, with n=64 and λ=1/2, the memory requirement is practical, and we gain a factor 32 over brute-force search. We also describe an algorithm with asymptotic complexity O(2nln2n/n2), improving the previous asymptotic complexity of O(2n/n), using a variant of the 3-SUM algorithm of Baran, Demaine, and Patrascu.

[article] [slides]

From Collisions to Chosen-Prefix Collisions — Application to Full SHA-1

Eurocrypt 2019, Gaëtan Leurent, Thomas Peyrin (©IACR)

Download:

paper slides

Keywords:

Hash function, Cryptanalysis, Chosen-prefix collision, SHA1, MD5

Abstract:

A chosen-prefix collision attack is a stronger variant of a collision attack, where an arbitrary pair of challenge prefixes are turned into a collision. Chosen-prefix collisions are usually significantly harder to produce than (identical-prefix) collisions, but the practical impact of such an attack is much larger. While many cryptographic constructions rely on collision-resistance for their security proofs, collision attacks are hard to turn into a break of concrete protocols, because the adversary has limited control over the colliding messages. On the other hand, chosen-prefix collisions have been shown to threaten certificates (by creating a rogue CA) and many internet protocols (TLS, SSH, IKE).
In this article, we propose new techniques to turn collision attacks into chosen-prefix collision attacks. Our strategy is composed of two phases: first, a birthday search that aims at taking the random chaining variable difference (due to the chosen-prefix model) to a set of pre-defined target differences. Then, using a multi-block approach, carefully analysing the clustering effect, we map this new chaining variable difference to a colliding pair of states using techniques developed for collision attacks.
We apply those techniques to MD5 and SHA1, and obtain improved attacks. In particular, we have a chosen-prefix collision attack against SHA1 with complexity between 266.9 and 269.4 (depending on assumptions about the cost of finding near-collision blocks), while the best-known attack has complexity 277.1. This is within a small factor of the complexity of the classical collision attack on SHA1 (estimated as 264.7). This represents yet another warning that industries and users have to move away from using SHA1 as soon as possible.

[article]

MDS Matrices with Lightweight Circuits

IACR Transactions on Symmetric Cryptology, 2018, Sébastien Duval, Gaëtan Leurent

Download:

paper

Keywords:

MDS matrix, Lightweight cryptography

Abstract:

MDS matrices are an important element for the design of block ciphers such as the AES. In recent years, there has been a lot of work on the construction of MDS matrices with a low implementation cost, in the context of lightweight cryptography.
Most of the previous efforts focused on local optimization, constructing MDS matrices with coefficients that can be efficiently computed. In particular, this led to a matrix with a direct xor count of only 106, while a direct implementation of the MixColumn matrix of the AES requires 152 bitwise xors.
More recently, techniques based on global optimization have been introduced, were the implementation can reuse some intermediate variables. In particular, Kranz et al. used optimization tools to a find good implementation from the description of an MDS matrix. They have lowered the cost of implementing the MixColumn matrix to 97 bitwise xors, and proposed a new matrix with only 72 bitwise xors, the lowest cost known so far.
In this work we propose a different approach to global optimization. Instead of looking for an optimized circuit of a given matrix, we run a search through a space of circuits, to find optimal circuits yielding MDS matrices. This results in MDS matrices with an even lower cost, with only 67 bitwise xors.

[article]

Cryptanalysis of MORUS

Asiacrypt 2018, Tomer Ashur, Maria Eichlseder, Martin M. Lauridsen, Gaëtan Leurent, Brice Minaud, Yann Rotella, Yu Sasaki, Benoît Viguier (©IACR)

Download:

paper

Keywords:

MORUS, CAESAR, Authenticated Encryption, Nonce Respecting, Linear Cryptanalysis, Confidentiality

Abstract:

MORUS is a high-performance authenticated encryption algorithm submitted to the CAESAR competition, and recently selected as a finalist. There are three versions of MORUS: MORUS-640 with a 128-bit key, and MORUS-1280 with 128-bit or 256-bit keys. For all versions the security claim for confidentiality matches the key size. In this paper, we analyze the components of this algorithm (initialization, state update and tag generation), and report several results.
As our main result, we present a linear correlation in the keystream of full MORUS, which can be used to distinguish its output from random and to recover some plaintext bits in the broadcast setting. For MORUS-1280, the correlation is 2-76 , which can be exploited after around 2152 encryptions, less than what would be expected for a 256-bit secure cipher. For MORUS-640, the same attack results in a correlation of 2-73 , which does not violate the security claims of the cipher.
To identify this correlation, we make use of rotational invariants in MORUS using linear masks that are invariant by word-rotations of the state. This motivates us to introduce single-word versions of MORUS called MiniMORUS, which simplifies the analysis. The attack has been implemented and verified on MiniMORUS, where it yields a correlation of 2-16.
We also study reduced versions of the initialization and finalization of MORUS, aiming to evaluate the security margin of these components. We show a forgery attack when finalization is reduced from 10 steps to 3, and a key-recovery attack in the nonce-misuse setting when initialization is reduced from 16 steps to 10. These additional results do not threaten the full MORUS, but studying all aspects of the design is useful to understand its strengths and weaknesses.

[article]

Generic Attacks against Beyond-Birthday-Bound MACs

Crypto 2018, Gaëtan Leurent, Mridul Nandi, Ferdinand Sibleyras (©IACR)

Download:

paper

Keywords:

Modes of operation, Cryptanalysis, Message Authentication Codes, Beyond-Birthday-Bound security

Abstract:

In this work, we study the security of several recent MAC constructions with provable security beyond the birthday bound. We consider block-cipher based constructions with a double-block internal state, such as SUM-ECBC, PMAC+, 3kf9, GCM-SIV2, and some variants (LightMAC+, 1kPMAC+). All these MACs have a security proof up to 22n/3 queries, but there are no known attacks with less than 2n queries.
We describe a new cryptanalysis technique for double-block MACs based on finding quadruples of messages with four pairwise collisions in halves of the state. We show how to detect such quadruples in SUM-ECBC, PMAC+, 3kf9, GCM-SIV2 and their variants with O(23n/4) queries, and how to build a forgery attack with the same query complexity. The time complexity of these attacks is above 2n, but it shows that the schemes do not reach full security in the information theoretic model. Surprisingly, our attack on LightMAC+ also invalidates a recent security proof by Naito.
Moreover, we give a variant of the attack against SUM-ECBC and GCM-SIV2 with time and data complexity Õ(26n/7). As far as we know, this is the first attack with complexity below 2n against a deterministic beyond-birthday-bound secure MAC.
As a side result, we also give a birthday attack against 1kf9, a single-key variant of 3kf9 that was withdrawn due to issues with the proof.

[article]

The Missing Difference Problem, and its Applications to Counter Mode Encryption

Eurocrypt 2018, Gaëtan Leurent, Ferdinand Sibleyras (©IACR)

Download:

paper

Keywords:

Modes of operation, CTR, GCM, Poly1305, Cryptanalysis

Abstract:

The counter mode (CTR) is a simple, efficient and widely used encryption mode using a block cipher. It comes with a security proof that guarantees no attacks up to the birthday bound (i.e. as long as the number of encrypted blocks σ satisfies σ≪2n/2, and a matching attack that can distinguish plaintext/ciphertext pairs from random using about 2n/2 blocks of data.
The main goal of this paper is to study attacks against the counter mode beyond this simple distinguisher. We focus on message recovery attacks, with realistic assumptions about the capabilities of an adversary, and evaluate the full time complexity of the attacks rather than just the query complexity. Our main result is an attack to recover a block of message with complexity Õ(2n/2). This shows that the actual security of CTR is similar to that of CBC, where collision attacks are well known to reveal information about the message.
To achieve this result, we study a simple algorithmic problem related to the security of the CTR mode: the missing difference problem. We give efficient algorithms for this problem in two practically relevant cases: where the missing difference is known to be in some linear subspace, and when the amount of data is higher than strictly required.
As a further application, we show that the second algorithm can also be used to break some polynomial MACs such as GMAC and Poly1305, with a universal forgery attack with complexity Õ(22n/3).

[article] [slides]

Quantum Differential and Linear Cryptanalysis

IACR Transactions on Symmetric Cryptology, 2016, Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia

Download:

paper slides

Keywords:

Symmetric cryptography, Differential cryptanalysis, Linear cryptanalysis, Post-quantum cryptography, Quantum attacks, Block ciphers

Abstract:

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.

[article]

Improved Generic Attacks Against Hash-based MACs and HAIFA (long version)

Algorithmica, 2016, Itai Dinur, Gaëtan Leurent

Download:

paper

Keywords:

Keywords Hash functions, MAC, HMAC, Merkle-Damgård, HAIFA, state-recovery attack, universal forgery attack, GOST, Streebog, SHA family

Abstract:

The security of HMAC (and more general hash-based MACs) against state-recovery and universal forgery attacks was shown to be suboptimal, following a series of results by Leurent et al. and Peyrin et al. These results have shown that such powerful attacks require significantly less than 2 computations, contradicting the common belief (where ℓ denotes the internal state size). In this work, we revisit and extend these results, with a focus on concrete hash functions that limit the message length, and apply special iteration modes.
We begin by devising the first state-recovery attack on HMAC with a HAIFA hash function (using a block counter in every compression function call), with complexity 24ℓ/5. Then, we describe improved tradeoffs between the message length and the complexity of a state-recovery attack on HMAC with a Merkle-Damgård hash function. Consequently, we obtain improved attacks on several HMAC constructions used in practice, in which the hash functions limits the maximal message length (e.g., SHA-1 and SHA-2). Finally, we present the first universal forgery attacks, which can be applied with short message queries to the MAC oracle. In particular, we devise the first universal forgery attacks applicable to SHA-1 and SHA-2.
Despite their theoretical interest, our attacks do not seem to threaten the practical security of the analyzed concrete HMAC constructions.

[article] [slides]

On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN

ACM CCS 2016, Karthikeyan Bhargavan, Gaëtan Leurent

Download:

paper slides

Keywords:

OpenVPN, TLS, HTTPS, CBC, collision attack

See also:

SWEET32 attack

Abstract:

While modern block ciphers, such as AES, have a block size of at least 128 bits, there are many 64-bit block ciphers, such as 3DES and Blowfish, that are still widely supported in Internet security protocols such as TLS, SSH, and IPsec. When used in CBC mode, these ciphers are known to be susceptible to collision attacks when they are used to encrypt around 232 blocks of data (the so-called birthday bound). This threat has traditionally been dismissed as impractical since it requires some prior knowledge of the plaintext and even then, it only leaks a few secret bits per gigabyte. Indeed, practical collision attacks have never been demonstrated against any mainstream security protocol, leading to the continued use of 64-bit ciphers on the Internet. In this work, we demonstrate two concrete attacks that exploit collisions on short block ciphers. First, we present an attack on the use of 3DES in HTTPS that can be used to recover a secret session cookie. Second, we show how a similar attack on Blowfish can be used to recover HTTP BasicAuth credentials sent over OpenVPN connections. In our proof-of-concept demos, the attacker needs to capture about 785GB of data, which takes between 19-38 hours in our setting. This complexity is comparable to the recent RC4 attacks on TLS: the only fully implemented attack takes 75 hours. We evaluate the impact of our attacks by measuring the use of 64-bit block ciphers in real-world protocols. We discuss mitigations, such as disabling all 64-bit block ciphers, and report on the response of various software vendors to our responsible disclosure of these attacks.

[article] [slides]

Breaking Symmetric Cryptosystems using Quantum Period Finding

Crypto 2016, Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia (©IACR)

Download:

paper slides

Keywords:

Post-quantum cryptography, symmetric cryptography, quantum attacks, block ciphers, modes of operation, slide attack

Abstract:

Due to Shor's algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it.
We study applications of a quantum procedure called Simon's algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon's algorithm: finding a collision requires Ω(2n/2) queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model.
We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenti- cated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF.
Second, we show that Simon's algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.

[article]

Key Recovery Attack against 2.5-round pi-Cipher

FSE 2016, Christina Boura, Avik Chakraborti, Gaëtan Leurent, Goutam Paul, Dhiman Saha, Hadi Soleimany, Valentin Suder (©IACR)

Download:

paper

Keywords:

Authenticated encryption, π-Cipher, CAESAR competition, guess and determine, cryptanalysis

Abstract:

In this paper, we propose a guess and determine attack against some variants of the π-Cipher family of authenticated ciphers. This family of ciphers is a second-round candidate of the CAESAR competition. More precisely, we show a key recovery attack with time complexity little higher than 2, and low data complexity, against variants of the cipher with ω-bit words, when the internal permutation is reduced to 2.5 rounds. In particular, this gives an attack with time complexity 272 against the variant π16-Cipher096 (using 16-bit words) reduced to 2.5 rounds, while the authors claim 96 bits of security with 3 rounds in their second-round submission. Therefore, the security margin for this variant of π-Cipher is very limited. The attack can also be applied to lightweight variants that are not included in the CAESAR proposal, and use only two rounds. The lightweight variants π16-Cipher096 and π16-Cipher128 claim 96 bits and 128 bits of security respectively, but our attack can break the full 2 rounds with complexity 272. Finally, the attack can be applied to reduced versions of two more variants of π-Cipher that were proposed in the first-round submission with 4 rounds: π16-Cipher128 (using 16-bit words) and π32-Cipher256 (using 32-bit words). The attack on 2.5 rounds has complexity 272 and 2137 respectively, while the security claim for 4 rounds are 128 bits and 256 bits of security.

[article] [slides]

Improved Differential-Linear Cryptanalysis of 7-round Chaskey with Partitioning

Eurocrypt 2016, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Differential cryptanalysis, linear cryptanalysis, ARX, addition, partitioning, Chaskey, FEAL

Abstract:

In this work we study the security of Chaskey, a recent lightweight MAC designed by Mouha et al., currently being considered for standardisation by ISO/IEC and ITU-T. Chaskey uses an ARX structure very similar to SipHash. We present the first cryptanalysis of Chaskey in the single user setting, with a differential-linear attack against 6 and 7 rounds, hinting that the full version of Chaskey with 8 rounds has a rather small security margin. In response to these attacks, a 12-round version has been proposed by the designers.
To improve the complexity of the differential-linear cryptanalysis, we refine a partitioning technique recently proposed by Biham and Carmeli to improve the linear cryptanalysis of addition operations. We also propose an analogue improvement of differential cryptanalysis of addition operations. Roughly speaking, these techniques reduce the data complexity of linear and differential attacks, at the cost of more processing time per data. It can be seen as the analogue for ARX ciphers of partial key guess and partial decryption for SBox-based ciphers.
When applied to the differential-linear attack against Chaskey, this partitioning technique greatly reduces the data complexity, and this also results in a reduced time complexity. While a basic differential-linear attack on 7 round takes 278 data and time (respectively 235 for 6 rounds), the improved attack requires only 248 data and 267 time (respectively 225 data and 229 time for 6 rounds).
We also show an application of the partitioning technique to FEAL-8X, and we hope that this technique will lead to a better understanding of the security of ARX designs.

[article]

Transcript Collision Attacks: Breaking Authentication in TLS, IKE, and SSH

NDSS 2016, Karthikeyan Bhargavan, Gaëtan Leurent

Download:

paper

Keywords:

TLS, IKE, SSH, transcript collision

Abstract:

In response to high-profile attacks that exploit hash function collisions, software vendors have started to phase out the use of MD5 and SHA-1 in third-party digital signature applications such as X.509 certificates. However, weak hash constructions continue to be used in various cryptographic constructions within mainstream protocols such as TLS, IKE, and SSH, because practitioners argue that their use in these protocols relies only on second preimage resistance, and hence is unaffected by collisions. This paper systematically investigates and debunks this argument.
We identify a new class of transcript collision attacks on key exchange protocols that rely on efficient collision-finding algorithms on the underlying hash constructions. We implement and demonstrate concrete credential-forwarding attacks on TLS 1.2 client authentication, TLS 1.3 server authentication, and TLS channel bindings. We describe almost-practical impersonation and downgrade attacks in TLS 1.1, IKEv2 and SSH-2. As far as we know, these are the first collision-based attacks on the cryptographic constructions used in these popular protocols.
Our practical attacks on TLS were responsibly disclosed (under the name SLOTH) and have resulted in security updates to several TLS libraries. Our analysis demonstrates the urgent need for disabling all uses of weak hash functions in mainstream protocols, and our recommendations have been incorporated in the upcoming Token Binding and TLS 1.3 protocols.

[article]

Collision Attacks against CAESAR Candidates — Forgery and Key-Recovery against AEZ and Marble

Asiacrypt 2015, Thomas Fuhr, Gaëtan Leurent, Valentin Suder (©IACR)

Download:

paper

Keywords:

CAESAR competition, authenticated encryption, cryptanalysis, Marble, AEZ, PMAC, forgery, key-recovery

Abstract:

In this paper we study authenticated encryption algorithms inspired by the OCB mode (Offset Codebook). These algorithms use secret offsets (masks derived from a whitening key) to turn a block cipher into a tweakable block cipher, following the XE or XEX construction.
OCB has a security proof up to 2n/2 queries, and a matching forgery attack was described by Ferguson, where the main step of the attack recovers the whitening key. In this work we study recent authenticated encryption algorithms inspired by OCB, such as Marble, AEZ, and COPA. While Ferguson's attack is not applicable to those algorithms, we show that it is still possible to recover the secret mask with birthday complexity. Recovering the secret mask easily leads to a forgery attack, but it also leads to more devastating attacks, with a key-recovery attack against Marble and AEZ v2 and v3 with birthday complexity.
For Marble, this clearly violates the security claims of full n-bit security. For AEZ, this matches the security proof, but we believe it is nonetheless a quite undesirable property that collision attacks allow to recover the master key, and more robust designs would be desirable.
Our attack against AEZ is generic and independent of the internal permutation (in particular, it still works with the full AES), but the key-recovery is specific to the key derivation used in AEZ v2 and v3. Against Marble, the forgery attack is generic, but the key-recovery exploits the structure of the E permutation (4 AES rounds). In particular, we introduce a novel cryptanalytic method to attack 3 AES rounds followed by 3 inverse AES rounds, which can be of independent interest.

[article]

Cryptanalysis of Feistel Networks with Secret Round Functions

SAC 2015, Alex Biryukov, Gaëtan Leurent, Léo Perrin

Download:

paper

Keywords:

Cryptanalysis, Feistel network, yoyo, generic attack, guess-and-determine

Abstract:

Generic distinguishers against Feistel Network with up to 5 rounds exist in the regular setting and up to 6 rounds in a multi-key setting. We present new cryptanalyses against Feistel Networks with 5, 6 and 7 rounds which are not simply distinguishers but actually recover completely the unknown Feistel functions.
When an exclusive-or is used to combine the output of the round function with the other branch, we use the so-called yoyo game which we improved using a heuristic based on particular cycle structures. The complexity of a complete recovery is equivalent to O(22n) encryptions where n is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively O(2n2n-1+2n) and O(2n2n+2n). However when modular addition is used, this attack does not work. In this case, we use an optimized guess-and-determine strategy to attack 5 rounds with complexity O(2n23n/4). Our results are, to the best of our knowledge, the first recovery attacks against generic 5-, 6- and 7-round Feistel Networks.

[article] [slides]

Differential Forgery Attack against LAC

SAC 2015, Gaëtan Leurent

Download:

paper slides

Keywords:

Differential cryptanalysis, differentials, characteristics, forgery attack, truncated differential, LBlock, LAC

Abstract:

LAC is one of the candidates to the CAESAR competition. In this paper we present a differential forgery attack on LAC. We study the collection of characteristics following a fixed truncated characteristic, in order to obtain a lower bound on the probability of a differential. We show that some differentials have a probability higher than 2-64, which allows a forgery attack on the full LAC. This work illustrates the difference between the probability of differentials and characteristics, and we describe tools to evaluate the probability of some characteristics.

[article] [slides]

Construction of Lightweight S-Boxes using Feistel and MISTY Structures

SAC 2015, Anne Canteaut, Sébastien Duval, Gaëtan Leurent

Download:

paper slides

Keywords:

S-Box, Feistel network, MISTY network, lightweight block-cipher

Abstract:

The aim of this work is to find large S-Boxes, typically operating on 8 bits, having both good cryptographic properties and a low implementation cost. Such S-Boxes are suitable building-blocks in many lightweight block ciphers since they may achieve a better security level than designs based directly on smaller S-Boxes. We focus on S-Boxes corresponding to three rounds of a balanced Feistel and of a balanced MISTY structure, and generalize the recent results by Li and Wang on the best differential uniformity and linearity offered by such a construction. Most notably, we prove that Feistel networks supersede MISTY networks for the construction of 8-bit permutations. Based on these results, we also provide a particular instantiation of an 8-bit permutation with better properties than the S-Boxes used in several ciphers, including Robin, Fantomas or CRYPTON.

[article] [slides]

The Sum can be Weaker than Each Part

Eurocrypt 2015, Gaëtan Leurent, Wang Lei (©IACR)

Download:

paper slides

Keywords:

Hash functions, combiners, XOR combiner, preimage attack

Abstract:

In this paper we study the security of summing the outputs of two independent hash functions, in an effort to increase the security of the resulting design, or to hedge against the failure of one of the hash functions. The exclusive-or (XOR) combiner H1(M) ⊕ H2(M) is one of the two most classical combiners, together with the concatenation combiner H1(M) ‖ H2(M). While the security of the concatenation of two hash functions is well understood since Joux's seminal work on multicollisions, the security of the sum of two hash functions has been much less studied.
The XOR combiner is well known as a good PRF and MAC combiner, and is used in practice in TLS versions 1.0 and 1.1. In a hash function setting, Hoch and Shamir have shown that if the compression functions are modeled as random oracles, or even weak random oracles (i.e. they can easily be inverted -- in particular H1 and H2 offer no security), H1 ⊕ H2 is indifferentiable from a random oracle up to the birthday bound.
In this work, we focus on the preimage resistance of the sum of two narrow-pipe n-bit hash functions, following the Merkle-Damgård or HAIFA structure (the internal state size and the output size are both n bits). We show a rather surprising result: the sum of two such hash functions, e.g. SHA-512 ⊕ Whirlpool, can never provide n-bit security for preimage resistance. More precisely, we present a generic preimage attack with a complexity of Õ(25n/6). While it is already known that the XOR combiner is not preserving for preimage resistance (i.e. there might be some instantiations where the hash functions are secure but the sum is not), our result is much stronger: for any narrow-pipe functions, the sum is not preimage resistant.
Besides, we also provide concrete preimage attacks on the XOR combiner (and the concatenation combiner) when one or both of the compression functions are weak; this complements Hoch and Shamir's proof by showing its tightness for preimage resistance.
Of independent interests, one of our main technical contributions is a novel structure to control simultaneously the behavior of independent hash computations which share the same input message. We hope that breaking the pairwise relationship between their internal states will have applications in related settings.

[article]

FPGA implementations of SPRING

CHES 2014, Hai Brenner, Lubos Gaspar, Gaëtan Leurent, Alon Rosen, François-Xavier Standaert (©IACR)

Download:

paper

Keywords:

SPRING, PRF, learning with rounding, lattices, PFGA implementation, side-channel security

Abstract:

SPRING is a family of pseudo-random functions that aims to combine the guarantees of security reductions with good performance on a variety of platforms. Preliminary software implementations for small-parameter instantiations of SPRING were proposed at FSE 2014, and have been demonstrated to reach throughputs within small factors of those of AES. In this paper, we complement these results and investigate the hardware design space of these types of primitives.
Our first (pragmatic) contribution is the first FPGA implementation of SPRING in a counter-like mode. We show that the "rounded product" operations in our design can be computed efficiently, reaching throughputs in the hundreds of megabits/second range within only 4% of the resources of a modern (Xilinx Virtex-6) reconfigurable device. Our second (more prospective) contribution is to discuss the properties of SPRING hardware implementations for side-channel resistance. We show that a part of the design can be very efficiently masked (with linear overhead), while another part implies quadratic overhead due to non-linear operations (similarly to what is usually observed, e.g., for block ciphers). Yet, we argue that for this second part of the design, resistance against simple power analysis may be sufficient to obtain concrete implementation security. We suggest ways to reach this goal very efficiently, via shuffling. We believe that such hybrid implementations, where each part of the design is protected with adequate solutions, is a promising topic for further investigation.

[article] [slides]

Improved Generic Attacks Against Hash-based MACs and HAIFA

Crypto 2014, Itai Dinur, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Hash functions, MAC, HMAC, Merkle-Damgård, HAIFA, state-recovery attack, universal forgery attack, GOST, Streebog, SHA family

Abstract:

The security of HMAC (and more general hash-based MACs) against state-recovery and universal forgery attacks was very recently shown to be suboptimal, following a series of surprising results by Leurent et al. and Peyrin et al. These results have shown that such powerful attacks require much less than 2 computations, contradicting the common belief (where ℓ denotes the internal state size). In this work, we revisit and extend these results, with a focus on properties of concrete hash functions such as a limited message length, and special iteration modes.
We begin by devising the first state-recovery attack on HMAC with a HAIFA hash function (using a block counter in every compression function call), with complexity 24ℓ/5. Then, we describe improved trade-offs between the message length and the complexity of a state-recovery attack on HMAC. Consequently, we obtain improved attacks on several HMAC constructions used in practice, in which the hash functions limit the maximal message length (e.g., SHA-1 and SHA-2). Finally, we present the first universal forgery attacks, which can be applied with short message queries to the MAC oracle. In particular, we devise the first universal forgery attacks applicable to SHA-1 and SHA-2.

[article]

The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function

SAC 2014, Jian Guo, Jérémy Jean, Gaëtan Leurent, Thomas Peyrin, Lei Wang

Download:

paper

Keywords:

Streebog, cryptanalysis, second-preimage attack, diamond structure, expandable message, HAIFA

Abstract:

Abstract. Streebog is a new Russian hash function standard. It follows the HAIFA framework as domain extension algorithm and claims to resist recent generic second-preimage attacks with long messages. However, we demonstrate in this article that the specific instantiation of the HAIFA framework used in Streebog makes it weak against such attacks. More precisely, we observe that Streebog makes a rather poor usage of the HAIFA counter input in the compression function, which allows to construct second-preimages on the full Streebog-512 with a complexity as low as n×2n/2 (namely 2266) compression function evaluations for long messages. This complexity has to be compared with the expected 2512 computations bound that an ideal hash function should provide. Our work is a good example that one must be careful when using a design framework for which not all instances are secure. HAIFA helps designers to build a secure hash function, but one should pay attention to the way the counter is handled inside the compression function.

[article]

Hardware Implementation and Side-Channel Analysis of Lapin

CT-RSA 2014, Lubos Gaspar, Gaëtan Leurent, François-Xavier Standard

Download:

paper

Keywords:

LPN, Ring-LPN, masking, side-channel analysis

Abstract:

Lapin is a new authentication protocol that has been designed for low-cost implementations. In a work from RFIDsec 2012, Berstein and Lange argued that at similar (mathematical) security levels, Lapin's performances are below the ones of block cipher based authentication. In this paper, we suggest that as soon as physical security (e.g. against side-channel attacks) is taken into account, this criticism can be mitigated. For this purpose, we start by investigating masked hardware implementations of Lapin, and discuss the gains obtained over software ones. Next, we observe that the structure of our implementations significantly differs from block cipher ones (for which most results in side-channel analysis apply), hence raising questions regarding how to evaluate physical security in this case. We then provide first results of side-channel analyzes against unprotected and masked Lapin. Despite interesting properties of the masked implementations, our conclusions are still contrasted because of the on-chip randomness requirements of Lapin protocol. These results give strong incentive to design similar but deterministic protocols, e.g. based on the recently introduced Learning With Rounding assumption.

[article] [slides]

LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations

FSE 2014, Vincent Grosso, Gaëtan Leurent, François-Xavier Standaert, Kerem Varıcı (©IACR)

Download:

paper slides

Keywords:

Masking, Block cipher design, Robin, Fantomas

See also:

CAESAR candidate SCREAM

Abstract:

Side-channel analysis is an important issue for the security of embedded cryptographic devices, and masking is one of the most in- vestigated solutions to mitigate such attacks. In this context, efficient masking has recently been considered as a possible criteria for new block cipher designs. Previous proposals in this direction were applicable to dif- ferent types of masking schemes (e.g. Boolean and polynomial). In this paper, we study possible optimizations when specializing the designs to Boolean masking. For this purpose, we first observe that bitslice ciphers have interesting properties for improving both the efficiency and the reg- ularity of masked software implementations. Next we specify a family of block ciphers (denoted as LS-designs) that can systematically take ad- vantage of bitslicing in a principled manner. Eventually, we evaluate both the security and performance of such designs and two of their instances, confirming excellent properties for physically secure applications.

[article] [slides]

SPRING: Fast Pseudorandom Functions from Rounded Ring Products

FSE 2014, Abhishek Banerjee, Hai Brenner, Gaëtan Leurent, Chris Peikert, Alon Rosen (©IACR)

Download:

paper slides

Keywords:

Pseudorandom functions, noisy learning problems, learning with rounding, lattices

Abstract:

Recently, Banerjee, Peikert and Rosen (EUROCRYPT 2012) proposed new theoretical pseudorandom function candidates based on "rounded products" in certain polynomial rings, which have rigorously provable security based on worst-case lattice problems. The functions also enjoy algebraic properties that make them highly parallelizable and attractive for modern applications, such as evaluation under homomorphic encryption schemes. However, the parameters required by BPR's security proofs are too large for practical use, and many other practical aspects of the design were left unexplored in that work.
In this work we give two concrete and practically efficient instantiations of the BPR design, which we call SPRING, for "subset-product with rounding over a ring." One instantiation uses a generator matrix of a binary BCH error-correcting code to "determinstically extract" nearly random bits from a (biased) rounded subset-product. The second instantiation eliminates bias by working over suitable moduli and decomposing the computation into "Chinese remainder" components.
We analyze the concrete security of these instantiations, and provide initial software implementations whose throughputs are within small factors (as small as 4.5) of those of AES.

[article] [slides]

New Generic Attacks against Hash-based MACs

Asiacrypt 2013, Gaëtan Leurent, Thomas Peyrin, Lei Wang (©IACR)

Download:

paper slides

Keywords:

NMAC, HMAC, hash function, distinguishing-H, key recovery, GOST

Abstract:

In this paper we study the security of hash-based MAC algorithms (such as HMAC and NMAC) above the birthday bound. Up to the birthday bound, HMAC and NMAC are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an n-bit MAC is built from a hash function with a ℓ-bit state (ℓ ≥ n), there is a well-known existential forgery attack with complexity 2ℓ/2. However, the remaining security after 2ℓ/2 computations is not well understood. In particular it is widely assumed that if the underlying hash function is sound, then a generic universal forgery attack should require 2n computations and some distinguishing (e.g. distinguishing-H but not distinguishing-R) and state-recovery attacks should also require 2 computations (or 2k if k < ℓ).
In this work, we show that above the birthday bound, hash-based MACs offer significantly less security than previously believed. Our main result is a generic distinguishing-H and state-recovery attack against hash-based MACs with a complexity of only Õ(2ℓ/2). In addition, we show a key-recovery attack with complexity Õ(23ℓ/4) against HMAC used with a hash functions with an internal checksum, such as GOST. This surprising result shows that the use of a checksum might actually weaken a hash function when used in a MAC. We stress that our attacks are generic, and they are in fact more efficient than some previous attacks proposed on MACs instanciated with concrete hash functions. We use techniques similar to the cycle-detection technique proposed by Peyrin et al. at Asiacrypt 2012 to attack HMAC in the related-key model. However, our attacks works in the single-key model for both HMAC and NMAC, and without restriction on the key size.

[article] [slides]

Construction of Differential Characteristics in ARX Designs — Application to Skein

Crypto 2013, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Symmetric ciphers, hash functions, ARX, Skein, generalized characteristics, differential attacks

See also:

ARXtools

Abstract:

In this paper, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger and the multi-bit constraints of Leurent. We describe a more efficient way to propagate multi-bit constraints, that allows us to use the complete set of 232 2.5-bit constraints, instead of the reduced sets used by Leurent.
As a result, we are able to build complex non-linear differential characteristics for reduced versions of the hash function Skein. We present several characteristics for use in various attack scenarios; this results in attacks with a relatively low complexity, in relatively strong settings. In particular, we show practical free-start and semi-free-start collision attacks for 20 rounds and 12 rounds of Skein-256, respectively.
To the best of our knowledge, these are the first examples of complex differential trails built for pure ARX designs. We believe this is an important work to assess the security of ARX designs against differential cryptanalysis.

[article] [slides]

Cryptanalysis of WIDEA

FSE 2013, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Cryptanalysis, block cipher, hash function, truncated differential, IDEA, WIDEA, HIDEA

Abstract:

WIDEA is a family of block ciphers designed by Junod and Macchetti in 2009 as an extension of IDEA to larger block sizes (256 and 512 bits for the main instances WIDEA-4 and WIDEA-8) and key sizes (512 and 1024 bits), with a focus on using them to design a hash function. WIDEA is based on the trusted IDEA design, and was expected to inherit its good security properties. WIDEA-w is composed of w parallel copies of the IDEA block cipher, with an MDS matrix to provide diffusion between them.
In this paper we present low complexity attacks on WIDEA based on truncated differentials. We show a distinguisher for the full WIDEA with complexity only 265, and we use the distinguisher in a key-recovery attack with complexity w·268. We also show a collision attack on WIDEA-8 if it is used to build a hash function using the Merkle-Damgård mode of operation.
The attacks exploit the parallel structure of WIDEA and the limited diffusion between the IDEA instances, using differential trails where the MDS diffusion layer is never active. In addition, we use structures of plaintext to reduce the data complexity.

[article] [slides]

Time-memory Trade-offs for Near-collisions

FSE 2013, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Hash function, near-collision, generic attacks, time-memory trade-off

Abstract:

In this work we consider generic algorithms to find near-collisions for a hash function. If we consider only hash computations, it is easy to compute a lower-bound for the complexity of near-collision algorithms, and to build a matching algorithm. However, this algorithm needs a lot of memory, and makes than 2n/2 memory accesses. Recently, several algorithms have been proposed without this memory requirement; they require more hash evaluations, but the attack is actually more practical. They can be divided in two main categories: some are based on truncation, and some are based on covering codes. In this paper, we give a new insight to the generic complexity of a near-collision attack. First, we consider time-memory trade-offs for truncation-based algorithms. For a practical implementation, it seems reasonable to assume that some memory is available and we show that taking advantage of this memory can significantly reduce the complexity. Second, we show a new method combining truncation and covering codes. The new algorithm is always at least as good as the previous works, and often gives a significant improvement. We illustrate our results by giving a 10-near collision for MD5: our algorithm has a complexity of 245.4 using 1TB of memory while the best previous algorithm required 252.5 computations.

[article] [slides]

Analysis of Differential Attacks in ARX Constructions

Asiacrypt 2012, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Symmetric ciphers, hash functions, ARX, generalized characteristics, differential attacks, boomerang attacks

See also:

ARXtools

Abstract:

In this paper, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger; we introduce new multi-bit constraints to describe differential characteristics in ARX designs more accurately, and quartet constraints to analyze boomerang attacks. We also describe how to propagate those constraints; this can be used either to assist manual construction of a differential characteristic, or to extract more information from an already built characteristic. We show that our new constraints are more precise than what was used in previous works, and can detect more cases of incompatibility.
We have developed a set of tools for this analysis of ARX primitives based on this set of constraints. In the hope that this will be useful to other cryptanalysts, our tools are publicly available.
As a first application, we show that several published attacks are in fact invalid because the differential characteristics cannot be satisfied. This highlights the importance of verifying differential attacks more thoroughly.

[article] [slides]

Cryptanalysis of the “Kindle” Cipher

SAC 2012, Alex Biryukov, Gaëtan Leurent, Arnab Roy

Download:

paper slides

Keywords:

Cryptanalysis, stream cipher, hash function, Pukall Cipher, PC1, PSCHF, MobiPocket, Amazon Kindle, e-book

Abstract:

In this paper we study a 128-bit-key cipher called PC1 which is used as part of the DRM system of the Amazon Kindle e-book reader. This is the first academic cryptanalysis of this cipher and it shows that PC1 is a very weak stream cipher, and can be practically broken in a known-plaintext and even in a ciphertext-only scenario.
A hash function based on this cipher has also been proposed and is implemented in the binary editor WinHex. We show that this hash function is also vulnerable to a practical attack, which can produce meaningful collisions or second pre-images.

[article]

Narrow-Bicliques: Cryptanalysis of Full IDEA

Eurocrypt 2012, Dmitry Khovratovich, Gaëtan Leurent, Christian Rechberger (©IACR)

Download:

paper

Keywords:

block ciphers, bicliques, meet-in-the-middle, IDEA, key recovery

Abstract:

Compared to most other symmetric primitives, the block cipher IDEA proved to be resistant to any cryptanalysis attempt since its design more than 20 years ago. Out of its 8.5 rounds, only up to 5 initial rounds or 6 middle rounds could be attacked. In this paper we apply and extend the recently introduced biclique framework to IDEA and improve various key recovery attacks on reduced-round versions. Moreover, for the first time we describe an approach to noticeably speed-up key-recovery for the full 8.5 round IDEA.
On the conceptual side, for the first time we show that the biclique approach to block cipher cryptanalysis can not only be used to obtain results on more rounds, but can also improve time complexities and data complexities. For this we consider e.g. the first 5 rounds of IDEA, and show better time complexities than the many earlier cryptanalysis attempts. All this is achieved by the amplified independent-bicliques technique: the recently introduced independent-biclique approach amplified with ways to use available degrees of freedom as known from hash cryptanalysis. We do not need to assume to know or be able to chose relations between multiple keys. Our cryptanalysis is of high computational complexity, and does not threaten the practical use of IDEA in any way, yet the techniques are practically verified to a large extent.

[article] [slides]

Boomerang Attacks on Hash Function using Auxiliary Differentials

CT-RSA 2012, Gaëtan Leurent, Arnab Roy

Download:

paper slides

Keywords:

Hash function, SHA-3 competition, chosen-key, Skein, Threefish, boomerang attack, higher order differential, zero-sum

Abstract:

In this paper we study boomerang attacks in the chosen-key setting. This is particularly relevant to hash function analysis, since many boomerang attacks have been described against ARX-based designs.
We present a new way to combine message modifications, or auxiliary differentials, with the boomerang attack. We show that under some conditions, we can combine three independent paths instead of two for the classical boomerang attack. Our main result is obtained by applying this technique to round-reduced Skein-256, for which we show a distinguisher on the keyed permutation with complexity only 257, and a distinguisher on the compression function with complexity 2114. We also discuss application of the technique to Skein-512 and show some problems with the paths used in previous boomerang analysis of Skein-512.

[article] [slides]

Practical Near-Collisions on the Compression Function of BMW

FSE 2011, Gaëtan Leurent, Søren S. Thomsen (©IACR)

Download:

paper slides

Keywords:

Hash function, SHA-3, BMW, ARX, cryptanalysis, partial-collision, near-collision

Abstract:

Blue Midnight Wish (BMW) is one of the fastest SHA-3 candidates in the second round of the competition. In this paper we study the compression function of BMW and we obtain practical partial collisions in the case of BMW-256: we show a pair of inputs so that 300 pre-specified bits of the outputs collide (out of 512 bits). Our attack requires about 232 evaluations of the compression function. The attack can also be considered as a near-collision attack: we give an input pair with only 122 active bits in the output, while generic algorithm would require 255 operations for the same result.
A similar attack can be developed for BMW-512, which will gives message pairs with around 600 colliding bits for a cost of 264. This analysis does not affect the security of the iterated hash function, but it shows that the compression function is far from ideal.
We also describe some tools for the analysis of systems of additions and xors, which are used in our attack, and which can be useful for the analysis of other systems.

[article] [slides]

Security Analysis of SIMD

SAC 2010, Charles Bouillaguet, Gaëtan Leurent, Pierre-Alain Fouque

Download:

paper slides

Keywords:

Hash function, SHA-3, SIMD, Distinguisher, Security proof

Abstract:

This paper provides three important contributions to the security analysis of SIMD.
First, we show a new free-start distinguisher based on symmetry relations. It allows to distinguish the compression function of SIMD from a random function with a single evaluation. However, we also show that this property is very hard to exploit to mount any attack on the hash function because of the mode of operation of the compression function. Essentially, if one can build a pair of symmetric states, the symmetry property can only be triggered once.
Then, we show that a class of free-start distinguishers is not a threat to wide-pipe hash functions. In particular, this means that our distinguisher has a minimal impact on the security of the SIMD hash function, and we still have a security proof for the iterated hash function. Intuitively, the reason why this distinguisher does not weaken the function is that getting into a symmetric state is about as hard as finding a preimage.
Finally, we study differential path in SIMD, and give an upper bound on the probability of related key differential paths. Our bound is in the order of 2-n/2 using very weak assumptions. Resistance to related key attacks is often overlooked, but it is very important for hash function designs.

[article] [slides]

Attacks on Hash Functions based on Generalized Feistel: Application to Reduced-Round Lesamnta and SHAvite-3₅₁₂

SAC 2010, Charles Bouillaguet, Orr Dunkelman, Gaëtan Leurent, Pierre-Alain Fouque

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, Generalized Feistel, Cancellation property, SHA-3, Lesamnta, SHAvite-3

Abstract:

In this paper we study the strength of two hash functions which are based on Generalized Feistels. We describe a new kind of attack based on a cancellation property in the round function. This new technique allows to efficiently use the degrees of freedom available to attack a hash function. Using the cancellation property, we can avoid the non-linear parts of the round function, at the expense of some freedom degrees.
Our attacks are mostly independent of the round function in use, and can be applied to similar hash functions which share the same structure but have different round functions. We start with a 22-round generic attack on the structure of Lesamnta, and adapt it to the actual round function to attack 24-round Lesamnta (the full function has 32 rounds). We follow with an attack on 9-round SHAvite-3₅₁₂ which also works for the tweaked version of SHAvite-3₅₁₂.

[article]

Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite-3₅₁₂

Africacrypt 2010, Praveen Gauravaram, Gaëtan Leurent, Florian Mendel, María Naya-Plasencia, Thomas Peyrin, Christian Rechberger, Martin Schläffer

Download:

paper

Keywords:

Cryptanalysis, Hash function, SHA-3, SHAvite-3

Abstract:

In this paper, we analyze the SHAvite-3₅₁₂ hash function, as proposed and tweaked for round 2 of the SHA-3 competition. We present cryptanalytic results on 10 out of 14 rounds of the hash function SHAvite-3₅₁₂, and on the full 14 round compression function of SHAvite-3₅₁₂. We show a second preimage attack on the hash function reduced to 10 rounds with a complexity of 2⁴⁹⁷ compression function evaluations and 2¹⁶ memory. For the full 14-round compression function, we give a chosen counter, chosen salt preimage attack with 2³⁸⁴ compression function evaluations and 2¹²⁸ memory (or complexity 2⁴⁴⁸ without memory), and a collision attack with 2¹⁹² compression function evaluations and 2¹²⁸ memory.

[article]

Cryptanalysis of ESSENCE

FSE 2010, María Naya-Plasencia, Andrea Röck, Jean-Philippe Aumasson, Yann Laigle-Chapuy, Gaëtan Leurent, Willi Meier, Thomas Peyrin (©IACR)

Download:

paper

Keywords:

Cryptanalysis, Hash function, SHA-3, ESSENCE

Abstract:

ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design. Previous analysis showed some non-randomness in the compression function which could not be extended to an attack on the hash function and ESSENCE remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanalysis. This paper disproves this claim, showing that advanced techniques can be used to significantly reduce the cost of such attacks: using a manually found differential characteristic and an advanced search algorithm, we obtain collision attacks on the full ESSENCE-256 and ESSENCE-512, with respective complexities 2⁶⁸ and 2¹³⁵. In addition, we show how to use these attacks to forge valid (message, MAC) pairs for HMAC-ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision.

[article] [slides]

Another Look at the Complementation Property

FSE 2010, Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Cryptanalysis, DES complementation property, Self-similarity, Hash function, SHA-3, Lesamnta, ESSENCE, Block cipher, XTEA, PURE

Abstract:

In this paper we present a collection of attacks based on generalisations of the complementation property of DES. We find symmetry relations in the key schedule and in the actual rounds, and we use these symmetries to build distinguishers for any number of rounds when the relation is deterministic. This can be seen as a generalisation of the complementation property of DES or of slide/related-key attacks, using different kinds of relations. We further explore these properties, and show that if the relations have easily found fixed points, a new kind of attacks can be applied.
Our main result is a self-similarity property on the SHA-3 candidate Lesamnta, which gives a very surprising result on its compression function. Despite the use of round constants which were designed to thwart any such attack, we show a distinguisher on the full compression function which needs only one query, and works for any number of rounds. We also show how to use this self-similarity property to find collisions on the full compression function of Lesamnta much faster than generic attacks. The main reason for this is the structure found in these round constants, which introduce an interesting and unexpected symmetry relation. This casts some doubt on the use of highly structured constants, as it is the case in many designs, including the AES and several SHA-3 candidates. Our second main contribution is a new related-key differential attack on round-reduced versions of the XTEA block-cipher. We exploit the weakness of the key-schedule to suggest an iterative related-key differential. It can be used to recover the secret key faster than exhaustive search using two related keys on 37 rounds. We then isolate a big class of weak keys for which we can attack 51 rounds out of the cipher's 64 rounds. We also apply our techniques to ESSENCE and PURE.

[article] [slides]

Practical Key Recovery Attack against Secret-IV Edon-R

CT-RSA 2010, Gaëtan Leurent

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, Edon-R, MAC

Abstract:

select a new hashing standard. Edon-R was one of the fastest candidates in the first round of the competition. In this paper we study the security of Edon-R, and we show that using Edon-R as a MAC with the secret- IV or secret-prefix construction is unsafe. We present a practical attack in the case of Edon-R256, which requires 32 queries, 230 computations, negligible memory, and a precomputation of 252 . The main part of our attack can also be adapted to the tweaked Edon-R in the same settings: it does not yield a key-recovery attack, but it allows a selective forgery attack.
This does not directly contradict the security claims of Edon-R or the NIST requirements for SHA-3, since the recommended mode to build a MAC is HMAC. However, we believe that it shows a major weakness in the design.

[article]

Practical Electromagnetic Template Attack on HMAC

CHES 2009, Pierre-Alain Fouque, Gaëtan Leurent, Denis Réal, Frédéric Valette (©IACR)

Download:

paper

Keywords:

Side-channel cryptanalysis, HMAC, SHA-1

Abstract:

channel attack against HMAC. Our attack assumes the presence of a side channel that reveals the Hamming distance of some registers. After a profiling phase in which the adversary has access to a device and can configure it, the attack recovers the secret key by monitoring a single execution of HMAC-SHA1. The secret key can be recovered using a "template attack" with a computation of about 232 3κ compression functions, where κ is the number of 32-bit words of the key. Finally, we show that our attack can also be used to break the secrecy of network protocols usually implemented on embedded devices.
We have performed experiments using a NIOS processor executed on a Field Programmable Gate Array (FPGA) to confirm the leakage model. We hope that our results shed some light on the requirements in term of side channel attack for the future SHA-3 function.

[article]

How Risky is the Random Oracle Model?

Crypto 2009, Gaëtan Leurent, Phong Nguyen (©IACR)

Download:

paper

Keywords:

Random Oracle Model (ROM), instantiation, hash function

Abstract:

RSA-FDH and many other schemes secure in the Random- Oracle Model (ROM) require a hash function with output size larger than standard sizes. We show that the random-oracle instantiations proposed in the literature for such cases are weaker than a random oracle, including the proposals by Bellare and Rogaway from 1993 and 1996, and the ones implicit in IEEE P1363 and PKCS standards: for instance, we obtain a practical preimage attack on BR93 for 1024-bit digests (with complexity less than 2³⁰). Next, we study the security impact of hash function defects for ROM signatures. As an extreme case, we note that any hash collision would suffice to disclose the master key in the ID-based cryptosystem by Boneh et al. from FOCS'07, and the secret key in the Rabin-Williams signature for which Bernstein proved tight security at EUROCRYPT'08. We also remark that collisions can be found as a precomputation for any instantiation of the ROM, and this violates the security definition of the scheme in the standard model. Hence, this gives an example of a natural scheme that is proven secure in the ROM but that in insecure for any instantiation by a single function. Interestingly, for both of these schemes, a slight modification can prevent these attacks, while preserving the ROM security result. We give evidence that in the case of RSA and Rabin/Rabin-Williams, an appropriate PSS padding is more robust than all other paddings known.

[article]

Practical key-recovery attack against APOP, an MD5 based challenge-response authentication

International Journal of Applied Cryptography (IJACT), 2008, Gaëtan Leurent

Download:

paper

Keywords:

Cryptanalysis, Hash function, message modifications, APOP authentication, POP3

Abstract:

Hash functions are used in many cryptographic constructions under various assumptions, and the practical impact of collision attacks is often unclear. In this paper, we show how collisions can be used to recover part of the password used in the APOP authentication protocol.
Since we actually need a little more than mere collisions, we look into the details of MD5 collisions. In Wang's attack, message modifications allow to deterministically satisfy certain sufficient conditions to find collisions efficiently. Unfortunately, message modifications significantly change the messages and one has little control over the colliding blocks. In this paper, we show how to choose small parts of the colliding messages, which will allow to build the APOP attack.
This shows that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat.

[article] [slides]

MD4 is not One-Way

FSE 2008, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, MD4, preimage

Abstract:

MD4 is a hash function introduced by Rivest in 1990. It is still used in some contexts, and the most commonly used hash functions (MD5, SHA-1, SHA-2) are based on the design principles of MD4. MD4 has been extensively studied and very efficient collision attacks are known, but it is still believed to be a one-way function.
In this paper we show a partial pseudo-preimage attack on the compression function of MD4, using some ideas from previous cryptanalysis of MD4. We can choose 64 bits of the output for the cost of 2³² compression function computations (the remaining bits are randomly chosen by the preimage algorithm).
This gives a preimage attack on the compression function of MD4 with complexity 2⁹⁶, and we extend it to an attack on the full MD4 with complexity 2¹⁰². As far as we know this is the first preimage attack on a member of the MD4 family.

[article] [slides]

Cryptanalysis of a Hash Function Based on Quasi-Cyclic Codes

CT-RSA 2008, Pierre-Alain Fouque, Gaëtan Leurent

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, Fast Syndrome Based (FSB), IFSB

Abstract:

At the ECRYPT Hash Workshop 2007, Finiasz, Gaborit, and Sendrier pro- posed an improved version of a previous provably secure syndrome-based hash function. The main innovation of the new design is the use of a quasi-cyclic code in order to have a shorter description and to lower the memory usage.
In this paper, we look at the security implications of using a quasi-cyclic code. We show that this very rich structure can be used to build a highly efficient attack: with most parameters, our collision attack is faster than the compression function!

[article] [slides]

Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5

Crypto 2007, Pierre-Alain Fouque, Gaëtan Leurent, Phong Nguyen (©IACR)

Keywords:

Cryptanalysis, Hash function, HMAC, MAC, MD4, MD5

Abstract:

At Crypto'06, Bellare presented new security proofs for HMAC and NMAC, under the assumption that the underlying compression function is a pseudo-random function family. Conversely, at Asiacrypt'06, Contini and Yin used collision techniques to obtain forgery and partial key-recovery attacks on HMAC and NMAC instantiated with MD4, MD5, SHA-0 and reduced SHA-1. In this paper, we present the first full key-recovery attacks on NMAC and HMAC instantiated with a real-life hash function, namely MD4. Our main result is an attack on HMAC/NMAC-MD4 which recovers the full MAC secret key after roughly 2⁸⁸ MAC queries and 2⁹⁵ MD4 computations. We also extend the partial key-recovery Contini-Yin attack on NMAC-MD5 (in the related- key setting) to a full key-recovery attack. The attacks are based on generalizations of collision attacks to recover a secret IV, using new differential paths for MD4.

[article] [slides]

Automatic Search of Differential Path in MD4

ECRYPT Hash Workshop 2007, Pierre-Alain Fouque, Gaëtan Leurent, Phong Nguyen

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, MD4, Differential paths

Abstract:

In 2004, Wang et al. obtained breakthrough collision attacks on the main hash functions from the MD4 family. The attacks are differential attacks in which one closely follows the inner steps of the underlying compression function, based on a so-called differential path. It is generally assumed that such differential paths were found “by hand”. In this paper, we present an algorithm which automatically finds suitable differential paths, in the case of MD4. As a first application, we obtain new differential paths for MD4, which improve upon previously known MD4 differential paths. This algorithm could be used to find new differential paths, and to build new attacks against MD4.

[article] [slides]

Message Freedom in MD4 and MD5 Collisions: Application to APOP

FSE 2007, Gaëtan Leurent (©IACR)

Download:

paper slides

Keywords:

Cryptanalysis, Hash function, message modifications, APOP authentication, POP3

Abstract:

In Wang's attack, message modifications allow to deterministically satisfy certain sufficient conditions to find collisions efficiently. Unfortunately, message modifications significantly change the messages and one has little control over the colliding blocks. In this paper, we show how to choose some part of the messages which collide. Consequently, we break a security countermeasure proposed by Szydlo and Yin at CT-RSA'06, where they added a fixed padding at the end of each block.
Furthermore, we also apply this technique to partially recover the passwords in the Authentication Protocol of the Post Office Protocol (POP). This shows that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat.

[article]

An Analysis of the XSL Algorithm

Asiacrypt 2005, Carlos Cid, Gaëtan Leurent (©IACR)

Download:

paper

Keywords:

Cryptanalysis, AES, Algebraic attacks, XL, XSL, Linearization

Abstract:

The XSL “algorithm” is a method for solving systems of multivariate polynomial equations based on the linearization method. It was proposed in 2002 as a dedicated method for exploiting the structure of some types of block ciphers, for example the AES and Serpent. Since its proposal, the potential for algebraic attacks against the AES has been the source of much speculation. Although it has attracted a lot of attention from the cryptographic community, currently very little is known about the effectiveness of the XSL algorithm. In this paper we present an analysis of the XSL algorithm, by giving a more concise description of the method and studying it from a more systematic point of view. We present strong evidence that, in its current form, the XSL algorithm does not provide an efficient method for solving the AES system of equations.

Invited talks

[slides]

Cryptanalysis beyond primitives

FSE 2024, Gaëtan Leurent

Download:

slides

Keywords:

Abstract:

Cryptography relies on both primitives and modes of operations to ensure security. Traditionally, the security of primitives is studied through cryptanalysis, while the security of modes of operations is assessed through security proofs. However, in this talk, we propose to explore cryptanalysis techniques beyond primitives to uncover potential vulnerabilities in modes of operations and protocols.
Generic attacks complement the results obtained with security proofs, and give a better understanding of the overall security. In some cases, advanced generic attacks show surprising results, such as key-recovery attacks with birthday complexity, attacks that get more efficient on more complex constructions, or devastating attacks in the quantum setting. We will also consider the practical impact of some cryptanalysis results, by leveraging generic attacks to break concrete protocols.

Breaking Symmetric Cryptosystems using Quantum Period Finding

TCCM CACR 2016, Gaëtan Leurent

Keywords:

Post-quantum cryptography, symmetric cryptography, quantum attacks, block ciphers, modes of operation, slide attack

Abstract:

Due to Shor's algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it.
We study applications of a quantum procedure called Simon's algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon's algorithm: finding a collision requires Ω(2n/2) queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model.
We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenti- cated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF.
Second, we show that Simon's algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.

[slides] [abstract]

Generic Attacks against MAC algorithms

SAC 2015, Gaëtan Leurent

Download:

slides abstract

Keywords:

MAC, Generic Atacks, CBC-MAC, PMAC, HMAC

Abstract:

In this talk we discuss the security of some classical MAC constructions based on block ciphers or hash functions. These construction are widely deployed, and their security has been proven based on idealized behavior of the underlying primitive.
We focus on generic attacks and how the relate to the complexity bounds of the security proof. The two approaches are complementary: generic attacks yields upper bounds on the security of a mode, and security proofs yield a lower bound. While there is usually an attack matching the proof, we point out that this only the case for the strongest security notion, resistance against existential forgery. For weaker security notions, there is usually a gap between the best attacks and the complexity bound of the proof, and the security loss when the bounds are exceeded is not well understood. Actually, constructions with similar security proofs can have very different security levels beyond the bound.
In particular, we will discuss recent attacks against hash-based MACs, showing that state recovery and universal forgery attacks require less than $2^n$ work.

New Generic attacks on Hash-based MACs

TCCM CACR 2013, Gaëtan Leurent

Keywords:

NMAC, HMAC, hash function, distinguishing-H, key recovery, GOST

Abstract:

In this talk we study the security of hash-based MAC algorithms (such as HMAC and NMAC) above the birthday bound. Up to the birthday bound, HMAC and NMAC are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an n-bit MAC is built from a hash function with a l-bit state (l > n), there is a well-known existential forgery attack with complexity 2^l/2. However, the remaining security after 2^l/2 computations is not well understood. In particular it is widely assumed that if the underlying hash function is sound, then a generic universal forgery attack should still require 2^n computations and some distinguishing (e.g. distinguishing-H but not distinguishing-R) and state-recovery attacks should still require 2^l computations. In this work, we show that above the birthday bound, hash-based MACs offer significantly less security than previously believed. Our main result is a generic distinguishing-H and state-recovery attack against hash-based MACs with a complexity of only 2^l/2. In addition, we show a key-recovery attack with complexity 2^3l/4 against HMAC used with a hash functions with an internal checksum, such as GOST. This surprising result shows that the use of a checksum might actually weaken a hash function when used in a MAC.

PhD and HDR Thesis

[thesis] [slides]

Symmetric Cryptanalysis Beyond Primitives

HDR Thesis, 2024, Université Sorbonne Université

Download:

thesis slides

[thesis] [slides]

Design and Analysis of Hash Functions

PhD Thesis, 2010, École Normale Supérieure (ENS) & Université Paris 7

Download:

thesis slides

Keywords:

Symmetric cryptography, Hash functions, design, cryptanalysis

Abstract:

Hash functions are essential primitives in modern cryptography, used in many protocols and standards.
My work has been organized around the SHA-3 competition, launched by NIST to select a new hash function standard. In the first part, I studied the new attacks of Wang et al. against MD4 and MD5. I describe some improvements of these attacks, and new applications to higher-level constructions. In the second part, I describe a new hash function, SIMD, which has been submitted to NIST for the SHA-3 competition. The design of SIMD follows ideas from the MD4 family, but I used my knowledge of this family to make it resistant to most attacks. Finally, in the third part, I describe new attacks against SHA-3 candidates. I give new attacks techniques which are general enough to apply to several hash functions or block ciphers. Thus, this thesis covers the two main realms of symmetric cryptography: design and analysis.

Position Paper

[paper]

A Proposal for Reorganizing the IACR Publications Landscape