23
$\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?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
31
$\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?

Improve this answer
$\endgroup$
5
  • 2
    $\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
    Commented Jun 28, 2017 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
    Commented Jun 28, 2017 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
    Commented Jun 28, 2017 at 9:44
  • $\begingroup$ Hey @tylo in 2020 the hash rate of the Bitcoin network has grown from 5,000,000 TH/s (around the date you answered) to a recent peak of 125,000,000 TH/s. Could you provide an update on how much of a dint this has made compared to 2017? Thanks $\endgroup$
    – joep
    Commented Mar 24, 2020 at 19:14
  • 1
    $\begingroup$ @joep it changes it from about 160 times the age of the universe to about 6 times the age of the universe. An impressive time save! But it doesn't change the core of the answer- 128-bit keys are for all practical purposes not possible to brute force now or any time in the foreseeable future. $\endgroup$
    – Chris
    Commented Sep 20, 2021 at 16:55
7
$\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 per second. 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The AES implementation you mentioned is from this paper, right? sciencedirect.com/science/article/pii/S2314717215000380 $\endgroup$
    – Cepheus
    Commented Dec 30, 2018 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
    Commented Jan 1, 2019 at 2:03
  • $\begingroup$ Has some of the details I was looking for (thanks), but without factoring in the likely arrival of quantum computing the answer is questionable. $\endgroup$
    – mc0e
    Commented Aug 18, 2019 at 4:42
3
$\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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jun 28, 2017 at 11:25
  • $\begingroup$ Sorry, meant $2^N$ ciphertexts, fixed it. $\endgroup$
    – Rukako
    Commented Jun 28, 2017 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".

Improve this answer
$\endgroup$
4
  • 4
    $\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
    Commented Feb 20, 2018 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
    Commented Feb 21, 2018 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
    Commented Feb 21, 2018 at 15:27
  • 1
    $\begingroup$ @Nick: So you are saying that a 128-key has a 128-bit safety margin. Yes. That is true. :-) $\endgroup$
    – Johannes Overmann
    Commented Jan 21, 2021 at 9:00

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.