Is AES-256 weaker than 192 and 128 bit versions?

Question

From a paper via Schneier on Security's Another AES Attack (emphasis mine):

In the case of AES-128, there is no known attack which is faster than the 2¹²⁸ complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2¹⁷⁶ and 2¹¹⁹ time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems.

In this paper we describe several attacks which can break with practical complexity variants of AES-256 whose number of rounds are comparable to that of AES-128.

Is the implication here that AES-192 is stronger than AES-256? If so, in simple terms, how is that possible?

The attack exploits the fact that the key schedule for 256-bit version is pretty lousy -- something we pointed out in our 2000 paper -- but doesn't extend to AES with a 128-bit key.

Again, in simple terms, what does that mean?

In practice, does this mean I should drop AES-256 in favor of its 128-bit counterpart, like Schneier recommends in the comments?

That being said, the key schedule for AES-256 is very poor. I would recommend that people use AES-128 and not AES-256.

Answer 1

AES is an algorithm which is split into several internal rounds, and each round needs a specific 128-bit subkey (and an extra subkey is needed at the end). In an ideal world, the 11/13/15 subkeys would be generated from a strong, cryptographically secure PRNG, itself seeded with "the" key.

However, this world is not ideal, and the subkeys are generated through a process called the key schedule, which is very fast but not a decent PRNG at all; it is meant to offer sufficient security in the very specific context of producing subkeys for the AES only. The key schedule of AES was already known to be somewhat weak in some ways, allowing some exploitable structure to leak from one subkey to another, and this means related-key attacks.

Related-key attacks are not a problem when the encryption algorithm is used for encryption, because they work only when the victim uses several distinct keys, such that the differences (bitwise XOR) between the keys are known to the attacker and follow a very definite pattern. This is not the kind of thing which often occurs in protocols where AES is used; correspondingly, resistance to related-key attacks was not a design criterion for the AES competition. Related-key attacks can be troublesome when we try to reuse the block cipher as a building block for something else, e.g. a hash function. In the formal land of academic cryptanalysis, related-key attacks still count as worthwhile results, despite their lack of applicability to most practical scenarios.

The key schedules for AES-128, AES-192 and AES-256 are necessarily distinct from each other, since they must work over master keys of distinct sizes and produce distinct numbers of subkeys. It turns out that the version of the key schedule for AES-128 seems quite stronger than the key schedule for AES-256 when considering resistance to related-key attacks. It is actually quite logical: to build a related-key attack, the cryptographer must have some fine control over the subkeys, preferably as independently from each other as possible. It seems natural that the longer the source master key, the more control over subkeys the cryptanalyst gets -- because the related-key attack model is a model where the attacker can somehow "choose" the keys (or at least the differences between the keys). In the extreme case of a 1408-bit master key which would simply be split into eleven 128-bit keys, the cryptanalyst would have all the independent control he could wish for. Therefore, an academic weakness relatively to related-key attacks should, generically, increase with the key size.

The apparent paradox of the decrease in academic security when the key size increases highlights the contrived nature of the related-key attack model.

Answer 2

No. AES-256 is not weaker than AES-128. Absolutely not. And I disagree with the the advice that you should avoid AES-256.

The attack against AES-256 is a related-key attack, which is irrelevant to most real-world uses of AES-256. Related-key attacks only become relevant if you use the block cipher improperly, which is not something that you ought to be doing. (Second, the related-key attack against AES-256 is completely infeasible in practice. $2^{100}$ steps of computation: harrumph. Not gonna happen. It's way beyond the realm of feasibility, no matter how many supercomputers you buy. So, the attack against AES-256 is far from being the weakest point in the system. You shouldn't waste any energy worrying about it. I can just about guarantee there will be other weaker links in your system -- maybe the people, or maybe the software.) I realize the adage is that "attacks only get better", but it's rare for a related-key attack to somehow turn into a non-related-key attack.

So, basically, pay no attention to those claimed attacks on AES-256. They are a theoretical curiousity with little or no relevance to practice at the moment. Unfortunately, when people hear the sound bite ("new attack on AES-256!"), it's easy for them to get the wrong impression about how serious the attacks are. As cryptographers and security experts, I think it is important to explain why users probably don't need to worry.

Answer 3

This depends on security notions. On the one hand, considering related-key scenarios AES-256 is weaker then AES, since Biryukov and Khovratovich introduced a related key attack that has $2^{99.5}$ time and data complexity.

On the other hand AES-128 is weaker considering – the much more realistic – single-key scenarios. Here Bogdanov et al. introduced a key recovery attack against AES-128 with computational complexity $2^{126.1}$. Furthermore, they also found a recovery attack against AES-256 with computational complexity $2^{254.4}$.

Note, that related-key scenarios are very academical. Here, cryptographers assume that an adversary can 'partially control' some relations among keys used in the computation. Therefore, minor topics regarding the key scheduler can become a major drama.

I do believe that single-key scenarios do much better model the restriction of an real world adversary than related-key scenarios do. Therefore, I claim that AES-256 is still stronger then AES-128, at least when its comes to practical security. :-)

The consideration for the case "AES-256 vs. AES-192" is similar.

Answer 4

It might be worth pointing out that the Boomerang attack by Alex Biryukov and Dmitry Khovratovich requires four keys. Some of the older related key attacks required $2^{35}$ keys, which makes the attack much harder in practice. But forcing a target to rekey four times is quite realistic.

Answer 5

Asked and answered on server fault. https://serverfault.com/questions/51895/are-128-and-256bit-aes-encryption-considered-weak

The follow-up sentence to your bold point though is:

And for new applications I suggest that people don't use AES-256. AES-128 provides more than enough security margin for the forseeable future. But if you're already using AES-256, there's no reason to change. http://www.schneier.com/blog/archives/2009/07/another_new_aes.html

So given that, the answer to the question of

In practice, does this mean I should drop AES-256 in favor of its 128-bit counterpart, like Schneier recommends in the comments?

would be no. If you're currently using AES-256, and are not having performance issues from it, and have implemented the full 14 rounds (or more) ...keep using 256. If, however, this is a new project and there is no requirement to use 256, then use 128.

Compared to AES128 all this suggests is that attack methods can be done faster than a fully exhaustive search - whereas no known attack for AES-128 can be done faster than 2^128 time. The implication is that cracking none of them is practical, that AES-192 would still take longer to break than AES-128 and no known attack can break more than 11 of the rounds of full AES-256.

To answer your specific questions:

Is the implication here that AES-192 is stronger than AES-256? If so, in simple terms, how is that possible?

The implication is exactly that, not all algorithms are created equal and a longer key doesn't necessarily mean a stronger algorithm. A thread on that exists here: https://security.stackexchange.com/questions/14068/why-most-people-use-256-bit-encryption-instead-of-128-bit/19762#19762

The issue at hand for these AES standards are their key scheduling and vulnerability to related-key and known-distinguished-key cryptanalysis. There's not room for a simple answer that does these justice, but the long and short of it is that without a sufficient key scope (part of the key schedule), then observation of input-output data can be used to determine key values by comparing how different keys output the same set of data (or how one key outputs differing sets of data). Honestly the Wiki articles are pretty good.

http://en.wikipedia.org/wiki/Related-key_attack

AES uses the Rijndael key schedule which is described in operation here

http://www.samiam.org/key-schedule.html and with all the good math at Wiki and/or Schneider's paper http://en.wikipedia.org/wiki/Rijndael_key_schedule