My understanding of how an exhaustive search on the key space can be used to break DES is that for every key, K, D(K,Cipher) is applied until the output matches something legible. Say that some random string, to be thrown out, is added to the beginning of the plain text, and that DES is applied in cbc mode, then how could such an attack work? My point, I don't see how DES can be broken if the initial block is a grabage block, and cipher block chaining is used. Please enlighten me (gently). One other point... is the decision to encrypt - decrypt -encrypt when applying triple des arbitrary? Why not just encrypt with k1 and then encrypt with k2. Isn't the effect the same? Thanks a lot, Wonderer ------------------------------------------------------------------------- To find out more about the anon service, send mail to help@anon.penet.fi. Due to the double-blind, any mail replies to this message will be anonymized, and an anonymous id will be allocated automatically. You have been warned. Please report any problems, inappropriate use etc. to admin@anon.penet.fi.
wonderer wrote:
One other point... is the decision to encrypt - decrypt -encrypt when applying triple des arbitrary? Why not just encrypt with k1 and then encrypt with k2. Isn't the effect the same?
Encrypting with k1 and then k2 leaves you open to the "meet in the middle" attack. Say I get a copy of the plaintext and ciphertext. I could encrypt the plaintext with 2^56 keys, and decrypt the ciphertext with 2^56 keys. Then by matching results of the above steps, I could figure out k1 and k2. The work for this attack is 2^56 + 2^56 = 2^57, which suggests that double encryption doesn't increase the complexity of breaking your text very much. It only increases it from 2^56 to 2^(56+1). So if you use the same k1 and k2 for all your documents and it is worth my time and money to figure out k1 and k2, favoring double encryption over single encryption doesn't make much sense. Otherwise, there was fear that DES was a group (encrypting with k1 and k2 is equivalent to encrypting once with k3), but I think this got buried (?) recently. Also, with the triple encrypt-decrypt-encrypt, if you pick the same key for each step, it is equivalent to just single encryption. Which may be of importance in compatibility issues, etc. -- Karl L. Barrus: klbarrus@owlnet.rice.edu keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5 3D F3 93 7E 81 B5 CC 32 "One man's mnemonic is another man's cryptography" - my compilers prof discussing file naming in public directories
Karl Lui Barrus says:
Encrypting with k1 and then k2 leaves you open to the "meet in the middle" attack.
Say I get a copy of the plaintext and ciphertext. I could encrypt the plaintext with 2^56 keys, and decrypt the ciphertext with 2^56 keys. Then by matching results of the above steps, I could figure out k1 and k2.
Tell you what, Karl -- when you build the device that can store 2^56 encryptions, let us know. You'll make a mint in the storage technology business. Also let us know how you'll index and fetch the encryptions in any reasonable time while you are at it, but by comparison thats a tiny problem.
The work for this attack is 2^56 + 2^56 = 2^57, which suggests that double encryption doesn't increase the complexity of breaking your text very much.
Karl, are you sure that you want people to think you believe this? Perry
"Perry E. Metzger" writes:
Tell you what, Karl -- when you build the device that can store 2^56
I have 1/72nd of that storage capacity in the next room, using off-the-shelf technology. Also, 8GB RAM, and another 300-500GB of 'fast' storage local to the CPU. (Cray C90, 1GW main memory, .5TB drive storage of various types, 9 tape silos) Again, all off-the-shelf technology. Tape robots are a few years old, actually. :-)
J. Eric Townsend says:
"Perry E. Metzger" writes:
Tell you what, Karl -- when you build the device that can store 2^56
I have 1/72nd of that storage capacity in the next room, using off-the-shelf technology. Also, 8GB RAM, and another 300-500GB of 'fast' storage local to the CPU.
My bogometer just triggered, so I decided to check your math. (2^56)*8 = 576,460,752,303,423,488 ((2^56)*8)/72 = 8,006,399,337,547,548 or eight quadrillion bytes.
(Cray C90, 1GW main memory, .5TB drive storage of various types, 9 tape silos)
Gee, half a terrabyte. Thats 16,000 times less than you claimed.
Again, all off-the-shelf technology. Tape robots are a few years old, actually. :-)
Your off the shelf slow speed tape technology isn't even 1/16,000 of what you claimed, and its over a million times less storage than you would need, in *RAM*, for the proposed task. Perry
"Perry E. Metzger" writes:
My bogometer just triggered, so I decided to check your math.
As I said, I was off by a few orders of magnitude or so.
(Cray C90, 1GW main memory, .5TB drive storage of various types, 9 tape silos) Gee, half a terrabyte. Thats 16,000 times less than you claimed.
The .5TB is *local* storage. The 9 tape silos hold a couple of terabytes, uncompressed.
what you claimed, and its over a million times less storage than you would need, in *RAM*, for the proposed task.
Wouldn't need to be in RAM. Would interleave the search in some banks with loads of data into other banks. Stream the damn thing.
Perry E. Metzger wrote:
Tell you what, Karl -- when you build the device that can store 2^56 encryptions, let us know. You'll make a mint in the storage technology business. Also let us know how you'll index and fetch the encryptions in any reasonable time while you are at it, but by comparison thats a tiny problem.
Maybe I'm being overly sensitive, but lately some of my posts are getting attacked for being wrong or impractical. I did not invent the cut-and-choose protocol (previously described as incorrect), nor did I invent the "meet in the middle" attack outlined in a previous post which Perry has so eloquently described above as infeasible. I am just passing along information about an attack against double DES which demonstrates that double DEs encryption does not increase complexity very much at all.
Karl, are you sure that you want people to think you believe this?
"I" do not care what "people" think of "this" attack, since it is valid and I didn't invent it. So maybe it's only of theoretical interest, sort of like differential cryptanalysis against the DES - which requires 10^47 chosen plaintexts. Why don't you mail Biham and Shamir that their method sucks. It's fairly infeasible as well. I think I need a long vacation from this list. Naturally, I'm not so egotistical to think anybody gives a damn. -- Karl L. Barrus: klbarrus@owlnet.rice.edu keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5 3D F3 93 7E 81 B5 CC 32 "One man's mnemonic is another man's cryptography" - my compilers prof discussing file naming in public directories
Karl Lui Barrus says:
So maybe it's only of theoretical interest, sort of like differential cryptanalysis against the DES - which requires 10^47 chosen plaintexts.
Why don't you mail Biham and Shamir that their method sucks. It's fairly infeasible as well.
It *IS* infeasable, and they realize it. The breakthrough was differential cryptanalysis itself, and the discovery that DES was fairly resistant to it. The fact that they made ANY crack in it was kind of neat, by the way. A huge number of chosen plaintexts is of course pretty much not possible in practice, especially since you might not get any chosen plaintexts at all! Perry
participants (4)
-
an41418＠anon.penet.fi -
jet＠netcom.com -
Karl Lui Barrus -
Perry E. Metzger