4 ms·

It's sad that efficient complete formulas for Weierstrass curves were found only after Curve25519 was well established. Now we are stuck with all these cofactor

It's sad that efficient complete formulas for Weierstrass curves were found only after Curve25519 was well established. Now we are stuck with all these cofactor issues. Ristretto is nice but so terribly complex: https://ristretto.group/details/isogenies.html https://ristretto.group/details/isogenies.html

beefhash 6y ago
> efficient complete formulas for Weierstrass curves were found only after Curve25519 was well established Assuming you are talking about the Renes–Costello–Batina formulas, they're complete, but not necessarily efficient. According to [1], optimized short Weierstrass with the complete formulas is still 1.5 to 3 times slower than Curve25519. I imagine the numbers won't be much better for Edwards25519, either. There's definitely a ton of potential for a better complete addition formula on Weierstrass still left. > Ristretto is nice but so terribly complex Ristretto is nice, terribly complex, and you don't actually need to care about the conceptual complexity. As an implementer, your only job is to execute the explicit formulas in section 5 of the Ristretto website. You do not have to be able to follow the hard math (just how you do not have to be able to follow the hard math involved in making the explicit formulas). Plus the entire thing can be trivially constant-time given a constant-time selection primitive and constant-time field arithmetic. It's not that much more difficult than doing regular point compression on your own. [1] Peter Schwabe, Daan Sprenkels. The complete cost of cofactor h=1 (published in INDOCRYPT19), https://eprint.iacr.org/2019/1166.pdf https://eprint.iacr.org/2019/1166.pdf
- shinigami 6y ago
  Exactly. Yes, it's still not as efficient... but it feels to me that if they were found before and were "marketed" as Curve25519 was, we would be using them instead. There were always more efficient formats (binary curves, extension fields) but they never caught on, so efficiency isn't everything. From a cursory reading, shouldn't that paper compare timings with a Ristretto implementation? The overhead may be small but must be measured for a fair comparison. It's good to know that implementing Ristretto is much easier than understanding it - that website is very intimidating ;) I need to study it more.
- cryptbe 6y ago
  >Ristretto is nice, terribly complex, and you don't actually need to care about the conceptual complexity. As an implementer, your only job is to execute the explicit formulas in section 5 of the Ristretto website. You do not have to be able to follow the hard math (just how you do not have to be able to follow the hard math involved in making the explicit formulas). I don't think one should blindly follow an instruction without understanding why in any fields, let alone in crypto where a small, subtle difference can make or break it. Also, understanding crypto requires less math than inventing (and attacking) crypto, so it takes some effort, but it's doable even for hobbyists. If the math makes one uncomfortable, maybe one shouldn't try to roll their own crypto for production use in the first place. Case in point: the author of this article that we're commenting on made a deadly mistake because they did not understand the math behind point conversion between Ed25519 and Curve25519 [1]. Below I also point out a mistake in their claim about malleability in EdDSA. [1] https://www.reddit.com/r/crypto/comments/8toywt/critical_vulnerability_in_monocypher_full/ https://www.reddit.com/r/crypto/comments/8toywt/critical_vul...
  - shinigami 6y ago
    That's a good example of how a "SafeCurve" caused a vulnerability that wouldn't exist in Weierstrass curve. But many smart people made many such mistakes in the past. If we gatekeep it to much then we won't have anyone left to implement crypto.
    - beefhash 6y ago
      Maybe we should gatekeep it so much though. As long as there exist at least two people capable of implementation per programming language (one to implement, another to audit), there will only ever be one, single, canonical implementation and there's no way around it. It is not and should not be an inherent right to be allowed to implement cryptography (that is put into production or made publicly available). The gatekeeping is there for a reason and it's important that we uphold it. Fewer implementations means that more people will be focused on having to write and check less code overall. Patents could be used to help with this by only permitting one upstream implementation to exist, but that's now how they end up being used in practice, and that's ignoring the fact that patent expiry is impractically short (compared to copyright expiry especially so).
- paulmillr 6y ago
  It's not that complex once you have formulas for computing square roots. I've recently implemented it in TypeScript using bigints for browsers & nodejs. Quite readable & performant. See index.ts file here: https://github.com/paulmillr/noble-ed25519 https://github.com/paulmillr/noble-ed25519 Wish ristretto folks added the library to their website though.
