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
On September 20, 2006 a new computer crime law was proposed by the German Bundestag. It will prohibit to publish computer programs suitable to crack passwords.
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 (2006-09-09)
Quite annoying about that idiotic german law. Found it all quite interesting anyway. Good luck.