Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 3 Solutions - Ex3.11- 2 mins
- Return to index
- Exercise 3.1
- Exercise 3.2
- Exercise 3.3
- Exercise 3.4
- Exercise 3.5
- Exercise 3.6
- Exercise 3.7
- Exercise 3.8
- Exercise 3.9
- Exercise 3.10
- Exercise 3.11
- Exercise 3.12
- Exercise 3.13
As the example of COPACOBANA shows, key-search machines need not be prohibitive from a monetary point of view. We now consider a simple bruteforce attack on DES which runs on COPACOBANA.
- Compute the runtime of an average exhaustive key-search on DES assuming the following implementational details:
- COPACOBANA platform with 20 FPGA modules
- 6 FPGAs per FPGA module
- 4 DES engines per FPGA
- Each DES engine is fully pipelined and is capable of performing one encryption per clock cycle
- 100 MHz clock frequency
- How many COPACOBANA machines do we need in the case of an average search time of one hour?
- Why does any design of a key-search machine constitute only an upper security threshold? By upper security threshold we mean a (complexity) measure which describes the maximum security that is provided by a given cryptographic algorithm.
This solution is verified as correct (mostly, see note under 2.) by the official Solutions for Odd-Numbered Questions manual.
1. Firstly we’ll calculate the number of DES encryptions for one machine per clock cycle:
There are clock cycles per second as per the question definition. As such, the number of keys checked per second (equivalent to number of encryptions performed per second) is:
To calculate the run-time of an average cause exhaustive search ( checks), we can use the following formula:
This comes out to approximately 8.69 days.
2. In order to calculate how many machines we need for a time of one hour (3600 seconds), we can construct the following equation:
We can rearrange this equation to calculate :
Obviously, you can’t have 0.5 of a COPACABANA machine, so the answer must be rounded up to 209.
Note: The solution manual claims that the answer is 18 machines, but after checking and re-checking my answer, I’ve become convinced this is a mistake. By feeding 18 machines back into the equation that produced a correct answer for (1), it does not come out to anything approaching one hour. If you divide 750,600 by 18, it also doesn’t produce the desired result of 1 hour.
3. The machine performs a brute–force attack. However, there might be more powerful analytical attacks which explore weaknesses of the cipher. Hence, the key–search machine provides only a lower security threshold