International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Marc Stevens

Affiliation: CWI, Netherlands

Publications

Year
Venue
Title
2019
EUROCRYPT
The General Sieve Kernel and New Records in Lattice Reduction 📺
We propose the General Sieve Kernel (G6K, pronounced / e.si.ka/), an abstract stateful machine supporting a wide variety of lattice reduction strategies based on sieving algorithms. Using the basic instruction set of this abstract stateful machine, we first give concise formulations of previous sieving strategies from the literature and then propose new ones. We then also give a light variant of BKZ exploiting the features of our abstract stateful machine. This encapsulates several recent suggestions (Ducas at Eurocrypt 2018; Laarhoven and Mariano at PQCrypto 2018) to move beyond treating sieving as a blackbox SVP oracle and to utilise strong lattice reduction as preprocessing for sieving. Furthermore, we propose new tricks to minimise the sieving computation required for a given reduction quality with mechanisms such as recycling vectors between sieves, on-the-fly lifting and flexible insertions akin to Deep LLL and recent variants of Random Sampling Reduction.Moreover, we provide a highly optimised, multi-threaded and tweakable implementation of this machine which we make open-source. We then illustrate the performance of this implementation of our sieving strategies by applying G6K to various lattice challenges. In particular, our approach allows us to solve previously unsolved instances of the Darmstadt SVP (151, 153, 155) and LWE (e.g. (75, 0.005)) challenges. Our solution for the SVP-151 challenge was found 400 times faster than the time reported for the SVP-150 challenge, the previous record. For exact-SVP, we observe a performance crossover between G6K and FPLLL’s state of the art implementation of enumeration at dimension 70.
2018
FSE
On breaking SHA-1
Marc Stevens
2017
CRYPTO
2017
TOSC
Refined Probability of Differential Characteristics Including Dependency Between Multiple Rounds
The current paper studies the probability of differential characteristics for an unkeyed (or with a fixed key) construction. Most notably, it focuses on the gap between two probabilities of differential characteristics: probability with independent S-box assumption, pind, and exact probability, pexact. It turns out that pexact is larger than pind in Feistel network with some S-box based inner function. The mechanism of this gap is then theoretically analyzed. The gap is derived from interaction of S-boxes in three rounds, and the gap depends on the size and choice of the S-box. In particular the gap can never be zero when the S-box is bigger than six bits. To demonstrate the power of this improvement, a related-key differential characteristic is proposed against a lightweight block cipher RoadRunneR. For the 128-bit key version, pind of 2−48 is improved to pexact of 2−43. For the 80-bit key version, pind of 2−68 is improved to pexact of 2−62. The analysis is further extended to SPN with an almost-MDS binary matrix in the core primitive of the authenticated encryption scheme Minalpher: pind of 2−128 is improved to pexact of 2−96, which allows to extend the attack by two rounds.
2016
EUROCRYPT
2015
EPRINT
2015
EPRINT
2015
CRYPTO
2015
ASIACRYPT
2013
CRYPTO
2013
EUROCRYPT
2009
CRYPTO
2007
EUROCRYPT
2006
EPRINT
Fast Collision Attack on MD5
Marc Stevens
In this paper, we present an improved attack algorithm to find two-block collisions of the hash function MD5. The attack uses the same differential path of MD5 and the set of sufficient conditions that was presented by Wang et al. We present a new technique which allows us to deterministically fulfill restrictions to properly rotate the differentials in the first round. We will present a new algorithm to find the first block and we will use an algorithm of Klima to find the second block. To optimize the inner loop of these algorithms we will optimize the set of sufficient conditions. We also show that the initial value used for the attack has a large influence on the attack complexity. Therefore a recommendation is made for 2 conditions on the initial value of the attack to avoid very hard situations if one has some freedom in choosing this initial value. Our attack can be done in an average of about 1 minute (avg. complexity $2^{32.3}$) on a 3Ghz Pentium4 for these random recommended initial values. For arbitrary random initial values the average is about 5 minutes (avg. complexity $2^{34.1}$). With a reasonable probability a collision is found within mere seconds, allowing for instance an attack during the execution of a protocol.
2006
EPRINT
Target Collisions for MD5 and Colliding X.509 Certificates for Different Identities
We have shown how, at a cost of about $2^{52}$ calls to the MD5 compression function, for any two target messages $m_1$ and $m_2$, values $b_1$ and $b_2$ can be constructed such that the concatenated values $m_1\|b_1$ and $m_2\|b_2$ collide under MD5. Although the practical attack potential of this construction of \emph{target collisions} is limited, it is of greater concern than random collisions for MD5. In this note we sketch our construction. To illustrate its practicality, we present two MD5 based X.509 certificates with identical signatures but different public keys \emph{and} different Distinguished Name fields, whereas our previous construction of colliding X.509 certificates required identical name fields. We speculate on other possibilities for abusing target collisions.

Program Committees

FSE 2020
Eurocrypt 2019
FSE 2019
FSE 2018
Asiacrypt 2018
FSE 2017
FSE 2016
Crypto 2014
Asiacrypt 2014