4 ms·

The only downside to Ed25519 is that it will fall to quantum computing before RSA 4096.

CameronNemo 6y ago
Is that because elliptic curve cryptography is more sensitive to quantum brute force in general, or is the key size of ed25519 the real factor?
ShorsHammer 6y ago
OpenSSH has a post-quantum hybrid algo using SNTRUPrime and ed25519. > * ssh(1), sshd(8): Add experimental quantum-computing resistant key exchange method, based on a combination of Streamlined NTRU Prime 4591^761 and X25519. https://www.openssh.com/txt/release-8.0 https://www.openssh.com/txt/release-8.0
nobodyshere 6y ago
Except nobody knows when that's gonna really happen. I've personally switched to ed25519-sk wherever I could.
- lucb1e 6y ago
  Same, the short key looks much nicer and both will fall to quantum anyhow. Haven't run into any incompatibilities among the services I use.
1vuio0pswjnm7 6y ago
And the only downside to RSA 4096 is that it will fall before Niederreiter using binary Goppa codes?
- benlivengood 6y ago
  The upside of RSA is that we'll likely have evidence of ed25519 being breakable (~1500 qubits) before breaking RSA 4096 is possible (~8000 qubits). [https://crypto.stackexchange.com/questions/35137/how-many-qubits-are-required-to-break-rsa-2048-or-4096-with-a-universal-quantum https://crypto.stackexchange.com/questions/35137/how-many-qu...] The number of usable qubits in a single computation is expensive and has been growing slowly and until that changes I figure it's more likely to be surprised by a break of ed25519 but not RSA 4096 than to be surprised by a break of both.
dependenttypes 6y ago
As far as I know elliptic curves at the same size as RSA are stronger both in a quantum and post-quantum setting.
- aborsy 6y ago
  True, in fact an elliptic key with 4096 bits would be way overkill. But there is also the issue of support. Ed25519 and RSA3072 offer around 128 bits of entropy, which is kind of on margin even classically. RSA 4096 offers more protection against brute force, around 144 bits if I recall correctly. Of course, RSA is vulnerable to side channel attacks (though these nay not be in the threat model of many people). You could use ed448 with 224 bits of security with still shorter keys than common RSA variants. But then it’s not supported in most places.
  - dependenttypes 6y ago
    > which is kind of on margin even classically Is it though? It requires around 2^128 operations to be broken. It does not seem very marginal to me. It is not like AES where you have to deal with batch-attacks or cryptographic hash functions where collisions for a n-length output require only sqrt(2^n) attempts.
    - aborsy 6y ago
      That’s not how it works! That 128 bits is theoretical upper bound, not necessarily an achievable security rate. That’s the point of margin.
      - dependenttypes 6y ago
        Very well, in that case, which symmetric encryption algorithm would you say has an acceptable security margin?

Is that because elliptic curve cryptography is more sensitive to quantum brute force in general, or is the key size of ed25519 the real factor?

ShorsHammer 6y ago

OpenSSH has a post-quantum hybrid algo using SNTRUPrime and ed25519. > * ssh(1), sshd(8): Add experimental quantum-computing resistant key exchange method, based on a combination of Streamlined NTRU Prime 4591^761 and X25519. https://www.openssh.com/txt/release-8.0 https://www.openssh.com/txt/release-8.0

nobodyshere 6y ago

Except nobody knows when that's gonna really happen. I've personally switched to ed25519-sk wherever I could.

lucb1e 6y ago
Same, the short key looks much nicer and both will fall to quantum anyhow. Haven't run into any incompatibilities among the services I use.

1vuio0pswjnm7 6y ago

And the only downside to RSA 4096 is that it will fall before Niederreiter using binary Goppa codes?

benlivengood 6y ago
The upside of RSA is that we'll likely have evidence of ed25519 being breakable (~1500 qubits) before breaking RSA 4096 is possible (~8000 qubits). [https://crypto.stackexchange.com/questions/35137/how-many-qubits-are-required-to-break-rsa-2048-or-4096-with-a-universal-quantum https://crypto.stackexchange.com/questions/35137/how-many-qu...] The number of usable qubits in a single computation is expensive and has been growing slowly and until that changes I figure it's more likely to be surprised by a break of ed25519 but not RSA 4096 than to be surprised by a break of both.

dependenttypes 6y ago

As far as I know elliptic curves at the same size as RSA are stronger both in a quantum and post-quantum setting.

aborsy 6y ago
True, in fact an elliptic key with 4096 bits would be way overkill. But there is also the issue of support. Ed25519 and RSA3072 offer around 128 bits of entropy, which is kind of on margin even classically. RSA 4096 offers more protection against brute force, around 144 bits if I recall correctly. Of course, RSA is vulnerable to side channel attacks (though these nay not be in the threat model of many people). You could use ed448 with 224 bits of security with still shorter keys than common RSA variants. But then it’s not supported in most places.
- dependenttypes 6y ago
  > which is kind of on margin even classically Is it though? It requires around 2^128 operations to be broken. It does not seem very marginal to me. It is not like AES where you have to deal with batch-attacks or cryptographic hash functions where collisions for a n-length output require only sqrt(2^n) attempts.
  - aborsy 6y ago
    That’s not how it works! That 128 bits is theoretical upper bound, not necessarily an achievable security rate. That’s the point of margin.
    - dependenttypes 6y ago
      Very well, in that case, which symmetric encryption algorithm would you say has an acceptable security margin?