[2853] in cryptography@c2.net mail archive
Brute forcing half a Clipper key.
daemon@ATHENA.MIT.EDU (Trei, Peter)
Thu Jun 25 14:34:29 1998
From: "Trei, Peter" <ptrei@securitydynamics.com>
To: "'Colin Plumb'" <colin@nyx.net>
Cc: "'cryptography@c2.net'" <cryptography@c2.net>
Date: Thu, 25 Jun 1998 10:14:41 -0400
> -----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
