Algorithmic Cryptanalysis Blog

This year, I have the pleasure to serve as FSE 2011 program chair. So far, the conference is running very nicely and I would like to thank all the people who contributed to this conference:

• The general co-chairs Lars Knudsen and Gregor Leander, together with all their team. Thanks for putting together this event and running everything so nicely.
• DTU (Technical University of Denmar) for hosting the event.
• The program committee members, for their work during the review process and for putting together such a nice program.
• The speakers and all the authors of submitted papers. Without their research, there would have been no FSE.
• The FSE steering committee and the IACR board.

Yesterday, I had the honor of presenting Takanori Isobe with the best paper award of the conference for his paper:

A single-key attack on the full GOST block cipher

Here are the slides I used during the presentation.

I addition to the contributed papers, FSE 2011 also features two invited talks:

• Willy Meier: Fast correlations attacks: Methods and countermeasures
• Ivan Damgård: The past, present and future of hash functions - a rehash of some old and new results

I am currently attending a meeting organized by Ecrypt. Since this meeting involves parallel working groups on several topics, giving an account of what is going on would be an impossible challenge. Instead, let us just say that the MAYA WG2 group featured a very interesting discussion of many hard problems in cryptography and possible algorithmic approaches to address these hard problem.

During the plenary session, held on September 8th, I gave a talk entitled Algorithmic Tools in Cryptanalysis (Slides here).

For the organizers, this year’s Eurocrypt must have been a huge challenge. Due to the France-Afrique summit, they had to relocate a large part of the conference from Nice to Monaco, with only a few months of delay. In any case, they did a great job and the conference is running very smoothly.

From a technical point of view, this Eurocrypt has also been very nice. One very active new trend concerns fully homomorphic schemes and the use of LWE (Learning with errors) and Lattices. In particular, Vinod Vaikuntanathan presented a new fully homorphic scheme based on learning with errors of the integers (from a paper with Marten van Dijk, Craig Gentry and Shai Halevi). I will not go into the details of their scheme, but I would like to present the underlying hard problem. In the simplest instantiation of their scheme, which was presented at the conference but slightly differ from the version described in the article, everything boils downs to the following problem:

Given an exact multiple of a prime p and many approximate multiples of p, recover the prime p.

Clearly, with two exact multiples, the problem is usually easy and it essentially suffices to compute a GCD to be done. With a single exact multiple, we have an approximate GCD problem (as introduced by Nick Howgrave-Graham at CaLC 2001). This problem can often be solved using lattice reduction. However, in the above homomorphic scheme, the parameters have been chosen to prevent this lattice reduction approach from working. More precisely, it would work without any trouble using a lattice reduction oracle but fails when LLL is used (due to the fact that LLL only finds an approximate shortest vector). More precisely, the chosen multiples (or approximate multiples) are huge compared to p.
In the proceedings, a more variant of the problem is used. In this variant, no exact multiple is available and only approximate multiples are given. In this case, no approach to solving the problem is currently known.

According to wikipedia, the first cryptographic scheme based on this approximate GCD problem was published by Levieil and Naccache at PKC 2008, in a paper entitled “Cryptographic Test Correction”.
On the cryptanalysis side of this lattice topic, Nicolas Gama presented his paper with Phong Nguyen and Oded Regev on a new analysis of pruned enumeration of short vectors in lattices. Remarkably, this allowed then to find the shortest non-zero vectors in lattices of dimension 110, a task which previously was completely out of practical range.

PS: For those who are interested, I attach my Eurocrypt 2010 slides of the knapsack algorithm developed with Nick Howgrave-Graham.

Yesterday in Remich, Serge Vaudenay gave a nice talk on related-key attacks on block ciphers and the validity of the claims based on these attacks. Note that Serge does not criticize that the existence of related-key attacks reflects undesirable properties of the target block cipher.

However, Serge wants to recall that in the related-key model, there exist very powerful generic attacks. Depending on the class of related-key attacks which are considered as acceptable, these generic attacks can be very different. When the model allows very strong related-key attacks, an adversary may recover the underlying key with a few queries. When only XOR related queries are allowed, a birthday-based attack is available and for a k-bit key, an attack with 2^(k/2) queries can run in time 2^(k/2).

