Slashdot Mirror
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?
http://en.wikipedia.org/wiki/Meet-in-the-middle_at tack
That's why we have triple-DES instead of double-DES.
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.
Fascism trolls keeping me up every night. When I starts a preachin', he HITS ME WITH HIS REICH!
Each bit doubles the strength
While you're double super secret encrypting that file why not keep compressing and re-compressing it until you have it down to 1 bit as well? :-)
I see even classic Slashdot is now pretty much unusable on dial up anymore.
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
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.
echo YOUR_OPINION >
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
Better known as 318230.
- 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.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.
Boffoonery - downloadable Comedy Benefit for Bletchley Park
Consider the (naive and insecure) XOR encryption.
Take your file, encrypt it with a 16 bit number.
Take the result, and encrypt it again with a different 16 bit number.
Now, how many possible keys do you have to go through to get back the original data?
(Hint: Try single decryption using key3 = key1 XOR key2.)
This counterexample invalidates the claim that encrypting twice with an N-bit key is equivalent to encrypting with a 2N-bit key. It also demonstrates the worst possible case, that encrypting twice may be no more secure than encrypting once.
GCHQ Quantum Insert installed. If only our tongues were made of glass, how much more careful we would be when we speak
In this case, you can simply refer to the meet-in-the-middle attack as mentioned by dtfinch.
However, in the general case of debunking bogus encryption statements, it can be quite difficult. Why? Because encryption is hard, hard, hard, hard stuff. I've taken a graduate course in cryptography and all it did was reinforce how easy it is to make a mistake.
The only encryption scheme I know of that is provably unbreakable is the one-time pad. However, proper implementaion of that is a pain. Is AES secure? We don't know. We think it is, but there are researchers looking for weaknesses because we don't know for sure. It is possible, (however unlikely), that someone will develop an attack tomorrow sending everyone scrambling for a new encryption algorithm.
Reading code is like reading the dictionary - you have to read half of it before you can go back and understand it.
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.
For every complex problem there is an answer that is clear, simple, and wrong. -- H L Mencken
... as long as the keys for each pass are different and there's no header.
A good encryption scheme doesn't have any header, for exactly this reason. It reads in n words and writes out n words and that's that. So if your coworker is doing:
C = E_K2(E_K1(P))
there are indeed 128 bits of information required to decrypt the document. Given given a plaintext+cyphertext pair a meet-in-the-middle attack might be possible, but the search space is still on the order of 2^128 (cryptanalysis could probably reduce this some). Given plaintext+intermediate+cyphertext, it's down to 2^64, because each half could be cracked separately.
With a good encryption algorithm the first pass ( E_K1(P) ) generates something approaching line noise - close enough so that there's no statistical way to tell real random bits from encrypted data (many RNGs now use encryption routines to boost incoming entropy). There is no structure, there is no header, and there is no way to verify that it's an encrypted anything. It might as well be a bunch of random bits. Given the cyphertext, your total search space to find the plaintext is still 2^64 * 2^64 = 2^128 sets of keys because there's no way to tell that the first round was performed correctly - it will always just be random bits.
Now, if there IS a header added you're back to n*2^64. For example, the software compresses (and thus adds a header to) the data before encrypting it. Given the cyphertext you can search for keys that decrypt to have a valid header, and then search for keys that produce reasonable english text from those outputs.
Sometimes things do what your mathematical intuition tells you, if you're mature enough in the field to have a solid intuition, but often they don't. Problems can be very hard if looked at from one direction and very easy (or at least less hard) when looked at from another direction, and a cryptographer's job is to make sure they've checked out _all_ the directions because it only takes one weak one to break something. NP-complete problems are especially that way - they're potentially useful for crypto because there's one easy direction if you know the key, but many problems can't be transformed in a way that you can use the easy path and the attacker's stuck on the hard paths.
But even the bit-twiddly algorithms, like most hash functions or the S-box building blocks inside Feistel-structured algorithms, can often be cracked by people examining them closely enough to find conditions under which they can deduce bits. For instance, MD5 is pretty much busted these days.
And both mathematical crypto and bit-twiddly crypto has to worry about Moore's Law and brute force - some algorithms scale well, so you can double the strength of an N-bit key by adding 1 bit or maybe logN bits, while others don't, or they form groups so that encrypting a message multiple times with an N-bit key still only gives you N bits of strength (leaving aside pathological cases like rot13.)
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
The Handbook of Applied Cryptography is an excellent book and is now available online for free. If you passed a couple college calculus courses, the material should be very accessible to you. In general, it's an excellent source of facts and analysis to debunk incorrect statements about cryptography.
:-).
In particular, the part that answers you question is found in Chapter 7 (block ciphers). The justification for fact 7.33 explains why, if you can store 2^64 blocks of ciphertext, you can break double 64-bit encryption in 2^64 operations.
If your coworker is not capable of understanding the math behind this reasoning, he really should not be making decisions about encryption
(Note: I'm not witholding the justification in this post simply to be obtuse. It's too much of a pain to format it reasonably in this input box... you'll just have to refer to the PDF.)
.sig: file not found
This is how I usually end this kind of conversation -- I go over their head. If I know more than they do about the subject, I speak jargon until their eyes glaze over, and then say something to the effect of "Do you really want to know why you're wrong, or will you take my word for it?" I'm a good enough teacher to back that up if they really do want to know. Or sometimes I start from the other end -- if I have a good enough analogy ready, I can start with that -- the money one is a good analogy for the crypto (Would you rather give me two $10 bills or one $100 bill? Would you let me settle a $100 debt with you by giving you two $10 bills?)
The other method of going over their head is to cite someone -- not always even a specific person -- who is smarter than both of us. So for crypto algorithms, I can ask them, "If it was really that easy, don't you think someone else would've thought of it by now? Why do you think we invent wholly new algorithms for 128 bits?"
And if both of those fail, the final method of going over their head is to cite specific sources and papers, and invite them to actually disprove what's said there (without really having to understand it yourself) if they really think they're right.
All of these, of course, are when I knwo I'm right. Quite often, I really don't know, and I stay humble there. But when I know I'm right, it's usually much more important to hit them over the head with one of the above than to try to explain why I'm right. After all, you don't have to know why a car is safer than open air for a lightning storm, you just have to do it. It's not important that someone understand why not to just double-encrypt with 64-bits, it's just important that they not do it.
Don't thank God, thank a doctor!
And how do you know, that you guessed right at every step? No, really. Good crypto doesn't let you distinguish from decryption with good or bad key, other than the content of the plaintext. And since the plaintext in this case is crypted text for another step, you have no chance of finding out, if it's right. So in reality, you have to check key 0 and 1 in first step, 0,1 for 0 from first step and 0,1 for 1 from first step etc...
Do the math wise ass, complexity of brute-forcing 128 1-bit passes is the same as complexity of brute-forcing single 128-bit pass -- 2^128
RobertBastard Operator From 193.219.28.162
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.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
I hope you were suggesting the "Each bit doubles the strength" as one of the bogus assertions, not one of the true ones. For some kinds of algorithms, against some kinds of attacks, it's true. For algorithms like RSA and Diffie-Hellman that have some special properties to the keys, doubling the strength may require adding LogN bits. Some algorithms don't have variable-sized keys, and some of those that do aren't very good at using them - they're as strong as they are, and piling stuff on doesn't change the weaknesses, like rot-26. Some algorithms are groups - combining R rounds of N-bit keys just gets you the equivalent of one round with a different N-bit key.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
You can buy a briefcase with two separate, three-digit combination locks in any stationery store, and it won't cost you a lot of money. Invest in one as a "prop" for this demonstration. Have your co-worker set a combination for the left-hand lock and a different combination for the right-hand lock, lock the case and spin the wheels randomly. Now, there are 1000 possible combinations for the LH lock and 1000 possible combinations for the RH lock, giving you 1000000 possible combinations. If you can try one combination a second, it could take you up to 9 months to get into the case. Right? {If your co-worker actually believes this, perhaps it would be simplest just to have them put to S-L-E-E-P}.
Once you have cracked the left-hand lock {which will take at most 1000 tries - 17 minutes} you are free to concentrate on the RH lock {which also will take at most 1000 tries}. You don't have to try anymore combinations on the LH lock. So you can open the briefcase in a maximum of 2000 tries, or just over half an hour. The key fact that makes this possible is that the two locks are independent: you can undo one while the other remains fastened. The combined keyspace is then the sum, not the product,of the two keyspaces.
If the encryption operation adds a predictable header to the ciphertext {for example, BEGIN OPHIOL ENCRYPTED MESSAGE} {and most of them do} then you have something to look for that will let you know when you have cracked the first layer of encryption -- in effect, popped open the left-hand lock.
Je fume. Tu fumes. Nous fûmes!
That's a potential problem with any mechanical combination lock: if the turny bit of the mechanism isn't properly decoupled from the locky bit, then you can identify a partial solution and so decrease the search space. But if it is too well decoupled, then the lock will give false positives or false negatives. Some of those cheap briefcase locks are actually quite poorly decoupled: you can feel just a little bit more movement when any one of the wheels is "solved". {Which is why that episode of Only Fools and Horses was a bit unrealistic.} Even although this can take more than a second a try, just getting the search down from 1000 tries to 30 tries is a good improvement in its own right.
Je fume. Tu fumes. Nous fûmes!
Let's make sure we're on the same page. In order to perform the "meet in the middle" attack, you first need to have a known Plaintext and Ciphertext pair, P and C. In our example, we'll assume these are 64 bit blocks, or 8 bytes. We're also assuming that the keys are 64 bits.
For each possible 64-bit key K, you need to generate and store Ek(P) in a table. It's the size of that table I was trying to calculate. So that's 8 bytes * 2^64 keys, which is 147,573,952,589,676,412,928. That sure looks like 147 Billion Billion to me.
In any case, even using your figure of 2.2 Billion GB, you've still got the number of drives very wrong. When you divide 2.2 Billion by 750, you get 2.9 million drives required. First of all, that's probably larger than the total production run of those drives. Second, it's much more like $1.1 Billion, rather than $1.2 Million, in cost.
I don't think hard drives are going to be the way to go. A decent tape library can hold 500 Terabytes or so, so you'd only need to buy (and power, and house) a mere 300,000 of those to hold the whole table.