22
$\begingroup$

Suppose that a single evaluation of a block-cipher (DES or AES) takes 10 operations, and the computer can do $10^{15}$ such operations per second.

How long would it take for to recover a DES key, using a brute-force search? How about a 128-bit AES key?

$\endgroup$
34
$\begingroup$

Assume that 1 evaluation of {DES, AES} takes 10 operations, and we can perform $10^{15}$ operations per second. Trivially, that means we can evaluate $10^{14}$, or about $2^{46.5}$ {DES, AES} encryptions per second. This is a simplistic view: we are ignoring here the cost of testing whether we found the correct key, and the key schedule cost.

So on our hypothetical machine, a 56-bit DES key would take, on average, $2^{55}/2^{46.5} = 2^{8.5} \approx 362$ seconds to find. Similarly, a 128-bit AES key would take $2^{127}/2^{46.5} = 2^{80.5}$ seconds $\approx 2^{55}$ (or approximately $36$ quadrillion) years to find.

$\endgroup$
  • $\begingroup$ Just because it confused me for a bit – 56 bits does of course mean $2^{56}$ possibilities, but on average you'll find the right one after trying half of them, hence $2^{55}$. $\endgroup$ – PJSCopeland Oct 17 at 3:01
1
$\begingroup$

You can look at the time taken by the 3 DES Challenges :

  • DES Challenge 1 = 140 days
  • DES Challenge 2 = 41 days
  • DES Challenge 3 = 56 hours

Source: http://cs-exhibitions.uni-klu.ac.at/index.php?id=263

$\endgroup$
-3
$\begingroup$

It depends on the implementation. I just cracked one in about five minutes using Task Manager and a hex editor. It was a commonly used public domain implementation, but free (so probably not a good example). Just took a dump of the process after it ran and searched it for my key. Looked for associate memory fragments surrounding the key. Now I can find the key for anyone running that implementation. Buy a good program that does not do a sloppy implementation.

$\endgroup$
  • 8
    $\begingroup$ Hi jjhiv and welcome. Cracking an application is not the same thing as a brute force search, as required in the question. Unfortunately I had to vote your answer down for that reason. $\endgroup$ – Maarten - reinstate Monica Jun 4 '17 at 23:02
  • $\begingroup$ I agree, I have not answered the question on the table. Please continue to enjoy the exercise. $\endgroup$ – jjhiv Jun 5 '17 at 13:50

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