## CryptoDB

### Gaëtan Leurent

#### Affiliation: INRIA

#### Publications

**Year**

**Venue**

**Title**

2019

EUROCRYPT

From Collisions to Chosen-Prefix Collisions Application to Full SHA-1
📺
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 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
📺
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 $$\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.

2018

CRYPTO

Generic Attacks Against Beyond-Birthday-Bound MACs
📺
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 $$\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
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.

2018

TOSC

MDS Matrices with Lightweight Circuits
📺
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, 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

TOSC

Quantum Differential and Linear Cryptanalysis
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.

2015

EPRINT

2015

ASIACRYPT

2010

EPRINT

Security Analysis of SIMD
Abstract

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.

2008

EPRINT

How Risky is the Random-Oracle Model?
Abstract

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

EPRINT

Automatic Search of Differential Path in MD4
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.

#### Program Committees

- FSE 2020
- 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)
- Alex Biryukov (1)
- Charles Bouillaguet (2)
- Christina Boura (1)
- Hai Brenner (2)
- Anne Canteaut (1)
- Avik Chakraborti (1)
- Carlos Cid (1)
- Itai Dinur (2)
- Orr Dunkelman (1)
- Sébastien Duval (2)
- Maria Eichlseder (1)
- Pierre-Alain Fouque (5)
- Thomas Fuhr (1)
- Lubos Gaspar (1)
- Vincent Grosso (1)
- Marc Kaplan (2)
- Dmitry Khovratovich (1)
- Yann Laigle-Chapuy (1)
- Martin M. Lauridsen (1)
- Anthony Leverrier (2)
- Willi Meier (1)
- Brice Minaud (1)
- Mridul Nandi (1)
- María Naya-Plasencia (3)
- Phong Q. Nguyen (4)
- Goutam Paul (1)
- Chris Peikert (1)
- Léo Perrin (1)
- Thomas Peyrin (4)
- Denis Réal (1)
- Christian Rechberger (1)
- Andrea Röck (1)
- Alon Rosen (2)
- Yann Rotella (1)
- Dhiman Saha (1)
- Yu Sasaki (1)
- Ferdinand Sibleyras (3)
- Hadi Soleimany (1)
- François-Xavier Standaert (2)
- Valentin Suder (2)
- Søren S. Thomsen (1)
- Frédéric Valette (1)
- Kerem Varici (1)
- Benoît Viguier (1)
- Lei Wang (4)