jim@randvax.UUCP (Jim Gillogly) (02/12/88)
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]