5 ms·

It's important to note that most ECC is not quantum-resistant and will be obsoleted in the coming years following completion of NIST's post-quantum cryptography

by cgshep 4y ago

It's important to note that most ECC is not quantum-resistant and will be obsoleted in the coming years following completion of NIST's post-quantum cryptography competition. Indeed, OpenSSH recently enabled PQC by default (NTRU Prime over X25519) [1]. ECC has, at best, a short-to-medium term lifespan right now. 1. https://www.zdnet.com/article/openssh-now-defaults-to-protecting-against-quantum-computer-attacks/?ftag=COS-05-10aaa0g&taid=6254b2f12c26f70001946bff&utm_campaign=trueAnthem%3A+Trending+Content&utm_medium=trueAnthem&utm_source=twitter&fr=operanews https://www.zdnet.com/article/openssh-now-defaults-to-protec...

akvadrako 4y ago
This assumes people consider practical million qubit quantum computers relevant. They might actually be impossible or close to it, i.e. millions of years away. I'd say by far the most important thing will stay resistance to unknown classical algorithms, at least until trends change.
adgjlsfhk1 4y ago
also, elliptic curves are much more vulnerable to quantum attacks than regular rsa since it uses smaller keys.
- politelemon 4y ago
  I wouldn't say more vulnerable necessarily — it requires fewer qubits, but requires larger coherence time. RSA requires more qubits and drastically less time. They're both vulnerable in different ways.
  - eternityforest 4y ago
    Isn't coherence time the big challenge?
    - dmlerner 4y ago
      I imagine it's a similar tradeoff - with more qubits there are more interactions, ergo lower coherence time
xiphias2 4y ago
I just recently played with an online quantum computer simulator to get a better understanding of how quantum fourier transform works, it's a lot of fun: https://algassert.com/quirk https://algassert.com/quirk
jjice 4y ago
I'm very excited to see the results of the post-quantum crypto competition. Most of it is above my head, but it's neat to read about lattice problems. Asymmetric cryptography in general is incredible to me.
tooltower 4y ago
AFAIK post-quantum crypto all has larger key sizes and much(?) worse performance. Has that changed? If not, I don't see ECC becoming obsolete any time soon.
- marcelluscat 4y ago
  I thought ring-lwe was pretty good. It's at least very embarrassingly parallel
  - less_less 4y ago
    They're all worse in terms of size and/or speed, but not disastrously so. Ring-LWE is faster than ECC, but has keys and ciphertexts of 600+B instead of as few as 32 B (for eg curve/ed25519). NTRU is pretty similar, with slower key generation and slightly smaller ciphertexts. If you go to the bleeding edge, you might be able to cut these to 300-400 bytes with severe compromises in eg error rate and security margin. There are also structured code-based systems with fairly similar sizes to the Ring-LWE ones, but they aren't finalists. McEliece is fast to encrypt and decrypt and has small ciphertexts (as few as 128 bytes), but has enormous public keys (multi-hundred KB) that are also slow to generate. The biggest benefit of McEliece is that we're pretty confident it will hold up to analysis. SIKE (an alternate) has reasonable keys and ciphertexts (200-250 B) but is pretty slow, on the order of 5ms on a laptop for the smallest parameters. The bleeding-edge CSIDH is much slower, but has even smaller keys, but we can't be at all confident that CSIDH is secure. On the sig side, Falcon is fast but extremely complicated, and has as low as ~660B sigs. Its main competitor, Dilithium, is modestly slower and larger, and also significantly simpler. The much more conservative SPHINCS+ is very slow and produces ~8kB sigs.
- eternityforest 4y ago
  We will probably just see more tricks like computing keys from random seeds and storing cached key exchanges, and AMP style clickbait accelerators to funnel stuff through CDNs you already have the key for(Assuming the EU lets us do that....)
KMag 4y ago
I have a mind to write a PQC daemon to negotiate/rotate WireGuard pre-shared keys. Even though WireGuard uses 3-way ECDH using Curve25519, with a 256-bit pre-shared key, an attacker will either need 2^128 work using Grover's quantum search algorithm or else find statistical flaws in ChaCha20. That way, you keep the post-quantum crypto out of the kernel, and if done carefully by hashing together PQC, ECDH, and a pre-shared-pre-key to generate the pre-shared key, it would be easier to demonstrate that it's no weaker than WireGuard. If the daemon removes and forgets the negotiated pre-shared-keys after 24 hours, then against classic attackers you'd still have perfect forward secrecy, and against quantum attackers you'd have 24-hour forward secrecy (assuming no statistical flaws in ChaCha20).
acchow 4y ago
Depends on how quickly quantum computer size grows? We don't seem to have anything resembling a Moore's Law yet
- als0 4y ago
  The Cloud Security Alliance is assuming something powerful enough shall exist in under 8 years. https://cloudsecurityalliance.org/press-releases/2022/03/09/cloud-security-alliance-sets-countdown-clock-to-quantum/ https://cloudsecurityalliance.org/press-releases/2022/03/09/...
  - oofbey 4y ago
    But their job is to figure the realistic worst case I.e fastest plausible timeoine. Not the most likely / expected time it will take.

