The use of cryptography is growing rapidly with the adoption of computer technology. The design of cryptographic ciphers is still not well understood; we cannot prove the security of an algorithm. Currently, the only way to be sure of the security of an algorithm is to study it for a long period of time and use the absence of attacks as evidence confirming its security.
All ciphers are vulnerable to an exhaustive key search attack. An attacker can try every single possible key to check its correctness. This is time consuming, but feasible for several widely deployed ciphers.
An obvious way to conduct an exhaustive key search attack is to write software that will check each key in turn. Current microprocessors have clock rates in the gigahertz range and can execute several instructions per clock cycle. They are also cheap, highly available and easy to program.
Another possibility is to use a Field Programmable Gate Array (FPGA) device to conduct an exhaustive key search. FPGAs provide the functionality of a custom chip without the high up-front cost and lead time. They have much lower clock rates than general-purpose CPUs, but can be designed to perform one task exceptionally well. Parallelism can also be exploited to increase the overall search rate.
We thus have several questions requiring investigation with regard to FPGA technology in cryptanalysis:
Exhaustive key search is guaranteed to be a possible attack for any cipher, but not necessarily feasible. Most new ciphers that are being deployed have key lengths of 128 bits or greater. A cipher with such a key length cannot be feasibly attacked with current technology. Nevertheless, there are many reasons why conducting research into exhaustive key search attacks is worthwhile.
A lot of currently deployed encryption is vulnerable to key search attacks. The default encryption used by GSM mobile phones and 802.11b wireless networks uses a key which is short enough to facilitate exhaustive key search. The DES cipher was widely deployed in the banking industry (amongst others) and is vulnerable. Many websites using SSL encryption are also vulnerable.
Export restrictions in many areas prevent the use of ciphers with long key lengths. The United States has a history of restricting the export of strong cryptography, often using key length as a deciding factor. The Wassenaar agreement stipulates similar limitations and is enforced by 33 countries around the world, including Australia.
Small embedded devices may not be able to support ciphers with long key lengths. Cheap smart card devices containing encryption software are becoming more widespread. In order to meet cost or size constraints, many of these devices use very short key lengths or known weak ciphers. The encrypted data transmitted from many of these devices can be attacked using exhaustive key search.
Many other attacks employ an exhaustive key search. Many attacks work by reducing the key space to an amount which can be feasibly searched or by removing large sections of the key space that can be proven to not contain the target key. Time/memory tradeoff attacks usually require a large preprocessing step which resembles key search. Both of these attack types require a key search to be conducted as part of their operation.
Key search machines can be useful research tools. Research into other attacks may require a cipher to perform particular operations or to generate plaintext or ciphertext with certain characteristics. Exhaustive key search can be used to achieve this.
Weak encryption has been used extensively in the past. Significant amounts of information has been encrypted with ciphers that are vulnerable to exhaustive key search or other attacks. Encrypted data could be stored until the technology or techniques to reveal that data become available. Key search machines may still be able to reveal valuable information that was encrypted in the past. Similarly, future technology may be able to reveal even today’s strongly encrypted data.
Exhaustive key search is highly parallelisable. This makes it a valuable application with which to experiment with parallel computing techniques.
In order to determine the utility of FPGAs when conducting exhaustive key search attacks, we need to consider their potential price and performance benefits over other technologies such as ASICs and CPUs. Pricing data can be obtained from suppliers, while performance data can be gathered from implementations. Performing implementations should also provide useful insights into the issues involved with cipher and key search machine design.
CPU pricing can be obtained from suppliers and performance measured with benchmark software. ASIC price and performance estimates can be obtained from suppliers.
The optimal family and device within each technology can be determined by computing the price for a certain search rate. Comparing price/performance ratios between technologies for different ciphers will help to determine which technology is best under what conditions.
From these analyses, it should be possible to recognise situations where FPGAs can be beneficial in key search applications.
Chapter 2 describes all of the past work, theory and knowledge that will be needed to understand the remainder of the thesis. It also sets the context for the new developments made by this thesis. Chapter 3 describes the design and implementation work that was performed in order to gather meaningful data. It allows the data analysis to use real-world data. Chapter 4 analyses the gathered data to form conclusions on a wide variety of areas, and forms the bulk of this thesis. Chapter 5 summarises the conclusions and provides directions for future work.
