10 ms·

Better-performing “25519” elliptic-curve cryptography

218 points by lemaudit 2y ago

nanolith 2y ago
The formal methods nerd in me is happy to see HOL Light being used to formally verify this implementation. I'm curious to see how closely their abstract machine models follow specific machine implementations. OOO, speculation, and deep pipelining have non-trivial impacts on potential side channels, and these vary quite a bit by stepping and architecture.
- holowoodman 2y ago
  Even worse: Each new CPU generation will need a new machine model and a reevaluation. Because OOO, speculation and all the timing behaviour are non-functional properties that frequently change due to new optimizations, different internal structuring, etc.
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
- 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.
SEJeff 2y ago
The firedancer team at one of the better HFT firms wrote an AVX512 optimized implementation of ed25519 and X25519 that’s significantly faster than OpenSSL. https://github.com/firedancer-io/firedancer/pull/716 https://github.com/firedancer-io/firedancer/pull/716 Ditto for sha256: https://github.com/firedancer-io/firedancer/pull/778 https://github.com/firedancer-io/firedancer/pull/778 And sha512: https://github.com/firedancer-io/firedancer/pull/760 https://github.com/firedancer-io/firedancer/pull/760 If you’re an optimization nerd, this codebase is wild.
- electricshampo1 2y ago
  Completely agree re: firedancer codebase. There is a level of thought and discipline wrt performance that I have never seen anywhere else.
  - SEJeff 2y ago
    That team is full of world experts in high performance computing.
  - dhx 2y ago
    It's much more than just performance they've thought about. Here are some of the secure programming practices that have been implemented: /* All the functions in this file are considered "secure", specifically: - Constant time in the input, i.e. the input can be a secret[2] - Small and auditable code base, incl. simple types - Either, no local variables = no need to clear them before exit (most functions) - Or, only static allocation + clear local variable before exit (fd_ed25519_scalar_mul_base_const_time) - Clear registers via FD_FN_SENSITIVE[3] - C safety */ libsodium[4] implements similar mechanisms, and Linux kernel encryption code does too (example: use of kfree_sensitive)[5]. However, firedancer appears to better avoid moving secrets outside of CPU registers, and [3] explains that libraries such as libsodium have inadequate zeroisation, something which firedancer claims to improve upon. [1] https://github.com/firedancer-io/firedancer/blob/main/src/ballet/ed25519/fd_curve25519_secure.c https://github.com/firedancer-io/firedancer/blob/main/src/ba... [2] https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Constant_time_Montgomery_ladder https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic... [3] https://eprint.iacr.org/2023/1713 https://eprint.iacr.org/2023/1713 [4] https://libsodium.gitbook.io/doc/internals#security-first https://libsodium.gitbook.io/doc/internals#security-first [5] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
londons_explore 2y ago
Does 25519 suffer from key/data-dependant execution time? Is this implementation resistant to that? If it isn't, it's kinda a footgun which shouldn't be published for general use.
- vitus 2y ago
  > Does 25519 suffer from key/data-dependant execution time? I mean, when implemented naively, yes, but the industry has been aware of timing attacks for decades such that this is table stakes for any crypto implementations. From the article: > We also do our best to execute the algorithms in constant time, to thwart side-channel attacks that infer secret information from the durations of computations. https://github.com/awslabs/s2n-bignum https://github.com/awslabs/s2n-bignum (where most of the heavy lifting is done, per the article) further explicitly states that "Each function is moreover written in a constant-time style to avoid timing side-channels."
  - justinwsmith 2y ago
    The next paragraph makes a slightly stronger statement about its constant-time'ness: > Our implementations of x/Ed25519 are designed with constant time in mind. They perform exactly the same sequence of basic CPU instructions regardless of the input values, and they avoid any CPU instructions that might have data-dependent timing.
  - deathanatos 2y ago
    > but the industry has been aware of timing attacks for decades such that this is table stakes for any crypto implementations. When I see CVE-fests like — https://people.redhat.com/~hkario/marvin/ https://people.redhat.com/~hkario/marvin/ — … I just do not come away with that impression. [Widely used] Cryptographic Rust crates offering "constant time" operations in "pure Rust" — but Rust has no primitives for doing constant time operations, so it's only through hopes and prayers that it might actually work, and with no guarantee anywhere that it actually should. (Other, less timing attack related stuff, but e.g., major companies still not supporting anything beyond RSA.)
