Cracking DES faster with John the Ripper

Version 1.7.8 of John the Ripper, a free password cracker, promises to be up to 20 per cent faster when cracking the Data Encryption Standard (DES) algorithm. The increase in speed is achieved by improvements in the processing of S-box. Although AES (Advanced Encryption Standard) has long been the encryption standard of choice, encryption and decryption with (triple) DES remain useful techniques.

The S-boxes (Substitution-boxes) used in DES are essentially tables intended to obscure the relationship between keys and encrypted text. An input bit pattern (6-bit) is substituted with a bit pattern (4-bit) specified in a table. Correlating inputs and outputs from the 8 S-boxes used in DES is relatively expensive and offers plenty of scope for optimisation.

The first step in doing so is to break down processing into simple standard operations such as AND, OR, NOT and XOR, as would be used in gates in circuits. Eli Biham described this procedure back in 1997. The correlation between S-box inputs and outputs was represented by a Boolean expression, thus rendering the table superfluous.

In 1998, Matthew Kwan improved (PostScript file) Bihan's approach by reducing the number of gates (and therefore operations) required for the S-boxes. This he achieved by adding additional gates (ANDNOT, NAND, NOR) and using Karnaugh minimisation. Kwan had several desktop computers running for weeks at a time. Developers Roman Rusakov and Alexander Peslyak, Openwall founder and CTO, have now re-optimised everything and further reduced the number of gates.

Furthermore, current "Core i 2000" processors, for example, support Advanced Vector Extensions (AVX), which can be used to process John the Ripper's DES algorithms more rapidly. In practice, this increases the speed of brute force attacks by 12 to 14 per cent. The developers have published benchmarks on the Openwall mailing list. The development work was sponsored by US security firm Rapid7 which also develops the exploit framework Metasploit. The optimised S-boxes will be open sourced.

(djwm)