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
participants (5)
-
Eric Hughes -
Jay Adams -
smb＠research.att.com -
Timothy Newsham -
Tom Knight