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.

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.

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.

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.