Hacker News Reader

Comment by ghshephard | Hacker News Reader

Hold on - I thought that AES fell into the category of encryption systems that wasn't vulnerable (for the forseeable future) to quantum attacks. I swear a ton of really smart people I follow on twitter claimed that it wasn't, and that it was all the public key/factoring stuff that would collapse.

See: https://qvault.io/2020/09/10/is-aes-256-quantum-resistant

View on HN

It's known that Grover's Algorithm quadratically reduces the difficulty of breaking AES and nearly all other symmetric encryption systems, as well as nearly all hash functions. So it reduces AES 128 to O(sqrt(2^128)) = O(2^64) difficulty, (brute forceable) AES 192 to O(2^96) difficulty, (brute forceable by major state level actors) and AES 256 to O(2^128) difficulty. (secure)

It's possible that they re-discovered Grover's Algorithm, in which case this is a big fat nothingburger. If/when quantum computers become widespread, we just switch from AES 128 by default to AES 256 by default, and talk about other things.

On the other hand, it's possible that they invented a new quantum attack on AES, which does an exponential speedup, as in AES 128 can be broken in O(log(2^128)) = O(128) time, AES 256 can be broken in = O(256) time, etc. If that's the case we get to reinvent symmetric key cryptography, similar to what we're currently doing with nearly all public key encryption schemes. Shor's algorithm does an exponential speedup on many classes of discrete log problems, which breaks encryption schemes based on integer factorization, elliptic curves, discrete log etc. All standardized public encryption schemes are broken by Shor's algorithm.

Note that when we say things like "AES is secure" that's shorthand for "AES is not known to be insecure". We don't have a proof that AES is secure, and if you did prove that AES is secure, that would probably imply P != NP which would be pretty neat. If someone proves P=NP, then all known encryption schemes except perhaps quantum encryption (which is unworkable at scale) is broken, and e-commerce as we know it is basically fucked.

AES really shouldn't be vulnerable to quantum attacks. Hence the expert they cited saying that the story "[..] seems somewhat unlikely on the face of it."

This'll be a really big deal... IF it's true.

AES has been observed to be very slightly leaky but not in a way that is practically exploitable, partly because even finding it is memory hard on a large volume of data. I know respected crypto experts that have been looking into this anomaly for a few years. It isn't out of the realm of possibility that there is a quantum shortcut related to that state leak.

If I understand correctly (and I may not), AES wasn't vulnerable to known or projected quantum attacks. And that was true, right up until Terra developed a new kind of attack.

And that's always been true, even with non-quantum attacks. You're invulnerable to known attacks? Great, until someone invents a whole new kind of attack.

Note well: All this is assuming that the article is accurate...

Not quite correct. Grover's Algorithm is provably asymptotically optimal for quantum attacks. That is, you'll never do better with just a quantum computer than Grover's will, unless you can also do better without the quantum computer. (One caveat is that Grover's has substantial low-order terms, and one could come up with an algorithm having the same big-O complexity but better practical efficiency. But they don't seem to be claiming that.)

It's not known that there are no classical attacks on AES. Just that a lot of people have looked quite hard for over 20 years and haven't found anything useful.

Terra hasn't provided any evidence of their attacks. Lots of claims, no proof. That doesn't inspire any trust in their claims, especially since proof would be easy. They claim to have found a way to "invert" MD5, which probably means a second preimage attack. If they had that, they could release data which hashes to an all-zero output. If they were ethical and telling the truth, they'd provide proof. If they were unethical and telling the truth, they'd generalize it to find second-preimages on double SHA256, and have a vastly more efficient way to mine bitcoin (and/or forge bitcoin transactions) and make a bunch of money instead of or before putting out a press release. Neither of these things (or anything similar) has happened, so they're almost certainly lying.

If I understand correctly, Grover's Algorithm is a brute-force guesser, which in quantum works much better than in classical. Grover's Algorithm is provably asymtotically optimal for brute-force quantum attacks. Which is great... for that class of attack.

Now, you correctly point out that there are no new classical attacks on AES. So what this would have to be (if true) is a new class of attack that has some quantum-only step, but is different from a Grover-style black-box-output-guessing attack.

As you said, that's if it's true...

That’s the whole point of the article, from what I understood. AES and most hash algorithms were quantum safe. They’re claiming they found new attacks on previously assumed quantum safe systems.

That’s not to say they can perform them, just that (if we believe them) quantum computers are fundamentally stronger than expected.

Reply on news.ycombinator.com