## CryptoDB

### Charles Bouillaguet

#### Publications

**Year**

**Venue**

**Title**

2020

TOSC

Practical seed-recovery for the PCG Pseudo-Random Number Generator
📺
Abstract

The Permuted Congruential Generators (PCG) are popular conventional (non-cryptographic) pseudo-random generators designed in 2014. They are used by default in the NumPy scientific computing package. Even though they are not of cryptographic strength, their designer stated that predicting their output should nevertheless be "challenging".In this article, we present a practical algorithm that recovers all the hidden parameters and reconstructs the successive internal states of the generator. This enables us to predict the next “random” numbers, and output the seeds of the generator. We have successfully executed the reconstruction algorithm using 512 bytes of challenge input; in the worst case, the process takes 20 000 CPU hours.This reconstruction algorithm makes use of cryptanalytic techniques, both symmetric and lattice-based. In particular, the most computationally expensive part is a guessand-determine procedure that solves about 252 instances of the Closest Vector Problem on a very small lattice.

2018

TOSC

Revisiting and Improving Algorithms for the 3XOR Problem
Abstract

The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. We study the 3XOR variant which is more cryptologically relevant. In this problem, the attacker is given black-box access to three random functions F,G and H and she has to find three inputs x, y and z such that F(x) ⊕ G(y) ⊕ H(z) = 0. The 3XOR problem is a difficult case of the more-general k-list birthday problem. Wagner’s celebrated k-list birthday algorithm, and the ones inspired by it, work by querying the functions more than strictly necessary from an information-theoretic point of view. This gives some leeway to target a solution of a specific form, at the expense of processing a huge amount of data. However, to handle such a huge amount of data can be very difficult in practice. This is why we first restricted our attention to solving the 3XOR problem for which the total number of queries to F, G and H is minimal. If they are n-bit random functions, it is possible to solve the problem with roughly

2014

EPRINT

2014

ASIACRYPT

2010

EPRINT

Fast Exhaustive Search for Polynomial Systems in $F_2$
Abstract

We analyze how fast we can solve general systems of multivariate
equations of various low degrees over \GF{2}; this is
a well known hard problem which is important both in itself and
as part of many types of algebraic cryptanalysis. Compared to the standard
exhaustive-search technique, our improved approach is more
efficient both asymptotically and practically.
We implemented several optimized versions of our techniques on CPUs and GPUs. Modern graphic cards allows our technique to run more than 10 times faster than the most powerful CPU available. Today, we can solve 48+ quadratic equations in 48 binary variables on a NVIDIA GTX 295 video card (USD 500) in 21 minutes.
With this level of performance, solving systems of equations supposed to ensure a security level of 64 bits turns out to be feasible in practice with a modest budget. This is a clear demonstration of the power of GPUs in solving many types of combinatorial and cryptanalytic problems.

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.

2009

EPRINT

On the Security of Iterated Hashing based on Forgery-resistant Compression Functions
Abstract

In this paper we re-examine the security notions suggested for hash
functions, with an emphasis on the delicate notion of second
preimage resistance. We start by showing that, in the random oracle
model, both Merkle-Damgaard and HAIFA achieve second preimage resistance beyond
the birthday bound, and actually up to the level of known generic
attacks, hence demonstrating the optimality of HAIFA in this respect.
We then try to distill a more elementary requirement out of the
compression function to get some insight on the properties it should
have to guarantee the second preimage resistance of its
iteration. We show that if the (keyed) compression function is a
secure FIL-MAC then the Merkle-Damgaard mode of iteration (or HAIFA) still
maintains the same level of second preimage resistance. We conclude
by showing that this ``new'' assumption (or security notion)
implies the recently introduced
Preimage-Awareness while ensuring all other classical security
notions for hash functions.

2007

EPRINT

Second Preimage Attacks on Dithered Hash Functions
Abstract

The goal of this paper is to analyze the security of dithered variants of the Merkle-Damgard mode of operation that use a third input to indicate the position of a block in the message to be hashed. These modes of operation for hash functions have been proposed to avoid some structural weaknesses of the Merkle-Damgard paradigm, e.g. that second preimages can be constructed in much less than $2^n$ work, as pointed out by Kelsey and Schneier. Among the modes of operation that use such a third input are Rivest's dithered hashing and Biham and Dunkelman's HAIFA proposal.
We propose several new second preimage attacks on the Merkle-Damgard mode of operation, which can also attack Rivest's dithered hash with almost the same complexity. When applied to Shoup's UOWHF, these attacks can be shown to be optimal since their complexity matches Shoup's security bound.

#### Coauthors

- Elena Andreeva (2)
- Alex Biryukov (2)
- Hsieh-Chung Chen (1)
- Chen-Mou Cheng (2)
- Tung Chou (2)
- Claire Delaplace (1)
- Patrick Derbez (1)
- Orr Dunkelman (3)
- Jean-Charles Faugère (1)
- Pierre-Alain Fouque (11)
- Jonathan J. Hoch (2)
- Antoine Joux (1)
- John Kelsey (2)
- Dmitry Khovratovich (2)
- Gaëtan Leurent (2)
- Gilles Macario-Rat (1)
- Florette Martinez (1)
- Ruben Niederhagen (2)
- Ludovic Perret (1)
- Julia Sauvage (1)
- Adi Shamir (5)
- Amandine Véber (1)
- Bo-Yin Yang (2)
- Sébastien Zimmer (3)