Breaking DES

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