Correction: "Optimized key rates?"

C Matthew Curtin (cmcurtin@research.megasoft.com)
Sun, 4 May 1997 02:08:09 -0400 (EDT)


Numerous transmission errors caused my previous comments regarding
Biham's DES implementation on 64-bit processors to contain errors that
need to be corrected. :-)

Moral of the story: don't read papers too quickly.

Now for the correction...

I stated that Biham's implementation is only suitable for 64-bit
processors, because DES uses 64-bit blocks. That is not correct.

Biham implements DES by representing S boxes by their logical gate
circuits. This view is taken of the entire cipher. The circuit is
then computed 64 times in parallel. The entire "circuit" has around
16,000 gates. So in 16,000 instructions, DES can be computed 64 times
on 64-bit processors. Using this method, the number of instructions
needed to perform DES encryption is about 300, versus 600+ in other
fast DES implementations.

Processors of other sizes: 32, 16, 8 bits, etc. can use the same
approach. However, in 16,000 instructions, they'll perform only as
many encryptions as the host architecture's word size. So, although
64-bit processors will be able to perform 64 encryptions in 16,000
instructions, 32-bit processors will perform 32 encryptions, 16-bit
will do 16, 8-bit will do 8, etc.

Sorry if my previous posting caused confusion.

Biham's paper ("A Fast New DES Implementation in Software") is an
interesting read. Even if you're not into the guts of DES
implementations, he has an interesting section in there on a "DES
Worm" that could run through the DES keyspace over the course of a
weekend. Interesting indeed.

-- 
Matt Curtin  Chief Scientist Megasoft Online  cmcurtin@research.megasoft.com
http://www.research.megasoft.com/people/cmcurtin/    I speak only for myself
Death to small keys.  Crack DES NOW!   http://www.frii.com/~rcv/deschall.htm