Debunking a Bogus Encryption Statement?

deviantphil asks: "Recently, a coworker tried to assert that encrypting a file twice with a 64 bit algorithm is equivalent to encrypting it once with a 128 bit algorithm. I know enough about encryption to know that isn't true, but I am having difficulties explaining why and how. Doesn't each pass of the encryption create a separate file header which makes this assertion untrue? Can anyone point me to references that would better help me explain this?" What other laughable claims have you heard attributed to encryption, and how were you able to properly lay them to rest?

Comments

Meet in the middle attack

[dtfinch]

http://en.wikipedia.org/wiki/Meet-in-the-middle_at tack

That's why we have triple-DES instead of double-DES.

Re:Meet in the middle attack

[swillden]

The block size is still 64-bit, which means 2^64 possible combinations versus the 2^128 for ideal 128-bit.

When talking about block ciphers, block size and key size are separate things. Generally, if you say algorithm X is an n-bit cipher, you're talking about key size, not block size. Given use of good block chaining modes, ciphers with larger block sizes don't really offer significant additional security.

typically attackers find ways of reducing the effective number of possible combinations for an algorithm. Original DES has been reduced significantly, so triple-DES was designed to improve it

Original DES hasn't really been reduced significantly. There are attacks which reduce the computational complexity to, IIRC ~41 bits, but at the expense of requiring impractical space. All in all, DES as stood up extremely well and its practical strength hasn't been significantly reduced by 30+ years of scrutiny.

The problem 3DES was created to address was a deliberate limitation of the design: The small keyspace. The strongest variant of Lucifer (the original IBM cipher which became DES), used a 128-bit key, but the NSA deliberately had it reduced to a 56-bit key, presumably because they thought they could break the cipher with the smaller key size, but it was still secure enough against others. Advances in computation technology, of course, have put a brute force search of a 56-bit keyspace within reach of run-of-the-mill desktop computers. 3DES addresses this by increasing the effective keyspace to 112 bits.

Re:Meet in the middle attack

[eddeye]

It's even worse if your cipher of permutations forms a group. In that case, for any two ENC keys k1 and k2, there exists a third ENC k3 such that ENC_k2 (ENC_k1 (x)) = ENC_k3 (x). In other words you can find a third key that produces the same permutation as the composition of keys 1 and 2. This means that breaking a double-encryption (or triple, quadruple, etc) is no harder than breaking a single encryption: the resulting permutation can always be described by a single key.

That's why 3DES uses EDE instead of EEE. While DES doesn't form a group, it does have some group-like structures which reduce the workload quite a bit. This doesn't apply to all ciphers btw; there are many more possible 64-bit permutations than 64-bit keys, so compositions can fall well outside those covered by keyspace.

I think this is covered in chapter 7 of the Handbook of Applied Cryptography.

Your keyspace wouldn't be that much bigger

[Profane MuthaFucka]

Seems like encrypting twice with a 64-bit key just means that instead of breaking a 64-bit key once, you have to do it twice. That's like using a 65-bit key, instead of a 64-bit key. Every bit doubles your keyspace.

Plus, you have to realize that the amount of time needed to brute force a single key of a certain size goes up non-linearly with each additional bit. If you just double the number of times you encrypt, you're pretty much just increasing the effort to brute force the thing linearly.

Re:Your keyspace wouldn't be that much bigger

[sr180]

Think of it as this: If you encrypt something as rot-13 twice, does it become any more secure?

Re:Your keyspace wouldn't be that much bigger

[Kadin2048]

I think a big part of that comes down to the file headers and how you actually implement the cryptographic algorithms into a system.

If you take a plaintext file and encrypt it into a file which has headers ("BEGIN ENCRYPTED CONTENT---"), and then encrypt the result again, assuming the attacker knows how you did it and that the intermediate file has plaintext headers, then they'll know the moment they broke the first 64-bit encryption layer. So in this example, you're basically at 65 bits.

