3 ms·
Is there a quantum algorithm for cracking ECDSA like Shor's for RSA? I was hoping they'd mention it in the article.
by nailer 3y ago
Is there a quantum algorithm for cracking ECDSA like Shor's for RSA? I was hoping they'd mention it in the article.
- frutiger 3y agoYes. See https://crypto.stackexchange.com/questions/53425/quantum-algorithm-for-elliptic-curves-private-keys https://crypto.stackexchange.com/questions/53425/quantum-alg....
- bawolff 3y agoI was under the impression that shor's algorithm worked for ecdsa just as well as rsa.
- gary_0 3y agoShor's algorithm can also break elliptic curve encryption: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
- mjevans 3y agoPart 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 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.
- tptacek 3y agoIt 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.
- nailer 3y agoSo ECDHE becomes EC(Post Quantum Exchange)? Am I understanding that correctly?
- tptacek 3y agoA 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).
- HappyPanacea 3y agoWhy 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?
- tptacek 3y agoHonestly, 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".)
- dadrian 3y agoWith 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.
- mjevans 3y agoI 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.
- flangola7 3y agoEvery 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.
- deleted 3y ago[deleted]
- pjs_ 3y agohttps://arxiv.org/abs/2306.08585 https://arxiv.org/abs/2306.08585
- akvadrako 3y agoPractically 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.