Are these emerging threats against AES affecting your designs?

Question

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?

Answer 1

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."

Answer 2

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.

Answer 3

No, these new attacks are not a practical concern, and not a reason to change what you're doing.

@Marsh Ray already did a good job of explaining the main reason why: 128-bit keys are already long enough that there is a tremendous safety margin here. The biclique attacks speed up exhaustive search by less than a factor of 2. We already have a safety margin of many orders of magnitude, so a 2x speedup just doesn't matter. Similarly for the AES-NI instructions; there's so much safety margin against exhaustive keysearch that a 10x or 100x speedup just doesn't matter.

In addition, there's a second reason why the new biclique attacks are not a threat in practice: they require an absolutely, totally impractical amount of chosen plaintext/ciphertext pairs. For instance, their 2^126.2 attack on AES-128 requires the attacker to ask for the encryption of 2⁸⁸ chosen-plaintexts, all encrypted under the same AES key. No current system is ever going to give an attacker the chance to acquire anywhere near that many chosen plaintexts within our lifetime. Not gonna happen.

So these attacks are completely outside the realm of practicality. They are nothing to worry about. In practice, the way that modern systems get broken is by bypassing the crypto, not by breaking the crypto. There's no way that biclique cryptanalysis of AES is gonna be the cheapest way to break into any real-world system: no way, no how.

So, don't worry about it. While the new results on biclique cryptanalysis are a highly impressive feat of mathematics, they are not a reason to shy away from AES or to change your practices. Personally, I'd say that AES is holding up remarkably well: after a decade of intense cryptanalysis, it still looks like a solid, well-thought-out design.