Expert advice: Encryption 101 -- Triple DES explained

Here is Jon Callas full expert response to a recent user question on Triple DES in Ask the Expert.

This commentary is the full response to an Ask the Expert question in the Secure Messaging category. Read the full question here.

What we all call Triple DES is EDE (encrypt, decrypt, encrypt). The way that it works is that you take three 56-bit keys, and encrypt with K1, decrypt with K2 and encrypt with K3. There are two-key and three-key versions. Think of the two-key version as merely one where K1=K3. Note that if K1=K2=K3, then Triple DES is really Single DES.

Triple DES was created back when DES was getting a bit weaker than people were comfortable with. As a result, they wanted an easy way to get more strength. In a system dependent on DES, making a composite function out of multiple DESes is likely to be easier than bolting in a new cipher and sidesteps the political issue of arguing that the new cipher is better than DES.

As it turns out, when you compose a cipher into a new one, you can't use a double enciphering. There is a class of attacks called meet-in-the-middle attacks, in which you encrypt from one end, decrypt from the other, and start looking for collisions (things that give you the same answer). With sufficient memory, Double DES (or any other cipher) would only be twice as strong as the base cipher -- or one bit more in strength.

There's more to it. If the cipher forms a group, then encrypting twice with two keys is equivalent to encrypting once with some key. Now, it's not trivial to know what that other key is, but it means that a brute-force attack would find that third key as it tried all possible single-keys. So if the cipher's a group, then multiple-ciphering is merely a waste of time.

In case you don't know what a group is, permit me a quick explanation. A group is a relationship between a set and an operator. If they behave more or less the way integers do with addition, they form a group. If you could keep encrypting a block and it would make a full circuit over the set of possible blocks, that would also form a group.

As you might guess, DES is not a group. If it was, we wouldn't be discussing this at all. However, DES does have known structural things in it that make people say that it's not strongly not-a-group. There are, for example, known loops in DES where if you keep encrypting with the same key, you run around in a long loop.

These structural weaknesses are why you wouldn't want to use EEE or DDD mode if you had a better option. You also wouldn't want to use EED, DEE, DDE or EDD for the same reason. Because of the weak-non-groupness of DES, you want to use EDE or DED compositions. And EDE just makes more sense -- if you use DED you have to explain to people why your Triple DES encryption starts with decrypting.

Now then, remember that the reason we're going through this multiple-encryption exercise is because we want to make a composite cipher that is stronger than single DES. Because of the meet-in-the-middle attack, double DES is only one-bit stronger than single DES. Two-key triple DES thus has 112 bits of strength. But what about the three-key version of triple DES? Common sense dictates it would be at least as strong as two-key triple DES, but how much stronger?

The answer is that no one knows. I've seen arguments suggest Triple DES always has 112 bits of strength. I've seen them that it has the full 168 bits. (Note that we're ignoring the obvious weak keys, like K1=K2.) I don't like either, myself, and actually think that the ones that you don't ever get more than 112 bits are better arguments, even though I disagree.

One thing to remember is that in cryptography there's a difference between a theoretic attack and a real one. Let's suppose, for example, I came up with an attack that needed 2^80 cipher blocks, and then could always make three-key Triple DES be no stronger than 112 bits.

That's worthy of publication, but it's not practical. A tera-block (eight terabytes) is 2^40 blocks. With this attack, you need eight-tera-tera-bytes of memory and a CPU that can address that much. Also, you could defend against this attack by re-keying after a mere few million terabytes of data.

So let's come right down to where I live -- practical cryptography. If you ask a good cryptographer if 168-bit Triple DES is weaker than some standard 128-bit cipher (CAST, Blowfish, AES, etc.), they'll almost certainly say no -- if you ask the right way. An example of asking the right way would be something like, "Oh, so you're saying I should use Blowfish instead of Triple DES because it's stronger." Even if they think that Triple DES is pretty weak, you'll probably get, "Mmmmmm, no, no, that's not what I'm saying" as an answer, and then maybe a discussion similar to this one. Similarly, a good cryptographer isn't going to tell you to use Triple DES as a stronger alternative to any of the standard 128-bit ciphers.

Therefore, by practical reasoning, it's about as strong as them. It seems safe to guess that Triple DES is stronger than 112 bits, and not as strong as the full 168. Somewhere between 113 and 167, 128 seems to be a good, conservative compromise.

There you have it, the long explanation of why we just lump Triple DES in with 128-bit ciphers. If DES were strongly not-a-group, then it would be 168 bits. Because DES is definitely not a group, but has weakness in that property, we don't exactly know how strong it is, but no one thinks it's all that much weaker than 128. So we just lump it in with the 128-bit ciphers.

This was first published in June 2004

Dig deeper on Disk Encryption and File Encryption

Pro+

Features

Enjoy the benefits of Pro+ membership, learn more and join.

0 comments

Oldest 

Forgot Password?

No problem! Submit your e-mail address below. We'll send you an email containing your password.

Your password has been sent to:

-ADS BY GOOGLE

SearchCloudSecurity

SearchNetworking

SearchCIO

SearchConsumerization

SearchEnterpriseDesktop

SearchCloudComputing

ComputerWeekly

Close