Xref: cantaloupe.srv.cs.cmu.edu sci.crypt:15640 alt.security.pgp:2609 alt.privacy.clipper:44
Newsgroups: sci.crypt,alt.security.pgp,alt.privacy.clipper
Path: cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!bb3.andrew.cmu.edu!news.sei.cmu.edu!fs7.ece.cmu.edu!europa.eng.gtefsd.com!howland.reston.ans.net!noc.near.net!uunet!harlequin.com!andyl
From: andyl@harlqn.co.uk (Andy Latto)
Subject: Re: Off the shelf cheap DES keyseach machine (Was: Re: Corporate acceptance of the wiretap chip)
In-Reply-To: smb@research.att.com's message of Wed, 21 Apr 1993 13:23:18 GMT
Message-ID: <ANDYL.93Apr21114940@epcot.harlqn.co.uk>
Sender: usenet@harlequin.com (Usenet Maintainer)
Nntp-Posting-Host: epcot.harlequin.com
Organization: Harlequin Limited, Cambridge, England
References: <1993Apr19.093227.1093@jarvis.csri.toronto.edu>
	<1993Apr20.150531.2059@magnus.acs.ohio-state.edu>
	<1993Apr20.192105.11751@ulysses.att.com> <C5sy1z.4tD@demon.co.uk>
	<1993Apr21.132318.16981@ulysses.att.com>
Date: Wed, 21 Apr 1993 16:49:40 GMT
Lines: 42


In article <1993Apr21.132318.16981@ulysses.att.com> smb@research.att.com (Steven Bellovin) writes:

   In article <C5sy1z.4tD@demon.co.uk>, Graham Toal <gtoal@gtoal.com> writes:
   > In article <1993Apr20.192105.11751@ulysses.att.com> smb@research.att.com (Steven Bellovin) writes:
   > :Thousands?  Tens of thousands?  Do some arithmetic, please...  Skipjack
   > :has 2^80 possible keys.
   > 
   > We don't yet know if all 80 bits count.

   That doesn't worry me at all; they're not going to cheat at something
   they can get caught at.  And key size is one of the things that can be
   verified externally.  Feed lots of random key/input pairs into the
   chip, then try flipping random key bits, and see what happens to the
   output.  We already know what *should* happen -- about half the output
   bits should vary, on average, from a 1-bit key change or input change.

   If they were out to build a weak cryptosystem, it might be the case that
   some of the bits are much less powerful than others, in the sense that
   they only enter into the encryption very late in the game.  By contrast,
   DES was designed to use each key bit as early as possible; the 50% output
   change rate appears as early as round 5.  Again, though, I don't think
   NSA is going to cheat that crudely; they're likely to get caught.

Consider a cryptosytem that starts out by XORing bits 23 and 47, and
not using either of these bits except through this XOR. This system
makes early use of every bit. but an exhaustive key search would now
only have 2^79 keys to search. Your test by varying single key bits
wouldn't turn up anything interesting.

   Remember that they've promised to let a committee of outside experts see
   the cryptosystem design.  If you assume something DES-like, a biased
   subkey generation schedule will stick out like a sore thumb.

The algorithm I suggest above would stick out like a sore thumb, but
I'm sure I could design a system with a more subtle key redundancy
which was well-hidden, but would still make an exhaustive key search
take far less than 2^80 encryptions. I don't believe your claim that
the real keysize can be verified externally.

							Andy Latto
							andyl@harlequin.com