- syncsynchalt 2y ago
deleted 2y ago
[deleted]
fefe23 2y ago
Holy shit these claims are wild! It's not just a percent more performance here and there, the graphs look more like 50% more throughput on the same hardware (depending on the cpu architecture). My immediate fear was that they optimized away the security features like absence of timing side channels, but they say they still have those. They also claim to have formal proof of correctness, which is even more amazing, because they are not doing it on a symbolic level but on a machine instruction level. Apparently they tought their reasoning system the semantics of all the CPU instructions used in the assembler implementation. I'll still wait what djb has to say about this, but it looks freaking amazing to me.
jonmon6691 2y ago
I'm assuming when they say that this improves user experience, that it implies the use case is primarily TLS. In which case store-now-decrypt-later attacks are already considered an urgent threat with regard to post quantum crypto. With FIPS 203 being released and Chrome is already using an implementation based on the draft standard, this seems like this algo (at least for TLS) should be on its way out.
- dlgeek 2y ago
  The industry is moving to a hybrid that mixes classic crypto (including ECC) with post-quantum crypto. AWS has even turned this on in some places - https://aws.amazon.com/about-aws/whats-new/2022/03/aws-kms-acm-support-latest-hybrid-post-quantum-tls-ciphers/ https://aws.amazon.com/about-aws/whats-new/2022/03/aws-kms-a... from 2022 and https://docs.aws.amazon.com/kms/latest/developerguide/pqtls.html https://docs.aws.amazon.com/kms/latest/developerguide/pqtls.... for some details.
  - jonmon6691 2y ago
    Thanks I forgot about that. So if understand it right, the idea is to provide some insurance in the case that these relatively young algorithms are broken as they get exposed to more and more cryptanalysis
- adgjlsfhk1 2y ago
  No one other than NIST is recommending phasing out pre-quantum crypto. Everyone else is using a combination of pre-quantum and post-quantum because trust in the security and robustness of the post-quantum ecosystem is fairly low.
aseipp 2y ago
I was aware of s2n-bignum which is a very cool project, but apparently there is a larger sister project, aws-lc, that aims for broader set of APIs including OpenSSL compatibility, while retaining the general approach and vibe (lots of formal verification + performance work): https://github.com/aws/aws-lc https://github.com/aws/aws-lc That's pretty sweet. I'm currently using BoringSSL in a project as a supplement to OpenSSL (mostly because it is much easier to build for Windows users than requiring them to fiddle with msys2/vcpkg etc; the alternative is to rely on the Windows CNG API, but it lacks features like ed25519 support.) I wonder how much effort it would take to use aws-lc instead... Not that I'm that interested, BSSL is pretty good, but free performance and heavy automated verification is always nice :) Related: one of the authors of this post, John Harrison, wrote a really good book about automated theorm proving about 15 years ago while working on floating point verification at Intel -- there's still no other book quite like this one, I think https://www.cl.cam.ac.uk/~jrh13/ https://www.cl.cam.ac.uk/~jrh13/
- newman314 2y ago
  Upon hearing about AWS-LC, I immediately thought about tying it to nginx to see if it will work. Turns out someone else has already tried: https://github.com/aws/aws-lc/issues/1827 https://github.com/aws/aws-lc/issues/1827
  - initsecret 2y ago
    [dead]
notfed 2y ago
> The x25519 algorithm also plays a role in post-quantum safe cryptographic solutions, having been included as the classical algorithm in the TLS 1.3 and SSH hybrid scheme specifications for post-quantum key agreement. Really though? This mostly-untrue statement is the line that warrants adding hashtag #post-quantum-cryptography to the blogpost?
- westurner 2y ago
  Actually, e.g. rustls added X25519Kyber768Draft00 support this year: https://news.ycombinator.com/item?id=41534500 https://news.ycombinator.com/item?id=41534500 /?q X25519Kyber768Draft00: https://www.google.com/search?q=X25519Kyber768Draft00 https://www.google.com/search?q=X25519Kyber768Draft00
  - notfed 2y ago
    Kyber768 is the post-quantum algorithm in that example, not x25519.
    - westurner 2y ago
      From "OpenSSL 3.4 Alpha 1 Released with New Features" (8 days ago) https://news.ycombinator.com/item?id=41456447#41456774 https://news.ycombinator.com/item?id=41456447#41456774 : > Someday there will probably be a TLS1.4/2.0 with PQ, and also FIPS-140 -4? > Are there additional ways to implement NIST PQ finalist algos with openssl? - open-quantum-safe/oqs-provider [implements mlkem512 through mlkem1024 and x25519_mlkem768]
      - notfed 2y ago
        Not sure what you're trying to say here . x25519 is objectively not PQC and never claimed to be, and this isn't debatable.
        westurner 2y ago
        In this case, hybrid means "not entirely PQ".
