next up previous
Next: The client/server connection Up: Stage 9 Previous: Work Description

The key tester

There are several possible modes of operation for DES, it can either work as a stream cipher or as a block cipher. We guessed that the block cipher mode, Electronic Code Book mode, was used as it for the other modes would not suffice to know the key; an initial value block of 64 bits also would have to be found. Attacking these modes of DES seemed too hard for us (and for this competition), so we hoped that ECB was used, in which case ``only'' 48 unknown key bits would have to be determined.

As we were about to test all the 248 keys, we had to decide upon a way to determine if a key could be the right key. This could of course be done by decrypting the entire message for each key, but this would mean that about a hundred blocks would have to be decrypted with each key. A back-on-the-envelope estimate of the number of keys we could hope to test in a second indicated that this was out of the question. Instead, we made the reasonable assumption that the plaintext only would contain characters from the 7-bit ASCII character set. Only if the first 8-character block of the plaintext we got for a key was solely 7-bit ASCII the next block was tested. This means that for about 255/256 of all keys, only the first block would have to be decrypted; a huge speedup compared to decrypting the entire ciphertext for each key. The complete rules we used for each key were the following:

If a key failed one of these tests, it was discarded and the later rules not applied. Based on the assumption that a text encrypted with DES behaves like a random string of binary numbers, we estimated that we would get less than 10 incorrect keys using these rules. On average, only slightly more than one block needed to be decrypted for each key.

The actual decryption of a key was done using a technique called bit-slicing: On a 32-bit processor, such as the Intel Pentium, 32 keys can be tried in parallel by letting each bit position correspond to each key. The processor is viewed as a SIMD (Single Instruction Multiple Data) parallel processor with a highly restricted instruction set. This approach restricts the operations possible during the decryption stage to the boolean operators AND, OR, XOR and NOT, but as was observed a couple of years ago by the Israeli researcher Eli Biham, it is possible to implement DES encryption and decryption efficiently using only these operators. By making use of this technique and optimizing the code heavily, we could obtain very high speeds: On the fastest workstation we had available, a DEC Alpha, more than 3 million keys/second could be tested.


next up previous
Next: The client/server connection Up: Stage 9 Previous: Work Description
solvers@codebook.org