D. J. Bernstein
Hash functions and ciphers
Notes on the ECRYPT Stream Cipher Project (eSTREAM)

Why switch from AES to a new stream cipher?

AES was published under the name Rijndael in 1998. Refereed cryptanalytic papers in the next three years culminated in attacks taking time "only" 2^140 to break 7 rounds of 256-bit AES and "only" 2^204 (with a huge amount of memory) to break 8 rounds of 256-bit AES. Subsequent work made very little progress. (Related-key attacks can break more rounds but are not of concern in any properly designed cryptographic protocol.)

Consequently the community has a very high confidence level in the full 14 rounds of 256-bit AES. There is a quite considerable "security margin": 256-bit AES has several rounds beyond the minimum number of rounds needed to resist all known attacks. I wouldn't be surprised by another round being broken eventually, but I would be astonished by a successful 14-round attack.

There have been successful attacks on the originally recommended implementation strategy for AES software. For example, Osvik, Shamir, and Tromer used cache-timing attacks to steal AES keys from a Linux disk-encryption device. But this problem is avoided by other AES software implementation strategies, notably "bitslicing."

Why, then, should anyone be interested in an alternative to AES? In particular, why should anyone be interested in the new wave of stream ciphers considered by eSTREAM? Illustrative example: Why should anyone be interested in Salsa20 as an alternative to AES? (I'm using Salsa20 as my example because I'm most familiar with Salsa20; I'm the Salsa20 designer.)

The answer is simple: Salsa20 provides a much better speed-security profile than AES.

Salsa20 was published in 2005. Refereed cryptanalytic papers by Crowley (SASC 2006), Fischer, Meier, Berbain, Biasse, Robshaw (INDOCRYPT 2006), Tsunoo, Saito, Kubo, Suzaki, Nakashima (SASC 2007), and Aumasson, Fischer, Khazaei, Meier, Rechberger (FSE 2008) have culminated in attacks that take time "only" 2^151 to break 7 rounds of 256-bit Salsa20 and "only" 2^251 to break 8 rounds of 256-bit Salsa20. Perhaps there will be slight further improvements, but it's reasonable to conjecture that Salsa20 and AES reach security with about the same number of rounds.

I have even more confidence in the full 20 rounds of 256-bit Salsa20 than I have in the full 14 rounds of 256-bit AES. The eSTREAM committee (Babbage, De Canniere, Canteaut, Cid, Gilbert, Johansson, Parker, Preneel, Rijmen, Robshaw) thought that 20 rounds were overkill; in the final eSTREAM portfolio they recommended Salsa20 with just 12 rounds.

At the same time, 20 rounds of Salsa20 are considerably faster than 14 rounds of AES. On a Core 2, for example, Salsa20 runs at 3.93 cycles/byte for long streams (or 4.25 cycles/byte for 576-byte packets), while the fastest speed ever reported for AES is 9.2 cycles/byte---and that's for just 10 rounds of bitsliced AES-CTR for long streams, with worse performance for 14 rounds and much worse performance for 576-byte packets.

Suppose you're a user who can only afford 3 cycles/byte for cryptography on your Core 2. (This doesn't mean that you're encrypting and decrypting gigabytes of data per second; surely most of your computer's time is spent doing something with the decrypted data.) You can scale Salsa20 down to 12 rounds, 2.8 cycles/byte, and you still have a cipher that has solidly resisted years of attacks. In the same 3 cycles/byte you can afford at most 3 rounds of AES; those 3 rounds don't provide any security at all.

Suppose you have 10 cycles/byte to devote to cryptography. Does it make more sense to devote your cycles to 50 rounds of Salsa20, spending 2 cycles/byte stopping all known attacks and the remaining 8 cycles/byte being conservative, or to AES, spending 8 cycles/byte stopping all known attacks and the remaining 2 cycles/byte being conservative?

Suppose you have 1000 cycles/byte to devote to cryptography. Does it make more sense to join other people in using a cipher that's of interest both for high security and for high speed, or to stick to an older standard that's unusable in high-speed applications?

I've commented only on software speeds on a large CPU, but Salsa20 is also better than AES on small CPUs, on FPGAs, and in dedicated circuits.

Of course, before starting the eSTREAM project, ECRYPT carefully considered the question of what reasons, if any, a cryptographic user would have for switching away from AES. They identified two situations where AES was unsatisfactory; one of those situations was "software applications with high throughput requirements." All of the eSTREAM software submissions were required to achieve higher speeds than AES.