webXL 2y ago
Why don't they just focus on making a Gravitron variant with those algorithms in the circuitry?
- AgentOrange1234 2y ago
  "just"?

218 points by lemaudit 2y ago

The formal methods nerd in me is happy to see HOL Light being used to formally verify this implementation. I'm curious to see how closely their abstract machine models follow specific machine implementations. OOO, speculation, and deep pipelining have non-trivial impacts on potential side channels, and these vary quite a bit by stepping and architecture.

holowoodman 2y ago
Even worse: Each new CPU generation will need a new machine model and a reevaluation. Because OOO, speculation and all the timing behaviour are non-functional properties that frequently change due to new optimizations, different internal structuring, etc.

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
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.

SEJeff 2y ago

The firedancer team at one of the better HFT firms wrote an AVX512 optimized implementation of ed25519 and X25519 that’s significantly faster than OpenSSL. https://github.com/firedancer-io/firedancer/pull/716 https://github.com/firedancer-io/firedancer/pull/716 Ditto for sha256: https://github.com/firedancer-io/firedancer/pull/778 https://github.com/firedancer-io/firedancer/pull/778 And sha512: https://github.com/firedancer-io/firedancer/pull/760 https://github.com/firedancer-io/firedancer/pull/760 If you’re an optimization nerd, this codebase is wild.

electricshampo1 2y ago
Completely agree re: firedancer codebase. There is a level of thought and discipline wrt performance that I have never seen anywhere else.
- SEJeff 2y ago
  That team is full of world experts in high performance computing.
- dhx 2y ago
  It's much more than just performance they've thought about. Here are some of the secure programming practices that have been implemented: /* All the functions in this file are considered "secure", specifically: - Constant time in the input, i.e. the input can be a secret[2] - Small and auditable code base, incl. simple types - Either, no local variables = no need to clear them before exit (most functions) - Or, only static allocation + clear local variable before exit (fd_ed25519_scalar_mul_base_const_time) - Clear registers via FD_FN_SENSITIVE[3] - C safety */ libsodium[4] implements similar mechanisms, and Linux kernel encryption code does too (example: use of kfree_sensitive)[5]. However, firedancer appears to better avoid moving secrets outside of CPU registers, and [3] explains that libraries such as libsodium have inadequate zeroisation, something which firedancer claims to improve upon. [1] https://github.com/firedancer-io/firedancer/blob/main/src/ballet/ed25519/fd_curve25519_secure.c https://github.com/firedancer-io/firedancer/blob/main/src/ba... [2] https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Constant_time_Montgomery_ladder https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic... [3] https://eprint.iacr.org/2023/1713 https://eprint.iacr.org/2023/1713 [4] https://libsodium.gitbook.io/doc/internals#security-first https://libsodium.gitbook.io/doc/internals#security-first [5] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

londons_explore 2y ago

Does 25519 suffer from key/data-dependant execution time? Is this implementation resistant to that? If it isn't, it's kinda a footgun which shouldn't be published for general use.

vitus 2y ago
> Does 25519 suffer from key/data-dependant execution time? I mean, when implemented naively, yes, but the industry has been aware of timing attacks for decades such that this is table stakes for any crypto implementations. From the article: > We also do our best to execute the algorithms in constant time, to thwart side-channel attacks that infer secret information from the durations of computations. https://github.com/awslabs/s2n-bignum https://github.com/awslabs/s2n-bignum (where most of the heavy lifting is done, per the article) further explicitly states that "Each function is moreover written in a constant-time style to avoid timing side-channels."
- justinwsmith 2y ago
  The next paragraph makes a slightly stronger statement about its constant-time'ness: > Our implementations of x/Ed25519 are designed with constant time in mind. They perform exactly the same sequence of basic CPU instructions regardless of the input values, and they avoid any CPU instructions that might have data-dependent timing.
- deathanatos 2y ago
  > but the industry has been aware of timing attacks for decades such that this is table stakes for any crypto implementations. When I see CVE-fests like — https://people.redhat.com/~hkario/marvin/ https://people.redhat.com/~hkario/marvin/ — … I just do not come away with that impression. [Widely used] Cryptographic Rust crates offering "constant time" operations in "pure Rust" — but Rust has no primitives for doing constant time operations, so it's only through hopes and prayers that it might actually work, and with no guarantee anywhere that it actually should. (Other, less timing attack related stuff, but e.g., major companies still not supporting anything beyond RSA.)
syncsynchalt 2y ago

deleted 2y ago

[deleted]

fefe23 2y ago

