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.
Encrypting a single document multiple times in that way is like using a piece of duct-tape to keep a box closed. Putting another strip of duct-tape directly over the top of the previous strip does not make the box any harder to open.
:-)
Of course this is just an analogy from a non-expert... Use at your own risk.
Hexy - a strategy game for iPhone/iPod Touch
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
If you encrypt a file and then encrypt the encrypted file all that has to be done is crack 2 layers of the same type of encryption. Try it on a file ive tried it before.
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.
Encrypting a message twice with 64-bit encryption only makes the message twice as hard to crack. Encrypting a message with 128-bit encryption instead makes it 2^64 times as hard to crack. So your friend's conclusion is off by a large factor.
- 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
I wonder if he goes through the trouble of making up two different keys or just uses the same key twice.
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
> What other laughable claims have you heard attributed to encryption, and how were you able to properly lay them to rest?
Well, after all these years I'm still shocked at how often I hear someone refer to "XOR encryption". As for laying them to rest though, you really shouldn't have to. I can come up with thousands of ways to mangle data and claim it's encrypted...but the burden would be on me to prove that any of the methods were reasonable encryption. In my opinion you're probably best to just avoid conversations like this because you're certainly not going to make any headway with someone who knows so little about the field.
This sig intentionally left blank.
Wouldn't this be like matrix multiplication? One can multiply any set of same dimensional matricies and have a single matrix at the end. Thus you can provide translations and rotations to a large set of points using this final matrix instead of applying each matrix to each point.
I do not know, but I would suspect that for double encryption by a 64 bit key could be decrypted by a single key different from each of the original keys.
This is right on the money, and far more correct than pretty much everything else I've seen posted here. It's even a first post! What's not to love?
There's a reason why triple encryption is used rather than double encryption. There's a technique known as the Meet-in-the-middle attack which, by trading off storage space for time, you can break a double encryption with two independent keys using only twice the time needed for single encryption, meaning that using two independent 64-bit keys would only require 2^65 work, rather than 2^128 as one might expect. That's the reason why you never hear of "double DES" but rather Triple DES with independent keys.
Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
Ask him if encrypting something with a 1 bit key 128 times is equally secure.
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.
Is to show how two rounds of the Caeser Shift
Is exactly equivilent to 1 round of the same, with a different key,
and no harder to crack. In fact, if your key is the same length as
your alphabet, it would be the plaintext again.
emt 377 emt 4
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.
Is everybody here retarded?
, 000
Okay so a 64 bit key has 18446744073709551616 possible combinations (2 ^ 64).
A 128 bit key has (2 ^ 128) has roughly 3,402,823,669,209,384,634,633,746,074,317,700,000
combinations
encrypting a 64 bit file TWICE means you get
2^64 * 2 = or 36893488147419103232
Effectively -- 65 bit encryption.
Albiet this is dramatically oversimplifying the type of attacks, etc. I feel dumber for even reading this question.
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
Well, we all know that 2^5 = 32.
So, if we take your slashdot userid of 318230 and multiply by 32 we get 10,183,360 (you can stop checking the math after this).
So, take 10,183,360 and re-write as 10 18 33 60 and then translate those four characters into "WEST" and it is perfectly clear that he is one of them!
I don't have to spell it out! Mr. East is leading you the wrong way, because you are getting too close!
This issue is a bit more complicated than you think.
As with any simple question, there's not a truly correct straightforward answer. First off, encryption strength is not just about the number of bits. A larger keyspace is preferably to ward off brute force attacks, but no system has eliminated the risk of a skilled and determined cryptanalyst.
Once you've established that bits aren't the only answer, start poking holes. For example, a guessable header produced by the first round of encryption would be known plaintext to work against the second round. As mentioned by others, the cipher itself may be vulnerable to an algebraic attack. Certain types of ciphers operate in such a way that the second round only changes the key needed to obtain the original plaintext C(k2,C(k1,P)) = C(k3,P)
Start poking holes in their knowledge of cryptanalysis.. that's the key to the argument.
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
"So the algorithm's Open Source, right?
Doesn't that mean that we don't have to protect the keys?"
This in reference to a 3DES application...
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!
The basic problem is that if you do E_KB(E_KA(plain_text)), there may be a key C with
E_KC (plaintext) = E_KB(E_KA(plain_text))
If you just encrypt 64 bit with an one-time pad (trivial example), then this is obvious:
C = A XOR B
I.e. with one-time pad you gain exactly no security at all.
For many ciphers, a key C may not exist, but even if it does not exist, an attack on E_KB(E_KA(plain_text)) may be just as easy as on a single key. What is worse is that for some ciphers (e.g. DES) it is not known whether double encryption with two different keys is more secure or not, and how much it is more secure.. Until this is known for a cipher, it has to be assumed that encryption of each block with two keys is not more secure than single encryption.
However there are ways to make a cipher more secure if you have more key material. For example you can use one part as the key and one part as the IV for CBC. Or you can split the message, and encrypt each part with a different key. That gives the attacker a bit less material to work with. Or you can use the keys with different ciphers and stack those on top of each other. If the ciphers are used in stream mode, then the result is provably as secure as the strongest one.
You can also mix in any extra key material as additional data blocks, e.g. in CBC. This again makes a ciphertext-only attack much harder.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Okay, lets play a game. Get your boss to write down 2 letters. You and your coworker have to guess the 2 letters.
You can guess the letters one at a time (i.e. "is the first letter 'a'?").
Your coworker has to guess the letters two at time (i.e. "is the phrase 'aa'?")
Generally speaking, who wins?
See the subject.
Actually, people that develop ciphers go out of their way to make sure the scrambling algorithms they use are not groups, or fields or other simple to analyze mathematical abstract algebraic construct like matrices. If a cipher was a group or a matrix, then repeated operations wouldn't be very secure (e.g., 3des would be pretty must just des with an alternate set of keys) just like a sequence of matrix operations can be replaced by a composite matrix.
Of course a cipher being a mapping function that maps it's input set to an equivalently sized output set will generate a high-dimensional permutation group, but that's subtly (but significantly) different than being a group or matrix...
Think of encryption as having a bunch of switches which can be off or on lined up in a sequence. In order to break the encryption, you have to somehow be able to guess the exact position of each and every one of these switches. In the case of 64-bit encryption, you have 64 of those on or off switches. In the case of 128-bit encryption, you have 128.
For those who aren't mathematically inclined, what you effectively have is 2 as your base number (on is one, off is another one, thus two total positions for each switch) and the total number of switches is your exponent (remember from 8th grade math, 2^3 = 2*2*2, if you had three switches that is.) If you are still lost, put it this way: 64-bit encryption is 2^64 different possibilities, and 128-bit encryption is 2^128 different possibilities. Thus 128-bit encryption is 18,446,744,073,709,551,616 times stronger than 64-bit encryption.
If you encrypt in 64-bit, and then encrypt it in 64-bit again, you only double the strength as you are basically adding 2^64 plus 2^64, which equals 2^65, or 65-bit encryption effectively. Whereas 2^128 on the other hand, is actually 2^64 times 2^64. So if your friend wanted to achieve 128-bit encryption this way, he would effectively have to encrypt that 64-bit file 64 times, not just two times.
Now 2^64 may sound like a pretty big number, but with computers being as fast as they are today, we always can factor (or in laymens terms, "brute force") the encryption keys in order to figure out what that switch sequence would be at a pretty fast rate, so that number isn't really that large in the grand scheme of things. However, if it is 2^64 times that amount, then that number suddenly becomes much much larger, and thus takes exponentionally longer for an everyday home computer or even a cluster of computers to break.
To cryptography know-it-alls: I know, this is an oversimplified explanation, but it completely answers the full scope of his question, so spare me of the "but you forgot this" or "you can break some encryption without factoring" replies.
Careful with names containing L slashdot.org/~AiphaWolf_HK slashdot.org/~AlphaWoif_HK slashdot.org/~AiphaWoif_HK
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
I'm a casual observer in this field, so someone correct me if need be.
Typically, with encryption, the time required to brute-force attack is exponential to the number of bits. So:
let n = the number of bits in the encryption key
let t = time required to crack said encryption
and a = an arbitrary constant
typically t is proportional to 2^n.
So, when you encrypt with a 128-bit key, t = a * 2^128
But if you use a 64-bit key twice, then t = 2a * 2^64 = a * 2^65 since all you have to do is crack a 64-bit key, then crack another.
As you can see, using two passes with a 64-bit key is 2^63 times worse than just using a 128-bit key once.
Out of those factorial(2^N) keys, only a very very very very very few are actually used, since the key size is nowhere near that large. In AES, for example, the block size is 128 bits, but the largest key size is 256 bits, even though the number of possible keys is 128!. This means that given a random plaintext/ciphertext block, it's actually very improbable that you'd find a key to generate that result.
The only reason that double encryption doesn't provide "double security", is that a meet-in-the-middle attack is possible (see other comments for more details), and that kind of attack only takes twice the time (on average) than a brute force attack on a single key. 3DES provides more security than regular DES, since a meet-in-the-middle attack on 3DES makes its security roughly equivilant to using a 112 bit key (56*2), and that's still too large to be practically broken by brute force alone.
A block cipher uses a key to map plaintext blocks to ciphertext blocks. Given 2^N plaintext blocks and 2^N ciphertext blocks, the number of possible encryptions are 2^N!, not 2^N. This is a staggering difference in magnitude.
For example, the maximum keysize of a 128 bit block cipher is about 10^22 bits.
If there is no known plain text in the second pass of the encryption, how do you know you've broken the first pass?
...
In effect, if there's no fixed header, no way to quickly distinguish a random putative clear text from rubbish added in between the two encryption phase, then in effect a brute force attack would take 2^64*2^64 steps, that's to say 2^128
Encrypting something twice is effectively creating a new cypher system. Always remember Friedman's remark, "No new cypher is worth looking at unless it comes from someone who has already broken a very difficult one."
(If you don't know who William Friedman was, you probably shouldn't be designing cyphers.)
No, it's not "equivalent", but he is closer to the truth than you are and something like this is widely used in practice. Look for "Triple DES" on Wikipedia for a longer description of the consequences of encrypting multiple times with the same algorithm.
To crack the first pass you have to find a key among 2^64 possibilities. Then you do the same search for the second pass. So your search space is 2^64 + 2^64 = 2^65. Hence encrypting twice with a 64 bits key is the same as encrypting once with a 65 bits key.
The sooner you fall behind, the more time you have to catch up.
There are a bunch of technical explanations here. Let me make a simple analogy.
If you have a lock on your door, which has only 100 different keys, a thief could take 100 keys along, and break in. Suppose you find this "100 keys" too easy, and install a second (100-key) lock.
There are now 10000 combinations of key1 and key2.
Do you expect the next thief to take along 10000 keyrings, each keyring having two keys one for the first lock, one for the second lock, or does he come in with 200 keys?
In the mechanical world, you would have to make a locking mechanism such that you cannot test the validity of either key without the other key being correct. The same goes in cryptography. This is not simple.
In practise it's easy to say: There are so many combinations to try. But the smart guys try to find ways not to have to try all of them, and in cryptography, it is difficult to devise schemes that actually succeed in preventing the bad guys in doing just that.
Isn't this discussion of exploitable weaknesses in encryption technology in violation of the DMCA?
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
First of all, what is a '64-bit encryption algorithm'? Is this a symmetric or asymmetric algorithm? Is it a block or stream cipher? Are you talking about block or key sizes? What specific algorithm are you referring to?
We can't analyze anything if all we're given are vague generalizations like "a 64-bit algorithm" and "a 128-bit algorithm". Some symmetric ciphers gain security under functional composition. We know that DES is one such cipher, since it has been shown that DES is not a group. However, it is not true in general that symmetric ciphers gain security under composition. For example, no matter how many times you encrypt something using a Caesar cipher (a generalization of ROT-13), there will always be a single key that decodes the resulting ciphertext. Ask your coworker to show that the specific algorithm you're discussing is not a group. If he can't, then what reason do you have to believe that you gain any security through what he proposes?
The second problem here is that your coworker seems to think that the onus is on you to prove that a given system is insecure. Every time an expert invents a new cryptosystem, there is a good chance that the system will be insecure; It is a near-certainty that any cryptosystem your coworker comes up with will be insecure. Bruce Schneier brought up this topic again in this month's Crypto-Gram :
Thirdly, even if your coworker's new cipher design---and that's what it is---miraculously has the security properties that he thinks it does, is that enough? If you're using 128-bit keys in a symmetric cipher, you're only getting 64 bits of security, thanks to the "Birthday Paradox". If you want an attacker to have to perform 2^128 steps to brute-force your key, then you should be using 256-bit keys anyway. Justin Troutman explains this in more detail in his two-part series, "Ideal-to-Realized Security Assurance In Cryptographic Keys".
Finally, all this talk about composing cipher primitives might well be irrelevant. What is this cipher being used for? Disk-based encryption, for example, has vastly different requirements than a typical secure channel. (See New Methods in Hard Disk Encryption for a discussion of some of the issues associated with hard disk encryption.) What mode of operation are you using? What are you using for authentication? How much information does your cryptosystem leak? How are you negotiating what protocol you're using? To what extent is your protocol switch vulnerable to a chosen protocol attack? What about implementation issues?
I suggest that your coworker read the first two chapters
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
enough analogies already. it seems like most of the people who say "it's just like if". don't trust the people who make analogies, trust the people who can explain the answer in the terms of the question. also, don't listen to some who says that the "simple answer is", and then writes 8 paragraphs.
simple answer is that your friend is not entirely wrong. everyone here using the 64+64=65 is wrong unless they mention that that only occurs in some cases where a thing called a "meet in the middle attack" can be used. if that attack can't be used, or the person trying to crack your password doesn't have on the order of 10^19 bytes of storage available (i know hard drives are cheap, but c'mon now), then due to the fact that you don't get a green light that says, you cracked the first of the two keys, now crack the second one, encrypting twice does more than double the number of keys you have to try. but then you get into group theory, which affects us in the same way as if i said, take the number 42, then add a random number between one and ten to it, and then add another number between one and ten to it. I don't have to guess both of the numbers (100 possible combinations), I'd just have to guess the sum of those two numbers (20 possible combinations). Similar things happen when you encrypt twice using two different keys that are in a group, that is i don't have to guess both the keys, as there'd be another key that would be equivalent to encrypting with the two keys. it's more complicated than that, but on the same vein, and you can look it up if you're interested.
ummmmm, i mean, it's like if you have a bunch of switches, and pools of lava, and each switch makes a tiger appear from a door and then 64+64=65.
cheers.
But 64 bits? There are a few algorithms that have variable key lengths that work at that size (RC5 is pretty strong), and then there's DES where you're counting the 8 parity bits as part of your keylength, but most of the 64-bit algorithms I've seen were things people hacked together to deal with US export laws. One choice was RC-4 - it's a reasonable algorithm, and scales well, but there are things you're not supposed to do with it, and PPTP and WEP went out and did them. It's not as weak as 40-bit crypto, but it's still weak.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Why dick around with your own encryption: use AES. Then you can tell your customers that you are using the standard suggested by the US government. There are free implementations available in many languages. You will be doing the best thing for your team and your company.
If you are worried about CPU, memory, etc, remind yourself that the criteria for selecting the AES algorithm included CPU usage, memory usage, and the ability to be implemented on silicon.
Note to ACs: I won't mod you up, even if you are being funny or insightful. So take a chance! It's not real life!
If you "randomly" select a cryptographic system for each stage of the process then you can increase the security of the system. You have to include the systems and in what order they were used in the key. Its down side is that if the number of crytographic systems are not to a power of 2 you are wasting space in you key. On the plus side you remove the problems of each cryptosystem. The attackers knowledge is reduced (depending on your PRNG) and as it doesnt rely on one cryptographic system for its security if the attacker knows an exploit for a system it will reduce the security but should not remove the security completely.
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!
What other laughable claims have you heard attributed to encryption
99% of the responses to this article.
A given 64-bit cipher might be 128-bit strong when doubled. Or it might be a little bit more strong. Or it might be no stronger. Or it might be less strong. There are simple examples for each case (one-time pad has the first property; DES has the second; using the same key twice has the third; ROT-13 has the last).
The initial statement is certainly wrong in the general case but it's hardly laughable, especially compared to several people's efforts here to show that it is wrong in every case.
"What other laughable claims have you heard attributed to encryption, and how were you able to properly lay them to rest?"
Simple, I watched Swordfish and learned everything I needed to know about encryption.
"The only encryption scheme I know of that is provably unbreakable is the one-time pad."
A curious thing about that: In theory, the one-time pad is provably unbreakable. In practice, no specific implementation of a one-time pad is provably unbreakable. The problem is that there is no provably unpredictable source of data for the pad.
In this sense, cryptography is remarkably tidy science; a claim that a particular system, even a one-time pad, provides a particular level of security cannot be proven—only falsified. Our confidence in any particular system is based on it having survived cryptanalysis by many experts, at which time we accept the claim as a usable theory—not as proven.
I'm a Programmer. That's one level above Software Engineer and one level below Engineer.
My father worked in military communications just prior to the Turkish invasion of Cyprus. Based on the few comments he has made on the subject - and it's harder to get information from him than from a Microsoft manual - the British used one-time pads on tape. Both tapes would be generated in parallel, one would then be delivered by courier, and each tape would have enough garbage at the front to guarantee the tapes were synchronised. (They could not be aligned simply on the Nth word on the tape, the tape machines themselves had to be configured to work at identical speeds, as there was no clock to synchronise with and it was intended to work on a lossy network.) Once the tapes were used, they were suppsed to be destroyed, though it wasn't completely clear to me if that always happened.
This was only one of several cipher machines they used, but my impression was that the bulk of encrypted information went via one-time pads despite the problems with getting the tapes to the other person and despite the enormous overheads of retuning everything in the system.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
And all other posts down.
64 bits is really 2^64 possible keys. 128 bits is 2^128 possible keys. Double-64 bits is, at best, 2*2^64 = 2^65 = 65-bit encryption. (And often is just 64.)
Use a traditional Vigenère cipher (basically a Caesar cipher with words instead) to see what happens. First with a 6-character key:
I H A V E B A B Y F O R M U L A
+G W B U S H G W B U S H G W B U
=O D B P W I G X Z Z G Y S Q M U
Then with two 3-character keys:
I H A V E B A B Y F O R M U L A
+T S A T S A T S A T S A T S A T
=B Z A O W B T T Y Y G R F M L T
+C I A C I A C I A C I A C I A C
=D H A Q E B V B Y A O R H U L V
Note that in effect your key is still 3 characters. You can decode this in one pass using TSA + CIA = VAA:
D H A Q E B V B Y A O R H U L V
-V I A V I A V I A V I A V I A V
=I H A V E B A B Y F O R M U L A
And as somebody else said, 128 1-bit encryptions is nowhere near one 128-bit encryption.
Even easier: if performing two 64-bit encryptions is the same as one 128-bit encryption, are you saying that performing a 1-bit encryption 128 times is just as secure?
Want to improve your Karma? Instead of "Post Anonymously", try the "Post Humously" option.
THe first obvious thing is that with a brute force attack you have
to check 2^128 keys if you got a 128 bit key.
For two 64 bit keys, you need to check 2^64 + 2^64 keys.
That's a hell of a lot less than 2^128.
(there's other more valid reasons as to why it's weaker:)
I think you'll find that DES is a group, which is why in 3DES the second round of encryption is run backwards (it's actually decryption under a different key). 3DES works like this:
...etc... ...total strength would always be 56 bits, precisely because DES is a group, as noted by AP.
Round 1: Encrypt under key 1
Round 2: Decrypt under key 2
Round 3: Encrypt under key 3
The total strength is roughly 3*56 bits (slightly less, IIRC).
That's the more secure and more expensive 3 key option. The 2 key option uses this:
Round 1: Encrypt under key 1
Round 2: Decrypt under key 2
Round 3: Encrypt under key 1
The total strength is roughly 2*56 bits (slightly less, IIRC).
The reason round 2 uses decryption is that DES is a group: If one were to do the following...
Round 1: Encrypt under key 1
Round 2: Encrypt under key 2
Round 3: Encrypt under key 3
Round 4: Encrypt under key 1
Round 5: Encrypt under key 2
Round 6: Encrypt under key 3
myvirtualid acting as an AC
From the Wikipedia article:
If the keysize is n, this attack uses only 2^(n + 1) encryptions (and O(2^n) space) in contrast to the naive attack, which needs 2^2n encryptions (but only O(1) space).
So for a 64-bit key and 64-bit block size, you'd need about 2^64 * 8 bytes of storage, which is 148 Billion Gigabytes. I doubt you could find any off-the-shelf storage solution you could use for that.
OR am I missing something in my calculation?
See "Parallel Collision Search with Cryptanalytic Applications" by Michael Weiner and Paul C Van Oorschot - you can get away with far less storage by iterating the key -> ciphertext map.
Xenu loves you!
Reminds me of the old cylinder bicycle locks. I had one with four spinners on it, but my friend broke it in a couple minutes. The problem was that when you got one number right, you could feel that the cable moved a little differently so you knew it was correct.
What other laughable claims have you heard attributed to encryption,
That a product does not need ssh when telnet can only be enabled by a super_secret web get.
I had no usefull response. It was laughable, but I wasn't laughing. Luckily, the things I said were not really intelligible.
I think you underestimate just how much I just dont care.
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.
Isn't this obvious?
Stupid comment poster ate my <<...
$ bc
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
2 * 2^64
36893488147419103232
2^128
340282366920938463463374607431768211456
Enough said.
The biggest issue is how much you trust your people. Since most corporations pretty much poop on their employees, it's no wonder that they're running scared. They lay people off just so that some upper managment dufus can be sure to get his bonus this quarter. They cut wages on the rank & file so that the CEO can keep his Manhattan penthouse. In a corporate culture like this, it's no wonder that the rank and file feels very little loyalty to the employer. The employer has absolutely none for them.
Axiom #1 - There is no such thing as unbreakable security.
Axiom #2 - Where there is a will, there is a way.
Myth #1 - Encrypted email is secure.
Phooey! Once it's sent, it's in the receivers hands. They can do what they want with it, including forward it on, after it's decrypted.
Myth #2 - Our can't have the data compromised. We don't allow print outs, etc.
HAH! If you can display the data on a screen, you are hackable. It's lo-tech, but it works. I can always take a photograph of the data. If nothing else, we can thank the guys that brought us camera phones.
Myth #3 - Our -bit encryption is good enough.
Ummm....have you guys seen what you can do with a beowulf cluster? It really isn't that hard and doesn't take all that much time. Plus there are some good how-to documents on the 'net. Besides that, a lot of the security of the encryption depends on the algorythm used. If that's faulty, it may take five minutes instead of five weeks.
Myth #4 - Encrypting everything will solve our security problems.
Really??? Let's see...you want to encrypt everything. Nifty... If all you data is encrypted and no one can read it, your employees can't do their jobs. If they can't work, we may as well send them home. Without the employees, we don't need the managers either so we may as well just shut the doors. What??? Oh, you *do* want them to have access. Well, then what's to stop them from doing something untoward with the unencrypted information. Why is that important? Well, most compromises are from within not without.
I can't even begin to think of all the completely retarded statements I've heard come out of some PHB who thinks that he understands encryption and data security. In the end, it all still boils down to the people. Do you trust your employees or not? Have your management policies pooped on them too many times or not?
2 cents,
Queen B
HDGary secures my bank
You can pretty easily see this with linear congruential methods; it's harder to prove this sort of thing for the common encryption algorithms.
The whole reason why people adopted 3DES, which is a three-time superencryption application of DES, is that DES is not a group for multiple applications, meaning that you do get "more encryption" when you apply it multiple times.
We don't know what algorithm was being used in the original poster's situation, so we have no idea whether multiple applications of the algorithm do any extra good or not.
If it "is a group," then multiple applications are completely worthless. If it isn't, then multiple applications might be hoped to provide some additional strength, but we don't know offhand whether an extra 64 bits of key provides 1 bit worth of extra protection, or if it provides a full 64 bit improvement.
If you're not part of the solution, you're part of the precipitate.
And that is an at most case scenario. It is simple math.
64 bit key 2^64= 18446744073709551616 combinations.
2 64 bit keys have then have 2 x 64 bit keys 2*2^64= 36893488147419103232
2*2^64 = 2^65 = 65 bit key.
And that explaination does not even go at all into the issues with different encryption algorithms, collision based attacks, or lookup table attacks, it is from a purely numbers only approach dealing with brute force only attacks. You would need to encrypt the file 64 times for her to have an equivelant(sp?) to a 128 bit key.
We were all warned a long time ago that MS products sucked, remember the Magic 8 Ball said, "Outlook not so good"