Page 2 of 4
This is an extremely clever man-in-the-middle timing attack against TLS that exploits the interaction between how the protocol implements AES in CBC mode for encryption, and HMAC-SHA1 for authentication. (And this is a really good plain-language description of it.)
In an excellent article in Wired, James Bamford talks about the NSA’s codebreaking capability.
According to another top official also involved with the program, the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or break, unfathomably complex encryption systems employed by not only governments around the world but also many average computer users in the US. The upshot, according to this official: “Everybody’s a target; everybody with communication is a target.”
Bamford has been writing about the NSA for decades, and people tell him all sorts of confidential things. Reading the above, the obvious question to ask is: can the NSA break AES?
My guess is that they can’t. That is, they don’t have a cryptanalytic attack against the AES algorithm that allows them to recover a key from known or chosen ciphertext with a reasonable time and memory complexity. I believe that what the “top official” was referring to is attacks that focus on the implementation and bypass the encryption algorithm: side-channel attacks, attacks against the key generation systems (either exploiting bad random number generators or sloppy password creation habits), attacks that target the endpoints of the communication system and not the wire, attacks that exploit key leakage, attacks against buggy implementations of the algorithm, and so on. These attacks are likely to be much more effective against computer encryption.
EDITED TO ADD (3/22): Another option is that the NSA has built dedicated hardware capable of factoring 1024-bit numbers. There’s quite a lot of RSA-1024 out there, so that would be a fruitful project. So, maybe.
EDITED TO ADD (4/13): The NSA denies everything.
“Biclique Cryptanalysis of the Full AES,” by Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger.
Abstract. Since Rijndael was chosen as the Advanced Encryption Standard, improving upon 7-round attacks on the 128-bit key variant or upon 8-round attacks on the 192/256-bit key variants has been one of the most difficult challenges in the cryptanalysis of block ciphers for more than a decade. In this paper we present a novel technique of block cipher cryptanalysis with bicliques, which leads to the following results:
- The first key recovery attack on the full AES-128 with computational complexity 2126.1.
- The first key recovery attack on the full AES-192 with computational complexity 2189.7.
- The first key recovery attack on the full AES-256 with computational complexity 2254.4.
- Attacks with lower complexity on the reduced-round versions of AES not considered before, including an attack on 8-round AES-128 with complexity 2124.9.
- Preimage attacks on compression functions based on the full AES versions.
In contrast to most shortcut attacks on AES variants, we do not need to assume related-keys. Most of our attacks only need a very small part of the codebook and have small memory requirements, and are practically verified to a large extent. As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.
This is what I wrote about AES in 2009. I still agree with my advice:
Cryptography is all about safety margins. If you can break n round of a cipher, you design it with 2n or 3n rounds. What we’re learning is that the safety margin of AES is much less than previously believed. And while there is no reason to scrap AES in favor of another algorithm, NST should increase the number of rounds of all three AES variants. At this point, I suggest AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds. Or maybe even more; we don’t want to be revising the standard again and again.
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.
The advice about AES-256 was because of a 2009 attack, not this result.
Again, I repeat the saying I’ve heard came from inside the NSA: “Attacks always get better; they never get worse.”
In this amusing story of a terrorist plotter using pencil-and-paper cryptography instead of actually secure cryptography, there’s this great paragraph:
Despite urging by the Yemen-based al Qaida leader Anwar Al Anlaki, Karim also rejected the use of a sophisticated code program called “Mujhaddin Secrets”, which implements all the AES candidate cyphers, “because ‘kaffirs’, or non-believers, know about it so it must be less secure”.
It’s serious:
The problem lies in the way that ASP.NET, Microsoft’s popular Web framework, implements the AES encryption algorithm to protect the integrity of the cookies these applications generate to store information during user sessions. A common mistake is to assume that encryption protects the cookies from tampering so that if any data in the cookie is modified, the cookie will not decrypt correctly. However, there are a lot of ways to make mistakes in crypto implementations, and when crypto breaks, it usually breaks badly.
“We knew ASP.NET was vulnerable to our attack several months ago, but we didn’t know how serious it is until a couple of weeks ago. It turns out that the vulnerability in ASP.NET is the most critical amongst other frameworks. In short, it totally destroys ASP.NET security,” said Thai Duong, who along with Juliano Rizzo, developed the attack against ASP.NET.
Here’s a demo of the attack, and the Microsoft Security Advisory. More articles. The theory behind this attack is here.
EDITED TO ADD (9/27): Three blog posts from Scott Guthrie.
EDITED TO ADD (9/28): There’s a patch.
Look at this new AES-encrypted USB memory stick. You enter the key directly into the stick via the keypad, thereby bypassing any eavesdropping software on the computer.
The problem is that in order to get full 256-bit entropy in the key, you need to enter 77 decimal digits using the keypad. I can’t imagine anyone doing that; they’ll enter an eight- or ten-digit key and call it done. (Likely, the password encrypts a random key that encrypts the actual data: not that it matters.) And even if you wanted to, is it reasonable to expect someone to enter 77 digits without making an error?
Nice idea, complete implementation failure.
EDITED TO ADD (3/4): According to the manual, the drive locks for two minutes after five unsuccessful attempts. This delay is enough to make brute-force attacks infeasible, even with only ten-digit keys.
So, not nearly as bad as I thought it was. Better would be a much longer delay after 100 or so unsuccessful attempts. Yes, there’s a denial-of-service attack against the thing, but stealing it is an even more effective denial-of-service attack.
A new and very impressive attack against AES has just been announced.
Over the past couple of months, there have been two (the second blogged about here) new cryptanalysis papers on AES. The attacks presented in the papers are not practical—they’re far too complex, they’re related-key attacks, and they’re against larger-key versions and not the 128-bit version that most implementations use—but they are impressive pieces of work all the same.
This new attack, by Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, and Adi Shamir, is much more devastating. It is a completely practical attack against ten-round AES-256:
Abstract.
AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). In the case of AES-128, there is no known attack which is faster than the 2128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2176 and 2119 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. One of our attacks uses only two related keys and 239 time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and 2120 time). Another attack can break a 10 round version of AES-256 in 245 time, but it uses a stronger type of related subkey attack (the best previous attack on this variant required 64 related keys and 2172 time).
They also describe an attack against 11-round AES-256 that requires 270 time—almost practical.
These new results greatly improve on the Biryukov, Khovratovich, and Nikolic papers mentioned above, and a paper I wrote with six others in 2000, where we describe a related-key attack against 9-round AES-256 (then called Rijndael) in 2224 time. (This again proves the cryptographer’s adage: attacks always get better, they never get worse.)
By any definition of the term, this is a huge result.
There are three reasons not to panic:
Not much comfort there, I agree. But it’s what we have.
Cryptography is all about safety margins. If you can break n round of a cipher, you design it with 2n or 3n rounds. What we’re learning is that the safety margin of AES is much less than previously believed. And while there is no reason to scrap AES in favor of another algorithm, NST should increase the number of rounds of all three AES variants. At this point, I suggest AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds. Or maybe even more; we don’t want to be revising the standard again and again.
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.
The paper I have is still a draft. It is being circulated among cryptographers, and should be online in a couple of days. I will post the link as soon as I have it.
UPDATED TO ADD (8/3): The paper is public.
There’s a new cryptanalytic attack on AES that is better than brute force:
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-Nikolic 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.
In an e-mail, the authors wrote:
We also expect that a careful analysis may reduce the complexities. As a preliminary result, we think that the complexity of the attack on AES-256 can be lowered from 2119 to about 2110.5 data and time.
We believe that these results may shed a new light on the design of the key-schedules of block ciphers, but they pose no immediate threat for the real world applications that use AES.
Agreed. While this attack is better than brute force—and some cryptographers will describe the algorithm as “broken” because of it—it is still far, far beyond our capabilities of computation. The attack is, and probably forever will be, theoretical. But remember: attacks always get better, they never get worse. Others will continue to improve on these numbers. While there’s no reason to panic, no reason to stop using AES, no reason to insist that NIST choose another encryption standard, this will certainly be a problem for some of the AES-based SHA-3 candidate hash functions.
EDITED TO ADD (7/14): An FAQ.
At this moment, Adi Shamir is giving an invited talk at the Crypto 2008 conference about a new type of cryptanalytic attack called “cube attacks.” He claims very broad applicability to stream and block ciphers.
My personal joke—at least I hope it’s a joke—is that he’s going to break every NIST hash submission without ever seeing any of them. (Note: The attack, at least at this point, doesn’t apply to hash functions.)
More later.
EDITED TO ADD (8/19): AES is immune to this attack—the degree of the algebraic polynomial is too high—and all the block ciphers we use have a higher degree. But, in general, anything that can be described with a low-degree polynomial equation is vulnerable: that’s pretty much every LFSR scheme.
EDITED TO ADD (8/19): The typo that amused you all below has been fixed. And this attack doesn’t apply to any block cipher—DES, AES, Blowfish, Twofish, anything else—in common use; their degree is much too high. It doesn’t apply to hash functions at all, at least not yet—but again, the degree of all the common ones is much too high. I will post a link to the paper when it becomes available; I assume Adi will post it soon. (The paper was rejected from Asiacrypt, demonstrating yet again that the conference review process is broken.)
EDITED TO ADD (8/19): Adi’s coauthor is Itai Dinur. Their plan is to submit the paper to Eurocrypt 2009. They will publish it as soon as they can, depending on the Eurocrypt rules about prepublication.
EDITED TO ADD (8/26): Two news articles with not a lot of information.
EDITED TO ADD (9/4): Some more details.
EDITED TO ADD (9/14): The paper is online.
Sidebar photo of Bruce Schneier by Joe MacInnis.