Now if you don't include any headers, so that there's no terribly good way to determine whether you've gotten the right key or not, as you're brute-forcing the first layer, then I think you're right -- the strength of the overall system is somewhere in a grey area between 65 and 128 bits.

If someone was just thinking that they could use a file-encryption utility twice (which produces output files that have plaintext headers) and double the keyspace, they are dead wrong.

Re:Your keyspace wouldn't be that much bigger

[swillden]

Wouldn't you have to do the "inner" 64bit bruteforce procedure for each possible key of the "outer" 64bit keyspace, thus making it 128bit again?

No, you do a meet-in-the-middle attack, which is basically 2^64 in complexity if you're using two 2^64 keys.

There are some optimizations that can be done, but the basic idea is this: You start with one ciphertext block and its corresponding known plaintext. Then you encrypt the plaintext with all 2^64 possible keys and store the results (with some indexes to make it easy to search for a particular block). Then you decrypt the ciphertext with all 2^64 possible keys, looking each result up. When you find a match, you have found the pair of 64-bit keys that turns that plaintext into that ciphertext. So to search the entire space, you have to do 2^64+2^64 = 2^65 trial operations. On average, you only have to search half of the second keyspace, so the complexity of the search is 2^64+2^63 = 2^64 (plus the huge storage cost).

Triple encryption is also weakened by a meet-in-the-middle attack. Using three 64-bit keys, it would be nice to think you have a 192-bit key. But a meet-in-the-middle requires encrypting with all 64-bit keys for the first step, and decryption with all 128-bit keys for the second step, giving an effective strenth of 2^64+2^127 = 2^127 (plus the huge storage cost).

Finally, keep in mind that DES keys aren't 64 bits. They're 56 bits. So 3DES has a brute force search computational complexity of 111 bits, on average.

Re:Your keyspace wouldn't be that much bigger

[mgblst]

Do you hear whoosh sound? It is as if something just went flying over your head.

Debunking this claim

[jordandeamattson]

The length of the key (64-bits, 128-bits) at a simple level describes the complexity or "hardness" of the encryption. Enrcypting with a 64-bit key will give you one level of "hardness" and 128-bit will give you another, greater, level of hardness.

If you encrypt twice with a 64-bit key you will just be taking a plain text file and encrypting it and then taking your encrypted file and encrypting it once again. To break encryption on this file, getting access to the plain text, you would need to break 64-bit encryption twice.

While this would be more of a challenge than breaking 64-bit standalone encryption, it wouldn't be equivalent to the security of a 128-bit key. The difficulty of breaking 128-bit encryption isn't 2 times 64-bit encryption. It is actually greater - I can't quantify it without additonal research, hopefully someone who can recall it off the top of their head can chime in with the details.

Now, breaking a doubly encrypted file would present some interesting challenges. The most obvious is that your plaintext for the first layer of encryption is anything but plaintext. Confirming that one set of encrypted text is right one vs. some other set of encrypted text would definitely be a challenge. It would make it difficult to determine if you had found the right key to decrypt your first layer of encryption.

As an aside, I do remember reading about code systems where double encryption acutally made the result encryption less secure. I don't remember the details, but now my brain is itching and I will have to do some research. Thanks!

Yours,

Jordan

Re:Debunking this claim

[Coryoth]

As an aside, I do remember reading about code systems where double encryption acutally made the result encryption less secure. I don't remember the details, but now my brain is itching and I will have to do some research.

It isn't very common for the resulting encryption to be less secure, but "no appreciable improvement" is certainly very possible.

