Re: fast des

how fast is fast des these days?  (i have measured over 2 mbps
	 on decent workstations.)

	 i was in a meeting today attended by someone from nsa who said
	 that 2.4 gbps des chips exists today.  (he got real silent after
	 blurting this out.  hmm.)

	 2.4 gbps is 37.5 million des per sec.

	 it is probably not much challenge to put together a 65,536 element
	 machine, which would run at 2.5 trillion des per sec.  if i have my
	 arithmetic right, this could exhaustively test the space of 56 bit
	 keys in about eight hours.

I don't know of any 2.4 gbps DES chips, but DEC has built a 1 gbps
chip.  They've even published a technical report on it, though I don't
have the number handy.  But there's more to know than simply the raw
speed.

First of all, most real DES chips -- i.e., those designed for
encryption, rather than brute-force cryptanalysis -- are optimized for
encrypting large blocks of data.  Key-loading is a different operation,
and that might not go nearly as fast.  Any hardware assists (i.e., DMA)
would be for the data, not for the next key to use on the same block of
data.

Second, what does this chip cost?  If it costs, say, 10x what the DEC
chip costs, it's not cost-effective; you can build your DES-cracker
more cheaply with the slower chips.  (The DEC TR gave cost figures for
DES-cracking...)

Date: Wed, 16 Jun 1993 11:09 EDT
    From: smb@research.att.com
	     ....  2.4 gbps is 37.5 million des per sec.

	     .... arithmetic right, this could exhaustively test the
			space of 56 bit keys in about eight hours.
    I don't know of any 2.4 gbps DES chips, but DEC has built a 1 gbps
    chip.
   ....  Key-loading is a different operation,
    and that might not go nearly as fast.  Any hardware assists (i.e., DMA)
    would be for the data, not for the next key to use on the same block of
    data.

Usually the limiting factor is examining the <ostensibly> decrypted data
for statistically significant patterns indicating that you have the
correct key.  The fast DES chips don't help with this at all.  A known
plaintext attack, of course, doesn't have this problem, but these are
probably of limited interest in real applications.

>Usually the limiting factor is examining the <ostensibly> decrypted data
>for statistically significant patterns indicating that you have the
>correct key.  

If you know that your plaintext is 7-bit ASCII, then you can reject if
you see too many 8th bits set.  Assuming that the size of your
intercepted ciphertexts is generous, say ten blocks, then the
likelihood of a false decryption which has all the 8th bits off is
extremely small.  Hint for implementors: don't allow such easy bit
correlations in your plaintext.

In any case, the point of a DES cracker is to reduce the size of the
space of probable decryptions, so that more computationally expensive
statistical tests of possible plaintexts may be performed on a shorter
list.  If your cracker can reduce the size of the probable keyspace by
eight bits, then you can run, in parallel, tests which take 2^8 times
as long.  For example, you may be able to reject many potential
plaintexts from a CBC ciphertext stream after the first block; longer
tests would look at a longer stream.

This is where measures of n-gram distribution really come into their
own.  These measures can distinguish between text types extremely
finely, but are often expensive.  Nevertheless, they are highly suited
to automation, particularly to distinguish between different languages
and to recognize non-linguistic forms such as protocol encapsulations,
object code, and compressed text.

Eric

>    I don't know of any 2.4 gbps DES chips, but DEC has built a 1 gbps
>    chip.
>   ....  Key-loading is a different operation,
>    and that might not go nearly as fast.  Any hardware assists (i.e., DMA)
>    would be for the data, not for the next key to use on the same block of
>    data.
>
> Usually the limiting factor is examining the <ostensibly> decrypted data
> for statistically significant patterns indicating that you have the
> correct key.  The fast DES chips don't help with this at all.  A known
> plaintext attack, of course, doesn't have this problem, but these are
> probably of limited interest in real applications.

If you were interested in cracking DES, I wonder if you couldn't just
build the hardware out of FPGAs.  That way, you could make key loading
and the decrypted data test fast as well.

- Jay

> 
> If you were interested in cracking DES, I wonder if you couldn't just
> build the hardware out of FPGAs.  That way, you could make key loading
> and the decrypted data test fast as well.
> 
> - Jay
> 
I tried this on the xilinx 3090 chip.  The tools to handle palasm
didnt seem to be designed to handle a job that size, I had to split
up the file into 3 sub parts (S boxes, key scheduler and everything
else).  I never got it completed but judging by some of the output
I got, it wouldnt have fit on the 3090, which is quite a big
FPGA.  The implementation is straight forward, but there is alot
of juggling you have to do to put it on a 3090 since the S boxes
are slightly bigger than the CLB's tables, and you end up wasting
alot of space when you just need a bunch of xor gates (2 xor's
per CLB, and you need alot of XORs).  Implementation with
standard cell technology would probably be very easy, and
save alot of space too.
(routing the thing is another problem too, since there are
so many permutations,  I am not sure if a near-full-capacity
FPGA would be able to route all the permutations)
                        Tim