Re: Breaking DES

[smb@research.att.com]

	  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).

The decryption equation for CBC mode is

	P[n] <- D(C[n]) ^ C[n-1]

In other words, decrypt the current ciphertext block, and XOR with the
previous ciphertext block.  Note carefully: the previous ciphertext
block.  That implies that you can start at any point in the string
and do your decryption.  You don't have to know the plaintext of the
previous block to proceed, which is what you're implying.

The property of CBC mode is related to its error propagation character-
istics, which are important in some environment.  Suppose that ciphertext
block C[n] is garbled, either by a bird sitting on a phone line or by
hostile action.  That will garble two blocks of output:  P[n] and P[n+1].
(Derivation is left as an exercise for the reader.)  But P[n+2] will
be decrypted properly, since it depends on P[n+1] and P[n+2].  (N.B.
I'm deliberately ignoring insertion/deletion errors.  If those are a
concern, use CFB mode.)

In accordance with my usual habits, I'll cite an excellent reference
on how to use cipher systems, and what the properties of the different
encryption modes are:

	@book{daviesprice,
	   author = {Donald W. Davies and Wyn L. Price},
	   edition = {second},
	   publisher = {John Wiley \& Sons},
	   title = {Security for Computer Networks},
	   year = {1989}
	}

Bruce Schneier's excellent book ``APPLIED CRYPTOGRAPHY: PROTOCOLS, ALGORITHMS,
AND SOURCE CODE IN C'' is due out next month; it covers this, too.  (I'll
forbear to cite my own book till it's nearer completion...)