Holy shit these claims are wild! It's not just a percent more performance here and there, the graphs look more like 50% more throughput on the same hardware (depending on the cpu architecture). My immediate fear was that they optimized away the security features like absence of timing side channels, but they say they still have those. They also claim to have formal proof of correctness, which is even more amazing, because they are not doing it on a symbolic level but on a machine instruction level. Apparently they tought their reasoning system the semantics of all the CPU instructions used in the assembler implementation. I'll still wait what djb has to say about this, but it looks freaking amazing to me.

jonmon6691 2y ago

I'm assuming when they say that this improves user experience, that it implies the use case is primarily TLS. In which case store-now-decrypt-later attacks are already considered an urgent threat with regard to post quantum crypto. With FIPS 203 being released and Chrome is already using an implementation based on the draft standard, this seems like this algo (at least for TLS) should be on its way out.

dlgeek 2y ago
The industry is moving to a hybrid that mixes classic crypto (including ECC) with post-quantum crypto. AWS has even turned this on in some places - https://aws.amazon.com/about-aws/whats-new/2022/03/aws-kms-acm-support-latest-hybrid-post-quantum-tls-ciphers/ https://aws.amazon.com/about-aws/whats-new/2022/03/aws-kms-a... from 2022 and https://docs.aws.amazon.com/kms/latest/developerguide/pqtls.html https://docs.aws.amazon.com/kms/latest/developerguide/pqtls.... for some details.
- jonmon6691 2y ago
  Thanks I forgot about that. So if understand it right, the idea is to provide some insurance in the case that these relatively young algorithms are broken as they get exposed to more and more cryptanalysis
adgjlsfhk1 2y ago
No one other than NIST is recommending phasing out pre-quantum crypto. Everyone else is using a combination of pre-quantum and post-quantum because trust in the security and robustness of the post-quantum ecosystem is fairly low.

aseipp 2y ago

I was aware of s2n-bignum which is a very cool project, but apparently there is a larger sister project, aws-lc, that aims for broader set of APIs including OpenSSL compatibility, while retaining the general approach and vibe (lots of formal verification + performance work): https://github.com/aws/aws-lc https://github.com/aws/aws-lc That's pretty sweet. I'm currently using BoringSSL in a project as a supplement to OpenSSL (mostly because it is much easier to build for Windows users than requiring them to fiddle with msys2/vcpkg etc; the alternative is to rely on the Windows CNG API, but it lacks features like ed25519 support.) I wonder how much effort it would take to use aws-lc instead... Not that I'm that interested, BSSL is pretty good, but free performance and heavy automated verification is always nice :) Related: one of the authors of this post, John Harrison, wrote a really good book about automated theorm proving about 15 years ago while working on floating point verification at Intel -- there's still no other book quite like this one, I think https://www.cl.cam.ac.uk/~jrh13/ https://www.cl.cam.ac.uk/~jrh13/

newman314 2y ago
Upon hearing about AWS-LC, I immediately thought about tying it to nginx to see if it will work. Turns out someone else has already tried: https://github.com/aws/aws-lc/issues/1827 https://github.com/aws/aws-lc/issues/1827
- initsecret 2y ago
  [dead]

notfed 2y ago

> The x25519 algorithm also plays a role in post-quantum safe cryptographic solutions, having been included as the classical algorithm in the TLS 1.3 and SSH hybrid scheme specifications for post-quantum key agreement. Really though? This mostly-untrue statement is the line that warrants adding hashtag #post-quantum-cryptography to the blogpost?

westurner 2y ago
Actually, e.g. rustls added X25519Kyber768Draft00 support this year: https://news.ycombinator.com/item?id=41534500 https://news.ycombinator.com/item?id=41534500 /?q X25519Kyber768Draft00: https://www.google.com/search?q=X25519Kyber768Draft00 https://www.google.com/search?q=X25519Kyber768Draft00
- notfed 2y ago
  Kyber768 is the post-quantum algorithm in that example, not x25519.
  - westurner 2y ago
    From "OpenSSL 3.4 Alpha 1 Released with New Features" (8 days ago) https://news.ycombinator.com/item?id=41456447#41456774 https://news.ycombinator.com/item?id=41456447#41456774 : > Someday there will probably be a TLS1.4/2.0 with PQ, and also FIPS-140 -4? > Are there additional ways to implement NIST PQ finalist algos with openssl? - open-quantum-safe/oqs-provider [implements mlkem512 through mlkem1024 and x25519_mlkem768]
    - notfed 2y ago
      Not sure what you're trying to say here . x25519 is objectively not PQC and never claimed to be, and this isn't debatable.
      - westurner 2y ago
        In this case, hybrid means "not entirely PQ".

webXL 2y ago

Why don't they just focus on making a Gravitron variant with those algorithms in the circuitry?

AgentOrange1234 2y ago
"just"?