Comment by JohnJamesRambo | Hacker News Reader

Comment by JohnJamesRambo | Hacker News Reader

Parent Full thread

Might be a long time though right?

> On average, to brute-force attack AES-256, one would need to try 2^255 keys. (This is the total size of the key space divided by 2, because on average, you'll find the answer after searching half the key space.) So the time taken to perform this attack, measured in years, is simply 2^255 / 2,117.8 trillion

> Expressed as an exponent of 10, that’s 2.73 * 1061. Written in full format:

>27,337,893,038, 406,611, 194,430,009, 974,922,940, 323,611,067, 429,756,962, 487,493,203 years.

>In English: 27 trillion trillion trillion trillion trillion years.

From-https://scrambox.com/article/brute-force-aes/

I’d love to hear Hacker News opinions on how long that will be valid due to faster computers, quantum computing etc. Or if it will always pretty much be valid in your opinion?

The number they get for all the PCs on earth trying it is still 13,689 trillion trillion trillion trillion years. The universe is only 14 billion years old and estimates of what the universe will be like in even a trillion years are more like science fiction than science because it is so wildly long.

Some algorithms of the past weren't cracked because we could brute-force them, but because somebody found a weakness that reduced the computational need by many orders of magnitudes. This could happen to AES as well.

I highly recommend reading “The Code Book” by Simon Singh if anyone wants to learn about old ciphers and how they were cracked.

I really enjoyed reading it.

Quantum computing would use Grover's algorithm, which is provably optimal for accelerating a brute-force search. That reduces the key space by half (so square root of the effort), eg AES-256 requires about 2^127 quantum operations to crack on average, instead of 2^255.

Bremermann's Limit[1] puts a fundamental limit on the rate of computation for any given amount of mass of about 1.36e50 bit changes/second/kg. Unless you get an amount of mass of literally planetary scale (as large as, say, Mercury) to take part in your computation the time will be enormous even for a 256-bit key.

[1] https://en.wikipedia.org/wiki/Bremermann%27s_limit

That article doesn’t talk about GPU decryption at all, which is many multitudes faster, and also it’s only talking about finding a specific AES key. It may be possible to search for multiple keys in parallel in the future, which could cut this figure down by the corresponding amount (if the goal is just to find some keys, and not specific ones).

Yes, they can be a hundred times faster so now it's only 273,378,930,384,066,111,944,300,099,749,229,403,236,110,674,297,569,624,874,932 years.

More seriously, GPUs are faster because they are highly parallel, and parallelism can only give you a speedup that is linear with the number of processing units. So unless you're planning to build a GPU with trillions units, that won't help much.

A farm of a billion GPUs, each with a thousand cores sounds quite feasible with today's tech and gets you to trillion-times speedup of brute force. So, feel free to divide by 10^12... still not tractable.

Have you tried to buy a GPU lately?

I was in the market for a single GPU about 6 months ago, it shipped in a week and didn't break the bank. Buying a billion GPUs is an entirely different question. I'd look into buying fab equipment and doing a custom architecture. Given the length of the computation we're talking about, even a decade of lead time wouldn't significant. But as I understand it, current lead times are still less than a year.

If you asked someone in the 50s how long until you could have 1TB of data in a chip the size of a fingernail (also cheap), it would've probably laughed and said "in a million years". Yet, here we are now ...

I went back to 1959 to ask Gordon Moore. He wasn't too far off on his guess. I do hope he heeds my advice and invests in bitcoin.

This assumes current computing speeds. The comment above talks about the future so you need to assume quantum computing exists.

https://www.nist.gov/publications/quantum-resistant-public-k...

AES is still believed to be quantum resistant.

But I see articles that say quantum computing will ruin encryption and some that say it won't. I don't know what to believe as it isn't my area of expertise.

Quantum computing solves RSA.

Quantum Computers, if and when they work in practice, will break some algorithms, halve the 'bit-security' (e.g. 256 -> 128bit) of some algorithms, and leave the other quantum-safe ones untouched.

So encryption will still work in a quantum world. We 'just' have to update the algorithms we use.

See also: https://csrc.nist.gov/projects/post-quantum-cryptography/rou... https://en.wikipedia.org/wiki/Post-quantum_cryptography

It will and it won't.

Quantum computing could allow an implementation of Shor's algorithm to exist. This algorithm breaks RSA which is the basis of a lot of asymmetric cryptographic implementations such as TLS and SSH. By breaking here we mean that it is trivial to crack. It is unclear right now whether or not an equivalent attack applies to elliptic curve-based algorithms which are gaining in popularity.

As far as symmetric encryption is concerned, the standard right now is AES-128 and AES-256 and might be vulnerable to Grover's algorithm which would effectively half the effective number of bits so AES-128 becomes roughly equivalent to a non-existing AES-64 which would be somewhat trivial to crack. However, data encrypted with AES-256 would simply go down to AES-128 which is still considered "good enough" as of today.

In practice, by the time we have real quantum computers there will be a new standard for both of asymmetric and symmetric encryption so it does not matter as much as one would think.

TLDR: RSA will break, elliptic curves might break, AES will be weakened and the impact on your life will probably be minimal.

Shor's algorithm works fine for the Elliptic Curve Discrete Logarithm Problem (ECDLP)[1]. So it'll break ECC.

There's no indication that it can be used to break several other types of problem that can be used in asymmetric cryptography. These other problems are less efficient and have different trade-offs (some have huge keys, some have huge outputs, some are really slow) and picking appropriate parameters to make them usable while still being secure is a difficult problem. Solving that is the aim of NIST's post-quantum standardization effort.

[1] https://crypto.stackexchange.com/questions/51346/shors-algor...

Didn't know about ECC, thanks!

The mass of Earth is about 6E24kg. The crust makes up about 1% of that, and silicon makes up about 28% of that. So about 1.68E22kg silicon is available on Earth. Assume we convert all of that to a giant computer, capable of operating at Bremermann's Limit[1]. That would give about 2.28E72 (quantum) operations/second. 2^255 / 2.28E72 ≈ 25400 seconds to count to 2^255. Figure a measly 100 operations to test each key, and you're looking at a month per key to brute-force. And that's ignoring light-speed communication delays between parts of the computer, which would dominate.

If it looks like someone is going to build a quantum computer out of the entire mass of the silicon in Earth's crust, I suggest 512-bit keys. That'll keep your secrets safe for about 9E73 years. I'd also suggest finding a new planet to live on, the mining operation would likely be somewhat disruptive.

For a more realistic comparison, perhaps they've only got a computer with as much mass of iron ore as the recent annual world production for the last thousand years (2.5E9 tonnes/year = 2.5E15 kg). Then it'll take around 5000 to run 2^255 operations.

https://en.wikipedia.org/wiki/Bremermann%27s_limit

> And that's ignoring light-speed communication delays between parts of the computer, which would dominate.

Light speed delays are not relevant to a highly concurrent problem. They would be an issue for a general purpose computer that size running a sequential program.

True if it's not a quantum computer. For a quantum computer, the entanglement effects propagate at the speed of light, so you can't just treat it as independent trials. Of course if it's lots of quantum computers you'd get some advantages, but you can't run Grover's on an ensemble so I'm not quite sure what the resulting complexity would end up being (you can run it on each individual QC, but I don't know how the resulting complexity would be calculated).

Either way it's a bit beyond what's economically possible for any human organization right now. And I implicitly assumed the computation is fully reversible and therefore took negligible energy.

Generalized Quantum Search with Parallelism — https://arxiv.org/abs/quant-ph/9904049

“We generalize Grover's”…

“We extend the analysis to the case of a society of k quantum searches acting in parallel”.

Disclaimer: I know absolutely nothing about the topic, but the first link I googled seems to justify my intuition that this decryption could be partitioned so that many quantum computers could run in parallel (thus avoiding the limit on speed of information transfer you are hypothesising).

> Either way it's a bit beyond what's economically possible for any human organization right now. And I implicitly assumed the computation is fully reversible and therefore took negligible energy.

Agree - I’m just being that contrary Internet!

Unless they can figure out reversible computing to the point their computer doesn't really need any power, they also have to contend with the Landauer limit, so counting to 2^255 (at current cosmic microwave background temperature) would need about 2^255 k 3kelvin ln(2) / c^2 = ~9 million solar masses of fuel (assuming perfect effeciency).

Reply on news.ycombinator.com