With block ciphers you can run into the issue that if the cipher scheme forms a group (as some do) then even if you use 2 different keys for each encryption round, there will be a single third key that provides identical encryption: an attacker never needs to break your two keys, they can simply find the single third key that is equivalent to your double encipherment. Depite encrypting twice with two different keys the result is no more secure than encrypting once. For a simple example of this, consider a ROT encryption scheme - if you encrypt a message with ROT9 then ROT12 that is just equivalent to ROT21, so instead of trying to find the two keys 9 and 12, the attacker can just solve the ROT21 problem (the worst case, of course, is if your combination of keys gives the identity element such as ROT9 and ROT17, or ROT13 twice, in which case you end up with an unencrypted document).

Even if that's not the case you can still get caught with a meet-in-the-middle approach if the attacker has some known plaintext (that is, they have some plaintext with the corresponding encrypted text and are attempting to extract your key) which does pretty much what it says, encrypting one way and decrypting the other to meet in the middle. Using such a scheme you can extract the keys with only marginally more effort than for single encryption.

Think about it as number of possibilities

[Phantombrain]

I'm going to think of it as if you were trying to bruteforce it.
If you have 64 bits, that is 1.84467441 × 10^19 (2^64), meaning maximum that many tries to break the first layer of encryption. The second layer is the same number, meaning to break it would mean a maximum of 3.68934881 × 10^19 attempts.
With 128 bit encryption, there are 3.40282367 × 10^38 (2^128) different possibilities, MUCh more than the double 64 bit encryption.

Obviously people don't usually bruteforce encrypted files, but you can see there are much more possiblities for 128 bit encryption than with double 64 bit.

Bad math

[Dan East]

Your both wrong. Encrypting twice at 64 bit is like 64*64=4096 bit encryption. Personally, I like to encrypt 7 times at 2 bit encryption for 128 bit strength. If its something I really want to keep secret, I encrypt four times at 128 bit for 268435456 bit encryption. However, don't make the mistake I made once of encrypting 128 times at 1 bit. Because that is just 1^128, which yields nothing more than 1 bit encryption.

In case anyone is wondering, I'm hoping some DRM coder will gain valuable insight from this post.

Dan East

Re:Bad math

[thefirelane]

In case anyone missed it though, there was a good insight in that humor: a clear way of expressing the answer to the posed question:

If two 64 bit encryptions equals one 128 bit, then 128 one-bit encryptions should also.

This means the file would have a password of either 1 or 0 ... you would be prompted for this password, and if you got it wrong, you could try again. Obviously you'd get it on the second try. You could repeat this 128 times, and that would be the total of all protection. Naturally, this means the most number of guesses you'd need to make is 256.

After thinking about it that way, it becomes quite clear: 128 bit encryption obviously requires more than 128 guesses to get the right key. As another poster pointed out, two 64 bit passes equals 65 bit encryption.

Get a book on cryptography

[cunkel]

Well, one common way to dispel a myth is to find an authoritative source on the subject that explains why the myth is untrue. Perhaps a book on cryptography would be helpful, for example:

• Applied Cryptography: Protocols, Algorithms, and Source Code in C by Bruce Schneier
• Handbook of Applied Cryptography by Alfred J. Menezes et al.

Either one will explain such things as why double-DES is not twice as strong as DES and common pitfalls in thought and design of cryptographic systems.

Snake oil FAQ

[Chuck Chunder]

Is a good place to start if you want to protect yourself against people hawking dodgy crypto.

I used to work at a small company where a guy came in and was trying to get us involved with some dodgy "crypto" product. Management were quite taken with it (he could talk and even had a patent!) but technically it was a load of horse shit with some pretty multicolour diagrams. That FAQ helped me crystalise my objections and the guy was given the heave ho before the company did anything embarrassing.

Re:While you're at it...

[QuantumG]

Geologists recently discovered that "earthquakes" are nothing more than Bruce Schneier and Chuck Norris communicating via a roundhouse kick-based cryptosystem.

Group theory

[coyote-san]

Let me see if I can explain this in a few paragraphs....

A single encryption key defines a one-to-one mapping between each plaintext block and ciphertext block. (In ECB (electronic codebook) mode, but the chained block encoding follows a similar analysis.) It has to be bidirectional so that the decryption is unique.

