5
$\begingroup$

How long would it take to crack a AES-128 key using the most advanced technology currently available? The hardware can be anything, be it a high-performance CPU, GPU or even FPGA?

$\endgroup$
13
$\begingroup$

I wrote a similar answer in the past, where the assumption was half the key is known. Since then, the bitcoin hashrate almost tripled (it's used in the estimation, as below). The estimation for half the known key would therefore be $~3.6$ seconds.

But to brute force a $128$ bit key, we get this estimate:

Let's assume we can test as many keys as the current hashrate of the bitcoin network. There special purpose hardware is used and it's for SHA-256, this makes it not directly usable, but it should be close. That means we could test approximately $5 \cdot 10^{18} \approx 2^{62.117}$ encryptions per second. Regarding the type of hardware: For some years now bitcoins are mined mostly with ASICs, which are faster and more efficient than all of those options you listed. That's special purpose hardware, which can't be programmed to do anything else - but it's the best we can do for speed.

That means, for the full key we need $\approx 2^{128} / 2^{62.117} = 2^{65.883}$ seconds. This is approximately:

  • $68 \cdot 10^{18}$ seconds
  • $18.9 \cdot 10^{15}$ hours
  • $2.158 \cdot 10^{12}$ years. Written as integer: $2,158,000,000,000$

Since that number is still slightly hard to grasp, this is the age of the universe: $13.799 \cdot 10^9 = 13,799,000,000$

So a rough estimation would be $156.4$ times the age of the universe for testing all keys. You can divide that number by $2$ to get the average time to find the correct key.

Related question: How much would it cost in U.S. dollars to brute force a 256 bit key in a year?

$\endgroup$
  • 1
    $\begingroup$ Since you're being pedantic and including the .4 in the 156.4 universes, have you allowed for Moore's law increases in computing power that will erode the X times estimate? i realise that would make the calculation more complex, but precision demands precision :-) $\endgroup$ – Paul Uszak Jun 28 '17 at 0:37
  • 1
    $\begingroup$ @PaulUszak You're right, we could include Moore's law, but then the calculation is pretty much impossible: We don't know how long Moore's law will be valid. It is physically impossible to go beyond certain thresholds, e.g. the laws of thermodynamics, the minimal energy required to stor a single bit would be one electron, etc. $\endgroup$ – tylo Jun 28 '17 at 8:01
  • $\begingroup$ And of course the basic assumption of the computation power of the bitcoin network is also quite arbitrary. It is just the largest publicly known system for paralllel computation (and it's thematically similar - large computing centers are often optimized for floating point operations). But the bitcoin network is still growing - we can't estimate how it develops over this period of time. And finally: We could also consider the estimated timespan until our sun expands to a red giant and burns earth in the process. Assuming that, the answer is: It's not finished befoe that point in time. $\endgroup$ – tylo Jun 28 '17 at 9:44
4
$\begingroup$

High efficiency AES implementations are known to operate at 277Mb/s using 13.21mW of power. That is 163,820,000 block encryptions per watt. Imagine we can do 128 times better over time, say in the next 100 years (should be easy with lots of money).

Now imagine we extract 7500TW of solar energy by covering the planet in solar panels (landmass not required for plant growth), and under those panels are our AES processors.

With our 'today' efficiency we can process $2^{80}$ keys per second, our future efficiency would be able to do $2^{88}$ easy, but that still leaves $2^{40}$ seconds required to fully process a 128-bit key, or over 34000 years.

We will hit the limits of lithography, but I would assume we can improve our compute performance another 128-times in that time period, and maybe improve solar efficiency by double, so lets say 136 years. If we really decide to cover all land mass with solar panels to do the job, we can get maybe 4X more power, and get it done in 40 years.... BUT it will take much longer than that for process tech and buildout of the panels, and the infrastructure to get it all working, so I would still say at least a few centuries, probably under 2000 years.

$\endgroup$
  • $\begingroup$ The AES implementation you mentioned is from this paper, right? sciencedirect.com/science/article/pii/S2314717215000380 $\endgroup$ – Cepheus Dec 30 '18 at 17:03
  • $\begingroup$ @Cepheus looks like it, and that is already 3 years old, power usage for a full general purpose CPU-SOC with crypto engine will be higher (a Microchip PIC32 will push 1800Mb/s but consume around 300mw) but a system designed for cracking is by design much more efficient, a Cavium Nitrox V is something like 40Mb/s per mW on a full ARMv8 board with ethernet right now $\endgroup$ – Richie Frame Jan 1 at 2:03
2
$\begingroup$

Assuming that you have $2^N$ ciphertexts with different keys each, finding one of the plaintext becomes easier as $N$ increases ($2^{128 - N + k}$ tries - where $k$ is $2^k$ = the amount of plaintexts you want to find), making it actually feasible to find some plaintexts of AES-128 with a large amount of ciphertexts in a reasonable time.

Also see https://cr.yp.to/snuffle/bruteforce-20050425.pdf or if you want a simpler explanation https://blog.cr.yp.to/20151120-batchattacks.html

$\endgroup$
  • $\begingroup$ That formula can't be right, because then $130$ plaintexts would be enough for $k = 2$ to reduce the overall number to $2^{128-130+2} = 1$. $\endgroup$ – tylo Jun 28 '17 at 11:25
  • $\begingroup$ Sorry, meant $2^N$ ciphertexts, fixed it. $\endgroup$ – Rukako Jun 28 '17 at 11:59
-3
$\begingroup$

I didn't understand the most answers here. I my view, exascale computing will be able, to easily crack 128 bit keys in near future. And in fact, 128 bit stands for random generated 16 byte masterkeys, with an security margin of 16^16 (a-f, 0-9). That masterkey is always used to encrypt the data, and is also encrypted by the user password.

That means: 16^16/10^18 (exascale computer) = 0,3 seconds to test all possibilities to find the masterkey (without delays/iterations), without any user password. So only 256 bit keys with 32 byte are secure enough, to protect our data for the next decades. An 512 or 1024 bit cipher would be even better, to have no problems for the next xxx hundred years. I didn't like that "secure enough for xx years".

$\endgroup$
  • 2
    $\begingroup$ 16^16 is much, MUCH less than 2^128. Each byte can take on one of 256 values, not just 16. That means it's 256^16 = 2^128 when expressed in bytes. $\endgroup$ – SAI Peregrinus Feb 20 '18 at 4:48
  • 1
    $\begingroup$ And even for the incorrect case used, your arithmetic is wrong, though not enough it would have mattered. (16^16=2^64) / 10^18 ~ 18.4. $\endgroup$ – dave_thompson_085 Feb 21 '18 at 0:43
  • $\begingroup$ I found one of my mistakes. Contrary to my statement, a 16-byte string does not correspond to a 16-digit string. And since 16 bytes are represented cryptographically in hex format, this results in a good 32-digit string, which corresponds to a safety margin of 128 bits. That would be far beyond what can be calculated within a reasonable time. $\endgroup$ – Nick Feb 21 '18 at 15:27

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.