From the analyses presented in Chapter 4, we can see that:
Key length, available resources and cipher design are the main three factors that influence the time taken to conduct an exhaustive key search attack.
Different implementation technologies favour different ciphers. DES key searches are best performed with FPGAs, while RC5 key searches are best performed with CPUs.
The resource usage of a pipelined FPGA cipher implementation is dependent on the frequency of register access, state size, number of rounds and complexity of the round function.
Frequency of register access is one of the biggest factors affecting resource usage for pipelined FPGA cipher implementations.
If sufficient FPGA resources are available, pipelined cipher implementations will perform far better than iterative cipher implementations.
Based on preliminary pricing, Spartan 3 FPGAs (particularly the XC3S400) have the best price/performance ratio.
Based on stable pricing, Spartan IIE FPGAs (particularly the XC2S200E) have the best price/performance ratio, followed closely by the XC2VP20 (which has a much higher density).
Duron and low-end Athlon XP CPUs provide the best price/performance ratio.
The performance estimates in [2] are most likely to be optimistic. This view is shared by Golberg and Wagner [16].
The cost of conducting a ciphertext-only attack with FPGAs depends on the cipher. The additional resource cost is quite small for DES, but significant for RC5. Ciphertext-only attacks favour large, fast search units over small slow search units.
A machine similar to the EFF DES cracker [10] could be built from FPGAs for approximately $34,000, a fraction of the price of the original machine.
CPUs are more cost-effective for RC5 key searches than FPGAs, although it remains to be seen whether this remains true for a pipelined RC5 implementation.
Cryptography that is restricted to a 56 bit key length by export controls provides little protection against a well-funded or patient adversary.
FPGAs will play a greater part in cryptanalysis in the future.
From these conclusions, we can see that in the right situations FPGAs are very useful cryptanalytic tools. Their low price and high performance allows key search attacks to be conducted at very low cost. If physical space devices is a concern, they can achieve much higher search rates per device than CPUs, even for ciphers that are designed for CPUs.
The EFF DES cracker can be reproduced now using FPGAs at a cost of about $34,000. At a price this low, DES should not be used for anything remotely secure. Government concessions to allow the export of 56 bit cryptography completely destroy the purpose of using cryptography.
FPGAs will play an increasing role in future cryptanalysis as the gap between CPU and FPGA performance for a given price widens.
Future work
Possible extensions to this work include:
Update the price/performance analyses as time progresses. This would allow the security of ciphers to be continually tracked and give a general idea of the rate of improvement in FPGA and CPU technology.
Analyse more ciphers and determine their resistance to exhaustive key search using various technologies.
Examine DSPs and CPLDs as possible low-priced technology alternatives.
Improve the DES benchmark software. The programs used for benchmarks were not designed with modern CPUs in mind, and may be able to achieve very high performance by taking advantage of available features. In particular, SIMD architectures such as Altivec and SSE2 may prove useful.
Implement RC5 as a long pipeline. Estimates show that this may result in very high search rates. High capacity FPGA devices would be needed to attempt this.
Examine different FPGA families. No Altera devices were considered for this thesis. Actel produces a gate array family called the Axcelerator [66] which is one-time programmable and is reported to have very low routing overheads and a low price. Spartan 3 devices should also be re-examined once better pricing data becomes available.
Improve the accuracy of the price/performance estimates for ASIC devices. Different fabrication processes may provide better price/performance ratios.
Extend the FPGA resource estimation techniques to include timing data. With careful analysis, it should be possible to approximate overall performance given a cipher algorithm.
Consider heat generation and power usage for FPGAs. One of the problems encountered with the EFF machine was the high power and cooling requirement for the machine. FPGA devices are reported to be inefficient in this regard, which may prove a stumbling point for large-scale key search machines.
References
[2] M. Blaze, W. Diffie, R. L. Rivest, B. Schneier, T. Shimomura, E. Thompson, and M. Wiener, “Minimal key lengths for symmetric ciphers to provide adequate commercial security,” A Report by an Ad Hoc Group of Cryptographers and Computer Scientists, January 1996. [Online]. Available: http://www.schneier.com/paper-keylength.pdf
