New Attacks on the AES

[Justin Troutman]

Perhaps some of you have read Schneier's blog post, regarding the new attacks on the AES, by Biryukov et al. In short, while these attacks are faster than exhaustive search, they are still impractical, and apply only to the AES when used with 192-bit and 256-bit keys -- not 128-bit keys. The authors created a convenient FAQ that should answer most everyone's concerns. Of course, I'll do my best to provide clarifications. This is good cryptanalysis, but it doesn't call for panic; it does, however, call for attention.

Edited to add:

I read two earlier papers about these attacks here and here. A more recent paper can be found here.

[box750]

That is why always that it is possible I go for cascade algorythms (Truecrypt allows it), such as a combination of AES-Serpent, in that case they will have to find a vulnerability not only in AES but also Serpent, making cracking of the encryption more difficult.

[StevieO]

Hi, interesting how it seems to be working on the higher bits. I would have expected it to be vice versa !

Only just read this thread, so havn't had chance to read the links yet, thanx.

[Justin Troutman]

Originally Posted by box750

That is why always that it is possible I go for cascade algorythms (Truecrypt allows it), such as a combination of AES-Serpent, in that case they will have to find a vulnerability not only in AES but also Serpent, making cracking of the encryption more difficult.

Actually, this is contrary to what I've always promoted. Bear in mind that this is what you might call a "certificational" weakness or "academic" attack; it isn't in the realm of practicality.

Cryptography is arguably the strongest layer of the proverbial security onion, and when it does fail, it's almost never because of the mathematics; it's because of the implementation. History reinforces this.

As such, design decisions should cater to the simplicity of the implementation. Cramming in multiple block ciphers and cascades only adds complexity to the implementation; complexity is security's -- and a cryptographic implementation's -- worst enemy.

Even Serpent's co-designer, Ross Anderson, echoes this. Read Ross's thoughts on this on page 94, in Chapter 5 of his book, Security Engineering: A Guide To Building Dependable Distributed Systems. Quoting Ross:

Originally Posted by Ross Anderson

It does not make any sense to implement Serpent as well, ‘just in case Rijndael is broken’: the risk of a fatal error in the algorithm negotiation protocol is orders of magnitude greater than the risk that anyone will come up with a production attack on Rijndael. (We’ll see a number of examples later where using multiple algorithms, or using an algorithm like DES multiple times, caused something to break horribly.)

Folks mistakingly dwell on the cryptography itself, when it's the implementations that are most vulnerable. Cryptanalytical progress is inevitable, and certainly worthy of prompt attention, but let's not let it distract us from the real problem.

[Justin Troutman]

Originally Posted by StevieO

Hi, interesting how it seems to be working on the higher bits. I would have expected it to be vice versa !

Indeed, this seemingly counterintuitive happening has many scratching their heads.

Originally Posted by StevieO

Only just read this thread, so havn't had chance to read the links yet, thanx.

No problem. The papers are dense jungles of mathematical foliage, so beware!

[lotuseclat79]

Justin,

Your link to the blog post is broken in your first post. You need to edit the underscores to dashes to fix the link.

-- Tom

[Justin Troutman]

Originally Posted by lotuseclat79

Justin,

Your link to the blog post is broken in your first post. You need to edit the underscores to dashes to fix the link.

-- Tom

Thanks a lot, Tom. I probably wouldn't have noticed that. Last night, while reading the comments in this thread, I clicked on that link to Schneier's blog, and noticed the error; at that point, I manually went to schneier.com/blog and noticed that it was down for maintenance. I mistakingly attributed the error to that. Cheers, and a happy 4th.

[Gusapat]

AES is good.

[Pleonasm]

For readers of this thread who may not have visited some of (very informative) links provided in prior posts, it may be wise to briefly consider the conclusion of Bruce Schneier in order to place this issue in perspective:

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.

Source: Schneier on Security

[Justin Troutman]

Originally Posted by Pleonasm

For readers of this thread who may not have visited some of (very informative) links provided in prior posts, it may be wise to briefly consider the conclusion of Bruce Schneier in order to place this issue in perspective:

