A month ago, the crypto-tea rooms were buzzing about the result in AES-256. Apparently, now weaker than AES-128. Can it be? Well, at first I thought this was impossible, because the cryptographers were not panicking, they were simply admiring the result. But the numbers that were reported indicated a drop in attack complexity to below AES-128, and the world was lapping it up.
So, a week back I got a chance to ask Dani Nagy of epointsystem.org, a real cryptographer, what the story is. Here it is. I've edited it for flow & style, but hopefully it unfolds like the original conversation:
On July 1, 2009, Bruce Schneier blogged about a related-key attack on the 192-bit and 256-bit versions of AES discovered by Alex Biryukov and Dmitry Khovratovich; the related key attack on the 256-bit version of AES exploits AES' somewhat simple key schedule and has a complexity of 2^119. This is a follow-up to an attack discovered earlier in 2009 by Alex Biryukov, Dmitry Khovratovich, and Ivica Nikolic, with a complexity of 2^96 for one out of every 2^35 keys.Another attack was blogged by Bruce Schneier on July 30, 2009 and published on August 3, 2009. This new attack, by Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, and Adi Shamir, is against AES-256 that uses only two related keys and 2^39 time to recover the complete 256-bit key of a 9-round version, or 2^45 time for a 10-round version with a stronger type of related subkey attack, or 2^70 time for a 11-round version. 256-bit AES uses 14 rounds, so these attacks aren't effective against full AES.
Dani: I agree with Scheier's assessment. Moreover, I think that AES-256 is no pareto-improvement over AES-128 (which is what I always use), and has all sorts of additional costs that are not justified. On the other hand, 32-bit optimized implementation of AES-128 are faster than RC4, which is absolutely amazing, IMHO.
Iang: OK. What I don't follow is, has the attack reduced the complexity of attacking AES-256 down from o(128) *OR* o(256) ? or alternatively, what is the brute force order of magnitude complexity of each of the algorithms?
Iang: The (3rd attack) abstract mentions:
However, AES-192 and AES-256 were recently shown to be breakable by attacks which require $2^{176}$ and $2^{119}$ time, respectively.
Dani: The abstract of the Biryukov-Khorvatovich paper does not give any quantitative description of the result about AES-128 ...
Abstract. In this paper we present two related-key attacks on the full AES. For AES-256 we show the first key recovery attack that works for all the keys and has complexity 2119 , while the recent attack by Biryukov-Khovratovich-Nikoli´c works for a weak key class and has higher complexity. The second attack is the first cryptanalysis of the full AES- 192. Both our attacks are boomerang attacks, which are based on the recent idea of finding local collisions in block ciphers and enhanced with the boomerang switching techniques to gain free rounds in the middle.
Dani: Oh, it's actually from 2^256 to 2^119 indeed for a first key recovery!
Iang: that's the implication ... a massive drop in orders of magnitude ... people are saying that with this attack, AES-256 is now weaker than AES-128 !
Dani: That's not entirely true, because it's also the space complexity (you need a database that long), while brute-forcing AES-128 has a space complexity of 1 key (the one being tried). For example, at my lab, we can manage a time complexity of 2^56, but we have nowhere near that amount of space.
Iang: hmmm.... so one part of the attack is down to 2^119 which space complexity is still 2^256?
Dani: No, the space complexity is also 2^119. But that's huge.
Dani: (the space complexity cannot be greater than time complexity, btw)
Iang: AES-128 has its 128 bit key ... so its space complexity is ... 2^128 ?
Dani: No, it's space complexity is 1.
Dani: You don't need pre-computed tables at all to brute-force it. When brute-forcing, you try one key at a time, 2^128 times.
Iang: Ah! (lightbulb) So AES-256 had time complexity of 2^256 and space complexity of 1, being the one brute forced key. Now, under this new attack, it has a time complexity of 2^119 and a space complexity of 2^119?
Dani: Yes, Time of 2^256 down to both time and space of 2^119.
Iang: Hmmm... so maybe that is why nobody reported the real comparison. So it is strictly not true to say AES-128 is now stronger than AES-256
Dani: It all depends on the time-space tradeoff one has to make. AES-128 is time-complexity of 2^128, and space complexity of 1. Is that stronger or weaker than 2^119 and 2^119?
Dani: But it seems true that AES-256 is strictly weaker than AES-192. The immediate practical implication is that it is even less worth bothering with larger AES keys than before. AES-128 is so much cheaper than the other two.
Iang: This explains the advice I have seen: "use AES-128"
Dani: But I would advise using AES-128 even without any weaknesses found. It is several times faster and more handy with both 32-bit and 64-bit architectures than the other two, without opening new practical avenues of attack even for the most powerful of adversaries.
Iang: Sounds good to me, especially as I chose it in my last crypto project :)
Iang: thanks for the clarification ... the real message was not easy to figure out from the press reports, and the abstract was cunningly written to cast in the best light, as always.
Dani: Thanks for the heads-up! Interesting developments and well-written papers.
Uhh, I think you've missed a key point. The new attack is a related-key attack. Related-key attacks are not relevant to most uses of AES. They're basically relevant only to: (a) people who use a block cipher improperly, (b) people who try to build a hash function out of a block cipher. (a) is poor practice anyway. So the main practical import of the new paper, in my opinion, is that AES is not a good basis for a hash function. But the smart money already suspected that already: people have been talking about how the AES key schedule is not the strongest part of the cipher since, oh, it was introduced.
It is NOT the case that AES-256 is only as good as a cipher with a 119-bit key. That's just not true.
And it is NOT the case that all it takes to break AES-256 is 2^119 steps of computation and 2^119 space. That's just not true, either. (You need the ability to mount related-key chosen-plaintext queries, which most well-designed systems do not permit.)
I think the practical import of this attack is much less than has been widely reported.
Posted by: David Wagner at September 6, 2009 11:54 PMDavid:
True, it must have been emphasized that we are looking at a related-key attack scenario. But look at WPA's key packing...
Posted by: Daniel Nagy at September 20, 2009 04:38 AM