Hacker News Reader

Comment by cortesoft | Hacker News Reader

I am not an expert, but while you are correct that a fast enough traditional computer (or a parallel enough computer) could brute force a 128 bit key, the amount of improvement required would dwarf what we have already experienced over the last 40 years, and is likely physically impossible without some major fundamental change in how computers work.

Compute has seen in the ballpark of a 5-10 orders of magnitude increase over the last 40 years in terms of instructions per second. We would need an additional 20-30 orders of magnitude increase to make it even close to achievable with brute force in a reasonable time frame. That isn’t happening with how we make computers today.

View on HN

> That isn’t happening with how we make computers today.

Keep here in mind that computers today have features approaching the size of a single atom, switching frequencies where the time to cross a single chip from one end to the other is becoming multiple cycles, and power densities that require us to operate at the physical limits of heat transfer for matter that exists at ambient conditions.

We can squeeze it quite a bit further, sure. But anything like 20-30 orders of magnitude is just laughable even with an infinite supply of unobtanium and fairy dust.

You don't need to keep shrinking features. Brute forcing is highly parallel; to break a key within a certain time frame all you need is a large enough quantity of chips. While it's in the realm of science fiction today, in a few centuries we might have nanorobots that can tile the entire surface of mars with processors. That would get you enough orders of magnitude of additional compute to break a 128 bit key. 256 bit would probably still be out though.

Classical brute force is embarrassingly parallel, but Grover's algorithm (the quantum version) isn't. To the extent you parallelize it, you lose the quantum advantage, which means that to speed it up by a factor of N, you need N^2 processors. The article discusses this in detail, and calculates that "This means we’ll need 140 trillion quantum circuits of 724 logical qubits each operating in parallel for 10 years to break AES-128 with Grover’s."

So then why is quantum always touted as being able to possibly beat AES ?

Is it? I've generally understood that most symmetric cryptography like AES is safe. QC only gives exponential speedups on some specific problems. The most is that naively you might want to double your keysize to get the same protection, something that the article points out is unecessary because that naive approach assumes that QC is like classical computing but with extra magic, as opposed to having its own tradeoffs.

Is it possible you are confusing AES with RSA?

I've heard a lot about Shor's algorithm breaking RSA, but this article on hackernews is the first I've heard anyone discuss quantum attacks for AES. Then again, I am in quantum computing not cryptography, maybe different circles have different discussions.

Because some people make their living from the vague possibly it might work one day. It's the cold fusion of computing.

The power and heat are the issues for that, though. Think about how much energy and heat are used/generated in the chips we have now. If we tiled out those chips to be 20 orders of magnitude larger… where is the heat going to go, and where is the energy coming from?

In my example I had imagined that your nanobots would also create solar panels and radiators for the chips you were tiling the surface of mars with. This is why it needs to be done on the surface instead of underground somewhere.

By the time you built this machine, someone could just bump to 256 bit AES and you suddenly need a billion Marses covered in chips.

We're nowhere near physical heat transfer limits. CNTs and monoisotopic diamond perform much better than silver. The latter can even be used as substrate.

Reply on news.ycombinator.com