by cgshep 4y ago

akvadrako 4y ago

This assumes people consider practical million qubit quantum computers relevant. They might actually be impossible or close to it, i.e. millions of years away. I'd say by far the most important thing will stay resistance to unknown classical algorithms, at least until trends change.

adgjlsfhk1 4y ago

also, elliptic curves are much more vulnerable to quantum attacks than regular rsa since it uses smaller keys.

politelemon 4y ago
I wouldn't say more vulnerable necessarily — it requires fewer qubits, but requires larger coherence time. RSA requires more qubits and drastically less time. They're both vulnerable in different ways.
- eternityforest 4y ago
  Isn't coherence time the big challenge?
  - dmlerner 4y ago
    I imagine it's a similar tradeoff - with more qubits there are more interactions, ergo lower coherence time

xiphias2 4y ago

I just recently played with an online quantum computer simulator to get a better understanding of how quantum fourier transform works, it's a lot of fun: https://algassert.com/quirk https://algassert.com/quirk

jjice 4y ago

I'm very excited to see the results of the post-quantum crypto competition. Most of it is above my head, but it's neat to read about lattice problems. Asymmetric cryptography in general is incredible to me.

tooltower 4y ago

AFAIK post-quantum crypto all has larger key sizes and much(?) worse performance. Has that changed? If not, I don't see ECC becoming obsolete any time soon.

marcelluscat 4y ago
I thought ring-lwe was pretty good. It's at least very embarrassingly parallel
- less_less 4y ago
  They're all worse in terms of size and/or speed, but not disastrously so. Ring-LWE is faster than ECC, but has keys and ciphertexts of 600+B instead of as few as 32 B (for eg curve/ed25519). NTRU is pretty similar, with slower key generation and slightly smaller ciphertexts. If you go to the bleeding edge, you might be able to cut these to 300-400 bytes with severe compromises in eg error rate and security margin. There are also structured code-based systems with fairly similar sizes to the Ring-LWE ones, but they aren't finalists. McEliece is fast to encrypt and decrypt and has small ciphertexts (as few as 128 bytes), but has enormous public keys (multi-hundred KB) that are also slow to generate. The biggest benefit of McEliece is that we're pretty confident it will hold up to analysis. SIKE (an alternate) has reasonable keys and ciphertexts (200-250 B) but is pretty slow, on the order of 5ms on a laptop for the smallest parameters. The bleeding-edge CSIDH is much slower, but has even smaller keys, but we can't be at all confident that CSIDH is secure. On the sig side, Falcon is fast but extremely complicated, and has as low as ~660B sigs. Its main competitor, Dilithium, is modestly slower and larger, and also significantly simpler. The much more conservative SPHINCS+ is very slow and produces ~8kB sigs.
eternityforest 4y ago
We will probably just see more tricks like computing keys from random seeds and storing cached key exchanges, and AMP style clickbait accelerators to funnel stuff through CDNs you already have the key for(Assuming the EU lets us do that....)

KMag 4y ago

I have a mind to write a PQC daemon to negotiate/rotate WireGuard pre-shared keys. Even though WireGuard uses 3-way ECDH using Curve25519, with a 256-bit pre-shared key, an attacker will either need 2^128 work using Grover's quantum search algorithm or else find statistical flaws in ChaCha20. That way, you keep the post-quantum crypto out of the kernel, and if done carefully by hashing together PQC, ECDH, and a pre-shared-pre-key to generate the pre-shared key, it would be easier to demonstrate that it's no weaker than WireGuard. If the daemon removes and forgets the negotiated pre-shared-keys after 24 hours, then against classic attackers you'd still have perfect forward secrecy, and against quantum attackers you'd have 24-hour forward secrecy (assuming no statistical flaws in ChaCha20).

acchow 4y ago

Depends on how quickly quantum computer size grows? We don't seem to have anything resembling a Moore's Law yet

als0 4y ago
The Cloud Security Alliance is assuming something powerful enough shall exist in under 8 years. https://cloudsecurityalliance.org/press-releases/2022/03/09/cloud-security-alliance-sets-countdown-clock-to-quantum/ https://cloudsecurityalliance.org/press-releases/2022/03/09/...
- oofbey 4y ago
  But their job is to figure the realistic worst case I.e fastest plausible timeoine. Not the most likely / expected time it will take.