This means that, AT A MAXIMUM, your meaningful keyspace can be no larger than the 2^(number of bits in block). In practice it takes a lot of hard work to ensure that you have 2^(number of bits in key) distinct and non-trivial mappings, and ideally for any arbitrary plaintext and ciphertext block you can guarantee that there is a unique key that will produce that result. However it's easy to screw up and only have, e.g., 2^40 actual encryptions even though you have a keysize of 64 or even 128 bits.

Double encryption also defines a one-to-one mapping between each plaintext block and ciphertext block... but you have the same blocksize. If the keys form a "group", then any double encryption will be equivalent to a single encryption with a different key. In fact any N-encryptions will be equavalent to encyrption with a single different key. Some combinations will leave you with no encryption. (XOR encryption is a trivial example of this -- you'll get no encryption whenever you have an even number of encryptions.)

Worse, your keys may not form a group because there's some property that gets cancelled out in a double encryption. E.g., maybe something drops out each time both keys have a '1' in the same spot. In this case double encryption would be significantly weaker than single encryption.

Triple-DES encryption is an oddball since it isn't (or wasn't) known whether DES keys form a group. Remember that a DES key is only 56 bits, but a DES cipherblock is 64 bits -- you know that can't get every possible mapping between plaintext and ciphertext by running through the keyspace.

Hence 3DES. However 3DES isn't simply encryption three times, e.g., the form we studied in my grad class used two (not three) 56-bit keys, in an EDE pattern. That is, you encrypt with the first key, then DECRYPT with the second key, then encrypt with the first key again. I didn't follow all of the reasoning but I seem to recall it was because of some property of the S and P boxes.

Re:Simple counterexample for your co-worker

[pclminion]

This actually raises a question to which I don't know the answer: if you take a fairly standard symmetric cypher, say DES, and two keys K1 and K2, does there always exist a key K3 such that E_K1(E_K2(Message)) == E_K3(Message) ?

No, this is not always the case. For DES it is certainly NOT the case. The terminology you are looking for is "idempotent cipher." A cipher is idempotent if it obeys the equation you stated -- i.e., for any key pair K1,K2, there is a K3 such that E_K2(E_K1(x))=E_K3(x). DES is NOT an idempotent cipher.

These questions only seem deep to non-crypto-experts (no offense to you intended) -- and it was certainly accounted for in the design of DES (along with features which harden it against differential cryptanalysis, a technique that wasn't even publically known outside the NSA at the time -- the people who work on these things are far from stupid)

DES design issues

[billstewart]

The general opinion about why NSA pushed DES to be 56 bits instead of 128 bits is that "differential cryptography" attacks weaken it to about 55 bits anyway, so in fact you're not losing anything, and the 56-bit version was more compact and easier to implement in hardware. Searching a 56-bit keyspace isn't exactly in the reach of run-of-the-mill computers - you need a whole bunch of them working together to get any speed. On the other hand, Gilmore's custom DES cracker and the distributed crack are *so* 1998. I don't know how much ASIC technology has improved since then - Pentium IIs were up to 400 MHz, compared to ~3 GHz for a typical Intel desktop today, and memory prices and performance have also improved significantly, so maybe you could use 1/10 as many machines.

Re:DES design issues

[WuphonsReach]

10x improvement over the last 10 years is about right (give or take 2 years).

A Celeron 566MHz has a memory bandwidth around 150-175MB/s. An Athlon64 3200+ has a memory bandwidth around 1600MB/s. (Approximate numbers, with all sorts of undocumented assumptions.) So it's a pretty good bet that modern single-core CPUs are at least 10x as fast as the ones from 8-10 years ago.

Of course, now we have things like dual/quad CPU machines with 2-4 cores per machine... so we could up that number to 150x as fast as a machine from 8-10 years ago. So instead of 3000 machines, we might only need 20-30.