FPGA Based UNIX Crypt Hardware Password Cracker

The goal is to get a ~100 Euro unit to do 10 million key guesses per second. This device is built for the fun of building it and to see what’s possible with current hardware.

UNIX Crypt requires 25 passes of a modified DES algorithm with each DES pass requiring 16 rounds to complete. This gives a total of 400 clock cycles to complete a single encryption, if each round is completed within one clock cycle. Doing this is easy since DES is very hardware friendly. A round only consists of permutations and a single lookup and xor operation.

To reduce the time needed below 400 cycles, multiple crypt cores are used on a single device. The cores are fed by a password candidate generator in a round robin fashion. While a pipeline approach might produce less overhead on huge devices, using multiple cores will scale better to the available amount of logic on smaller devices.
The current design supports up to 200 crypt cores, which is sufficient for devices currently available to end users.

Target Device

A Xilinx XC3S1000-4 is being used. It is available on a handy micro module from Trenz Electronic. The micro module is mounted on a carrier board for easy access to the FPGA’s pins.

The onboard 1.2V core power supply only delivers up to 600mA, but calculations show an expected consumption of 1.6A. Thus an external power supply must be added.

Add Ons

A LM317 produces 1.24V for the core and a MAX232 provides a serial port for data exchange with a PC.

In addition to the big heatsink for the LM317 one is added to the FPGA. The FPGA will still heat up to about 60C. The LM317 reaches a temperature of 55C.

This is not surprising as most of the logic is used in crypt cores and due to the nature of cipher algorithms every bit has a 50% chance to toggle. The result is a worst case power consumption and heat production.

Performance Data

Device Comparison

Hardware MKeys/sec Crypt Cores Clock (MHz) Cost (Euro) Notes
XC3S5000-4 45.0 150 (1)
XC3S1000-4 9.2 35 105 78
XC3S200-4 2.1 7 120 28
AMD64 3000+ 0.4 2000 120 (2)

(1) = estimated values as device is not easily obtainable
(2) = running ‘john’ password cracker with heavily optimized crypt implementation

Times for a Single Unit in Hours (XC3S1000-4)

Password Set 5 Chars 6 Chars 7 Chars 8 Chars Notes
a-z 0 0 0.2 6.3
a-z, 0-9 0 0.1 2.4 85.2
a-z, 0-9, (A-Z) 0 0.1 3.4 123
a-z, A-Z 0 0.6 31 1614.1
a-z, A-Z, 0-9 0 1.7 106.3 6592.4

Cost for Cracking Within One Hour in Euro (XC3S1000-4)

Password Set 5 Chars 6 Chars 7 Chars 8 Chars Notes
a-z 78 78 78 546
a-z, 0-9 78 78 234 5332
a-z, 0-9, (A-Z) 78 78 312 6448
a-z, A-Z 78 78 1984 67830
a-z, A-Z, 0-9 78 156 5564 276906

The prices listed are private end user prices in Germany. Companies can likely get the chips much cheaper in large quantities. Discounts used: 1-25: 78 Euro, 26-100: 62 Euro, 101-250: 52 Euro, >250: 42 Euro

License

Files found in the downloadable archives below are released under the GNU GPL.

Downloads

As I do not have time to stay up to date on the issue, the full VHDL code will not be available for download anymore. You can still download the VHDL crypt implementation. (includes DES) It basically performs the same operation as the UN*X function, except that comparison with the target hash is integrated and not done externally.

Crypt Implementation