Hacker News Reader

Comment by nailer | Hacker News Reader

Is there a quantum algorithm for cracking ECDSA like Shor's for RSA? I was hoping they'd mention it in the article.

Shor's algorithm can also break elliptic curve encryption: https://en.wikipedia.org/wiki/Post-quantum_cryptography

Part of the issue as a prospective cryptographic user/consumer is that not only do I not know which algorithm(s) should be used, the most likely library https://github.com/open-quantum-safe/liboqs also explicitly states that it shouldn't be used in production.

Hybrid deployment (E.G. with ECC using a curve like 25519) is a great recommendation and probably obvious, far more so than picking a winner among the available post quantum possibly safe algorithms.

It is more or less universally assumed in practice that PQ key agreement algorithms will be paired with classical (RSA/ECC) cryptography. There's not much need to discuss or standardize it; it's a given.

So ECDHE becomes EC(Post Quantum Exchange)? Am I understanding that correctly?

A good Google search term is "CECPQ2". Roughly: run a PQ KX to reach a shared secret, and run an independent X25519 to reach a second share secret, and then HKDF them both (conceptually: just cat them together and use them as a single secret).

Why not just XOR them? Is the reason we use HKDF is so if one or both is only partially broken (only some bits or some correlation) instead of fully broken we still benefits from the information that is still there?

Honestly, for all I know, they do XOR them. I didn't look carefully at how CECPQ2 works! Just: there's very straightforward joinery for running two key agreements and combining them so they both have to succeed to arrive at the session secret.

Later

(Leaving this comment here in perpetuity as evidence that I didn't think about your question as hard as David Adrian did. The message still holds, and that message is: "big ol' shrug".)

With an XOR, if you can control bits on one of the inputs, you can deterministically change one of the bits on the outputs. That is not the case with an HKDF.

I suspect you do not understand given the phrasing.

Think of Tunneling or layers or nesting dolls. The order doesn't particularly matter from a security perspective. Though today I'd wrap with the conventional algorithm on the OUTSIDE layer, since it takes less computational time to check / validate. The inner layer would then be one or more of the post-quantum algorithms; a particularly paranoid application might use more than one if something absolutely must remain a secret.

Thanks for answering.

So you’re encrypting with an asymmetric post quantum algorithm then using that as a payload with regular ED25519 or similar?

What value does the pre quantum wrapper add?

It's like using different technologies to protect against nuclear waste leaking from storage. Each plausibly suitable layer of a different sort makes a leak less likely.

Post-quantum algorithms are, as yet, young and very possibly poorly understood. They may even offer no security at all (due to presently unseen flaws); therefore as a hedge against that include at least another currently in use and current best practice algorithm so that at least _that_ level of security is retained.

Plus, as I pointed out several replies ago, if the current (and fast since reasonable key size Elliptic Curve based) algorithm is the outer layer it can be validated quickly which is a better guard against denial of service attacks and other poor fakes.

Doesn’t NSA object hybrid schemes on weird grounds that current implementations suck, full of implementation errors and all-new PQ-only ones will not?

Edit: reference https://mailarchive.ietf.org/arch/msg/spasm/McksDhejGgJJ6xG6...

That doesn't make much sense as an objection, since the classical cryptography code is better ironed out than the PQ stuff, and the logic to combine the two is fairly simple.

Unless there is an unexpected leap in the viability of quantum cryptanalysis, you should expect that all commercial/standard cryptography with PQ capabilities will run in a hybrid configuration.

I'm only commenting here because there's a pervasive belief that this is controversial in cryptography engineering circles, or that NIST is trying somehow to prevent hybrid schemes from happening, which is simply not the case --- though they may not bother to standardize any particular mechanism of combining ECC/RSA with PQ exchanges (but: they don't standardize stuff like TLS ciphersuites, either).

Every mainstream asymmetric cipher is broken by quantum computing. Post-quantum ciphers are only this year slowly rolling out in canary & beta platforms and demand more memory and CPU cycles

A conservative but reasonable risk assumption is to act as if all internet traffic prior to the year 2023 was transmitted in the clear. This includes Signal, PGP, and Tor.

Yes. See https://crypto.stackexchange.com/questions/53425/quantum-alg....

Practically a quantum computer breaking ECC would happen much sooner than RSA, since ECC uses much smaller keys and the main issue with quantum computers is scaling.

https://arxiv.org/abs/2306.08585

I was under the impression that shor's algorithm worked for ecdsa just as well as rsa.

Reply on news.ycombinator.com