xmmrm 6y ago
By the way, what’s the status of ristretto255? The latest version of the internet-draft [0] expired a while ago. [0] https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/ https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristr...
- beefhash 6y ago
  From what I can tell, they were trying to get it adopted as RFC, but then a couple more things popped up on the CFRG, so they're planning a new version[1]. It's been adopted by the CFRG officially[2]. I haven't seen any sign of when the next version may be out (which will be draft-irtf-cfrg-ristretto-00[3]), however. I kind of hope they'll also add ristretto448 since RFC 7748 and 8032 include X448/Ed448, so that the draft has feature parity (and covers the h = 4 case properly). [1] https://mailarchive.ietf.org/arch/msg/cfrg/3RRpX9hME5ErtAzCoVgzUoP27Ys/ https://mailarchive.ietf.org/arch/msg/cfrg/3RRpX9hME5ErtAzCo... [2] https://mailarchive.ietf.org/arch/msg/cfrg/wd8pprUfJoNhvEQE0PH_gGPS374/ https://mailarchive.ietf.org/arch/msg/cfrg/wd8pprUfJoNhvEQE0... [3] https://mailarchive.ietf.org/arch/msg/cfrg/pT2ML68BapPAcUiSk94LW298L4k/ https://mailarchive.ietf.org/arch/msg/cfrg/pT2ML68BapPAcUiSk...
- str4d 6y ago
  We've just finished our own updates to the draft, and are currently getting some feedback on it off-list before we publish the next version.
zahllos 6y ago
> It's sad that efficient complete formulas for Weierstrass curves were found only after Curve25519 was well established This is not the only motivating factor for curve25519. There is also: that montgomery curves work well with the montgomery ladder, which is easy to use in constant time, and that any 32-byte string is a valid public key for ECDH. > Now we are stuck with all these cofactor issues. They are not a major problem for ECDH. If you are doing only ECDH and don't care about group structure, you can simply use the existing clamping mitigations. The point of ristretto, and its precursor/similar project decaf, is to preserve group structure while using these curves, and also eliminating small subgroups.
- shinigami 6y ago
  > Montgomery curves work well with the montgomery ladder, which is easy to use in constant time, and that any 32-byte string is a valid public key for ECDH. You can also have Montgomery ladder an a 32-byte encoding with Weierstrass curve, even though it would be slower. > The point of ristretto, and its precursor/similar project decaf, is to preserve group structure while using these curves, and also eliminating small subgroups. Exactly. Because we are stuck with all these cofactor issues. Not to mention how clamping also "contaminated" EdDSA.
xmmrm 6y ago
Have you seen Curve9767 [0] ? Short-Weierstrass, prime-order, but the implementation does not use the complete formulas. Competitive performance, on the ARM Cortex-M0+ at least. [0] https://github.com/pornin/curve9767 https://github.com/pornin/curve9767

beefhash 6y ago

> efficient complete formulas for Weierstrass curves were found only after Curve25519 was well established Assuming you are talking about the Renes–Costello–Batina formulas, they're complete, but not necessarily efficient. According to [1], optimized short Weierstrass with the complete formulas is still 1.5 to 3 times slower than Curve25519. I imagine the numbers won't be much better for Edwards25519, either. There's definitely a ton of potential for a better complete addition formula on Weierstrass still left. > Ristretto is nice but so terribly complex Ristretto is nice, terribly complex, and you don't actually need to care about the conceptual complexity. As an implementer, your only job is to execute the explicit formulas in section 5 of the Ristretto website. You do not have to be able to follow the hard math (just how you do not have to be able to follow the hard math involved in making the explicit formulas). Plus the entire thing can be trivially constant-time given a constant-time selection primitive and constant-time field arithmetic. It's not that much more difficult than doing regular point compression on your own. [1] Peter Schwabe, Daan Sprenkels. The complete cost of cofactor h=1 (published in INDOCRYPT19), https://eprint.iacr.org/2019/1166.pdf https://eprint.iacr.org/2019/1166.pdf

