Schneier on Security

Can this be extended DOWN the scale? Does it affect AES128?

Bruce, does this strengthen the case for your hash candidate, skein?

Weren't there structural weaknesses evident in Rijndael and the ciphers it was modeled after that were discussed during the NIST competition nine years ago? I also remember somebody finding key schedule weaknesses in the cipher around that time that were demonstrable in reduced-round variants. I refuse to believe that anyone is surprised by this, but I'm sure there will be plenty of chicken-little-ing.

"...attacks always get better, they never get worse."

This always amazes me. Attacks keep getting more and more vicious, yet the crypto community keeps comming up with more resilient algorithms. It makes me wonder how quickly a modern cryptographer could break older algorithms using equipment of the day. If we'd had people like Bruce around in WWII, would Enigma have fallen faster thanks to the improved techniques we've learend?

Note that the attack doesn't apply on AES-128, which is the most used primitive for AES-based hash functions submitted to the NIST competition.

Phew! I'm glad I only use AES 128...

What should the complexity be? 2^256? And what can realistically be brute forced at the moment?

Bruce, some people on Hacker News http://news.ycombinator.com/item?id=683104 want to know if this means that AES-256 is weaker than AES-128.

It doesn't affect AES-128, and 2^119 certainly seems less than 2^128 (but I'm not sure if that's the right way to measure it).

And, importantly, it's a related-key attack. SSH, SSL, etc. don't allow related-key queries, at least not in a way that would make most related-key attacks straightforward. The attack is important if the AES key schedule is used in a hash function, as Bruce says, and it's interesting if it leads to other, non-related-key attacks.

@Ariel: Seems unlikely that AES-256 would be weaker than AES-128 in real applications.

And as a commenter at your ycombinator.com link says, don't panic. Academically "broken" algorithms can still be fine in practice. (On the other hand, they can also be MD5.) More importantly, we're bitten every day by much less exciting security bugs that have nothing to do with cutting-edge algorithm research.

This is a good example of why the TLS IETF working group's aversion to including more well-tested block ciphers - like other AES candidates - ("We've already got a good block cipher, why would we need more?") was pretty shortsighted.

@Tim A brute-force search would be around 2^128 (probabilistically,) thanks to the Birthday Paradox.

I don't know how weak enigma is to an attack using hardware from WW-II, but modern cryptoanalytic techniques, but I do know that it's beyond trivial to crack enigma today.

Infact, doing so was one of 9 different tasks for the ACM collegiate programming contest when I took part -- that is, cracking enigma was one of 9 tasks that a team consisting of one graduate and two undergraduate students where expected to have a chance of solving in 5 hours.

What's the actual complexity of the attack? Is it 2^119, 2^(119+119) or 2^(119+77)? This is not clear to me from the paper.

We have written a FAQ on our attacks, which covers most of the questions popping up here and in other discussions.

https://cryptolux.org/FAQ_on_the_attacks

Tim : "What should the complexity be? 2^256? And what can realistically be brute forced at the moment?"
Jones : "@Tim A brute-force search would be around 2^128 (probabilistically,) thanks to the Birthday Paradox. "

@Tim : No AES256 complexity should be 2^256. Since bruteforce consist to try all keys, in practice you have 1 chance over 2 to find it in 2^255 tries, 1/4 in 2^254 ...

@Jones : Birthday paradox does not work like this (if so AES128 complexity should be 2^64, I would be able to crack it with my dual core in days :-) )

First, congratulations to Alex and Dmitry on this great work!

A couple of observations: people tend to write down related key attacks as not being very practical, but in at least one area they are devastating: use of the block cipher as a primitive in one of the hash functions constructions in which the message is put into the cipher's "key" input.

The second and even more interesting thing concerns NSA's certification of AES for protection of classified information. They approved AES-128 for protection of SECRET information, and AES-192 and AES-256 for protection of TOP SECRET information: the different certifications strongly suggesting that not only does NSA accept that these algorithms are strong, but more particularly that they believe, as one might expect, that AES-256 and AES-192 are stronger than AES-128.

This new analysis seems to show that at least for one type of attack, this is not true and AES-128 is actually the strongest of the three. This seems to suggest that NSA's review did not discover Alex and Dmitry's attack before certifying these algorithms for TOP SECRET applications. (Or perhaps they did discover them, and decided the attacks are too impractical for them to care; it will be interesting what happens to the AES certifications in the coming days.)

@Gian-Carlo Pascutto:

The complexity is 2^119. (To be stricter, it is actually 2^119 plus a few other steps on the order of 2^72. But whereas 2^(119+72) is much larger than 2^119, 2^119 + 2^72 is negligibly more than 2^119.)

2^77 is the amount of memory required. (Quite a lot.)

forgive my ignorance, but what's to keep, say, intel from building a highly-specialized 32nm AES-dedicated chip that can run through trillions/quadrillions of encryptions per second? is it just not possible?

Sorry, Dmitry, the URL you gave did not work for me. I found that FAQ at https://cryptolux.uni.lu/FAQ_on_the_attacks

