Path: utzoo!mnetor!uunet!husc6!rutgers!ames!sdcsvax!sdcc6!sdcc13!ln63wgq
From: ln63wgq@sdcc13.ucsd.EDU (Keith Messer)
Newsgroups: sci.crypt
Subject: Re: Is DES breakable with a known-plaintext attack?
Message-ID: <974@sdcc13.ucsd.EDU>
Date: 29 Jan 88 10:05:33 GMT
References: <1449@crlt.UUCP> <1736@faline.bellcore.com>
Reply-To: ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer)
Organization: Univ. of California, San Diego
Lines: 34
Keywords: DES known plaintext

That's a very interesting problem:

	You have a 64 bit key, 56 bits of which are being used in the
	encryption.  There is a known 64 bit plaintext and a known
	64 bit cyphertext.  We must assume that IBM worked things out
	so a large number of plaintexts are not mapped into the same
	cyphertext with different keys, lest key searching be easier than
	it already is.  So...

	There >is< a way to narrow the key search down to within a few
	orders of 255 possibilites (the 8 bit mandatory gap between the
	number of possible keys and the number of possible cyphertexts).

	I'm trying to work out a method now for making assertions about
	the intermediate stages of the algorithm (1 of 16 s-box XOR steps
	back, for instance).  A correct "guess" about information in the
	intermediate steps will give you a 33% knowledge about the key
	because of key selection (33% is from memory & may be incorrect).
	My really big problem right now is not the s-boxes which everyone
	talks about as being the big strong point of des, but the XOR's.
	Anyone who's thought about this, >please< leave me mail or post
	here.  I feel fairly close to figuring this thing out, and have
	been working out single-table solutions to the iterative part of
	the code (there is an excellent paper published on the subject,
	which I will site when I can find it).  Does anyone see big faults
	with this line of reasoning?

Keith Messer
ln63wgq@sdcc13.ucsd.edu

"The NBS comittee members who decided to use 56-bit instead of 128-bit
 keys for the DEA should be set on fire." -- Me