Publications
Here is a full list of my publications:
- Conference and journal papers
- Invited talks
- Lectures
- Seminar talks
- PhD and HDR thesis
- Position Paper
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
See also:
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 x^{e} requires at least log2(e) sequential
multiplications.
In this work, we analyze the security of these algebraic VDF candidates.
In particular, we show that the latency of exponentiation can be reduced
using parallel computation, against the preliminary assumptions.
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:
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(2^{3c/4}) to O(2^{2c/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(2^{3n/7}).
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:
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 2^{52} 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 2^{46.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 2^{69.5} to 2^{67}.
Design of a Linear Layer Optimised for Bitsliced 32-bit Implementation
IACR Transactions on Symmetric Cryptology, 2024, Gaëtan Leurent, Clara Pernot
Download:
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.
Truncated Boomerang Attacks and Application to AES-Based Ciphers
Eurocrypt 2023, Augustin Bariant, Gaëtan Leurent (©IACR)
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 2^{97} and a key recovery attack with
complexity 2^{61}.
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 2^{83}(rather than 2^{103}). 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.
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:
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.
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:
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 2^{46}, 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 2^{31} encryptions (with experimental success rate of 75%). This is the first practical key recovery attack on a candidate of the NIST standartization project.
Quantum Linearization Attacks
Asiacrypt 2021, Xavier Bonnetain, Gaëtan Leurent, María Naya-Plasencia, André Schrottenloher (©IACR)
Download:
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.
Clustering Effect in Simon and Simeck
Asiacrypt 2021, Gaëtan Leurent, Clara Pernot, André Schrottenloher (©IACR)
Download:
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.
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:
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.
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:
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 2^{40} 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 2^{45.1} GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.
New Representations of the AES Key Schedule
Eurocrypt 2021, Gaëtan Leurent, Clara Pernot (©IACR)
Download:
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.
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:
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 2^{64}. We also provide a practical distinguisher on 23 out of the full 24 rounds of Gimli that has been implemented.
Next, we give (full state) collision and semi-free start collision attacks on Gimli-Hash, reaching, respectively, up to 12 and 18 rounds. On the practical side, we compute a collision on 8-round Gimli-Hash. In the quantum setting, these attacks reach 2 more rounds. Finally, we perform the first study of linear trails in Gimli, and we find a linear distinguisher on the full permutation.
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:
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.
Generic Attacks on Hash Combiners
Journal of Cryptology, Zhenzhen Bao, Itai Dinur, Jian Guo, Gaëtan Leurent, Lei Wang (©IACR)
Download:
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.
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:
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 2^{64}. We
also provide a practical distinguisher on 23 out of the full 24 rounds of
Gimli that has been implemented.
Next, we give (full state) collision and semi-free-start collision attacks on
Gimli-Hash, reaching respectively up to 12 and 18 rounds. On the practical
side, we compute a collision on 8-round Gimli-Hash. In the quantum
setting, these attacks reach 2 more rounds. Finally, we perform the first
study of linear trails in the permutation, and we propose
differential-linear cryptanalysis that reach up to 17 rounds of Gimli.
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:
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.
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:
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.
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:
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.
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:
Keywords:
SHA-1, Cryptanalysis, Chosen-prefix collision, HPC, GPU, PGP, GnuPG
Link:
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 2^{61.2} rather than 2^{64.7}, and chosen-prefix collisions with a complexity of 2^{63.4} rather than 2^{67.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).
Cryptanalysis of Forkciphers
IACR Transactions on Symmetric Cryptology, 2020, Augustin Bariant, Nicolas David, Gaëtan Leurent
Download:
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).
Universal Forgery Attack against GCM-RUP
CT-RSA 2020, Yanbin Li, Gaëtan Leurent, Meiqin Wang, Wei Wang, Guoyan Zhang, Yu Liu
Download:
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 2^{2n/3} operations, and many schemes do not have any known universal forgery attacks faster than 2^{n}. 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.
Lightweight MACs from Universal Hash Functions
CARDIS 2019, Sébastien Duval, Gaëtan Leurent
Download:
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 2^{64} 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.
Low-Memory Attacks against Two-Round Even-Mansour using the 3-XOR Problem
Crypto 2019, Gaëtan Leurent, Ferdinand Sibleyras (©IACR)
Download:
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
2^{2n/3} evaluations of the underlying permutations and
encryption, and the best known attacks have a complexity of roughly
2^{n}/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
2^{n}. From a practical standpoint, previous works with a
data and/or memory complexity close to 2^{n} 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, 2^{n}/λn 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(2^{n}ln^{2}n/n^{2}),
improving the previous asymptotic complexity of
O(2^{n}/n), using a variant of the 3-SUM algorithm
of Baran, Demaine, and Patrascu.
From Collisions to Chosen-Prefix Collisions — Application to Full SHA-1
Eurocrypt 2019, Gaëtan Leurent, Thomas Peyrin (©IACR)
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 2^{66.9} and 2^{69.4} (depending on assumptions
about the cost of finding near-collision blocks), while the best-known
attack has complexity 2^{77.1}. This is within a small factor of the
complexity of the classical collision attack on SHA1 (estimated as
2^{64.7}). This represents yet another warning that industries and users
have to move away from using SHA1 as soon as possible.
MDS Matrices with Lightweight Circuits
IACR Transactions on Symmetric Cryptology, 2018, Sébastien Duval, Gaëtan Leurent
Download:
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.
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:
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 2^{152} 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.
Generic Attacks against Beyond-Birthday-Bound MACs
Crypto 2018, Gaëtan Leurent, Mridul Nandi, Ferdinand Sibleyras (©IACR)
Download:
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 2^{2n/3} queries, but
there are no known attacks with less than 2^{n} 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(2^{3n/4}) queries, and how to build a
forgery attack with the same query complexity. The time complexity of
these attacks is above 2^{n}, 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
Õ(2^{6n/7}). As far as we know, this is the first
attack with complexity below 2^{n} 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.
The Missing Difference Problem, and its Applications to Counter Mode Encryption
Eurocrypt 2018, Gaëtan Leurent, Ferdinand Sibleyras (©IACR)
Download:
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
σ≪2^{n/2}, and a matching attack that can distinguish
plaintext/ciphertext pairs from random using about 2^{n/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
Õ(2^{n/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
Õ(2^{2n/3}).
Quantum Differential and Linear Cryptanalysis
IACR Transactions on Symmetric Cryptology, 2016, Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia
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.
Improved Generic Attacks Against Hash-based MACs and HAIFA (long version)
Algorithmica, 2016, Itai Dinur, Gaëtan Leurent
Download:
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 2^{4ℓ/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.
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
Keywords:
OpenVPN, TLS, HTTPS, CBC, collision attack
See also:
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 2^{32} 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.
Breaking Symmetric Cryptosystems using Quantum Period Finding
Crypto 2016, Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia (©IACR)
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 Ω(2^{n/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.
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:
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^{4ω}, 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 2^{72} 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 2^{72}. 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 2^{72} and 2^{137} respectively, while the security claim for 4 rounds are 128 bits and 256 bits of security.
Improved Differential-Linear Cryptanalysis of 7-round Chaskey with Partitioning
Eurocrypt 2016, Gaëtan Leurent (©IACR)
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 2^{78} data and time
(respectively 2^{35} for 6 rounds), the improved attack requires only 2^{48}
data and 2^{67} time (respectively 2^{25} data and 2^{29} 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.
Transcript Collision Attacks: Breaking Authentication in TLS, IKE, and SSH
NDSS 2016, Karthikeyan Bhargavan, Gaëtan Leurent
Download:
Keywords:
TLS, IKE, SSH, transcript collision
See also:
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.
Collision Attacks against CAESAR Candidates — Forgery and Key-Recovery against AEZ and Marble
Asiacrypt 2015, Thomas Fuhr, Gaëtan Leurent, Valentin Suder (©IACR)
Download:
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 2^{n/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.
Cryptanalysis of Feistel Networks with Secret Round Functions
SAC 2015, Alex Biryukov, Gaëtan Leurent, Léo Perrin
Download:
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(2^{2n}) encryptions
where n is the branch size. This attack can be used against 6- and
7-round Feistel Networks in time respectively O(2^{n2n-1+2n}) and
O(2^{n2n+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(2^{n23n/4}).
Our results are, to the best of our knowledge, the first recovery
attacks against generic 5-, 6- and 7-round Feistel Networks.
Differential Forgery Attack against LAC
SAC 2015, Gaëtan Leurent
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.
Construction of Lightweight S-Boxes using Feistel and MISTY Structures
SAC 2015, Anne Canteaut, Sébastien Duval, Gaëtan Leurent
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.
The Sum can be Weaker than Each Part
Eurocrypt 2015, Gaëtan Leurent, Wang Lei (©IACR)
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 H_{1}(M) ⊕ H_{2}(M) is one of the two
most classical combiners, together with the concatenation combiner H_{1}(M) ‖ H_{2}(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 H_{1} and H_{2} offer no security),
H_{1} ⊕ H_{2} 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 Õ(2^{5n/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.
FPGA implementations of SPRING
CHES 2014, Hai Brenner, Lubos Gaspar, Gaëtan Leurent, Alon Rosen, François-Xavier Standaert (©IACR)
Download:
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.
Improved Generic Attacks Against Hash-based MACs and HAIFA
Crypto 2014, Itai Dinur, Gaëtan Leurent (©IACR)
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 2^{4ℓ/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.
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:
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×2^{n/2} (namely 2^{266}) compression function evaluations for long messages. This complexity has to be compared with the expected 2^{512} 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.
Hardware Implementation and Side-Channel Analysis of Lapin
CT-RSA 2014, Lubos Gaspar, Gaëtan Leurent, François-Xavier Standard
Download:
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.
LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations
FSE 2014, Vincent Grosso, Gaëtan Leurent, François-Xavier Standaert, Kerem Varıcı (©IACR)
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.
SPRING: Fast Pseudorandom Functions from Rounded Ring Products
FSE 2014, Abhishek Banerjee, Hai Brenner, Gaëtan Leurent, Chris Peikert, Alon Rosen (©IACR)
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.
New Generic Attacks against Hash-based MACs
Asiacrypt 2013, Gaëtan Leurent, Thomas Peyrin, Lei Wang (©IACR)
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 2^{n} computations and some distinguishing
(e.g. distinguishing-H but not distinguishing-R) and state-recovery
attacks should also require 2^{ℓ} computations (or
2^{k} 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
Õ(2^{3ℓ/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.
Construction of Differential Characteristics in ARX Designs — Application to Skein
Crypto 2013, Gaëtan Leurent (©IACR)
Keywords:
Symmetric ciphers, hash functions, ARX, Skein, generalized characteristics, differential attacks
See also:
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 2^{32} 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.
Cryptanalysis of WIDEA
FSE 2013, Gaëtan Leurent (©IACR)
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 2^{65}, and we
use the distinguisher in a key-recovery attack with complexity
w·2^{68}. 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.
Time-memory Trade-offs for Near-collisions
FSE 2013, Gaëtan Leurent (©IACR)
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 2^{n/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 2^{45.4} using 1TB of memory while the best previous algorithm required 2^{52.5} computations.
Analysis of Differential Attacks in ARX Constructions
Asiacrypt 2012, Gaëtan Leurent (©IACR)
Keywords:
Symmetric ciphers, hash functions, ARX, generalized characteristics, differential attacks, boomerang attacks
See also:
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.
Cryptanalysis of the “Kindle” Cipher
SAC 2012, Alex Biryukov, Gaëtan Leurent, Arnab Roy
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.
Narrow-Bicliques: Cryptanalysis of Full IDEA
Eurocrypt 2012, Dmitry Khovratovich, Gaëtan Leurent, Christian Rechberger (©IACR)
Download:
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.
Boomerang Attacks on Hash Function using Auxiliary Differentials
CT-RSA 2012, Gaëtan Leurent, Arnab Roy
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 2^{57}, and a distinguisher on the compression function with
complexity 2^{114}. 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.
Practical Near-Collisions on the Compression Function of BMW
FSE 2011, Gaëtan Leurent, Søren S. Thomsen (©IACR)
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 2^{32} 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 2^{55} 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 2^{64}.
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.
Security Analysis of SIMD
SAC 2010, Charles Bouillaguet, Gaëtan Leurent, Pierre-Alain Fouque
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.
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
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₅₁₂.
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:
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.
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:
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.
Another Look at the Complementation Property
FSE 2010, Charles Bouillaguet, Orr Dunkelman, Pierre-Alain Fouque, Gaëtan Leurent (©IACR)
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.
Practical Key Recovery Attack against Secret-IV Edon-R
CT-RSA 2010, Gaëtan Leurent
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.
Practical Electromagnetic Template Attack on HMAC
CHES 2009, Pierre-Alain Fouque, Gaëtan Leurent, Denis Réal, Frédéric Valette (©IACR)
Download:
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 2^{32} 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.
How Risky is the Random Oracle Model?
Crypto 2009, Gaëtan Leurent, Phong Nguyen (©IACR)
Download:
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.
Practical key-recovery attack against APOP, an MD5 based challenge-response authentication
International Journal of Applied Cryptography (IJACT), 2008, Gaëtan Leurent
Download:
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.
MD4 is not One-Way
FSE 2008, Gaëtan Leurent (©IACR)
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.
Cryptanalysis of a Hash Function Based on Quasi-Cyclic Codes
CT-RSA 2008, Pierre-Alain Fouque, Gaëtan Leurent
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!
Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5
Crypto 2007, Pierre-Alain Fouque, Gaëtan Leurent, Phong Nguyen (©IACR)
Download:
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.
Automatic Search of Differential Path in MD4
ECRYPT Hash Workshop 2007, Pierre-Alain Fouque, Gaëtan Leurent, Phong Nguyen
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.
Message Freedom in MD4 and MD5 Collisions: Application to APOP
FSE 2007, Gaëtan Leurent (©IACR)
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.
An Analysis of the XSL Algorithm
Asiacrypt 2005, Carlos Cid, Gaëtan Leurent (©IACR)
Download:
Keywords:
Cryptanalysis, AES, Algebraic attacks, XL, XSL, Linearization
DOI:
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
Cryptanalysis beyond primitives
FSE 2024, Gaëtan Leurent
Download:
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
See also:
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 Ω(2^{n/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.
Generic Attacks against MAC algorithms
SAC 2015, Gaëtan Leurent
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
See also:
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.
Seminars and Workshops
- 2018
- Lightweight Crypto Day 2018, Tel Aviv, Israel
- Flexible Symmetric Cryptography Workshop, Lorentz Center, Leiden, Netherlands
- 2017
- Journées nationales pre-GDR Sécurité Informatique, Paris, France
- FOQUS Workshop, Paris, France
- La demi-heure de science, Inria Paris, France
- UVSQ, Versailles, France
- ESC 2017, Canach, Luxembourg
- 2016
- University of Oxford, Mathematical Institute Cryptography Seminar, Oxford, UK
- Dagstuhl Seminar 16021: Symmetric Cryptography, Dagstuhl, Germany
- 2015
- ASK 2015, Singapore
- ESC 2015, Clervaux, Luxembourg
- 2014
- Dagstuhl Seminar 14021: Symmetric Cryptography, Dagstuhl, Germany
- 2013
- Tsinghua University, Institute for Advanced Study Cryptology Seminar, Beijing, China
- ASK 2013, Weihai, China
- Séminaire CCA, Paris, France
- ESC 2013, Mondorf-les-Bains, Luxembourg
- 2012
- SKLOIS, Chinese Academy of Sciences, Beijing, China
- University Joseph Fourier, Grenoble, France
- Université Catholique de Louvain, Louvain-la-Neuve, Belgique
- IRMAR, Rennes, France
- 2011
- UVSQ, Versailles, France
- 2010
- ESC 2010, Remich, Luxembourg
PhD and HDR Thesis
Design and Analysis of Hash Functions
PhD Thesis, 2010, École Normale Supérieure (ENS) & Université Paris 7
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.