1
$\begingroup$

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}$?

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm voting to close this question as off-topic because it's an exercise in arithmetic only tangentially related to cryptography. $\endgroup$
    – Reid
    Commented Sep 7, 2017 at 21:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – dave_thompson_085
    Commented Sep 8, 2017 at 3:20

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ The key search would take on average 2^127 guesses, not 2^128. $\endgroup$
    – user13741
    Commented Sep 7, 2017 at 21:14
  • 1
    $\begingroup$ 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.) $\endgroup$
    – dave_thompson_085
    Commented Sep 8, 2017 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.