# Are these emerging threats against AES affecting your designs?

Recentally, an attack on AES was discovered which reduces its computationally complexity, by a very slight amount.

• The first key recovery attack on the full AES-128 with computational complexity $2^{126.1}$.
• The first key recovery attack on the full AES-192 with computational complexity $2^{189.7}$.
• The first key recovery attack on the full AES-256 with computational complexity $2^{254.4}$.

There is also the new AES-NI instruction set, which allows attackers to make hundreds of billions of parallel guesses per day.

In light of these emerging threats, have you made changes to your designs to mitigate the impact? If so, what has changed?

-

We in the Tahoe-LAFS project had already been planning to switch from AES-256 to XSalsa20⊕AES-128, for One hundred year cryptography.

This news makes me think "Oh yeah, we should really get around to doing that soon." It also makes me think "Hm, maybe the extra CPU cycles for AES-256 vs. AES-128 is worth it for added longevity and for advance notice of plausible future attacks."

-
Which kind of security requirements do you have that you use the AES-256? See also my comment to Rook's answer. –  j.p. Aug 18 '11 at 9:23
As Rook removed his (down-voted) answer and replaced it by a new one, I repeat my comment on his idea to use AES-192: It's an overkill. The only attacks one should be worry about are side channel attacks like cache attacks or, if applicable, SPA and DPA. –  j.p. Aug 18 '11 at 17:56
I think the "100 year crypto" concept is cool enough that it should be exempt from the usual advice about appropriately-sized functions. Isn't that sort of the point? Hmm, I think I'm going to open a question about this... –  Marsh Ray Aug 18 '11 at 18:22
@Marsh: I wouldn't worry about crypto in 100 years. In 35 years nobody will be able to read your disks and file formats ;-). –  j.p. Aug 19 '11 at 6:18
I like the link and the idea of a 100 year crypto system. I think this is a pragmatic approach. –  Rook Aug 21 '11 at 18:32
show 1 more comment

No, an attack on AES-128 requiring $2^{126.1}$ computations and $2^{88}$ bytes of known plaintext is not a concern. Brute-force guessing of keys (e.g., using the AES-NI instructions you mentioned) will succeed in $2^{127}$ computations on average and requires negligible known plaintext. Part of why key lengths are selected conservatively is precisely to ensure a safety margin which renders these tiny differences insignificant.

What the paper presents is an interesting method of analyzing block ciphers using a technique developed for analyzing hash functions. That this novel cryptanalysis technique fails to improve on brute force by even a full bit confirms the fundamental soundness and resiliency of AES's design.

Still, this technique is new and the paper explores multiple approaches to applying it. Cryptographers will be watching with interest to see if anyone goes farther with it, either through refinement or in combination with other cryptanalytic techniques.

Edit: In other discussion it was pointed out that this attack succeeds with probability 1, so an apples-to-apples comparison would be with worst-case brute force at $2^{128}$. It would be an exceedingly unlucky attacker who actually paid worst-case cost! A comparison of the typical scenario seems more relevant. The average-case for this AES-attack is probably a bit better than $2^{126.1}$, but it's not obvious from the paper. Still, the difference seems likely to be under a couple of bits (for now), while brute force retains its overriding advantage of not requiring $2^{88}$ data.

Of course one can build a weak protocol (or use a non-weak protocol in a weak way) on top of AES-128. WPA2-PSK can usually broken quite easily, because the pre-shared key is derived from a user-given password, which can be brute-forced in a short time. Even changing to an algorithm with a 10000-bit key would not help, if this key is derived from a weak password.

-