True; that is important to note. However, it's important to note that while this particular attack model (related-key*) might not have a significant impact in a scenario where an adversary can't choose the key, such as using a block cipher for encryption, it very well may have a significant impact in a scenario where an adversary can influence the key, such as using the block cipher as a hash function. In short, while an attack may not affect the breaking of one primitive, it may affect the making of another.

* In this model, we assume that an adversary can obtain the ciphertexts that correspond to plaintexts of his choice, encrypted under an unknown key, k, as well as the ciphertexts corresponding to plaintexts encrypted under a second key, k', where (k' xor k) is chosen by the adversary.

[Pleonasm]

However, it's important to note that while this particular attack model (related-key*) might not have a significant impact in a scenario where an adversary can't choose the key, such as using a block cipher for encryption, it very well may have a significant impact in a scenario where an adversary can influence the key…

So, to clarify, a practical lesson from this research is to always generate your own private/public keys (rather than obtaining them elsewhere), to ensure that an adversary hasn’t influenced their construction?

[caspian]

Folks mistakingly dwell on the cryptography itself, when it's the implementations that are most vulnerable. Cryptanalytical progress is inevitable, and certainly worthy of prompt attention, but let's not let it distract us from the real problem.

Justin, for a person like me who does not know much, what method of encryption would you recommend? TrueCrypt? Axcrypt?

[stap0510]

Is this attack also dependent to a kind of mode you are using?
So is there a difference in cracking the encyption based on the difference for like saying...ECB of some block-chaining mode of operation?

[Justin Troutman]

Originally Posted by Pleonasm

So, to clarify, a practical lesson from this research is to always generate your own private/public keys (rather than obtaining them elsewhere), to ensure that an adversary hasn’t influenced their construction?

Not exactly. I'm not referring to asymmetric cryptography or key derivation.

Quoting Lucks from a paper on related-key cryptanalysis:

