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?
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
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:
... 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.
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
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.
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
... 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.
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.
Craft Beer Programming T-shirts
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 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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Unless said one-bit decypter doesn't tell/know when its right or not.
So, in your above scenerio, you enter 0 and get, say, 'g6bSyfS5d...' while 1 gives '3SEgvu6yt...'. Which one is correct and to be decoded with your second (1-bit) key and which one is garbage. If you don't know you'd have to try both. Giving you 4 possible results after your second key, all of which look like encrypted garble awaiting your third key...
So you actually can get a 128-bit key. Coming up with a strong 128-step 1-bit encryption algorithm is a different matter, but 2-pass 64-bit encryption algorithms are not uncommon (some programs use different algorithms for each step, so if a major flaw is discovered in one, the file still has the protection of the other).
Well, while reading these books may work for this particular problem, it is not always the case that books answer simple problems like this.
For most questions, you can read as many books as you want, but if the question is simple but stupid, you often won't find the answer.
In these cases, you often need to find someone who is very knowledgeable in the subject, or ask slashdot.
Anybody who has studies an of-campus course will realise the value of being able to ask stupid questions, and talk to knowledgeable people.
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!
2DES is not worse than DES.
Suppose 2DES is more than trivially easier to crack than DES. This means it is less work to crack something encrypted with 2DES than with DES. Take something DES-encrypted. Generate a random key and encrypt the ciphertext with it. Congratulations. Now you've got some 2DES ciphertext. Apply 2DES crack to the result. This is only trivially more difficult than if it had been 2DES in the first place. Contradiction; the premise is false. QED. (Latin for "Suck it, bitch.")
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!