9
$\begingroup$

Given that much of our ECC crypto primitives provide “only” 128-bit security when defined over a 256-bit curve due to pollard-rho, is it then still safe in 2020 to consider 128-bit security safe for the medium term (5-8 years).

I’m looking for an answer from an energy/thermodynamic POV given advances in current lithography and GPUs, rather than with regard to a specific cipher, however for discussion I consider AES-GCM or Salsa20 as example symmetric ciphers I use with 128-bit keys.

Bruce Schneier speaks of AES-128 in Cryptographic Engineering as if it’s already broken!

$\endgroup$
  • 1
    $\begingroup$ Can I call this a dupe of this Has AES-128 been fully broken?? AES-128 is theoretically broken and any block cipher has weakness on the multi-target attack What is a multi-target attack? $\endgroup$ – kelalaka Jan 13 at 21:13
  • 1
    $\begingroup$ @Kelalaka yup that answers my question thanks. $\endgroup$ – Woodstock Jan 13 at 21:52
  • 2
    $\begingroup$ This Q/A is more generic than asking if AES-128 is broken, so I'll leave it here even though the supposed dupe of the mentioned question about AES-128. If anybody sees any harm in that please flag the question and provide the reason. $\endgroup$ – Maarten Bodewes Jan 14 at 9:51
  • 3
    $\begingroup$ I disagree with that last statement, the ECC should be included in the more generic title, if it was just about AES then it would be a dupe. Personally, I don't think the current title is that bad, to be honest. $\endgroup$ – Maarten Bodewes Jan 14 at 12:31
  • 2
    $\begingroup$ 64-bit keys are barely broken, you'd need a supercomputer to brute-force a key of that size in a reasonable time. $2^{128}$ is $2^{64}$ (~18 million million million) times that. $\endgroup$ – BlueRaja - Danny Pflughoeft Jan 14 at 12:49
22
$\begingroup$

I strongly disagree with saying that AES-128 is broken, in any way, shape or form, and likewise ECC with 256-bit keys. Note that even in this answer by @kelaka regarding AES-128, you would need over 34 million years of the entire bitcoin mining power to carry out a computation of $2^{128}$. This is far from broken. If quantum computers ever happen at scale, it is very very unclear how long it would have to actually run to achieve $2^{64}$ quantum computations for AES-128 (but ECC-256 would be in bigger trouble). Bottom line, these are far from broken. (I don't know what Schneier quote you are referring to, but anyway I completely disagree.)

$\endgroup$
  • 1
    $\begingroup$ Don't we say that an algorithm is theoretically broken if an attack requires less time then the brute-force? There is no classical computing power that can reach $2^{126.1}$. Of course, this doesn't mean it is broken in practice. Or we should use a minor term as a weakness has found? $\endgroup$ – kelalaka Jan 14 at 6:13
  • 10
    $\begingroup$ We do, but here one also needs to apply some reason. I don't think that $2^{126.1}$ classifies as a weakness that is a concern. On the contrary, the fact that after 20 years, the best attack is $2^{126.1}$ increases my confidence significantly in AES. $\endgroup$ – Yehuda Lindell Jan 14 at 7:04
  • $\begingroup$ It's a bit like the DES attack in $2^{55}$ time due to the complementary property. It's a weakness, but not one that is of real concern. $\endgroup$ – Yehuda Lindell Jan 14 at 7:33
  • $\begingroup$ I would say the DES complement property is a simple property compared to the Biclique attack. Not sure, but, maybe designers also was aware of it ( enlighten me if there is reverse evidence). Small correction, now it is almost 22 years since the NIST called for algorithm; September 12, 1997,@fgrieu, In my opinion, any attack diverge from the brute-force, must use much more resources if there is no backdoor, etc... $\endgroup$ – kelalaka Jan 14 at 8:07
  • 5
    $\begingroup$ "broken" means different things to academic cryptographers and cybersecurity people. An academic will call it broken if you could compute it within the next billion years or so. $\endgroup$ – Tom Jan 15 at 11:57
8
$\begingroup$

The current recommendations of the BSI recommend 120 bit of security beyond 2022. And AES 128 is still in their recommendations.

If the current estimate of AES128 is about 126.1 bits of security, that's still above the threshold. And AES has been subject to a lot of cryptanalysis for many years, so that estimate seems quite strong.

For crypto with keys, that are too short, it's quite likely that people use too short RSA keys.

$\endgroup$
8
$\begingroup$

As you specifically asked for comparisons of the 128-bit security with concrete things, here is some food for thoughts (to complement the other answers):

  • $2^{61} ≈$ SHA-1 chosen-prefix collision (i.e. definitively practical) from the recent SHA-mbles attack.
  • $2^{63} ≈$ the initial SHA-1 collision from SHAttered attack (which ran over multiple months). (i.e. practical for Google, 3-letters agencies, and other large scale actors.)
  • $2^{66} ≈$ current Bitcoin hashrate per seconds! (i.e. shows the limits of current computing power)

Notice how the $2^{80}$ level is already attained by the raw computing power leveraged by the Bitcoin network: every ~4.5 hours the bitcoin network has performed $2^{80}$ SHA computation.

This also means that the 64-bit and 80-bit levels are broken, and we should definitively move away from 64-bit block ciphers. To quote the above-mentioned "SHA-mble" research:

As a side result, this shows that it now costs less than 100k USD to break cryptography with a security level of 64 bits (i.e. to compute $2^{64}$ operations of symmetric cryptography).

Now, you might have heard of Bruce Schneier, and his book "Applied Cryptography", in which he says:

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×10^{-16}$ erg/°Kelvin, and that the ambient temperature of the universe is 3.2°Kelvin, an ideal computer running at 3.2°K would consume $4.4×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×10^{41}$ ergs. This is enough to power about $2.7×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 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.

Sadly, this is advocating for the security of the 256-bit level, and when converted for the 128-bit level, it just tells us that we would need to use all of the sun's energy for roughly 0.1 nanoseconds in order to flip through all the possibles states of a 128-bit counter.

Thermodynamics doesn't really help us with impressive comparison with the 128-bit level, because it is still relatively small.

$\endgroup$
  • 1
    $\begingroup$ Interesting thank you! $\endgroup$ – Woodstock Jan 14 at 12:16
  • 1
    $\begingroup$ @fgrieu You're right, I made too many mistakes there. I'll say I was hungry and rushing to my lunch as an excuse. :( Hopefully I've addressed them now. $\endgroup$ – Lery Jan 14 at 13:36
  • 2
    $\begingroup$ @Lery: yes the answer is now fine. Note: bitcoin hash rate is customarily given for the SHA-256d hash, and we can double (add one bit) for SHA-256. That speed is made possible by using ASICs and wasting energy. According to my back-of-the-envelope calculations, we are only 20 bits or so before the best way to make money with bitcoin is designing and operating an ASIC to break the private keys of the whales. If that leads to a ban or otherwise end of all cryptocurrencies based on mining, that's good! $\endgroup$ – fgrieu Jan 14 at 15:19
  • $\begingroup$ @fgrieu, "only 20 bits" may not sound like much, but it's 30 years of progress under Moore's law. $\endgroup$ – Mark Jan 14 at 23:42
  • $\begingroup$ @Mark likely more considering Moore's Law is slowing down as we approach physical limits for transistor sizes. Then again, anything could happen in 30 years: from major physics breakthrough to WW3. $\endgroup$ – Dan M. Jan 15 at 13:08

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.