In a related-key scenario, the adversary can partially control the key. It remains secret to the adversary (i.e., she can't read it), but she can choose key transformations, modify the key accordingly, and request encryptions under the modifed keys. The well-known DES complementation property can be viewed as a vulnerability against a related-key DES-distinguisher.

Quoting Ferguson, Kelsey, Schneier, and Whiting, in a paper regarding related-key attacks on reduced-round Twofish:

In a related-key attack, the attacker is permitted to request encryptions under a number of different keys. He is allowed to choose the relationship between
the keys, but not the keys themselves. An attacker can exploit a weak key pair to mount a related key attack. He requests a large set of keys, with some simple relationship (such as a fixed xor between pairs of keys), and hopes to end up with a weak key pair. He then mounts an attack to detect this weak key pair.

This is strictly within the context of symmetric cryptography.

Originally Posted by caspian

Justin, for a person like me who does not know much, what method of encryption would you recommend? TrueCrypt? Axcrypt?

I have confidence in PGP Corporation's ability to build good cryptographic software, so I would recommend their offerings. AxCrypt is the only file encryption software that I'm aware of that is seemingly IND-CCA2 /\ INT-CTXT secure (AES-CBC-then-HMAC-SHA-1), although I haven't analyzed the implementation in order to verify it. I really like the designer's simplistic approach, though. As for TrueCrypt, I've always been hopeful that it will "be a good role model," given its cult following that hasn't been seen since PGP, but I remain uneasy about the developers' lack of interaction. At least, I've made several efforts to contact them, with no luck. I'll give them the benefit of the doubt though, and write it off as them not receiving my messages. I disagree with some of the algorithmic design decisions, but they seem to be trying to keep up with disk encryption trends. They could do better. All in all, it's probably decent software. I hope it is. Despite my predominantly critical views towards TrueCrypt, I'm actually rooting for the project.

Originally Posted by stap0510

Is this attack also dependent to a kind of mode you are using?
So is there a difference in cracking the encyption based on the difference for like saying...ECB of some block-chaining mode of operation?

The related-key attacks are against the key schedule of the AES, which doesn't concern the mode of operation. Speaking of modes, however, ECB is deterministic and stateless; any deterministic and stateless encryption scheme is insecure, regardless of how strong the underlying block cipher is. Given that, AES-ECB is insecure, while AES-CBC is secure, if we assume that the AES is secure.

[demoneye]

Justin Troutman

say , what the best implementation software u recommended for AES ?
what about Folder Lock ? it uses aes 256 also ...


10x

[stap0510]

Originally Posted by demoneye

Justin Troutman

say , what the best implementation software u recommended for AES ?
what about Folder Lock ? it uses aes 256 also ...


10x

Or what about Truecrypt for that matter.
I hope Truecrypt would stand even a theoratical attack like this.

[Justin Troutman]

Originally Posted by demoneye

say , what the best implementation software u recommended for AES ?
what about Folder Lock ? it uses aes 256 also ...

From experience, I can only recommend the offerings of PGP Corporation, primarily because I trust their ability to securely implement cryptography. I'm not sure about Folder Lock; it doesn't appear to use a MAC, so I am not optimistic about its ability to preserve integrity. Furthermore -- and I just discovered this while reading their site -- they say:

Encryption process guarantees the full integrity of information.

Encryption provides confidentiality -- not integrity. Oftentimes, even confidentiality can be lost without integrity protection. Given that, I'm not convinced that they possess the ability to design good cryptographic software.

Originally Posted by stap0510

Or what about Truecrypt for that matter.
I hope Truecrypt would stand even a theoratical attack like this.

Keep in mind that these attacks examine the use of the AES as a hash function, while most real-world applications use the AES as a block cipher -- the latter application of which the AES is hardened rather. That being said, I'm not aware of any cryptographic software that is immediately affected by this.

[Leonid]

Justin, I tried Folder Lock. It's a moneystealer. It does not provide anything worth mentioning really. If you open secret files hidden by Folder Lock, and if your comp is turned off or restarted for any reason (system crash, power outage), files "hidden" by Folder Lock will remain visible when you boot the system again.

Also, from my experience, Folder Lock can damage your data located on your hard drive during uninstallation.

[chronomatic]

Originally Posted by demoneye

Justin Troutman

say , what the best implementation software u recommended for AES ?
what about Folder Lock ? it uses aes 256 also ...


10x

Use GnuPG for e-mail encryption and Truecrypt for disk encryption.

Never use an encryption product where the source code is closed. Both GnuPG and Truecrypt are 100% open-source. So, even if the Truecrypt developers are a bit secretive, their code speaks for itself. If there were major flaws with it, they would have been discovered by the plethora of paranoid technical people who examine the code.

[Justin Troutman]

Originally Posted by chronomatic

Use GnuPG for e-mail encryption and Truecrypt for disk encryption.

Never use an encryption product where the source code is closed. Both GnuPG and Truecrypt are 100% open-source. So, even if the Truecrypt developers are a bit secretive, their code speaks for itself. If there were major flaws with it, they would have been discovered by the plethora of paranoid technical people who examine the code.

I'm certainly a proponent of the open-source model, but I think it's important that I play the devil's advocate here, by saying that open-source isn't inherently more secure than closed-source; what it has, though, is the potential to be. The "many eyes" defense is only half right; it doesn't matter how many eyes are looking if the right eyes aren't looking. I've worked on both open-source and closed-source security projects before, and there were instances where the closed-source implementations were more secure than the open-source implementations. When the conclusion presented itself, it turns out that the entity developing the closed-source implementation had the monetary resources to hire a select group of the right eyes, whereas the group responsible for the open-source implementation did not, thus relying on a large, but untrained, community of eyes. (Note: I'm not saying this because you implied otherwise; it's just something I wanted to share, in general.)

Has anyone published a significant analysis of TrueCrypt? I know of a paper by A. Czeskis, D. J. St. Hilaire, K. Koscher, S. D. Gribble, T. Kohno, and B. Schneier, titled, "Defeating Encrypted and Deniable File Systems: TrueCrypt v5.1a and the Case of the Tattling OS and Applications," but that's about it.

[lakecliff]

Cryptography is arguably the strongest layer of the proverbial security onion, and when it does fail, it's almost never because of the mathematics; it's because of the implementation. History reinforces this.

As such, design decisions should cater to the simplicity of the implementation. Cramming in multiple block ciphers and cascades only adds complexity to the implementation; complexity is security's -- and a cryptographic implementation's -- worst enemy.

Sounds comprehensible.

[Pleonasm]

I have confidence in PGP Corporation's ability to build good cryptographic software…

Users who are evaluating encryption software may wish to check if that software is FIPS 140-2 certified, which is the case with PGP: “FIPS 140-2 validation provides independent assurance that the standard cryptographic algorithms … are implemented correctly” (see here).

Has anyone published a significant analysis of TrueCrypt?

I’m not aware of one. And, to the best of my knowledge, TrueCrypt is not FIPS 140-2 certified.

[LockBox]

Originally Posted by Pleonasm

Users who are evaluating encryption software may wish to check if that software is FIPS 140-2 certified, which is the case with PGP: “FIPS 140-2 validation provides independent assurance that the standard cryptographic algorithms … are implemented correctly” (see here).


I’m not aware of one. And, to the best of my knowledge, TrueCrypt is not FIPS 140-2 certified.

I agree, in principle. However, with regards to Truecrypt, they can't apply for the FIPS certification without giving up their identities and they've already indicated TC will continue to be an anonymous, albeit open-source project.

[stap0510]

Originally Posted by Justin Troutman

I'm certainly a proponent of the open-source model, but I think it's important that I play the devil's advocate here, by saying that open-source isn't inherently more secure than closed-source; what it has, though, is the potential to be. The "many eyes" defense is only half right; it doesn't matter how many eyes are looking if the right eyes aren't looking. I've worked on both open-source and closed-source security projects before, and there were instances where the closed-source implementations were more secure than the open-source implementations. When the conclusion presented itself, it turns out that the entity developing the closed-source implementation had the monetary resources to hire a select group of the right eyes, whereas the group responsible for the open-source implementation did not, thus relying on a large, but untrained, community of eyes. (Note: I'm not saying this because you implied otherwise; it's just something I wanted to share, in general.)

Has anyone published a significant analysis of TrueCrypt? I know of a paper by A. Czeskis, D. J. St. Hilaire, K. Koscher, S. D. Gribble, T. Kohno, and B. Schneier, titled, "Defeating Encrypted and Deniable File Systems: TrueCrypt v5.1a and the Case of the Tattling OS and Applications," but that's about it.

The paper you are reffering doesn't concern full-disk-encryption.
The paper that you're reffering to merely shows flaws in the host-journalling OS, where TrueCrypt is running on.
With full-disk-encryption the bottom-line outing from that paper wouldn't fly.

[Justin Troutman]

Originally Posted by Pleonasm

Users who are evaluating encryption software may wish to check if that software is FIPS 140-2 certified, which is the case with PGP: “FIPS 140-2 validation provides independent assurance that the standard cryptographic algorithms … are implemented correctly” (see here).

This is definitely important; thanks for mentioning it. I was just discussing this recently with some federal contacts of mine, who are tightly bound by FIPS certification.

Originally Posted by Pleonasm

I’m not aware of one. And, to the best of my knowledge, TrueCrypt is not FIPS 140-2 certified.

FIPS 140-2 certification is attractive, but I would be happy just to see a significant analysis.

Originally Posted by Gerard Morentzy

I agree, in principle. However, with regards to Truecrypt, they can't apply for the FIPS certification without giving up their identities and they've already indicated TC will continue to be an anonymous, albeit open-source project.

That's interesting. I wasn't aware of that. Do you think this is a good trade-off? By doing so, they are cutting potential ties with a large market. The benefit of this market isn't simply commercial, either, as some of these FIPS-bound entities possess the ability to conduct intense analysis -- something that would only benefit the evolution of TrueCrypt.

Originally Posted by stap0510

The paper you are reffering doesn't concern full-disk-encryption.
The paper that you're reffering to merely shows flaws in the host-journalling OS, where TrueCrypt is running on.
With full-disk-encryption the bottom-line outing from that paper wouldn't fly.

Right. I probably should have said that this is the only TrueCrypt-related paper that I know of, disregarding its actual subject matter. I've no doubt that many have looked at the code, but I'm only interested in who looked. Inspecting code is tricky business, and despite my ongoing involvement with looking at cryptographic code, I wouldn't trust myself alone to make any definitive security statements.