Re: Cryptanalysis

[Bill Stewart <stewarts@ix.netcom.com>]

At 11:21 AM 2/15/97 -0500, you wrote:
>Was wondering if anyone could help me with short explainations on the
>cryptanalysis of SKIPJACK and DES.  If ya hit www.sauge.com/crypt you
>might get a better idea of what i'm trying to accomplish.
>
>Vague explanations are OK.  Dont want long drawn out explainations on
>the implementation of an attack (source code, proofs, statistical
>analysis and the like), just a short explaination of the attack.

Cryptanalysis of DES is a 25-year ongoing academic exercise, with
lots and lots of results.  It's easy to attack it in 2**55 tries,
because of symmetry, but that's a very large number :-)
Differential cryptanalysis, discovered by Biham and Shamir, 
shows that the NSA probably did help the design process when
working with IBM to turn IBM's 128-bit-key Lucifer system into DES,
and certainly didn't weaken it.  Linear cryptanalysis, discovered
more recently, shaves some more bits off the strength if you have
an extremely large amount of known plaintext.  

Brute-force attacks on DES (just try lots of keys until you win) 
used to be viewed as almost infeasible, but about 5-6 years ago there 
were a couple of designs for cracking machines that could do a 1-day crack
for $30-50M, and then Wiener's design for a $1M, 3.5-hour cracking machine
about 5 years ago.  Gate arrays have gotten denser, faster, and cheaper 
since then, and if you want to crack a _lot_ of keys (e.g. you're the NSA)
you can probably afford to burn ASICs to get even denser and faster.
The slow part of the attack _had_ been key scheduling, but recent work
by Peter Trei and others shows that you can do key scheduling very
efficiently for the brute-force keysearch problem by picking keys
in Gray Code order (since a one-bit change in key causes a simple
change in key-schedule - it's totally useless for normal encryption/
decryption, but it's a big win for brute-force cracks.)  
There may be a distributed Internet crack using that approach, 
though DES is still very inefficient on general-purpose computers and 
works better on bit-twiddliing chips.

SKIPJACK is a totally different game - the NSA keeps the algorithm secret,
and the only semi-outsiders who've seen it were a group of 5 people
including Dorothy Denning and Dave Maher who were allowed to do a study
when the NSA were trying to foist Clipper onto us.  They concluded that
SKIPJACK was reasonably strong (in their interim report), which gave
them good propaganda points, and never did the "final report" that
was supposed to address the entire Clipper chip (where most of the
technical weaknesses were) and the key-handling charade around it.
I don't remember if Matt Blaze's spoofing attack on the Clipper chip
came before or after their interim report - the checksums were too short
so you could impersonate another chip under reasonably wide conditions.
According to the data sheets for the Mykotronx Clipper Chip, SKIPJACK
is a Feistel-structured cypher with N rounds (I think it was 16 or 32.)
80 bits is enough that if anybody can discover the algorithm, 
it's too long to brute force today but starts looking pretty vulnerable
in 10-20 years, and of course the Feds would have your keys today,
so they can wiretap you, without needing legal authorization,
and you can probably bribe a Fed faster than you can brute-force the chip.

#			Thanks;  Bill
# Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com
# You can get PGP outside the US at ftp.ox.ac.uk/pub/crypto/pgp
#     (If this is a mailing list, please Cc: me on replies.  Thanks.)