@mike: The problem is sheer scale. We're dealing with numbers on the order of 10 ^ 38 for a brute force attack on a 128-bit key. If you can run through a trillion keys a second, you can get the key in 10 ^ 26 seconds, which is a few hundred trillion years. If you can somehow speed that up by a factor of a thousand, perhaps by dealing with Intel, you can crack it in a few hundred billion years.

As far as the chip goes, there are significant limitations on how fast a chip can go, with fundamental limitations based on the speed of light, the necessary size of chip elements to avoid drowning in random and quantum effects, and the like. There are also engineering issues, such as the fact that signals in any medium go slower than the speed of light, the difficulty of making extremely small chip elements, and the like.

Several years ago, people were able to use expensive equipment to brute-force the 56-bit DES key. An AES-128 key is 72 bits longer, as I understand it, which multiplies the number of cases by about four sextillion. We're nowhere near a sextillion times as efficient as we were back then, and we'd have to have an entirely new idea of computation to get there.

Therefore, keys like that can't be brute-forced. The systems have to be cracked.

@mike The world fastest supercomputer has around 2^50 FLOPS. Assume that we can check with one FLOP one key. Also assume we can shrink this giant to an area of 1 mm^2. The surface of the earth is around 2^69 mm^2. Conclusion, if we cover the whole earth with this super mini computers we would still need around 8 1/2 minutes to crack one key with 100% certainty.

Mike: Nothing. That's precisely how people break cryptographic schemes. When you consider how suitable an algorithm is, you have to figure in the resources of your attacker. An algorithm that would keep your little sister from reading your diary won't keep out the CIA.

That is why AES-128 is used almost exclusively for applications where it is believed to be billions of times more secure than it needs to be. And that's why an attack that makes AES-256 a billion times easier to break is still impractical to use.

@Roger: Some of NSA's algorithms from the FORTEZZA project (BATON, JUNIPER) had a 160-bit keyspace; it's documented in the PKCS#11 spec. So I think they required AES-192/256 just because 160 bits is their standard key length for TOP SECRET info. Myself, I don't think AES's use to handle TOP SECRET data will change unless a much better attack comes along.

@caf: Guess I have to agree it would be better to have more TLS ciphers. We don't want another MD5 problem; we want uninterrupted security with minimal pain when algorithms start to look shaky. Of course, AES does not look shaky yet by a long shot.

In retrospect, however, several of the other AES candidates (though none of the other finalists) were eliminated early-on for having far less serious "certificational" weaknesses.

This is an 'engineered' bug!!!

AES-192 & 256 are 'intentionally' weakened in the key expansion phase... The original Rijndael versions use 192-bit and 256 bit block sizes (a 192b key MATCHes with a 192b block & the 256b key MATCHes with a 256b block)

so is it surprising to see AES192 & 256 are weaker than expected??? NOOOO

Looking for another next-gen cipher (like SHA-3) competition??? NO NEED Just use the original Rijndael.

Different revisions of candidates/submissions/footnote details giving "enhancements" are a bit creepy to outsiders. Hard to trust such a small community of independent skillsets like programming, math, and computer knowledge.

I would like to see more serpent implementations, however, AES is the "standard." Too bad that Serpent does not get the attention and $'s.

The devil is always in the details. Banks pay good money for good reasons for hopefully good work. I do not trust NSA/NIST to do the right thing, they are not trustworthy, but only a rat race security. GRR.

Would be interesting to read more about the custom crypto business.

Security is a very closed world, you only read about some of the insecurity.

@PackagedBlue

In the early 90s I would have agreed with you. But not anymore.

NSA turns up to open conferences cus they are not that far ahead anymore.

Like others I feel pretty confidant that they can't crack PGP with reasonable settings.

Keyboard loggers yes. But directly crack.. No.

OT: @Bruce, nice touch on the comment system. It's been getting awfully busy in the last year, and hard to tell yours apart from the rest.

so is it surprising to see AES192 & 256 are weaker than expected??? NOOOO

___________________
Smarry
Get 28 movie channals for 3 months free

Is it true that AES128 is stronger than AES256 ?

Karthik Balaguru

Another example that our future is more to combine all.:

Encryption (Password and Keyfiles) + Hide-Out + small, mobile Hardware.

Brute Force is only possible if the file is visible / known / acccessible. We can give forensic much more frustration if we encrypt + hide files.

Here you can find new compression algorithms - no forensic software can read it - if so than its mostly to late cause some dozen new algorithms are out every 6 month.:

http://encode.ru/forum/

To say here is one new encryption algorithm and anything is fine is no longer our future.

Encryption + Hiding Place + no physical access etc. etc.

Funny - 99% of all forensic workers and police officers forget the postbox. Its true - they strip search you, the house, the garden, garage, basement, top flor, car but they look not at the postbox for an ciphered USB Stick.

From http://eprint.iacr.org/2009/317

on 2009-12-04: "Note: The attack on AES-256 improved to complexity 2^99."