[2246] in cryptography@c2.net mail archive
RE: DES, MMX, and FPGAs
daemon@ATHENA.MIT.EDU (Trei, Peter)
Tue Mar 3 14:28:00 1998
From: "Trei, Peter" <ptrei@securitydynamics.com>
To: cryptography@c2.net
Cc: "'ptrei@securitydynamics.com'" <ptrei@securitydynamics.com>
Date: Tue, 3 Mar 1998 10:18:03 -0500
> -----Original Message-----
> Andreas Bogk [SMTP:andreas@telekom.artcom.de } wrote:
> On Mon, Mar 02, 1998 at 02:53:55PM -0800, David Koontz wrote:
> > /*
> > * sbox.c
> > *
> > * c program to generate vhdl entity/architecture pairs
> > * for DES S boxes. Source for the S box values is the
> > * char S[8][64] array extracted from crypt.c
> (crypt(3)).
> > */
>
> I know that program. It produces a straightforward representation
> of the S-boxes in VHDL. If you synthesize them, your S-boxes will
> eat up about 150 LEs, compared to 28 that should be neccessary.
>
> Andreas
>
Response:
Indeed - the reason I referenced the bitslice work in earlier
messages is that hand-optimizing the Sbox code gives
*much* better results than generic decoder code. The
gate count reduction work which was done for the bitslice
versions of DES on general porcessors is directly
applicable to non-bitslice FPGA implementations: it
gives smaller DES engines which use fewer sites on the
chip, and require fewer connections and cross-overs.
This improves the chances of fitting an unrolled
search engine on a chip.
I've spoken to the authors of theScientific American article
(John Villasenor and Bill Mangione-Smith at UCLA), and I'm
afraid they were *not* unrolling the DES rounds. This
suggests a full Wiener DES keysearch engine would fit
only on the largest current FPGAs, if at all.
Prof Mangione-Smiith (billms) (along with Jason Leonard)
also has a formal paper describing the DES work
referenced in the SA article, at
http://www.icsl.ucla.edu:80/~billms/publicat.htm
"A Case Study of Partially Evaluated Hardware Circuits:
Key-Specific DES."
I have not read this fully yet, but it looks very helpful.
BTW: billms confirms that the wiring for permutations is
a major limiting factor.
Peter Trei
