[2856] in cryptography@c2.net mail archive
Re: Brute forcing half a Clipper key.
daemon@ATHENA.MIT.EDU (Adam Shostack)
Thu Jun 25 14:41:20 1998
From: Adam Shostack <adam@homeport.org>
In-Reply-To: <D104150098E6D111B7830000F8D90AE80178EF@exna02.securitydynamics.com> from "Trei, Peter" at "Jun 25, 98 10:14:41 am"
To: ptrei@securitydynamics.com (Trei, Peter)
Date: Thu, 25 Jun 1998 12:35:59 -0400 (EDT)
Cc: colin@nyx.net, cryptography@c2.net
The half keys were (ostensibly) going to be stored as 2 80 bit values
which needed to be xored together to get the key. So you didn't get
to brute force a 40 bit key.
Adam
Trei, Peter wrote:
|
|
| > -----Original Message-----
| > From: Colin Plumb [SMTP:colin@nyx.net]
| > Sent: Wednesday, June 24, 1998 8:16 PM
| > To: cryptography@c2.net; jya@pipeline.com
| > Subject: RE: "damn the bitmaps..."
| >
| > As for speed, I'm currently getting 1.36 us/byte (encrypting the same
| > block
| > over and over to make 10 MB) on a (non-MMX) Pentium 133 with C code.
| >
| > You can *almost* do a good assembly implementation using the 8 byte
| > registers on an x86, leaving si di and bp available for indexing,
| > pointers, and so on, but you need a 9th byte to hold the g2 ^ *key++
| > part of g1 ^= F[g2 ^ *key++] in the inner loop.
| >
| > Perhaps some work on key scheduling to move the location of the key XOR
| > around would work.
| >
| > The algorithm is *almost* self-inverse, with just a reversed key schedule.
| > I wonder how the hardware does the switch?
| >
| > It seems easiest to me to swap the input bytes around (to achieve the
| > effect
| > of swapping the halves in the G operation) and then just change which byte
| > the counter gets added to.
| > --
| > -Colin
| [Trei, Peter]
| I wouldn't touch bp, but have always considered si and di fair
| game.
|
| The almost non-existant key scheduling has interesting implications:
|
| 1.36 us/byte @ 133 MHz
| -> 10.88 us/block
| = 1447 clocks/block
|
| -> 2^39 blocks = 8E14 clocks
|
| -> on average, 69 machine-days on a 133 MHz machine to brute force
| a Clipper key if half the bits are known. Note that this is using
| what I expect is a far-from-optimized implementation - I would not
| be at all astonished if it could be speeded up by a factor of 4 or
| more.
|
| The bottom line is: Splitting the key in two, and storing the two
| halves in different agencies wouldn't have made people much more
| secure from corrupt government agents, or an 'escrow'
| agency compromised by other criminals or terrorists. With
| half the key and a dozen high-end machines you could brute
| force a complete unit key in a few hours, after
| which all communications from that Clipper chip would be
| compromised.
|
| This is assuming a known plaintext attack on EBC or CBC mode
| Clipper, similar to the RSA DES challenges.
|
| Peter Trei
|
|
|
--
"It is seldom that liberty of any kind is lost all at once."
-Hume
