Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 3 Solutions - Ex3.11

- 2 mins

Exercise 3.11

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.

  1. 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
  2. How many COPACOBANA machines do we need in the case of an average search time of one hour?
  3. 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.

Solution

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


Thomas Busby

Thomas Busby

I write about computing stuff

comments powered by Disqus
rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora