Hacker News Reader

Comment by thomasjames | Hacker News Reader

That is good because, provided there is not some enormous leap forward in number theory in the meantime, they can keep working on trying to break 256-bit key RSA encryption "indefinitely" as well thanks to a higher law by the name of thermodynamics.

View on HN

Wait 25 years until Moore's Law catches up, and they can break all those 256-bit encrypted things you did back in 2013.

From Schneier in "Applied Cryptography" (1996):

"Longer key lengths are better, but only up to a point. AES will have 128-bit, 192-bit, and 256-bit key lengths. This is far longer than needed for the foreseeable future. In fact, we cannot even imagine a world where 256-bit brute force searches are possible. It requires some fundamental breakthroughs in physics and our understanding of the universe.

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/K, 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 1^051 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."

I've seen this argument quoted a couple of times and blindly accepted it as a traditional Fermi-style attack on the problem. This is the first time I've pondered the implementation.

Schneier's argument that 3.2K is a limit is perhaps not the best one? Dilution fridges let you into the millikelvin quickly. Optical cooling can readily reach nanokelvin. Power dissipation remains a significant problem, but the power requirement is reduced by ~10^9.

From the quantum-computing side of things, it's not that crazy to imagine a 256 bit quantum computer, especially if you have a GDP-caliber budget. Researchers worldwide are working hard on the relevant technological precursors.

I'm under the impression that quantum computers buy you a square root. So instead of doubling the number of bits in your key to improve the strength of a key by a ludicrous amount, you should quadruple them.

In addition to this, I don't know how well quantum computers help against (good) symmetric encryption. They help against certain types of PKI because they give you the aforementioned speedup in factoring large integers. However, I think Schneier's argument holds, because brute forcing 2^256 possible keys is.. well, see the argument above about forcing a counter through all those states.

(apologies for not citing sources. Hopefully someone more knowledgeable can weigh in)

For AES you are correct. The best known quantum attack is Grover's Search Algorithm (but emphasis on 'known' here), reducing the key space to 2^128. RSA, however, is based on prime factors, so it can be broken with Shor's Algorithm, which means it will take on the order of (256)^3 operations.

Limiting the energy source to a single star is weak. If you use a whole galaxy (or several) you can easily bring that up to 256 bits. For example, the Milky Way has on the order of 10^11 stars; most of those aren't supernova-sized, but if we use a few million galaxies we can get that many. That gives you an extra 37 bits, bringing the counter to 256.

So, if you have terrifically huge enemies, who will burn galaxies to get at your secrets, you might want to use a few more bits.

You might worry about quantum computers, too, since afaik Grover's algorithm halves effective key size.

> So, if you have terrifically huge enemies, who will burn galaxies to get at your secrets, you might want to use a few more bits.

If you have enemies who can burn galaxies, then you have really other problems than keeping any possible secret.

Even if Moore's Law holds up that long, Second Law of Thermodynamics says you can't brute-force 256-bit keys[1].

However, it's entirely possible (though unlikely) that actual, significant progress will be made either in DLP or in attacking AES/RC4 -- at which case, yeah, that data is as good as clear.

[1]https://www.schneier.com/blog/archives/2009/09/the_doghouse_...

256-bit RSA, eh?

To expand on this a little, 256-bit RSA is easily crackable, since there are good algorithms for integer factorization. You need a significant increase in key length to get equivalent security to symmetric keys: Wikipedia claims 3072-bit RSA ~ 128-bit symmetric, 15360-bit RSA ~ 256-bit symmetric. [0]

[0]: https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_...

Reply on news.ycombinator.com