🚀 go-pugleaf

In article <980@sdcc13.ucsd.EDU> ln63wgq@sdcc13.ucsd.edu.UUCP (Keith Messer) writes:
>
>About breaking crypt() ...
>
>	I've worked out a technique and some of the tables for a simplified
>       DES even now...
>
>	Think of the DES purely as a boolean function, and its insecurity
>       becomes obvious. ...
>       ... 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!
>       ... you can begin to solve for bits of the key
>
>	It's very clear, then, that all that'll be required to do the work
>       is a boolean expression simplifier...

I've been working on this approach from time to time without much success.
Yes, you can define DES as boolean functions, and yes, you could theoretically
solve for each of the 56 bits of key given the known input and output.
However, your "very nasty" modifier is rather optimistic in my view.
It doesn't take many rounds before your intermediate results get
humungous.  Yes, there are simplifications, but there is a limit to the
amount of simplifying that can be done at each step.  Konheim gives some
information about the complexity limit for the S-boxes, for example, and
points out that they can't be reduced beyond a certain point.

My hope was that if there is actually a back door in there someplace it
would be discoverable by running this thing through -- at some point there
would be a dramatic collapse, instead of the expected geometric increase
in complexity.  I haven't demonstrated either the existence or
nonexistence of that trap door.

-- 
	Jim Gillogly
	{hplabs, ihnp4}!sdcrdcf!randvax!jim
	jim@rand-unix.arpa    [HASA: U (Spam) division]