Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!ucsd!sdcsvax!sdcc6!sdcc13!ln63wgq
From: ln63wgq@sdcc13.ucsd.EDU (Keith Messer)
Newsgroups: sci.crypt
Subject: Re: Crypt() hackers
Message-ID: <980@sdcc13.ucsd.EDU>
Date: 9 Feb 88 07:31:23 GMT
References: <538@ddsw1.UUCP> <8045@eddie.MIT.EDU>
Reply-To: ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer)
Organization: Univ. of California, San Diego
Lines: 48
Keywords: DES, des, crypt()


About breaking crypt() ...

	I've worked out a technique and some of the tables for a simplified
	DES even now.  I am convinced that the algorithm is vulnerable to
	a known-plaintext attack, and have good feelings about breaking it
	even in the other modes that are currently thought to be secure.

	Think of the DES purely as a boolean function, and its insecurity
	becomes obvious.  UNIX*, for instance, uses a variation of the DES
	with a known 64 bit plaintext and a secret 56 bit key to produce
	64 bits of cyphertext output.  So, if you want to hack these 56
	bit passwords, all you need to do is express each cyphertext bit in
	terms of every bit of the key.  That makes 64 very nasty boolean
	expressions for the encryption---but they can be simplified!  And
	once each cyphertext bit is expressed in the simplest possible way
	in terms of the key bits, you can begin to solve for bits of the
	key.  This may sound like a bit of work, but it only has to be done
	once.  The result is a machine which makes breaking UNIX* passwords
	a trivial exercise and a technique that can be extended to help
	break DES in its really nasty modes like CBC, used to make milnet
	passwords.

	It's very clear, then, that all that'll be required to do the work
	is a boolean expression simplifier.  Although I'm no expert at that
	sort of thing, I'm convinced I can write one if I have to.  It would
	be better if someone out there has written one already or has one and
	can send it to me, though.  Anyone who knows about this--either how
	to code a boolean simplifier or where to find one--I'd be very happy
	to hear from you!

	If you're interested and want a bibliography papers on the subject,
	send me mail.  Unfortunately, though, most of the current literature
	puts so much emphasis on higher level mathematical structures that
	it loses track of solving the problem.  Anyway, send me mail anyway.
	I'm curious about what kind of people read this group!


	Keith Messer
	ln63wgq@sdcc13.ucsd.edu

-------------------------------------------------------------------------------
"The National Bureau of Standards comittee that told IBM to make the DES use
56-bit instead of 128-bit keys should be set on fire."
						--Me

"The impatient explorer... invents a box in which all journeys may be kept."
						--Kenneth Patchen
-------------------------------------------------------------------------------