Path: utzoo!utgpu!water!watmath!clyde!rutgers!ucsd!ucbvax!degas.Berkeley.EDU!wallace
From: wallace@degas.Berkeley.EDU (David E. Wallace)
Newsgroups: sci.crypt
Subject: Re: Crypt() hackers
Keywords: DES, des, crypt()
Message-ID: <22925@ucbvax.BERKELEY.EDU>
Date: 9 Feb 88 22:19:10 GMT
References: <538@ddsw1.UUCP> <8045@eddie.MIT.EDU> <980@sdcc13.ucsd.EDU>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: wallace@degas.Berkeley.EDU.UUCP (David E. Wallace)
Organization: University of California, Berkeley
Lines: 72

In article <980@sdcc13.ucsd.EDU> ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer) writes:
>
>About breaking crypt() ...
(and suggests a technique for breaking DES based on finding boolean
expressions for the output bits in terms of the key, and then simplifying
them)...

This approach is a nice try - the problem is it's extremely unlikely to
be at all practical.  It's fairly easy to see that boolean expression
simplification (all the way to simplest form) is NP-hard: if there
was a polynomial algorithm to do it, then we could solve SAT (given
a boolean expression, find out if there is some setting of the input
variables that makes the expression true) in polynomial time: just
run the input expression through the simplifier, and see if the result
is 0.  If so, there is no solution, otherwise there is.
SAT is known to be NP-complete.  So if you have an algorithm to do
simplification in polynomial time, you have just shown that P=NP,
and all the theoreticians that have been working on that problem over
the years can go on to something else.  This is extremely unlikely,
to say the least.  Hence any simplification algorithm you are likely
to come up with either won't be able to simplify all expressions all the
way, or will take an exponential amount of time (exponential in the
size of the input expression), or both.

Also, those "very nasty boolean expressions" may very well themselves involve
an exponential number of terms (something close to 2^56, say).
So first you formulate the boolean expression (with a possibly exponential
number of terms), and then you simplify it (taking time that's probably
exponential in the size of that expression) - and you still haven't solved the
whole problem, you've just got a simpler boolean expression that you
hope will lead you to a solution.  It sounds like it would be far faster to
just try all 2^56 keys and see which one works.  Of course, you might
get really lucky, and find that the expressions don't have an unreasonable
number of terms, and find a simplification heuristic that happens
to work quickly in this particular case.  But it's a real long, long
shot.  Nice try - but no cigar.

Dave Wallace

>	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!
>
>
>	Keith Messer
>	ln63wgq@sdcc13.ucsd.edu

Dave Wallace	UUCP: ...!ucbvax!wallace  ARPA: wallace@degas.Berkeley.EDU