Differential Computation Analysis: Hiding your White-Box Designs is Not Enough

Joppe W. Bos – NXP Semiconductors
10 Feb 2016 @ 15.00, room INF 211

Although all current scientific white-box approaches of standardized cryptographic primitives are broken, there is still a large number of companies which sell “secure” white-box products. After an introduction to the concept of white-box cryptography, I will introduce a new approach to assess the security of white-box implementations which requires neither knowledge about the look-up tables used nor any reverse engineering effort. This differential computation analysis (DCA) attack is the software counterpart of the differential power analysis attack as applied by the cryptographic hardware community.

We developed plugins to widely available dynamic binary instrumentation frameworks to produce software execution traces which contain information about the memory addresses being accessed. We show how DCA can extract the secret key from all publicly (non-commercial) available white-box programs implementing standardized cryptography by analyzing these traces to identify secret-key dependent correlations.

Recovering Short Generators of Principal Ideals in Cyclotomic Rings

Léo Ducas – CWI
14 Apr 2015 @ 15.00, room INF 211

A handful of recent cryptographic proposals rely on the conjectured hardness of the following problem in cyclotomic rings: given a basis of an ideal that is guaranteed to have a “rather short” generator, find such
a generator.  In the past year, Bernstein and Campbell-Groves-Shepherd have sketched potential attacks against this problem.  Most notably, the latter authors claimed a quantum polynomial-time algorithm (alternatively, replacing the quantum component with an algorithm of Biasse and Fieker would yield a classical subexponential-time algorithm).  A key claim of Campbell et al. is that one step of their algorithm – namely, decoding the log-unit lattice of the ring to recover a short generator from an arbitrary one – is efficient (whereas the standard approach takes exponential time).  However, very few convincing details were provided to substantiate this claim, and as a result it has met with some skepticism.

In this work, we remedy the situation by giving a rigorous theoretical and practical confirmation that the log-unit lattice in indeed efficiently decodable, in cyclotomics of prime-power index.  The proof consists of two main technical contributions: the first is a geometrical analysis, using tools from analytic number theory, of the canonical generators of the group of cyclotomic units.  The second shows that for a wide class of typical distributions of the short generator, a standard lattice-decoding algorithm can recover it, given any generator.

Joint work with Ronald Cramer, Chris Peikert and Oded Regev.

Sieving for shortest lattice vectors using locality-sensitive hashing

Thijs Laarhoven – TU/e
14 Apr 2015 @ 16.00, room INF 211

Most lattice-based cryptographic primitives rely on the shortest vector problem (SVP) on lattices being hard.  To assess the computational hardness of SVP and breaking these schemes, one commonly relies on the estimated time complexity of enumeration for solving SVP.  In 2001 the breakthrough work of Ajtai et al. showed that SVP can actually be solved faster in high dimensions, using a technique called sieving. Although this technique seemed impractical at first, various improvements have since shown that sieving may be competitive with enumeration after all.  In this talk we will look at recent advances in sieving using a technique called locality-sensitive hashing.

Discrete Logarithms in Binary Fields and “128-bit Secure” Supersingular Curves

Jens Zumbrägel – TU Dresden
24 Nov 2014 @ 14.00, room INF 211

The Discrete Logarithm Problem in finite fields of small characteristic underwent a dramatic development in 2013, with the (heuristic) asymptotic complexity dropping from subexponential to quasi-polynomial time.  However, the question remained whether the algorithmic progress practically affects the concrete security of any discrete log based cryptosystem proposed in the literature.

We introduce a new field representation and efficient general descent principles which make the recent techniques far more practical.  In particular in the context of pairings, at the “128-bit security level” we show a weakness of supersingular elliptic curves over GF(2^1223) and report a total break of a supersingular genus two curve over GF(2^367).  Inspired by this work, we also present a new descent
strategy, which is more widely applicable and better suited to theoretical analysis.

This is joint work with Robert Granger and Thorsten Kleinjung.

Designing a lattice reduction library, and Deep Insertion experiments

Felix Fontein – Uni Zürich
21 Nov 2013 @ 15.00, room INF 211

The main goals I had in mind when writing a lattice reduction library were:
  * efficiency,
  * clear and easy to understand codebase,
  * one algorithm should be at only one place (no repetition of slightly different variants all over the code),
  * simplicity of using it, while allowing a wide spectrum of options,
  * possibility to retrieve intermediate results to avoid data loss when crashes appear after weeks of running.

In this talk, I want to explain why I had these goals in mind, how these compare to previously existing lattice reduction libraries, and most importantly, how I tried to achieve them all at once, and in which regards I was successful and what I learned from that.

I will also compare these goals to other libraries, most importantly NTL and fplll, and will explain why I didn’t tried to improve them but instead started from scratch.

Finally, I will discuss experiments on Deep Insertions for LLL and BKZ aimed at helping to improve the choice of reduction parameters.  I will present preliminary results and some surprising and not so surprising practical conclusions for every-day lattice reduction.  The last part is joint work with Urs Wagner.

Discrete logarithms in small/medium characteristic finite fields

Antoine Joux – UPMC, University Paris 6
14 Nov 2013 @ 16.15, room BC 420

In this talk, we present a new algorithm for the computation of discrete logarithms in finite fields of small characteristic.  This algorithm combines several previously existing techniques with a few additional ingredients.

Among those, the most notable is a new method for generating multiplicative relations with a “systematic side” by composing the polynomial (X^q-X) with homographies.

This results in an algorithm of quasi-polynomial complexity for discrete logs in GF(q^k) where k is close to q.

Biography: Antoine is the holder of the Cryptology Chair of the Foundation of the UPMC (Université Pierre et Marie Curie – Paris 6) and a senior security expert at CryptoExperts.  He was formerly a part-time professor at the Universit of Versailles and the head of the scientific division of the french security agency DCSSI (now known as ANSSI).  Together with Dan Boneh and Matt Franklin, he received the 2013 Gödel prize for his work on pairing-based cryptography.

The Special Number Field Sieve in F_{p^n} – Application to pairing-friendly constructions

Cecile Pierrot – UPMC, University Paris 6
14 Nov 2013 @ 14.00, room INF 211

The security of pairing-based cryptographic schemes relies on two distinct hard problems: the discrete logarithm problem on an elliptic curve and the discrete logarithm problem in a rather large finite field.  To obtain efficient schemes, it is important to understand these two problems in details in order to balance their respective complexities.

In this talk, we revisit this issue and present an extension of the Special Number Field Sieve (SNFS) for the whole range of applicability of the Number Field Sieve (NFS), namely for finite fields with medium to high characteristic.  Our improved algorithm compute discrete logarithms in F_{p^n}, where p, the characteristic of the field, has an adequate sparse representation. In particular, our variant of SNFS applies to discrete logarithm in finite fields related to pairing-friendly constructions.