"Peter Trei" writes:
The fastest general purpose, freely available des implementation I'm aware of is libdes. by Eric Young. With this, I can do a set_key in 15.8 us, and an ecb_encrypt in 95 us/block. That adds up to about 9,000 keytests/sec (this is on a 90 MHz P5, running NT).
I'll point out that like most DES implementations, Eric's tries to spend a lot of time in key setup to save time later on in encryption/decryption. This tradeoff would probably be very different if you didn't plan on trying more than one or two blocks of decryption after getting a key.
Perry
Yep - with good optimization, the keygen and the des rounds get very close to each other in processing cost. Let's look at the steps involved (I'm refering to the DES description in Schneier, 2nd ed, p 270-278). I've not yet coded these optimizations, so this may be subject to revision. I'm assuming a known plaintext attack on a single 64 bit block, ECB mode. What we want to obtain is the key (which was presumably also used to encode interesting data which we can't read) First of all, we can move the initial and final permutes (tables 12.1 and 12.8) completely out of the testing loop. These have to done only once per run, and thus are effectively zero cost. Similarly, we can eliminate the key permutation (table 12.2), and iterate the permuted 56 bit key. If we get at hit, we invert the key permutation and add back the parity bits to get the original key. In the DES round The S-box and P-box steps can be combined into a single 48->32 bit permutation. So, per round (there are 16), we now have: 1. copy 32 bit sub-block to use as 'other' half in next round. 2. expansion permutation (32 -> 48) 3. xor with appropriate subkey. 4. perform the s-p permutation. (48->32) 5. xor with 'other' half from previous round. The key scheduling can be done in parallel with the rounds, since we're only planning on using each key once. However, on the Pentium it may be more efficient to do it before the des rounds, due to register starvation. Generating the subkeys is actually quite painful. You have to rotate the 56 bit key as two 28 bit halves, by one or two bits depending on the round, and then do a 56-> 48 bit permutation to generate the subkey. This step needs to be done 16 times. In a regular DES implementation, you generate the key schedules once at the start, and reuse them for each block, so there is little to be gained by optimzing this step. In a keysearch situation it's a different matter. Optimizing the permutations: DES was originally designed for hardware implementation, where permutation is a simple matter of braiding the wires between the input and output. It's a lot harder in software. I'm aware of two basic approaches: 1. Algorithmic: Analyse the permutation table to find bits which get shifted in the same direction, by the same number of bits, and arrange a series of SHIFTs, ANDs, and ORs to generate the desired permutation. This is essentially a geometry problem. 2. Lookup: Create tables for the permutation. While a permutation with n bits of input requires 2^n entries (each the size of the output data) if done as a single table, it's possible to break the permutation into several smaller tables, at increased processing time. This is a classic speed vs space tradeoff, with a big step if your tables are too large to fit into cache (and even bigger if they go to virtual memory) Example: A straight 32 -> 32 bit permutation: If done as one table, it would have 2^32 entries, and take about 16 Gbytes. If broken up into 4 tables, each of which dealt with 8 bits of the input, it would take 4096 bytes total. However, the calculation would require extracting the four eight bit subkeys from the input, doing four lookups, and ORing the four results together to get the final output. A 32 bit perm could also be done with two tables, but they would occupy half a Mb. The S-P step and the compression step of the key schedule are probably faster by lookup than by algorithm. I'm not sure about the expansion permutation, which is very regular. The size and number of tables used is going to depend a lot on cache size and available memory - for example, the rotates in the key scheduling can be eliminated if I'm willing to maintain 16 key compression tables (one for each round). I strongly expect that the whole key testing loop can fit into the 8k L1 code cache. The lookup tables *may* fit into the L2 cache. If anyone has any other optimizations, I'd like to hear about them. Peter Trei trei@process.ocm Peter Trei Senior Software Engineer Purveyor Development Team Process Software Corporation http://www.process.com trei@process.com