International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Gaëtan Leurent

Publications

Year
Venue
Title
2021
EUROCRYPT
2021
TOSC
2021
EUROCRYPT
New Representations of the AES Key Schedule
Gaëtan Leurent Clara Pernot
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 220GB), 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 sub-keys and information from the last sub-keys, in order to reconstruct the corresponding master keys. In particular we improve previous impossible-differential attacks against AES-128.
2021
ASIACRYPT
Quantum Linearization Attacks
Recent works have shown that quantum period-finding can be used to break many popular constructions (some block ciphers such as Even-Mansour, multiple MACs and AEs...) in the superposition query model. So far, all the constructions broken exhibited a strong algebraic structure, which enables to craft a periodic function of a single input block. The recovery of the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes. In this paper, we introduce the \emph{quantum linearization attack}, a new way of using Simon's algorithm to target MACs in the superposition query model. Specifically, we use inputs of multiple blocks as an interface to a function hiding a linear structure. The recovery of this structure allows to perform forgeries. We also present some variants of this attack that use other quantum algorithms, which are much less common in quantum symmetric cryptanalysis: Deutsch's, Bernstein-Vazirani's, and Shor's. To the best of our knowledge, this is the first time these algorithms have been used in quantum forgery or key-recovery attacks. Our attack breaks many parallelizable MACs such as {\sf LightMac}, {\sf PMAC}, and numerous variants with (classical) beyond-birthday-bound security ({\sf LightMAC+}, {\sf PMAC+}) or using tweakable block ciphers ({\sf ZMAC}). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task.
2021
ASIACRYPT
Clustering Effect in Simon and Simeck
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 Simeck-64, leaving only two rounds of security margin, and an attack against 45-round Simon-96/144, reducing the security margin from 16 rounds to 9 rounds.
2021
ASIACRYPT
QCB: Efficient Quantum-secure Authenticated Encryption
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.
2020
TOSC
2020
TOSC
2020
TOSC
Cryptanalysis of Forkciphers 📺
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).
2020
CRYPTO
Out of Oddity -- New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems 📺
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.
2020
TOSC
Saturnin: a suite of lightweight symmetric algorithms for post-quantum security 📺
The cryptographic algorithms needed to ensure the security of our communications have a cost. For devices with little computing power, whose number is expected to grow significantly with the spread of the Internet of Things (IoT), this cost can be a problem. A simple answer to this problem is a compromise on the security level: through a weaker round function or a smaller number of rounds, the security level can be decreased in order to cheapen the implementation of the cipher. At the same time, quantum computers are expected to disrupt the state of the art in cryptography in the near future. For public-key cryptography, the NIST has organized a dedicated process to standardize new algorithms. The impact of quantum computing is harder to assess in the symmetric case but its study is an active research area.In this paper, we specify a new block cipher, Saturnin, and its usage in different modes to provide hashing and authenticated encryption in such a way that we can rigorously argue its security in the post-quantum setting. Its security analysis follows naturally from that of the AES, while our use of components that are easily implemented in a bitsliced fashion ensures a low cost for our primitives. Our aim is to provide a new lightweight suite of algorithms that performs well on small devices, in particular micro-controllers, while providing a high security level even in the presence of quantum computers. Saturnin is a 256-bit block cipher with a 256-bit key and an additional 9-bit parameter for domain separation. Using it, we built two authenticated ciphers and a hash function.• Saturnin-CTR-Cascade is an authenticated cipher using the counter mode and a separate MAC. It requires two passes over the data but its implementation does not require the inverse block cipher.• Saturnin-Short is an authenticated cipher intended for messages with a length strictly smaller than 128 bits which uses only one call to Saturnin to providenconfidentiality and integrity.• Saturnin-Hash is a 256-bit hash function. In this paper, we specify this suite of algorithms and argue about their security in both the classical and the post-quantum setting. https://project.inria.fr/saturnin/
2020
TOSC
Spook: Sponge-Based Leakage-Resistant Authenticated Encryption with a Masked Tweakable Block Cipher 📺
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.
2020
ASIACRYPT
New results on Gimli: full-permutation distinguishers and improved collisions 📺
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.
2019
EUROCRYPT
From Collisions to Chosen-Prefix Collisions Application to Full SHA-1 📺
Gaëtan Leurent Thomas Peyrin
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 break of concrete protocols, because the adversary has a limited control over the colliding messages. On the other hand, chosen-prefix collisions have been shown to break certificates (by creating a rogue CA) and many internet protocols (TLS, SSH, IPsec).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 SHA-1, and obtain improved attacks. In particular, we have a chosen-prefix collision attack against SHA-1 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 SHA-1 (estimated as $$2^{64.7}$$). This represents yet another warning that industries and users have to move away from using SHA-1 as soon as possible.
2019
CRYPTO
Low-Memory Attacks Against Two-Round Even-Mansour Using the 3-XOR Problem 📺
Gaëtan Leurent Ferdinand Sibleyras
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 $$\ell = 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^{\ell /3}$$ queries, and the best known algorithms require around $$2^{\ell /2}/\ell $$ 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 $$\lambda n$$ known plaintext/ciphertext pairs, for some constant $$0< \lambda < 1$$, $$2^n/\lambda n$$ time, and $$2^{\lambda n}$$ memory. For instance, with $$n=64$$ and $$\lambda = 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 $$\mathcal {O}(2^{n} \ln ^2 n/n^2)$$, improving the previous asymptotic complexity of $$\mathcal {O}(2^n/n)$$, using a variant of the 3-SUM algorithm of Baran, Demaine, and Pǎtraşcu.
2019
JOFC
Generic Attacks on Hash Combiners
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) combiner $$ \mathcal {H}_1(M) \oplus \mathcal {H}_2(M) $$ H 1 ( M ) ⊕ H 2 ( M ) and the concatenation combiner $$ \mathcal {H}_1(M) \Vert \mathcal {H}_2(M) $$ H 1 ( M ) ‖ H 2 ( 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 $$\mathcal {H}_2(\mathcal {H}_1(IV, M), M)$$ H 2 ( H 1 ( I V , M ) , M ) and the Zipper hash $$\mathcal {H}_2(\mathcal {H}_1(IV, M), \overleftarrow{M})$$ H 2 ( H 1 ( I V , M ) , M ← ) , where $$\overleftarrow{M}$$ 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. We summarize our attacks and their computational complexities (ignoring the polynomial factors) as follows: 1. Several generic preimage attacks on the XOR combiner: A first attack with a best-case complexity of $$ 2^{5n/6} $$ 2 5 n / 6 obtained for messages of length $$ 2^{n/3} $$ 2 n / 3 . It relies on a novel technical tool named interchange structure. It is applicable for combiners whose underlying hash functions follow the Merkle–Damgård construction or the HAIFA framework. A second attack with a best-case complexity of $$ 2^{2n/3} $$ 2 2 n / 3 obtained for messages of length $$ 2^{n/2} $$ 2 n / 2 . It exploits properties of functional graphs of random mappings. It achieves a significant improvement over the first attack but is only applicable when the underlying hash functions use the Merkle–Damgård construction. An improvement upon the second attack with a best-case complexity of $$ 2^{5n/8} $$ 2 5 n / 8 obtained for messages of length $$ 2^{5n/8} $$ 2 5 n / 8 . It further exploits properties of functional graphs of random mappings and uses longer messages. These attacks show a rather surprising result: regarding preimage resistance, the sum of two n -bit narrow-pipe hash functions following the considered constructions can never provide n -bit security. 2. A generic second-preimage attack on the concatenation combiner of two Merkle–Damgård hash functions. This attack finds second preimages faster than $$ 2^n $$ 2 n for challenges longer than $$ 2^{2n/7} $$ 2 2 n / 7 and has a best-case complexity of $$ 2^{3n/4} $$ 2 3 n / 4 obtained for challenges of length $$ 2^{3n/4} $$ 2 3 n / 4 . It also exploits properties of functional graphs of random mappings. 3. The first generic second-preimage attack on the Zipper hash with underlying hash functions following the Merkle–Damgård construction. The best-case complexity is $$ 2^{3n/5} $$ 2 3 n / 5 , obtained for challenge messages of length $$ 2^{2n/5} $$ 2 2 n / 5 . 4. An improved generic second-preimage attack on Hash-Twice with underlying hash functions following the Merkle–Damgård construction. The best-case complexity is $$ 2^{13n/22} $$ 2 13 n / 22 , obtained for challenge messages of length $$ 2^{13n/22} $$ 2 13 n / 22 . The last three attacks show that regarding second-preimage resistance, the concatenation and cascade of two n -bit narrow-pipe Merkle–Damgård hash functions do not provide much more security than that can be provided by a single n -bit hash function. Our main technical contributions include the following: 1. The interchange structure, which enables simultaneously controlling the behaviours of two hash computations sharing the same input. 2. The simultaneous expandable message, which is a set of messages of length covering a whole appropriate range and being multi-collision for both of the underlying hash functions. 3. New ways to exploit the properties of functional graphs of random mappings generated by fixing the message block input to the underlying compression functions.
2018
EUROCRYPT
2018
CRYPTO
Generic Attacks Against Beyond-Birthday-Bound MACs 📺
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 $$\mathcal {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 $$\tilde{\mathcal {O}}(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.
2018
ASIACRYPT
Cryptanalysis of MORUS
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.
2018
TOSC
MDS Matrices with Lightweight Circuits 📺
Sébastien Duval Gaëtan Leurent
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, where the implementation can reuse some intermediate variables. In particular, Kranz et al. used optimization tools to find a 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.
2016
EUROCRYPT
2016
CRYPTO
2016
FSE
2016
TOSC
Quantum Differential and Linear Cryptanalysis
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.
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EUROCRYPT
2015
ASIACRYPT
2014
CRYPTO
2014
EPRINT
2014
EPRINT
2014
CHES
2014
FSE
2014
FSE
2013
CRYPTO
2013
ASIACRYPT
2013
FSE
2013
FSE
Cryptanalysis of WIDEA 📺
Gaëtan Leurent
2012
EUROCRYPT
2012
ASIACRYPT
2011
FSE
2010
EPRINT
Security Analysis of SIMD
In this paper we study the security of the SHA-3 candidate SIMD. We first 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. In the second part, we show that a class of free-start distinguishers is not a threat to the wide-pipe hash functions. In particular, this means that our distinguisher has a minimal impact on the security of the hash function, and we still have a security proof for the SIMD 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, in the third part 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.
2010
FSE
2010
FSE
2009
CHES
2009
CRYPTO
2008
FSE
MD4 is Not One-Way
Gaëtan Leurent
2008
EPRINT
How Risky is the Random-Oracle Model?
Gaëtan Leurent Phong Q. Nguyen
RSA-FDH and many other schemes provably secure in the Random-Oracle Model (ROM) require a cryptographic hash function whose output size does not match any of the standard hash functions. We show that the random-oracle instantiations proposed in the literature for such general cases are insecure, including the two historical instantiations proposed by Bellare and Rogaway themselves in their seminal papers from ACM~CCS~'93 and EUROCRYPT~'96: for instance, for 1024-bit digests, we present a $2^{68}$ preimage attack on BR93 and a $2^{106}$ collision attack on BR96. This leads us to study the potential security impact of such defects. While one might think that a hash collision may at worst give rise to an existential forgery on a signature scheme, we show that for several (real-world) schemes secure in the ROM, collisions or slight hash function defects can have much more dramatic consequences, namely key-recovery attacks. For instance, we point out that a hash collision discloses the master key in the Boneh-Gentry-Hamburg identity-based cryptosystem from FOCS~'07, and the secret key in the Rabin-Williams signature scheme for which Bernstein proved tight security at EUROCRYPT~'08. This problem can be fixed, but still, such schemes, as well as the Rabin-Williams variant implemented in the IEEE P1363 standard, strongly require that the hash function is immune to malleability variants of collision attacks, which does not hold for the BR93 instantiation. Our results suggest an additional criterion to compare schemes secure in the ROM: assessing the risks by carefully studying the impact of potential flaws in the random-oracle instantiation. In this light, RSA-PSS seems more robust than other RSA signatures secure in the ROM.
2007
CRYPTO
2007
FSE
2007
EPRINT
Automatic Search of Differential Path in MD4
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.
2005
ASIACRYPT

Program Committees

FSE 2020 (Program chair)
CHES 2019
FSE 2019
Asiacrypt 2018
FSE 2018
FSE 2017
Crypto 2017
FSE 2016
FSE 2015
Eurocrypt 2013

Coauthors

Tomer Ashur (1)
Jean-Philippe Aumasson (1)
Abhishek Banerjee (1)
Zhenzhen Bao (1)
Augustin Bariant (1)
Christof Beierle (1)
Davide Bellizia (1)
Francesco Berti (1)
Tim Beyne (1)
Ritam Bhaumik (1)
Alex Biryukov (1)
Xavier Bonnetain (2)
Charles Bouillaguet (2)
Christina Boura (1)
Hai Brenner (2)
Olivier Bronchain (1)
Anne Canteaut (3)
Gaëtan Cassiers (1)
André Chailloux (1)
Avik Chakraborti (1)
Carlos Cid (1)
Nicolas David (1)
Patrick Derbez (1)
Itai Dinur (6)
Orr Dunkelman (1)
Sébastien Duval (4)
Maria Eichlseder (2)
Pierre-Alain Fouque (5)
Thomas Fuhr (1)
Lubos Gaspar (1)
Vincent Grosso (1)
Chun Guo (1)
Jian Guo (1)
Antonio Flórez Gutiérrez (1)
Marc Kaplan (2)
Dmitry Khovratovich (1)
Yann Laigle-Chapuy (1)
Martin M. Lauridsen (1)
Gregor Leander (3)
Anthony Leverrier (2)
Itamar Levi (1)
Willi Meier (1)
Brice Minaud (1)
Charles Momin (1)
Mridul Nandi (1)
María Naya-Plasencia (8)
Phong Q. Nguyen (4)
Goutam Paul (1)
Chris Peikert (1)
Olivier Pereira (1)
Clara Pernot (2)
Léo Perrin (4)
Thomas Peters (1)
Thomas Peyrin (4)
Thomas Pornin (1)
Håvard Raddum (1)
Denis Réal (1)
Christian Rechberger (1)
Andrea Röck (1)
Alon Rosen (2)
Yann Rotella (2)
David Rupprecht (1)
Dhiman Saha (1)
Yu Sasaki (3)
André Schrottenloher (5)
Yannick Seurin (1)
Ferdinand Sibleyras (4)
Hadi Soleimany (1)
François-Xavier Standaert (3)
Lukas Stennes (1)
Valentin Suder (2)
Søren S. Thomsen (1)
Yosuke Todo (1)
Balazs Udvarhelyi (1)
Frédéric Valette (1)
Kerem Varici (1)
Benoît Viguier (1)
Lei Wang (5)
Friedrich Wiemer (2)