About a month ago annual Eurocrypt conference took place in Cologne, Germany. This is rather academic event (as most if not all events held by IACR) so it is not always easy to read its proceedings filled with formulas and theorems. Nonetheless there are usually couple of very interesting works presented at each such event. Let me tell you a little bit about this year’s highlights.

Particularly interesting for me (although not completely new) was work «ECM on Graphics Cards» by Daniel Bernstein and his group. They managed to adopt NVIDIA GPUs for factoring integers with Elliptic Curve Method (ECM). Although factoring can break some asymmetric cryptosystem (such as RSA), ECM itself cannot be applied in those cases because it is inefficient for large numbers (such as usually used in those cryptosystems). ECM is efficient for numbers of up to 150 bits or so while typical RSA key today is more than 1024 bits. Factoring moderately sized integers is done with Number Field Sieve algorithm (current record factorization for general numbers is 663 bits) which internally requires factoring of smaller numbers, and this is where faster ECM may help.

Same authors also presented some new results during Rump Session with further speedups on both CPU and GPU, but no corresponding paper or report have been published yet.

I’d like also to highlight two other presentations from Rump Session. First one is «Automatic Differential Path Searching for SHA-1» which sets new estimation on complexity of finding collisions for SHA-1 hash function. Authors claim they found way to find collisions with complexity of 252 (instead of previously best 263) which is a huge improvement. If they are correct, SHA-1 collisions are now well within reach of current technology. A detailed report should appear in Cryptology ePrint Archive soon.

Second one is «AES-256 is Not Ideal» and corresponding reports «Distinguisher and Related-Key Attack on the Full AES-256» and «Examples of differential multicollisions for 13 and 14 rounds of AES-256» in which authors present for first time in open literature a distinguisher and key recovery attack on full AES-256. Although complexities are quite high, this puts some questions to AES security.

Next major IACR event, CRYPTO 2009, will take place on August 16-20, 2009 at Santa Barbara, CA.