Thoughts on AES
I posted here in early June with some general-purpose cryptographic recommendations; one of my suggestions was to use 256-bit AES rather than 128-bit or 192-bit AES. Since then, a couple of new attacks which specifically target AES-256 have been announced; and Bruce Schneier has commented that "[T]he key schedule for AES-256 is very poor. I would recommend that people use AES-128 and not AES-256.". Despite this, I still recommend the use of AES-256 for encryption in software implementations where cryptographic keys are generated randomly.My reasoning for this is based on the nature of these attacks: They're both related-key attacks which exploit AES-256's key schedule. These break the notion of the "ideal block cipher" -- i.e., the notion that AES acts as an oracle mapping keys to random permutations -- and can be very bad if you allow an attacker to select a cryptographic key -- which is effectively how block ciphers get used to construct hash functions. I don't think it's a coincidence that related-key attacks are suddenly being found while NIST's SHA3 hash competition is running.
There are other situations where related-key attacks can be used. Some poorly designed protocols allow keys to be constructed in malleable ways (i.e., such that by fiddling with part of the protocol, a negotiated key can be modified in a predictable manner); and in smart cards and other hostile environments, it is possible for related-key attacks to be applied via the induction of faults.
However, for encrypting data in software on general-purpose systems using randomly-generated cryptographic keys -- which constitutes the vast majority of the situations where anyone reading this is ever likely to want to use AES -- none of these are relevant, and thus related-key attacks are not something which should be a major consideration. In contrast, side channel attacks are very real; and thus I believe that it is more important to provide a margin of safety in case some key bits are leaked via a side channel than it is to use a stronger key expansion function (such as AES-128 has and AES-256 lacks) which provides greater safety against related-key attacks.
Normally I would conclude by pointing out that attacks always get stronger and a small crack now can grow into a major break later -- but in this case I don't think such warnings are warranted. The AES key schedule -- especially the AES-256 key schedule -- have been known to be rather weak for many years, and the "natural" way that key schedules break is by inducing related-key attacks. If someone had found a way to translate a weakness in AES's key schedule into an attack other than a related-key attack, I'd be far more concerned; but as it is, there really isn't anything very surprising here.
Instead I'll end with a cautionary note: I haven't yet read the latest (Biryukov-Dunkelman-Keller-Khovratovich-Shamir) attack paper -- I'm just writing based on the abstract and Schneier's commentary. It is possible that they present a startling new attack method which can be leveraged to attack AES in other (more practical) ways. But I doubt it; after all, if you discovered a powerful new attack method, why would you demonstrate it by constructing a related-key attack on a cipher with a relatively puny key expansion function?