As a consequence, evaluating the impact of related-key attacks on block cipher should be done with care. Most importantly, one should keep the generic attacks in mind and not oversymplify things. In particular, saying “this attack is faster than exhautive search, thus the cipher is broken” is often excessive.

Note that this talk caused many reactions and that this issue of related-key attacks is a hot and somewhat controversial topic.

I am currently attending the ESC 2010 seminar in Remich, Luxemburg.

Despite its name, this seminar not only features symmetric cryptography but also algorithms and public-key crypto related topics. Please, look-up the program, on the seminar wiki.

Yesterday, I presented a recent result with Nick Howgrave-Graham on the complexity of knapsack problems. This result consists in a new generic algorithm which beats Shamir-Schroeppel complexity (which had time O(2^(n/2)) and memory O(2^(n/4)), ignoring polynomial factors in n). For balanced knapsacks (where the solution contains as many 0s as 1s), the new method achieves time O(2^(0.311n)) and memory O(2^(0.256n)). See the slides for more details.

Here are the slides from my talk on 3-collisions. During the talk, I mentionned that the parallel version of the algorithm for 3-collisions is essentially optimal, since its full cost is equal to N^(2/3) when N^(1/3) processors are available. I also indicated that according to Adi Shamir, the sequential algorithm can also be proved to be optimal under reasonable assumptions.

This Asiacrypt was very rich in terms of cryptanalytic results. One of my favorites is the paper by Mathias Herrmann and Alexander May about Blum-Blum-Shub and other power generators titled “Attacking power generators using unravelled linearization: When do we output too much?”. In particular, it also to breaks BBS as soon as half of the state bits are output at each round of the pseudo-random generator.

Asiacrypt started today in Tokyo:

For once, the rump session was held on monday. Among the various rump presentations, I was especially interested by the announce of “A practical-time attack on the encryption algorithm used in third generation telephony” by Orr Dunkelman, Nathan Keller and Adi Shamir. I am looking forward to the eprint version of this attack against Kasumi.

In the regular program for Monday, there was also a large number of interesting block cipher and hash function results.

Yesterday and today, in Bochum (Germany), a workshop on factoring is taking place.

The program from the workshop is available here.

A particularly notable talk was Striding Towards a New Subexponential Factoring Algorithm by Francesco Sica. It proposed a new idea for factoring based on analytic methods. According to the speaker, it could lead to a new L(1/2) factoring algorithm.

There was also a talk Clauss Schnorr called Average-Time Fast SVP and CVP Algorithms: Factoring Integers in Polynomial Time. This talk revisited the idea of factoring using Schnorr-Adleman method using a new heuristic for finding short vectors in lattices. At the present, this heuristic has not been implemented. The author also mentionned that the dimension of the involved lattices was so large that this factoring method would not become practical in the foreseable future.

During this workshop, I gave a talk about the cryptanalysis of Real-Nice using an homogeoneous Coppersmith method (paper to be included in Asiacrypt’2009). The slides are here.

Here is a first practical application of the new triple collision algorithm by Stefan Lucks and myself (see eprint). We choose to use a standard construction for a pseudo-random function, namely we consider:

F(x)=DES_K1(x) XOR DES_K2(x)   with K1=3322110077665544 (hexa), K2=3b2a19087f6e5d4c (hexa)

We have (everything in hexa):
F(d332b9ba5e5a7d4e)= F(51b8095db532afcc)= F(b084dc15dce042ab)= 33a3da242371fede

This can be easily tested using the DES calculator.

Note: For extra triple collisions, see the comment I left after the initial post.

Recently, a new bunch of articles applying Coppersmith’s small root algorithm to various factoring problems have been released.

Here are pointers to a few of those articles on the IACR eprint archive:

• Factoring unbalanced moduli with known bits by Eric Brier, David Naccache and Medhi Tibouchi
• The Fermat factorization method revisited by Robert Erra and Christophe Grenier
• Further results on implicit factoring in polynomial time by Santanu Sarkar and Subhamoy Maitra
• Fault attacks on RSA signatures with partially unknown messages by Jean-Sébastien Coron, J., Ilya Kizhvatov, David Naccache and Pascal Paillier

See also Cryptanalysis of RSA using the ratio of primes by Adderrahmane Nitaj in AfricaCrypt proceedings.