The minimum key length for the AES algorithm is 128 bit. Assume that a special-purpose hardware key-search machine can test one key in 10 ns on one processor. The processors can be parallelized. Assume further that one such processor costs $10$, including overhead. (Note that both the processor speed and the prize are rather optimistic assumptions.) We assume also that Moore’s Law holds, according to which processor performance doubles every 18 months. How long do we have to wait until an AES key search machine can be built which breaks the algorithm on average in one week and which doesn’t cost more than $1$ million?

  • 1
    $\begingroup$ Does the answer of How long does it take to crack DES and AES? satisfy you? $\endgroup$ – kelalaka Jan 17 '19 at 7:32
  • $\begingroup$ no,i just cant understand $\endgroup$ – Network reader Jan 17 '19 at 7:35
  • 1
    $\begingroup$ This seems this is a purely mathematical question and is not actually related to cryptography. $\endgroup$ – forest Jan 17 '19 at 7:35
  • $\begingroup$ @kelalaka Those answers are grossly overestimated as they ignore the exponential effect of Moore's Law. $\endgroup$ – Paul Uszak Jan 18 '19 at 3:41

Disclaimer: This answer is only a mathematical evaluation of Network reader's question. In reality, the maximum possible (traditional) processor performance is limited in space, time and cost by Planck time, Planck length and quantum tunneling.

As forest pointed out, this question is purely mathematical and not very practical (optimistic assumptions), so it would be better suited on a mathematical site.

Nonetheless, it's an interesting problem and I couldn't resist.

To start with, we first need to calculate how many attempts (tests) $n$ are necessary in the worst case. Assuming the minimum AES key length, that number would be $$ n = 2^{128} \approx 3.402824 \times 10^{39} $$ Next, we need to create a function that models the time $1$ processor needs to test all possible keys, where $m$ is the number of months passed. Every $18$ months, the time required to test a single key is halved, as processing power doubles: $$ t_1(m) = n \times 10 \times 2^{-\frac{m}{18}} \ \ \mathrm{ns} $$ One week $w$ equals $6.048 \times 10^{14} \ \ \mathrm{ns}$, so the time you'd have to wait until one processor is fast enough to test all possible keys in one week is $1,480$ months.

If you were to buy more processors (100,000 in your example, as each one costs 10 and you want to spend a million), it would only speed up the process by the number of processors you used. Usually quite an advantage, but in this case it only makes the numbers a little less crazy: Assuming we are able to distribute the work equally to all $100,000$ computers $$ t_{100,000}(m) = t_1(m) \times \frac{1}{100,000} $$ we would still have to wait $1,181$ months, that's about $98$ years until your hypothetical processors are fast enough to test all possible AES-128 keys in one week, with things only getting worse when you consider bigger key lengths.

Desmos Graph: https://www.desmos.com/calculator/du9vsqthdv

| improve this answer | |
  • 4
    $\begingroup$ What this answer ignores is of course that Moore's Law is just wrong when considered in these time scales. Within the framework of this question, according to Moore's law after a mere 118 18 month cycles (2124 month or 177 years) the processor achieves the quite unlikely feat of testing a key within less than one Planck time. Exponential growth like that just doesn't work in the real world long term. $\endgroup$ – Maeher Jan 18 '19 at 8:24
  • 1
    $\begingroup$ I realized that the million-dollar part actually requires more detail than is addressed here: The cost will almost certainly be dominated by the cost of energy to run and cool the devices, rather than the up front cost of the hardware. You'd need to factor in the cost of energy, which would probably drastically change the already wildly optimistic bottom line. $\endgroup$ – Ella Rose Jan 21 '19 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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