The Crypto Year in Review from Bart Preneel

Bart Preneel is a professor at the Katholieke Universiteit Leuven, in Brussels, and leader of COSIC, one of the largest security and cryptography research groups in Europe. This is the research group that produced Rijndael, which eventually became the AES. Preneel is a frequent speaker on security and cryptography, and in this post we will review a recent presentation on the topic of the Crypto Year in Review.

Preneel begins by observing that cryptographic research is alive and well, with over 600 papers published on the pre-print server of the IACR, amounting to over 10,000 pages of written research. Not all of these papers will be published, but it does give you some idea of the reading load to keep abreast of new ideas and developments.

His attention then turns to AES, which still remains secure despite the publication of several theoretical attacks. AES now runs at 110 MB/seconds in software, and Intel has announced direct hardware support beginning with its Westmere line of chips. Referring to the security of AES-256, Preneel states that for $5 billion USD, a key cracking device could be built to search a 120-bit key space that would take a billion years. This was about the same work required by the so-called Luxembourg Attack announced in June, which was the first attack against full AES-256 that saved significant time over exhaustive search (though a large amount of ciphertext is required).

Preneel calls this an academic weakness, since it relies on a related key attack which is hard to arrange in practice and can be easily avoided by making the AES key schedule more non-linear. The slide below shows that relationship between AES key size and the number of rounds. There are several feasible attacks when the number of rounds is 10 or less with small key sizes. The 2^{119} effort of the Luxembourg Attack is located far above what is considered practical.

Preneel then considers hash functions, the topic of his PhD thesis. He gives a benchmark slide showing the complexity of collision attacks against well-known hash functions, assuming a $100K USD funded adversary using special hardware (equivalent to 4 million PCs).

The downward trend of the graphs is suggestive of a meltdown for hash functions, with the worst implications for protocols and signatures yet to play out. The transition path to a better hashing standard via the SHA-3 hash contest of NIST in underway, and a new standard by will be selected by 2012. However Preneel is concerned that the design of SHA-3 will be based on state-of-the-art from 2008 – that is, all of the additional insights and learnings produced in the evaluation of the SHA-3 candidates will not be exploited until SHA-4.

It was a relatively quite year for public key cryptography, with no factoring records announced, but a lot of fretting over the coming upgrade of RSA-1024 keys in 2010 in compliance with US standards. Elliptic curves are rising in importance due to support from the NSA, and quantum computers remain a very long term threat to the security of public key systems.

There are some additional topics considered by Preneel, mainly around protocols and deploying cryptography. His summary is that 2009 was a relatively unexciting year on the surface but you may find interesting details when you look closer. Also, always remember that cryptography is a building block for information security, an essential block but far from the whole story.