From: John Gilmore <gnu@toad.com>
Date: Thu, 6 Jun 1996 21:43:05 +0800
To: gnu@toad.com
Subject: Triple-DES chip idea: built-in 1DES-cracker
Message-ID: <199606060750.AAA06399@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


It just occurred to me that companies which are designing Triple-DES
chips should spend a small chunk of their chip area and design time
on building in features for fast single-DES key search.

As in Matt Wiener's design, this would include logic to generate a
sequence of trial keys, and a circuit to evaluate the likelihood that
the trial key was "interesting" after examining the trial plaintext.
All of this logic would be on-chip and isolated from the pins of the
chip, so it could run at high speed without any impact on the rest of
the system.

Then, as these chips are deployed into consumer boards or
motherboards, a small amount of software plus the Internet will make
distributed DES cracking feasible.  Whenever the chip wasn't busy
doing some "real work" encoding data for the user, it would be
spinning its wheels cracking a DES key for fun or profit.

There are lots of interesting ways to build the comparison circuitry
to examine the trial plaintext.  The cheapest is to provide a single
64-bit register with the desired plaintext; that's what Matt's design
did.  Another cheap way would be to provide two 64-bit registers: a
mask and a value.  AND with the mask and compare to the value; it's
interesting if equal.  A second and/or third set of mask and value
registers (and another ciphertext register) would permit the test to
be across 16 or 24 bytes of ciphertext/plaintext rather than just 8.
This would be useful if e.g. your mask is only looking to see that the
high order bit of each byte is off in the ciphertext (indicating a
probability of ASCII text).  8-byte comparison would give you a
false-hit every 256 keys; 16-byte comparison would reduce that to one
every 65,536 keys.

Matt's chips froze when they got a match.  A FIFO on the comparison
output would let the chip continue to spin, looking for more matches,
before software got around to reading the results of a previous hit.
This would permit the chip to do DES-cracking in polled mode, without
using interrupts.  If the DES-cracking control registers were all
disjoint from the ordinary DES operational registers, the DES-cracking
could be initiated at any time, independent of the chip's encryption
functions, and could then be checked-up on periodically, again without
impacting the chip's normal functioning.  As an extreme example, it
could be started at system boot time, and checked only at system
shutdown for hits.

If you wanted to get truly fancy, the comparison should have eight
256-bit vectors, one per byte of plaintext.  Each vector is indexed by
the byte of plaintext, producing a single bit.  If it's 1, that byte
has an interesting value.  So if you set only the bits corresponding
to ASCII uppercase letters, then only a plaintext ASCII uppercase
letter is interesting.  So, the eight trial-plaintext bytes produce
eight bits, one from each vector.  Mash those together, and use this
8-bit value as an index to a ninth bit vector, which would let you
specify which combinations of "interesting" plaintext bytes are truly
interesting enough to stop the chip for.  E.g. if you insist that all
of the ciphertext bytes are ASCII uppercase letters, then all the
eight bit-vectors will be set up the same, and this ninth bit vector
will have a single 1-bit at index 11111111 (all bytes match).  If on
the other hand, any six out of the eight being uppercase is good
enough for you, you'd put a bunch of 1-bits into the ninth vector (one
for each possible way that six of the eight would match, such as
11010111 and 00111111 and 01111110).  In nine 256-bit vectors (less
than 300 bytes of on-chip storage), you could specify truly complex
and useful conditions like "First two bytes of plaintext equals
0x2C07, next three bytes are uppercase ASCII, next byte is a
don't-care, following byte is an ASCII digit".  This would be great
for matching up packet headers or partial plaintext, when looking for
the key to encrypted network traffic.  However, even these days,
adding 300 bytes of static storage to a 3DES chip for this kind of
ancillary function doesn't seem likely, until the market for
DES-cracker boxes matures.  (Each such box tends to consume large
numbers of DES chips, making them an attractive target market for a
chip vendor.)

But some of the simpler des-cracker assists I mentioned should be easy
to implement with only a few dozen bytes of static storage, some small
circuits and maybe one more address pin, making them suitable for
mass-market chips for PC's and such.

	John Gilmore, gnu@toad.com

PS:  Note that this feature would not affect the exportability of your
chip, which was already nil.  Design and build it overseas.