Entries Tagged "AES"

Page 2 of 3

How Peer Review Doesn't Work

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

Posted on March 30, 2011 at 7:14 AMView Comments

New Attack Against ASP.NET

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.

EDITED TO ADD (10/13): Two more articles.

Posted on September 27, 2010 at 6:51 AMView Comments

Crypto Implementation Failure

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.

Posted on March 4, 2010 at 6:05 AMView Comments

Another New AES 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:

  • 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.
  • It’s a related-key attack, which requires the cryptanalyst to have access to plaintexts encrypted with multiple keys that are related in a specific way.
  • The attack only breaks 11 rounds of AES-256. Full AES-256 has 14 rounds.

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.

Posted on July 30, 2009 at 9:26 AMView Comments

New Attack on AES

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.

Posted on July 1, 2009 at 11:49 AMView Comments

Adi Shamir's Cube Attacks

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.

Posted on August 19, 2008 at 1:15 PMView Comments

Mujahideen Secrets 2

Mujahideen Secrets 2 is a new version of an encryption tool, ostensibly written to help Al Qaeda members encrypt secrets as they communicate on the Internet.

A bunch of sites have covered this story, and a couple of security researchers are quoted in the various articles. But quotes like this make you wonder if they have any idea what they’re talking about:

Mujahideen Secrets 2 is a very compelling piece of software, from an encryption perspective, according to Henry. He said the new tool is easy to use and provides 2,048-bit encryption, an improvement over the 256-bit AES encryption supported in the original version.

No one has explained why a terrorist would use this instead of PGP — perhaps they simply don’t trust anything coming from a U.S. company. But honestly, this isn’t a big deal at all: strong encryption software has been around for over fifteen years now, either cheap or free. And the NSA probably breaks most of the stuff by guessing the password, anyway. Unless the whole program is an NSA plant, that is.

My question: the articles claim that the program uses several encryption algorithms, including RSA and AES. Does it use Blowfish or Twofish?

Posted on February 8, 2008 at 5:39 AMView Comments

A New Secure Hash Standard

The U.S. National Institute of Standards and Technology is having a competition for a new cryptographic hash function.

This matters. The phrase “one-way hash function” might sound arcane and geeky, but hash functions are the workhorses of modern cryptography. They provide web security in SSL. They help with key management in e-mail and voice encryption: PGP, Skype, all the others. They help make it harder to guess passwords. They’re used in virtual private networks, help provide DNS security and ensure that your automatic software updates are legitimate. They provide all sorts of security functions in your operating system. Every time you do something with security on the internet, a hash function is involved somewhere.

Basically, a hash function is a fingerprint function. It takes a variable-length input — anywhere from a single byte to a file terabytes in length — and converts it to a fixed-length string: 20 bytes, for example.

One-way hash functions are supposed to have two properties. First, they’re one-way. This means that it is easy to take an input and compute the hash value, but it’s impossible to take a hash value and recreate the original input. By “impossible” I mean “can’t be done in any reasonable amount of time.”

Second, they’re collision-free. This means that even though there are an infinite number of inputs for every hash value, you’re never going to find two of them. Again, “never” is defined as above. The cryptographic reasoning behind these two properties is subtle, but any cryptographic text talks about them.

The hash function you’re most likely to use routinely is SHA-1. Invented by the National Security Agency, it’s been around since 1995. Recently, though, there have been some pretty impressive cryptanalytic attacks against the algorithm. The best attack is barely on the edge of feasibility, and not effective against all applications of SHA-1. But there’s an old saying inside the NSA: “Attacks always get better; they never get worse.” It’s past time to abandon SHA-1.

There are near-term alternatives — a related algorithm called SHA-256 is the most obvious — but they’re all based on the family of hash functions first developed in 1992. We’ve learned a lot more about the topic in the past 15 years, and can certainly do better.

Why the National Institute of Standards and Technology, or NIST, though? Because it has exactly the experience and reputation we want. We were in the same position with encryption functions in 1997. We needed to replace the Data Encryption Standard, but it wasn’t obvious what should replace it. NIST decided to orchestrate a worldwide competition for a new encryption algorithm. There were 15 submissions from 10 countries — I was part of the group that submitted Twofish — and after four years of analysis and cryptanalysis, NIST chose the algorithm Rijndael to become the Advanced Encryption Standard (.pdf), or AES.

The AES competition was the most fun I’ve ever had in cryptography. Think of it as a giant cryptographic demolition derby: A bunch of us put our best work into the ring, and then we beat on each other until there was only one standing. It was really more academic and structured than that, but the process stimulated a lot of research in block-cipher design and cryptanalysis. I personally learned an enormous amount about those topics from the AES competition, and we as a community benefited immeasurably.

NIST did a great job managing the AES process, so it’s the perfect choice to do the same thing with hash functions. And it’s doing just that (.pdf). Last year and the year before, NIST sponsored two workshops to discuss the requirements for a new hash function, and last month it announced a competition to choose a replacement for SHA-1. Submissions will be due in fall 2008, and a single standard is scheduled to be chosen by the end of 2011.

Yes, this is a reasonable schedule. Designing a secure hash function seems harder than designing a secure encryption algorithm, although we don’t know whether this is inherently true of the mathematics or simply a result of our imperfect knowledge. Producing a new secure hash standard is going to take a while. Luckily, we have an interim solution in SHA-256.

Now, if you’ll excuse me, the Twofish team needs to reconstitute and get to work on an Advanced Hash Standard submission.

This essay originally appeared on Wired.com.

EDITED TO ADD (2/8): Every time I write about one-way hash functions, I get responses from people claiming they can’t possibly be secure because an infinite number of texts hash to the same short (160-bit, in the case of SHA-1) hash value. Yes, of course an infinite number of texts hash to the same value; that’s the way the function works. But the odds of it happening naturally are less than the odds of all the air molecules bunching up in the corner of the room and suffocating you, and you can’t force it to happen either. Right now, several groups are trying to implement Xiaoyun Wang’s attack against SHA-1. I predict one of them will find two texts that hash to the same value this year — it will demonstrate that the hash function is broken and be really big news.

Posted on February 8, 2007 at 9:07 AMView Comments

Sidebar photo of Bruce Schneier by Joe MacInnis.