Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

words.filippo.io

Post reply on HN
Print view View original

111–116 of 116 posts

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#111

Post by GoblinSlayer »

amluto wrote: post #56
staticassertion wrote: post #54

Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?

Yes and no. Grover's algorithm is provably optimal [0]. No quantum algorithm will ever find an n-bit key by queries to any reasonable sort of oracle faster than Grover's algorithm, and Grover's algorithm is way too slow to be a serious problem. But symmetric ciphers are not black boxes. They're mostly built on some variant of a Feistel network, which is a very nice construction for turning a messy function into an in…

You want to combine quantum computation with classical computation? Do you want them to run in parallel or in lockstep?

Also not all ciphers are Feistel networks, stream ciphers use Vernam construction and aren't reversible. This was used in an attack on USA export restriction which declared cryptographic hash functions as exportable, so it inadvertently applied only to Feistel ciphers, but a stream cipher constructed from hash function thus dodged export restriction, because stream ciphers are irreversible.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#112

Post by daneel_w »

rcxdude wrote: post #107
daneel_w wrote: post #103

Earlier quoted context omitted.

The simplified answer is, larger keys that demand a far larger effort to break, in a way similar to RSA-4096 vs RSA-2048. The predicted timelines for quantum computer advances (and the requirements for practical applications) have shrunk dramatically in the past 15 years. What used to be a no-later-than-2035 recommendation for getting off e.g. RSA-2048 in good time, is today no-later-than-2030. The admission of 256-b…

The whole point is that RSA and ECDH can't be made safe against quantum computers by making the keys bigger. The speedup is exponential and so breaking a 4096-bit key is only twice as hard as a 2048-bit key. The 'cutting in keysize in half' is true in principle in general (but not in practice, as the article points out), but for some algorithms it's much worse.

Just to be clear, I'm not advocating for Ed448 for the KEX - we already have ML-KEM and SNTRUP in OpenSSH and everyone should start using those. I'm advocating for Ed448 DSA ("SSH pubkey").

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#113

Post by dlcarrier »

tsimionescu wrote: post #86
Mithriil wrote: post #40

Earlier quoted context omitted.

> instantly Shor's and Grover's still are algorithm that require a massive amount of steps...

I don't think they meant "in O(1) steps", I think they meant "the day someone figures out how to keep many thousands of qubits entangled while operating on them with gates will be the same day we have the first QC that can start breaking encryption in reasonable time". Where, of course, same day is also an exaggeration. But the general point is that we need a single breakthrough to achieve this, and it's very hard to…

Exactly

You could say it'd be a quantum jump in capabilities.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#114

Post by eru »

gpderetta wrote: post #87
eru wrote: post #66

Earlier quoted context omitted.

If you like this kind of thing: there's a deterministic algorithm for finding minimum spanning trees in a graph that's proven optimal, but no one knows its exact runtime. Basically, the best they've proven is something like O(n * inverse_ackermann(n)), but it seems likely the algorithm actually runs in O(n). We also already have a randomised algorithm for this problem that runs in O(n) expected time on worst case inp…

Interesting, after the mention of inverse Ackerman and spanning trees, I was sure this was going to be Union-Find (i.e. Kruskal's)!

No, it's based on soft heaps. A remarkable data structure that I recently used to prove that you can simulate a priority queue in linear time.

By simulate I mean:

You get a sequence of instructions like 'insert x' and 'delete minimum', and you want to know what's elements are left in your priority queue at the end; but you don't care about any intermediate state.

It turns out that even in the comparison model, you can answer this question in linear time in the worst case. Precisely, with no approximation.

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#115

Post by SahAssar »

bob1029 wrote: post #95
SahAssar wrote: post #62

Earlier quoted context omitted.

I'm not sure I understand, but haven't you just moved the problem to the out of band layer? And is that layer not secured using the same normal (somewhat) long-lived TLS as most sites? I don't think I understand the threat model you are using here?

Think of the out of band layer as two human executives exchanging URLs and GUIDs in person. You still need a secure transport, but in this model the thing that is being secured on the wire expires within 15 minutes. The only way to break the model is to defeat a transport or protocol key and only before rotation, revocation and expiration can catch up each time.

So, that'd be the same for a private CA with short lifetime certs used with TLS, right?

Re: Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

#116

Post by ignoramous »

tptacek wrote: post #12
kd913 wrote: post #5

If this is true, I feel teh wifi alliance have a tonne to answer for the ewaste they generate. WPA3 moved from symmetric AES to ECDH which is vulnerable to Quantum. Gonna be a tonne of IOT inverters waste.

For what it's worth, cryptography engineers were generally not happy with the Dragonfly PAKE, and PQC was a legitimate concern even in 2012.

For those curious, a more elegant PAKE family is being formalized:

CPace (balanced): https://datatracker.ietf.org/doc/draft-irtf-cfrg-cpace/

OPAQUE (augumented): https://datatracker.ietf.org/doc/rfc9807/

Post reply on HN