shinigami 6y ago
Exactly. Yes, it's still not as efficient... but it feels to me that if they were found before and were "marketed" as Curve25519 was, we would be using them instead. There were always more efficient formats (binary curves, extension fields) but they never caught on, so efficiency isn't everything. From a cursory reading, shouldn't that paper compare timings with a Ristretto implementation? The overhead may be small but must be measured for a fair comparison. It's good to know that implementing Ristretto is much easier than understanding it - that website is very intimidating ;) I need to study it more.
cryptbe 6y ago
>Ristretto is nice, terribly complex, and you don't actually need to care about the conceptual complexity. As an implementer, your only job is to execute the explicit formulas in section 5 of the Ristretto website. You do not have to be able to follow the hard math (just how you do not have to be able to follow the hard math involved in making the explicit formulas). I don't think one should blindly follow an instruction without understanding why in any fields, let alone in crypto where a small, subtle difference can make or break it. Also, understanding crypto requires less math than inventing (and attacking) crypto, so it takes some effort, but it's doable even for hobbyists. If the math makes one uncomfortable, maybe one shouldn't try to roll their own crypto for production use in the first place. Case in point: the author of this article that we're commenting on made a deadly mistake because they did not understand the math behind point conversion between Ed25519 and Curve25519 [1]. Below I also point out a mistake in their claim about malleability in EdDSA. [1] https://www.reddit.com/r/crypto/comments/8toywt/critical_vulnerability_in_monocypher_full/ https://www.reddit.com/r/crypto/comments/8toywt/critical_vul...
- shinigami 6y ago
  That's a good example of how a "SafeCurve" caused a vulnerability that wouldn't exist in Weierstrass curve. But many smart people made many such mistakes in the past. If we gatekeep it to much then we won't have anyone left to implement crypto.
  - beefhash 6y ago
    Maybe we should gatekeep it so much though. As long as there exist at least two people capable of implementation per programming language (one to implement, another to audit), there will only ever be one, single, canonical implementation and there's no way around it. It is not and should not be an inherent right to be allowed to implement cryptography (that is put into production or made publicly available). The gatekeeping is there for a reason and it's important that we uphold it. Fewer implementations means that more people will be focused on having to write and check less code overall. Patents could be used to help with this by only permitting one upstream implementation to exist, but that's now how they end up being used in practice, and that's ignoring the fact that patent expiry is impractically short (compared to copyright expiry especially so).
paulmillr 6y ago
It's not that complex once you have formulas for computing square roots. I've recently implemented it in TypeScript using bigints for browsers & nodejs. Quite readable & performant. See index.ts file here: https://github.com/paulmillr/noble-ed25519 https://github.com/paulmillr/noble-ed25519 Wish ristretto folks added the library to their website though.

xmmrm 6y ago

By the way, what’s the status of ristretto255? The latest version of the internet-draft [0] expired a while ago. [0] https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/ https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristr...

beefhash 6y ago
From what I can tell, they were trying to get it adopted as RFC, but then a couple more things popped up on the CFRG, so they're planning a new version[1]. It's been adopted by the CFRG officially[2]. I haven't seen any sign of when the next version may be out (which will be draft-irtf-cfrg-ristretto-00[3]), however. I kind of hope they'll also add ristretto448 since RFC 7748 and 8032 include X448/Ed448, so that the draft has feature parity (and covers the h = 4 case properly). [1] https://mailarchive.ietf.org/arch/msg/cfrg/3RRpX9hME5ErtAzCoVgzUoP27Ys/ https://mailarchive.ietf.org/arch/msg/cfrg/3RRpX9hME5ErtAzCo... [2] https://mailarchive.ietf.org/arch/msg/cfrg/wd8pprUfJoNhvEQE0PH_gGPS374/ https://mailarchive.ietf.org/arch/msg/cfrg/wd8pprUfJoNhvEQE0... [3] https://mailarchive.ietf.org/arch/msg/cfrg/pT2ML68BapPAcUiSk94LW298L4k/ https://mailarchive.ietf.org/arch/msg/cfrg/pT2ML68BapPAcUiSk...
str4d 6y ago
We've just finished our own updates to the draft, and are currently getting some feedback on it off-list before we publish the next version.

zahllos 6y ago

> It's sad that efficient complete formulas for Weierstrass curves were found only after Curve25519 was well established This is not the only motivating factor for curve25519. There is also: that montgomery curves work well with the montgomery ladder, which is easy to use in constant time, and that any 32-byte string is a valid public key for ECDH. > Now we are stuck with all these cofactor issues. They are not a major problem for ECDH. If you are doing only ECDH and don't care about group structure, you can simply use the existing clamping mitigations. The point of ristretto, and its precursor/similar project decaf, is to preserve group structure while using these curves, and also eliminating small subgroups.

shinigami 6y ago
> Montgomery curves work well with the montgomery ladder, which is easy to use in constant time, and that any 32-byte string is a valid public key for ECDH. You can also have Montgomery ladder an a 32-byte encoding with Weierstrass curve, even though it would be slower. > The point of ristretto, and its precursor/similar project decaf, is to preserve group structure while using these curves, and also eliminating small subgroups. Exactly. Because we are stuck with all these cofactor issues. Not to mention how clamping also "contaminated" EdDSA.

xmmrm 6y ago

Have you seen Curve9767 [0] ? Short-Weierstrass, prime-order, but the implementation does not use the complete formulas. Competitive performance, on the ARM Cortex-M0+ at least. [0] https://github.com/pornin/curve9767 https://github.com/pornin/curve9767