3 ms·

My (probably naive) understanding is that 25519 already provided better performance than other algorithms used for similar purposes (e.g. RSA) when tuned for a

by saghm 2y ago

My (probably naive) understanding is that 25519 already provided better performance than other algorithms used for similar purposes (e.g. RSA) when tuned for a roughly similar level of security; anecdotally, generating 2048-bit or larger RSA keys for me tends to be a lot slower than ed25519. At times I've run into places that require me to use RSA keys though (ironically, I seem to remember first experiencing this with AWS years back, although I honestly can't recall if this is still the case or not). If this further improvement becomes widely used, it would be interesting to see if it's enough to tip the scales towards ed25519 being more of the de facto "default" ssh key algorithm. My experience is that a decent number of people still use RSA keys most of the time, but I don't feel like I have nearly enough of a sample size to conclude anything significant from that.

stouset 2y ago
> anecdotally, generating 2048-bit or larger RSA keys for me tends to be a lot slower than ed25519 That’s not really anecdotal. Generating an ed25519 key is barely more than generating a random 256-bit value. Generating an RSA key is significantly more work.
- saghm 2y ago
  I did say my understanding was probably naive; I didn't know the details to be able to assert anything beyond my own observation!
  - stouset 2y ago
    Yep, not faulting you at all! I too was surprised when I found out that it’s a straight 256-bit random value with a few bits masked.
    - saghm 2y ago
      I pretty quickly realized in college when learning about this stuff that the math was well over my head, and I shifted my focus more to understanding how to properly use cryptography rather than implement it (which turned out to be more important as a software engineer anyhow). In retrospect, I really appreciate how the professor I had in a security-focused course explicitly told us it was okay if we didn't understand the math and wouldn't be tested on it when going over how it worked.
      - tptacek 2y ago
        Counterpoint: it's not OK to skip the math with cryptography. You may not need to power through all of Silverman's curve book (though: I don't know for sure that's true, which is why I don't call myself a cryptography engineer), but you have to get as deep into the math as you can in order to safely use cryptographic algorithms. If you're math-avoidant, stick with high-level abstractions like NaCL and TLS. There's nothing wrong with that! A professor talking about and demonstrating cryptography at the level of individual algorithms is doing their class a disservice if they say "none of the math will be on the test". The algorithms are enough to put something together that seems like it works; the math is what you need to find out if your resulting system actually does work. It's where many of the fun bug classes live.
        saghm 2y ago
        I'm not sure if you're reading more into what I said than I intended, but I'm not convinced by this argument. You might have missed that this course was on security in general, not cryptography; not everything in the course was cryptographic related. That said, I'd argue that for the vast majority of software engineers the type of stuff they're dealing with can be dealt with without needing to know the math. For example, you don't need to understand the math to behind the algorithms to know that bcrypt is a reasonable password hashing algorithm and that sha1 and md5 are not, or that salts are used to mitigate issues when users reuse passwords. These are principles that you can understand at a high level without fully understanding the underlying details. If anything, I think that overemphasis on requiring people to learn and understand the math has the effect of over-focusing on simpler algorithms that aren't actually what people want to be using in practice due to the fact that they're easier to teach and often foundational in conveying concepts that would need to be learned to understand the more complicated algorithms. If using cryptographic algorithms directly requires knowing the math, then I'd agree that most people shouldn't be using them directly, but I'd go further and say that a lack of libraries that are safe for people to use for software engineering without understanding the implementation is a failing of the ecosystem; as much as "regular" software engineering people (like myself!) can struggle with the math behind cryptography, I think that a lot of people developing cryptographic libraries struggle with building reasonable abstractions and making user-friendly APIs (which is a skill I think in general is not emphasized enough for most software engineers, to the detriment of everyone).
  - syncsynchalt 2y ago
    Learning X25519 isn't too hard! See https://curves.xargs.org https://curves.xargs.org for the basics and https://x25519.xargs.org https://x25519.xargs.org for some refining details.
toast0 2y ago
> My (probably naive) understanding is that 25519 already provided better performance than other algorithms used for similar purposes (e.g. RSA) when tuned for a roughly similar level of security; anecdotally, generating 2048-bit or larger RSA keys for me tends to be a lot slower than ed25519. My also naive (an possibly out of date) understanding is key generation is much faster in with ecc, and that signing is faster too, but verifying is faster for rsa. So switching from a RSA to an ECC server certificate saves bytes on the wire, because keys are smaller, and saves server cpu because signing is faster, but may increase client cpu because verification is slower. The byte savings may make up for the increase in cpu though.
- saghm 2y ago
  > My also naive (an possibly out of date) understanding is key generation is much faster in with ecc, and that signing is faster too, but verifying is faster for rsa. So switching from a RSA to an ECC server certificate saves bytes on the wire, because keys are smaller, and saves server cpu because signing is faster, but may increase client cpu because verification is slower. The byte savings may make up for the increase in cpu though. Interesting! I wonder if this new algorithm is intended to help with that. I'm super curious if the smaller payload does indeed make a difference (with the current algorithm) like you mention; I know that with databases and filesystems, compression is commonly used to shift the balance from I/O to CPU due to disk writes being slow (with reduced storage size being a side benefit but not usually the main motivation), but I also know that cryptographic verification being too slow can be an anti-feature if it makes brute forcing feasible, so the amount of CPU work needed might be pretty high still.
  - toast0 2y ago
    On my ancient box, only including a few lines of output: $ openssl speed rsa ecdsa sign verify sign/s verify/s rsa 1024 bits 0.000117s 0.000008s 8518.7 132449.2 rsa 2048 bits 0.000884s 0.000025s 1130.6 39499.3 sign verify sign/s verify/s 256 bits ecdsa (nistp256) 0.0000s 0.0001s 33210.9 11483.0 384 bits ecdsa (nistp384) 0.0009s 0.0008s 1070.6 1268.9 It's 11 k verify/s for ecda vs 39k verify/s for rsa-2048. A TLS handshake needs at least one sign and verify from the server cert, plus some verifies for the signature on the cert chain (but those signatures are used over and over).
scrapheap 2y ago
> My experience is that a decent number of people still use RSA keys most of the time, but I don't feel like I have nearly enough of a sample size to conclude anything significant from that. I wouldn't be surprised if a lot of people still use RSA for SSH keys for one or more of the following reasons: 1. A lot of tutorials about generating SSH Keys were written before ed25519, so if they follow an old tutorial they'll probably be generating an RSA key. 2. Older versions of OpenSSH, that you'd find on CentOS 7 and below, would default to RSA if you didn't specify a key type when running ssh-keygen. 3. There are some systems out there that don't support ed25519, though they are becoming rarer. If you have to deal with those systems then you're forced to use RSA (at least for that system). 4. Some of us have been using SSH keys from way before OpenSSH add support for ed25519 keys in 2014, so any long lived SSH keys won't be ed25519 keys (wow, ed25519 has now been about in OpenSSH for over 10 years).
- miki123211 2y ago
  5. a lot of people (especially older people I suspect) think "RSA" when they hear "public key cryptography". I'm in my twenties and still have that reaction. I know elliptic curves exist, I even sort-of-kind-of have an awareness of how they work, but if I was asked to name one cryptosystem that used public and private keys, I'd definitely say RSA first and not elliptic curves.
  - vitus 2y ago
    This is likely in no small part due to CS education only really teaching the mechanics of RSA (modular arithmetic, Fermat's little theorem, etc), or at least, that still seems to be the case at Berkeley. I'd guess because elliptic curve crypto requires more advanced math to reason about (more advanced group theory, at least) and doesn't map as cleanly to existing concepts that non-math-major undergrads have. cryptopals.com also doesn't cover any elliptive curve crypto until you get into the last set.
    - throw0101b 2y ago
      I would think that the (non-EC) Diffie-Hellman would also be easy enough to teach as well: exponentials and discrete log problem aren't any/much complicated than explaining factorization.
upofadown 2y ago
Another article from the same blog about optimizing RSA: * https://www.amazon.science/blog/formal-verification-makes-rsa-faster-and-faster-to-deploy https://www.amazon.science/blog/formal-verification-makes-rs... RSA signature verification is already very fast and TLS doesn't use RSA for encryption anymore so the problem reduces to optimizing signing operations.

by saghm 2y ago

stouset 2y ago

> anecdotally, generating 2048-bit or larger RSA keys for me tends to be a lot slower than ed25519 That’s not really anecdotal. Generating an ed25519 key is barely more than generating a random 256-bit value. Generating an RSA key is significantly more work.

saghm 2y ago
I did say my understanding was probably naive; I didn't know the details to be able to assert anything beyond my own observation!
- stouset 2y ago
  Yep, not faulting you at all! I too was surprised when I found out that it’s a straight 256-bit random value with a few bits masked.
  - saghm 2y ago
    I pretty quickly realized in college when learning about this stuff that the math was well over my head, and I shifted my focus more to understanding how to properly use cryptography rather than implement it (which turned out to be more important as a software engineer anyhow). In retrospect, I really appreciate how the professor I had in a security-focused course explicitly told us it was okay if we didn't understand the math and wouldn't be tested on it when going over how it worked.
    - tptacek 2y ago
      Counterpoint: it's not OK to skip the math with cryptography. You may not need to power through all of Silverman's curve book (though: I don't know for sure that's true, which is why I don't call myself a cryptography engineer), but you have to get as deep into the math as you can in order to safely use cryptographic algorithms. If you're math-avoidant, stick with high-level abstractions like NaCL and TLS. There's nothing wrong with that! A professor talking about and demonstrating cryptography at the level of individual algorithms is doing their class a disservice if they say "none of the math will be on the test". The algorithms are enough to put something together that seems like it works; the math is what you need to find out if your resulting system actually does work. It's where many of the fun bug classes live.
      - saghm 2y ago
        I'm not sure if you're reading more into what I said than I intended, but I'm not convinced by this argument. You might have missed that this course was on security in general, not cryptography; not everything in the course was cryptographic related. That said, I'd argue that for the vast majority of software engineers the type of stuff they're dealing with can be dealt with without needing to know the math. For example, you don't need to understand the math to behind the algorithms to know that bcrypt is a reasonable password hashing algorithm and that sha1 and md5 are not, or that salts are used to mitigate issues when users reuse passwords. These are principles that you can understand at a high level without fully understanding the underlying details. If anything, I think that overemphasis on requiring people to learn and understand the math has the effect of over-focusing on simpler algorithms that aren't actually what people want to be using in practice due to the fact that they're easier to teach and often foundational in conveying concepts that would need to be learned to understand the more complicated algorithms. If using cryptographic algorithms directly requires knowing the math, then I'd agree that most people shouldn't be using them directly, but I'd go further and say that a lack of libraries that are safe for people to use for software engineering without understanding the implementation is a failing of the ecosystem; as much as "regular" software engineering people (like myself!) can struggle with the math behind cryptography, I think that a lot of people developing cryptographic libraries struggle with building reasonable abstractions and making user-friendly APIs (which is a skill I think in general is not emphasized enough for most software engineers, to the detriment of everyone).
- syncsynchalt 2y ago
  Learning X25519 isn't too hard! See https://curves.xargs.org https://curves.xargs.org for the basics and https://x25519.xargs.org https://x25519.xargs.org for some refining details.

toast0 2y ago

> My (probably naive) understanding is that 25519 already provided better performance than other algorithms used for similar purposes (e.g. RSA) when tuned for a roughly similar level of security; anecdotally, generating 2048-bit or larger RSA keys for me tends to be a lot slower than ed25519. My also naive (an possibly out of date) understanding is key generation is much faster in with ecc, and that signing is faster too, but verifying is faster for rsa. So switching from a RSA to an ECC server certificate saves bytes on the wire, because keys are smaller, and saves server cpu because signing is faster, but may increase client cpu because verification is slower. The byte savings may make up for the increase in cpu though.

saghm 2y ago
> My also naive (an possibly out of date) understanding is key generation is much faster in with ecc, and that signing is faster too, but verifying is faster for rsa. So switching from a RSA to an ECC server certificate saves bytes on the wire, because keys are smaller, and saves server cpu because signing is faster, but may increase client cpu because verification is slower. The byte savings may make up for the increase in cpu though. Interesting! I wonder if this new algorithm is intended to help with that. I'm super curious if the smaller payload does indeed make a difference (with the current algorithm) like you mention; I know that with databases and filesystems, compression is commonly used to shift the balance from I/O to CPU due to disk writes being slow (with reduced storage size being a side benefit but not usually the main motivation), but I also know that cryptographic verification being too slow can be an anti-feature if it makes brute forcing feasible, so the amount of CPU work needed might be pretty high still.
- toast0 2y ago
  On my ancient box, only including a few lines of output: $ openssl speed rsa ecdsa sign verify sign/s verify/s rsa 1024 bits 0.000117s 0.000008s 8518.7 132449.2 rsa 2048 bits 0.000884s 0.000025s 1130.6 39499.3 sign verify sign/s verify/s 256 bits ecdsa (nistp256) 0.0000s 0.0001s 33210.9 11483.0 384 bits ecdsa (nistp384) 0.0009s 0.0008s 1070.6 1268.9 It's 11 k verify/s for ecda vs 39k verify/s for rsa-2048. A TLS handshake needs at least one sign and verify from the server cert, plus some verifies for the signature on the cert chain (but those signatures are used over and over).

scrapheap 2y ago

> My experience is that a decent number of people still use RSA keys most of the time, but I don't feel like I have nearly enough of a sample size to conclude anything significant from that. I wouldn't be surprised if a lot of people still use RSA for SSH keys for one or more of the following reasons: 1. A lot of tutorials about generating SSH Keys were written before ed25519, so if they follow an old tutorial they'll probably be generating an RSA key. 2. Older versions of OpenSSH, that you'd find on CentOS 7 and below, would default to RSA if you didn't specify a key type when running ssh-keygen. 3. There are some systems out there that don't support ed25519, though they are becoming rarer. If you have to deal with those systems then you're forced to use RSA (at least for that system). 4. Some of us have been using SSH keys from way before OpenSSH add support for ed25519 keys in 2014, so any long lived SSH keys won't be ed25519 keys (wow, ed25519 has now been about in OpenSSH for over 10 years).

miki123211 2y ago
5. a lot of people (especially older people I suspect) think "RSA" when they hear "public key cryptography". I'm in my twenties and still have that reaction. I know elliptic curves exist, I even sort-of-kind-of have an awareness of how they work, but if I was asked to name one cryptosystem that used public and private keys, I'd definitely say RSA first and not elliptic curves.
- vitus 2y ago
  This is likely in no small part due to CS education only really teaching the mechanics of RSA (modular arithmetic, Fermat's little theorem, etc), or at least, that still seems to be the case at Berkeley. I'd guess because elliptic curve crypto requires more advanced math to reason about (more advanced group theory, at least) and doesn't map as cleanly to existing concepts that non-math-major undergrads have. cryptopals.com also doesn't cover any elliptive curve crypto until you get into the last set.
  - throw0101b 2y ago
    I would think that the (non-EC) Diffie-Hellman would also be easy enough to teach as well: exponentials and discrete log problem aren't any/much complicated than explaining factorization.

upofadown 2y ago

Another article from the same blog about optimizing RSA: * https://www.amazon.science/blog/formal-verification-makes-rsa-faster-and-faster-to-deploy https://www.amazon.science/blog/formal-verification-makes-rs... RSA signature verification is already very fast and TLS doesn't use RSA for encryption anymore so the problem reduces to optimizing signing operations.