Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 1 Solutions - Ex1.3- 2 mins
- Return to index
- Exercise 1.1
- Exercise 1.2
- Exercise 1.3
- Exercise 1.4
- Exercise 1.5
- Exercise 1.6
- Exercise 1.7
- Exercise 1.8
- Exercise 1.9
- Exercise 1.10
- Exercise 1.11
- Exercise 1.12
- Exercise 1.13
- Exercise 1.14
We consider the long-term security of the Advanced Encryption Standard (AES) with a key length of 128-bit with respect to exhaustive key-search attacks.
AES is perhaps the most widely used symmetric cipher at this time.
- Assume that an attacker has a special purpose application specific integrated circuit (ASIC) which checks keys per second, and she has a budget of $1 million. One ASIC costs $50, and we assume 100% overhead for integrating the ASIC (manufacturing the printed circuit boards, power supply, cooling, etc.). How many ASICs can we run in parallel with the given budget? How long does an average key search take? Relate this time to the age of the Universe, which is about years.
- We try now to take advances in computer technology into account. Predicting the future tends to be tricky but the estimate usually applied is Moore’s Law, which states that the computer power doubles every 18 months while the costs of integrated circuits stay constant. How many years do we have to wait until a key-search machine can be built for breaking AES with 128 bit with an average search time of 24 hours? Again, assume a budget of $1 million (do not take inflation into account).
This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.
1. By the numbers specified, each machine costs $100.
Each of our 10,000 machines checks $5 \times 10^8$ keys per second, so we can calculate the speed of our parallelised machines as:
On average, we’ll find the correct key halfway through our search of the keyspace (), so the average case will be checks.
To calculate the length of time to find a key in the average case:
This comes out to:
This is approximately times longer than the elapsed age of the universe.
2. If we represent the number of Moore’s Law iterations to bring the using then we can express the equation as:
We can rearrange this equation to make the only item on the left:
The reveals a value of which is roughly .
Rounding the number of iterations to 69 allows us to calculate the number of years: