230
$\begingroup$

I am often told that any key can be broken and that it is only a matter of time and resources for any key to be broken. I know that this is technically true. However, I think that there is probably a point where it makes sense to say a key is uncrackable (for example, if it would cost 100 times the world GDP to crack it, it is essentially uncrackable without the help of an advanced alien civilization, etc.).

How much would it cost in U.S. dollars to brute-force a 256-bit key using a strong algorithm such as AES or Twofish in a year?

I would also be curious to know what it would cost to crack a 128-bit key in a year.

I am asking this mostly out of curiosity. I do not know very much about cryptography, so please feel free to pick the algorithm of your choice if that matters. I am interested in how one would project the cost (assume you have to buy the hardware but you get to choose what hardware you buy).

$\endgroup$
4
  • 145
    $\begingroup$ According to xkcd, $5 for hardware. $\endgroup$ Jun 24, 2012 at 20:54
  • 1
    $\begingroup$ You're asking the wrong question; you can use batch attacks to attack a lot of keys at the same time $\endgroup$
    – Navin
    May 16, 2017 at 12:32
  • 2
    $\begingroup$ @HendrikBrummermann I've never liked that comic. It ignores the fact that a huge percentage of keys are not even known by the people who operate them. $\endgroup$
    – forest
    Feb 25, 2018 at 3:47
  • $\begingroup$ @HendrikBrummermann that XKCD doesn't work for the most common case:The user lost their password and are desperately trying to gain access to their own data again. $\endgroup$ May 12, 2020 at 11:43

8 Answers 8

202
$\begingroup$

The average cost of electricity in the US is $\$0.12$ per kWh. For a single server, I'll use 3741 kWh annually as an estimate. That would be about $\$450$ per year for one machine.

Let's say you can do $10^{14}$ decryptions per second. That is $3.15\times 10^{21}$ decrypts per year for one machine. You need to do (on average) $2^{255}$ decryptions in a year, so you would need $\frac{2^{255}}{3.15\times 10^{21}} \approx 1.84\times 10^{55}$ machines. To figure your cost you would multiply that by $\$450$ and get about $\$8\times 10^{57}$ or 8 octodecillion dollars. Gross world product, or GWP, is about $63\times 10^{12}$, so brute-forcing a 256-bit key would cost about $10^{44}$ times the GWP.

You can follow similar math to get the cost of brute forcing a 128-bit key.


Note:

I am completely ignoring hardware costs, maintenance, etc. The estimate above is for electricity only. We can take a hint from the NSA on this. You'd be a lot better off hiring a few thousand mathematicians and have them work on breaking the cipher as opposed to trying to brute-force it.

$\endgroup$
3
  • 10
    $\begingroup$ So I made a spreadsheet with various costs. It would take \$1 trillion to crack 102 bit key, but only \$1000 to crack a 73 bit key. I could not find a source for your decryptions/s. Here is the sheet: docs.google.com/spreadsheet/… $\endgroup$
    – Chloe
    Aug 27, 2013 at 18:50
  • 14
    $\begingroup$ Or you could hire a few thousand crackers, indemnify them against criminal charges, and have them work on establishing access to the endpoint node which already has the key. $\endgroup$
    – user
    Dec 26, 2016 at 18:58
  • $\begingroup$ Trying to acquire that much of the necessary equipment (or ultimately, the materials and energy to build it) would distort the world markets in those items, so the price would theoretically be much higher than shown by this calculation. In fact, since the necessary materials/energy are not to available to humankind at all (the laws of physics preclude transporting the necessary matter/energy to earth in that timeframe), the price (according to supply and demand) would have to rise to the point that buyers could not afford it. But then you have to consider the effect on the value of currencies. $\endgroup$ Aug 27, 2018 at 21:50
186
$\begingroup$

There is some Thermodynamic Limitations. A good explanation about Thermodynamic Limitations is by Bruce Schneier in Applied Cryptography:

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than $kT$, where $T$ is the absolute temperature of the system and $k$ is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that $k =1.38 \cdot 10^{-16} \mathrm{erg}/{^\circ}\mathrm{Kelvin}$, and that the ambient temperature of the universe is $3.2{^\circ}\mathrm K$, an ideal computer running at $3.2{^\circ}\mathrm K$ would consume $4.4 \cdot 10^{-16}$ ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about $1.21 \cdot 10^{41}$ ergs. This is enough to power about $2.7 \cdot 10^{56}$ single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all of its energy for 32 years, without any loss, we could power a computer to count up to $2^{192}$. Of course, it wouldn’t have the energy left over to perform any useful calculations with this counter.

But that’s just one star, and a measly one at that. A typical supernova releases something like $10^{51}$ ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

$\endgroup$
10
  • 58
    $\begingroup$ I so love the absolute ambiguity, the concrete confusion, the exact existentialism of "something other than matter" and "something other than space". $\endgroup$
    – Patrick M
    Jun 22, 2015 at 22:55
  • 18
    $\begingroup$ Kelvin does not use degrees. It's an absolute unit. $\endgroup$
    – Alex
    Nov 30, 2015 at 15:41
  • 27
    $\begingroup$ It is a quote from a book, thus even if it has an error, it should stay as is. To edit because Kelvin should not use the degrees sign is irrelevant and does not improve the quality of the answer. Also when you edit a quote, edition should be done between [square brackets]: english.stackexchange.com/questions/2271 $\endgroup$
    – Biv
    Dec 20, 2016 at 14:56
  • 3
    $\begingroup$ @MikeOunsworth pp. 157–8 (taken from here: schneier.com/blog/archives/2009/09/the_doghouse_cr.html) $\endgroup$
    – A. Hersean
    Aug 30, 2017 at 12:54
  • 5
    $\begingroup$ I love this quote, but good god, ergs per degrees Kelvin is a heinous unit to define. $\endgroup$
    – Dancrumb
    Sep 1, 2017 at 15:33
127
$\begingroup$

256-bit key cracking through exhaustive search is totally out of reach of Mankind. And it takes quite a lot of wishful thinking to even envision a 128-bit key cracking:

  • trying one key must be reduced to the flip of a single logic gate (compared to the hundreds of thousands which are actually required);
  • that gate must be more energy-efficient than the most efficient logic gates currently in production;
  • all of the energy production on Earth must be diverted to that single key cracking goal.

Under these conditions (each of which is utterly unrealistic in its own way), a 128-bit key cracking effort could be imagined.

But this is far beyond the point where the notion of "dollar" makes any sense. The dollar is a currency: a conventional representation of "values", that people give to each other under the assumption that they could convert it back to tangible objects or services as they wish. So there is no possible notion of the dollar when the sum far exceeds the total worth of what can ever be bought on Earth. The Gross World Product is, as of 2011, somewhere between 60 and 80 trillions of dollars: it depends a lot on what dollar you use as a basis and how you try to map that on "purchase power". The point is that there is no meaningful notion of dollar beyond about $8*10^{13}$.

If you follow @mikeazo argument (450\$ of energy consumption per machine and per year, where one machine can try about $3.2*10^{21}$ keys per year), then the GWD, converted entirely in energy, would allow for $2.5*10^{35}$ keys to be tried, i.e. a space of 118 bits or so. A 128-bit key space is 1024 times harder than that. Also, this assumes that everything produced on Earth can be reduced to energy with the same efficiency than the most competitive coal plants, which is a bit optimistic because GWD includes a lot of things which are not energy-convertible, such as artistic creations: how exactly would you make electricity out of, say, a song ? Moreover, all the energy invested in the computation becomes, ultimately, heat, so there could be some climatic consequences, as in "the Earth is cooked".


To sum up: even if you use all the dollars in the World (including the dollars which do not exist, such as accumulated debts) and fry the whole planet in the process, you can barely do 1/1000th of an exhaustive key search on 128-bit keys. So this will not happen. And a 256-bit key search is about 340 billions of billions of billions of billions times harder than a 128-bit key search, so don't even think about it.

$\endgroup$
5
  • 32
    $\begingroup$ If 128-bit key cracking is already impossible, then why do we have 256-bit keys? $\endgroup$
    – Joren
    Nov 9, 2011 at 4:42
  • 27
    $\begingroup$ @Joren Good question! :) Some attacks compromise a certain number of rounds of AES with some complexity. For instance, a 2009 attack by Biryukov et. al. compromises 9 rounds of AES with a complexity of 2^39 (as opposed to 2^256 for brute force). It stands to reason that using a 256 bit key rather than a 128 bit key is the easiest way to increase the number of rounds from 10 to 14, i.e. without changing the AES spec. On a side note, Bruce Schneier has previously commented that if ever AES is broken too badly, we merely need to increase the number of rounds to fix it. $\endgroup$ Nov 9, 2011 at 5:25
  • 26
    $\begingroup$ @Joren: historically, AES has 128-, 192- and 256-bit keys because some inflexible US military regulations mandate the use of three distinct "security levels" (under the assumption that "really secure" cryptosystems are necessarily slow -- which was true in the 1930s, but not anymore). The three key sizes are enough to satisfy these regulations; but nobody said that the lower level had to be weak ! Nowadays, the 256-bit key size is rationalized by talking about quantum computers, but that's an afterthought. $\endgroup$ Nov 9, 2011 at 12:03
  • 5
    $\begingroup$ @Joren "If a suitably sized quantum computer capable of running Grover's algorithm reliably becomes available, it would reduce a 128-bit key down to 64-bit security, roughly a DES equivalent. This is one of the reasons why AES supports a 256-bit key length." $\endgroup$
    – daniel
    Jun 21, 2017 at 14:05
  • $\begingroup$ 128 bit brute force cracking is infeasible, but someone might come up with a more clever method than brute force. $\endgroup$
    – gnasher729
    Dec 21, 2021 at 15:30
35
$\begingroup$

Non-technical brute force method:

The most cost-effective "brute-force" method I can think of is to hire a gang of mobsters to force the guy who knows the password into giving it up. For a guy with no security, a good mobster would probably cost about \$5,000, and you'd need at least 3 of them. If you are going for a high-profile guy, a good mobster would probably cost about \$50,000 and you would need about 25 of them. Thus, you are looking at anywhere from \$15,000 to \$1.25 million using this method.

Technical brute force method using quantum computers:

If you want to go the technical route, you need to first be sure that you can check the key solely on your resources. Any dependence on someone else's system and they will be the limiting factor, because it will be impossible to try that many combinations without overloading their system.

Once you figure out how to check the key on your system, I'd suggest using a quantum computer in parallel with your other computers. Currently, the largest quantum computer is 14 qubits. This kind of computer could theoretically try all combinations of 14 bits in one operation. Thus, the first 14 bits can be treated as one bit if you put it in parallel with your normal computer. This means you can crack the password as if it were 115 or 243 bits instead of 128 or 256, which is a huge gain (8,192 times less expensive).

The cost of your 14-qubit computer will be insignificant to your total cost, even if it were \$1 billion dollars. Thus, using mikeazo's formula, this means that you could crack the 256 bit code with $\frac{2^{242}}{7*10^{18}} \approx \$10^{54}$ dollars and the 128 bit code with $\frac{2^{114}}{7*10^{18}} \approx \$3*10^{15}$ = \$3 quadrillion dollars.

In summary, with each qubit increase in our parallel quantum computer, the above prices will decrease in approximately half until they approach the point where the price of the quantum computer becomes the limiting factor. So dig down deep into that research quantum computer guys, we've got a code to crack!

$\endgroup$
5
  • 14
    $\begingroup$ The non-technical method is often called rubber-hose cryptanalysis, not brute-force. Also note, that as far as we currently know, a quantum computer will only halve the key space for a symmetric cipher (such as AES). See en.wikipedia.org/wiki/Quantum_computer#Potential Thus AES-256 in a quantum world would be equal to AES-128 in the classical world. That result could be improved upon though. $\endgroup$
    – mikeazo
    Nov 8, 2011 at 17:45
  • 2
    $\begingroup$ @mikeazo: The mobsters are brutes, so "brute"-force...oh so funny ;) For my real answer I made the assumption that there was a way to test if any combination of the set of qubits plus a definite combination of the remaining bits is a solution. Worst case if that assumption is false, since a 256-bit quantum computer is able to reduce the key complexity by 128 bits, it is safe to assume that a 14-bit quantum computer would be able to reduce the key complexity by at least 7 bits, which is still a gain of $2^7 = 128$ times less resources. $\endgroup$
    – Briguy37
    Nov 8, 2011 at 19:27
  • 16
    $\begingroup$ The bit about a quantum computer with 14 qubits being able to "try all combinations of 14 bits in one operation" is incorrect. It is a very tempting assumption (a view of quantum computers as zillions of computers all running in parallel through the magic of quantum), but it is wrong -- otherwise, a QC with 256 qubits could break a 256-bit key in time 1. QC does offer (theoretically) a performance boost on exhaustive search, but not to that point: it can reduce a space of size $N$ to $\sqrt{N}$ (hence 256-bit key search with a QC should be as hard as 128-bit "normal" key search). $\endgroup$ Nov 8, 2011 at 19:36
  • $\begingroup$ @Thomas Pornin: I don't know how you can say concretely that my assumption is incorrect. For example, can you prove that it is impossible to make a boolean quantum function that checks if any answer in the combination of qubits is a valid key? This function would allow us to fix one bit as 0 and provide the rest as qubits in both states. If the result our quantum function was true, then the bit we fixed is 0, otherwise it is 1. Thus, the number of operations to determine the key would be the number of bits in the key. $\endgroup$
    – Briguy37
    Nov 8, 2011 at 21:03
  • 18
    $\begingroup$ @Briguy37: I cannot prove it, but some smart people can. Roughly speaking, if we can break a cipher with an $n$-bit key in less than $2^{n/2}$ operations on a quantum computer, then we can break it in less than $2^n$ operations on a classical computer. It is quite technical, but a part of the problem is that even if you have a superposition of many states, the "filtering out" part to get a classical result (a definite 0 or 1) is constrained and cannot be done "at will". $\endgroup$ Nov 8, 2011 at 21:43
22
$\begingroup$

I don't think anyone has addressed the time issue. According to the Margolus-Levitin theorem the limit on the number of operations per second is $6\times10^{33}$ per Joule. The Sun's energy output is about $3.83\times10^{26}$J/sec. You would need to save up the energy output of the Sun for about 25 years to be able to then do $2^{255}$ operations in one year (even assuming you only needed to do one operation per decode).

Another limit might be the Planck time unit, $5.391\times10^{-44}$ seconds. If the time it takes for one device to do one decryption is 1 Planck time, you'd need about $2^{86}$ devices to do $2^{255}$ operations in one year. Since the Earth's mass is about $2^{92}$ grams, if you could keep the mass of each device under 2 oz then converting the entire Earth would give you enough devices.

On the other hand, since doing a billion operations per picosecond would be about $2^{74}$ Planck time per operation, each device running at that speed would need to mass less than 69 silicon atoms in order to have enough without exceeding the mass of the Earth. Unfortunately, light would need to be about 650 times faster to get across even one silicon atom in that amount of time. If you were to reduce it to only 1.5 million decryptions per picosecond, so light could cross one silicon atom each time, you'd need a lot more devices. If each device massed as much as a silicon atom, you'd end up with about 9.7 times Earth's mass.

It would be much more practical to try to brute force a 256-bit key in 10 years. You'd only need one Earth's mass of computing silicon atoms and 1/4th the energy output of the Sun.

Of course, if you could make a device that could be that small and run that fast, it still doesn't help with heat dissipation or the total amount of energy required.

$2^{256}$ is a very large number.

$\endgroup$
7
$\begingroup$

The reason that encryption works is that you have to try on average the order of magnitude of 1/2 the number of permutations in the set of all possible answers. So with 128 bits you have to explore the set of 128 bit numbers and if your are lucky you will explore less than half of the possible answers and if you are unlucky you will explore more than half of the possible answers. Doubling the number of digits thus is the product of the number of possible answers multiplied by itself. Which is, of course, a very big number.

It is not that a quantum computer can do it in one operation any more than an ordinary computer can find the solution of a math problem in one calculation. There is an algorithm and you work the algorithm to find the answer. The difference between ordinary computers and quantum computers is that the quantum algorithm will examine each possible answer of your set at the same time while an ordinary computer will examine only one of the possible answer of your problem at a time (assuming a simple computer rather than one with multiple CPUs.)

As for why you can have a 128 bit key, this becomes clear if you assume that the encryption method is factoring large prime numbers. The way you encrypt is to find the largest secret prime number you practically can, and then multiply it by another prime number of similar order of magnitude. From the previous discussion it is quite clear that the result will be a number that is about twice the number of digits that you can practically factor, and to factor it would take a huge amount of time...probably more time than for the Sun to burn out.

So you encode stuff using the large number as a public cipher to cipher the message, and the only way you can decode it is to factor the public key. Only the person who knows the factors can decode the message, because this calculations are much faster. Such systems use what are called trap door functions. That is to say calculations which are very easy to do, and extremely hard to do in reverse unless you have additional information that is not public, and that can not be easily discovered.

Now the last part, which is really the kicker with quantum computers. It turns out there is some doubt whether we will be able to use such devices in the publicly claimed way. You see in order to use a quantum calculation you have to some how read the answer. The only way you have to read the answer is with statistics. There is no other way. Well, it turns out to do very accurate statistics is a difficult task. If, for example, you wished to find a 256 bit prime number, you would have to do good enough statistics to distinguish the correct 256 bit prime number for all other 256 bit prime numbers, which is to say, you must have an answer that is accurate to about 1 part in 2 raised to the 256th power. It may turn out that this task is as hard as finding the same prime number using an ordinary computer.

The fact is, one of the few definitive results in quantum research relating to interactive quantum computers is IQC = PSPACE. The result means that no interactive quantum computer can give results any faster than calculation in polynomial time. Those that are funded for quantum research claim that this doesn't mean you can't do quantum computing, and I guess they are right. But I haven't heard any of them make a public statement about how one can do an end run around the IQC limitation.

$\endgroup$
3
  • 2
    $\begingroup$ Factoring 256-bit numbers is not really a big problem nowadays, and is much faster than brute-forcing a similar-size key. The RSA key sizes where factoring needs a quantum computer are much larger. (Welcome to Cryptography Stack Exchange, by the way.) $\endgroup$ Dec 2, 2011 at 22:34
  • $\begingroup$ You've confused P with PSPACE there at the end. PSPACE = calculations possible in polynomial space (that is, memory). PSPACE is (probably) even bigger than NP. We don't know that IQC or BQP or any of the other quantum complexity classes are bigger than P, but it's a safe bet on the same order as betting P != NP. $\endgroup$
    – zwol
    Dec 20, 2011 at 20:23
  • $\begingroup$ This is post number 1337 :) $\endgroup$
    – Polynomial
    Jul 23, 2012 at 18:49
0
$\begingroup$

Let's take the GDP and crypto miners as the auxiliary tools to show how big would it cost.

  • GDP of America: it is about 200 billion dollars in 2018, noted as $2\times 10^{12}$, which is approximately equal to $2^{37}$ ($10^{12}>8^{12}>2^{36}$).
  • Crypto miner: take the Bitmain S19 pro as an example, it's sold about 2000 dollars each one and its hash rate is 110TH/s, which has the highest hash rate among all types of crypto miners in Bitmain. Note that 110 TH/s means the miner can compute 110 billion hashes per second, which is approximately equal to $2^{36}$.

Using the Brute Force attack to extract a 256-bit key, it takes $2^{256}$ operations in total. Bitmain S19 can do a year ($2^{36}\times 3600\times 24\times 360=2^{36}\times 3\times 10^7>2^{36}\times 3\times 2^{21}=3\times 2^{57}>2^{58}$). So it costs 2000 dollars a year to do $2^{58}$ operations, then $2^{84}$ operations can be done with the GDP of America in 2018. In this way, it would cost $2^{172}$ years' GDP ($2^{256}/2^{84}=2^{172}$)to make the Brute Force attack successful. It is still a tremendous number for us, so let's just forget about it.

$\endgroup$
-8
$\begingroup$

Anything is crackable if you take one part of the whole. The key is made up of "parts" and if you treat it as such it can solve your problem faster. Table the data then move forward simultaneously. 128 bits at 8 bits with 16 threads with 1.3 flops a minute with a true 2.67 ghz cpu can crack 128 bits in 11.67 hours...obviously you need to write the code to process the decryption based on the type of encryption.

$\endgroup$
3
  • 9
    $\begingroup$ Your math is completely wrong. $\endgroup$ Mar 29, 2015 at 14:52
  • 3
    $\begingroup$ Fortunately, movies and tv shows have a completely and utterly wrong image of breaking encryption. In reality, there is no way to distinguish a partially correct key. All those ideas of breaking a key or password symbol by symbol is just fiction. $\endgroup$
    – tylo
    Mar 30, 2015 at 12:05
  • 7
    $\begingroup$ yeah why not break the 128 bits into 128 single-bit "parts". This would reduce the operation into just 128 iterations, or 256 if you are super unlucky $\endgroup$
    – Solo
    Nov 27, 2015 at 9:14

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