17% Smaller DES S-box Circuits Found

solardiz writes "DES is still in use, brute-force key search remains the most effective attack on it, and it is an attractive building block for certain applications (the key size may be increased e.g. with 3DES). Openwall researchers, with funding from Rapid7, came up with 17% shorter Boolean expressions representing the DES S-boxes. Openwall's John the Ripper 1.7.8 tests over 20 million combinations against DES-based crypt(3) per second on a Core i7-2600K 3.4 GHz, which roughly corresponds to a DES encryption speed of 33 Gbps."

Stupid question from crypto-newb

[DriedClexler]

Why did it take so long to find a shorter boolean expression? Aren't there programs that take in a truth table and churn through all the expressions that can generate it? And isn't the S-box I/O size pretty small to begin with?

Re:Stupid question from crypto-newb

[NoSig]

Huge SAT problems are routinely solved on computers. In fact the CPU in your computer was probably formally tested in software by solving a huge SAT problem. NP-completeness does not necessarily mean that a problem can't be solved in practice even if it is huge. Complexity theory does provide an approximation to what is tractable, but it isn't all that accurate.

Re:i7 what? Who cares?

[solardiz]

Here are some specific performance numbers for DES-based crypt(3) on GPUs (for comparison, recall that we're reporting over 20M c/s on a CPU):

oclhashcat-plus is reported to achieve 55M on ATI HD 5970, only 25M on NVidia GTX570 at 1600 MHz core clock, 310M on 8x ATI HD 6970, 181M on 7x NVidia GTX580 (1594 MHz). The numbers for oclhashcat-lite are very similar (57M, 26M, 297M, 181M, respectively). These are off the hashcat website. This does not use our new S-boxes yet (I expect that future versions of *hashcat tools will).

Notice how the number for high-end NVidia is on par with that for our CPU, and for ATI is less than 3x better. Of course, GPUs do have an advantage, but it still does make sense to use CPUs as well, which a typical organization has more of and doesn't need to spend extra time to deploy, install drivers for, etc.

Now, our new S-boxes and other optimizations will provide better performance. Per discussions with a tripcode cracker author, I expect all the way up to 400M c/s on ATI HD 5970, which is close to its theoretical peak speed (approx. 80% of it per some estimates). This is a 20x improvement over our figure for the Core i7 CPU, which is significant. (There's a little room for improvement on the CPU as well, though - specifically, if we pre-generate or runtime-patch the code for each salt as opposed to using pointers at runtime like we do now. This kind of optimization is assumed in the 400M figure for the GPU. So with both having the optimization, the GPU's advantage will be less than 20x.)

Curiously, 400M c/s for 25 iterations of DES will mean that a single ATI HD 5970 with proper code will be able to crack 56-bit DES keys in just 42 days on average.

So, yes, GPUs have an advantage, and we have contributed to that as well.