Algorithmic Cryptanalysis Blog

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.

Yesterday, at the rump session, I presented new results (with Stefan Lucks) on the search for multi-collisions on generic functions. The preprint is now available on eprint and the slides are here: AfricaCrypt Rump Slides.

This morning, I gave an invited talk on the blockwise security of modes of operation. The slides are here:  Africacrypt Invited Talk Slides. More information about this can be found in Chapter 7, from page 238 of Algorithmic Cryptanalysis.

I noticed earlier today that Algorithmic Cryptanalysis is now available on Amazon.com.

I am currently setting up the companion website with the additional material announced in the book. Everything is not yet online, so do not hesitate to come back and check the site content.

I will be glad to get reader’s feedback on the book and website. You can contact me using the “Contact author” menu item.