# how to calculate the average key search for AES-128bit?

Assume that an attacker has a special purpose application specific integrated circuit (ASIC) which checks $5\times 10^{8}$ 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 $10^{10}$ years.

I know that we can run $20\ 000$ ASICs with ONE million budget, but I don't understand how to calculate the average key search, is it $2.5 \times 10^{19}$?

• I'm voting to close this question as off-topic because it's an exercise in arithmetic only tangentially related to cryptography. – Reid Sep 7 '17 at 21:55
• You missed the '100% overhead' so you have 10,000 ASICs. Although there is also ongoing cost for power and cooling, which your teacher seems to have left out. – dave_thompson_085 Sep 8 '17 at 3:20

## 1 Answer

Since key search is "embarrasingly parallel", i.e., you can have different ASICs searching different parts of the key space, you have $$20{,}000\approx 2\times 10^{11}$$ processors and the keyspace is of size $2^{128}$. There are $$3600\times 24\times 365.25\approx 2^{24.9}$$ seconds in a year so you can check $$2^{11} \times 2^{24.9} \times 2^{28.9}\approx 2^{64.8}$$ keys per year, the last factor being $2^{28.9}\approx5\times 10^8$. So this gives $$2^{127} \times 2^{-64.8} =2^{62.2}\approx 10^{18.72} \approx 5.25 \times 10^{18}$$years if I haven't made a mistake somewhere.

Also I interpreted your

can search 5.108 keys per second

as $5\times 10^8.$

Edit: Fixed computation. Thanks, @dave_thompson_085

• The key search would take on average 2^127 guesses, not 2^128. – user13741 Sep 7 '17 at 21:14
• You actually have 10,000 chips (see my comment on Q) each doing 5e8 trials/sec -> 5e12/sec~2^42/sec -> 2^67/year thus average about 2^60 years for completion which is conveniently close to 10^18 years. PS: if your 2^11 was correct (not quite) the sum of 11+24.9+28.9 is 64.8. (Sorry I'm too lazy to texify.) – dave_thompson_085 Sep 8 '17 at 3:37