FPGA Parallel DES cracker

This is a project intended to learn distributed computing with an FPGA. The DES keyspace is split up into blocks with multiple cores processing them in parallel until the key we're looking for is found, or we reach the end of the keyspace.

As a proof of concept, I've tested this with 16 cores clocked at 150MHz on an Altera DE2i-150 development board featuring a Cyclone IV FPGA.

Keyspace and distribution

The 56-bit DES keyspace (72,057,594,037,927,936 keys) is split up into blocks with 4,294,967,296 keys (32 bits) per block, resulting in 16,777,216 blocks (24 bits). With 16 cores, the keyspace can be split up as follows:

55 - 3634 - 3231 - 0
Block indexBlock keyspace
CounterCore ID

All cores will finish processing the blocks at the same time, so we can assign a new block to all of them at the same time. Since that's the case we can simply remove 4 bits of the 24-bit counter in the block manager and hardwire that part of the block index per core, leaving us with 1,048,576 blocks (20 bits) to process.

More cores!

The next step is to increase the amount of cores to whatever my DE2i-150 board can handle, limited to a power of 2 since it affects the block index. Currently a single block takes about 8.6 minutes to process, the following table shows the total time to process the entire keyspace and block counts for a few different setups.

CoresBlock countTotal time
16104857617y 57d
325242888y 211d
642621444y 105d
1281310722y 52d
256655361y 26d

More information coming soon.