Cofactor Explained: Clearing Elliptic Curves' dirty little secret(loup-vaillant.fr)
loup-vaillant.fr
Cofactor Explained: Clearing Elliptic Curves' dirty little secret
http://loup-vaillant.fr/tutorials/cofactor
37 comments
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
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
[0] https://github.com/pornin/curve9767
> 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
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
>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_vul...
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_vul...
> 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
By the way, since you seem to work on Wycheproof: would you take a look at my pull request? The EdDSA test vectors would have saved me (and my users), but the front page didn't mention them, so I didn't know they even existed for over a year. I initially believed you were concentrating on other, even more error prone, primitives.
Others might be in my position: letting bugs through because they think Whycheproof is not relevant to their project. A pity, considering how amazing Whycheproof is (I'm now systematically integrating any new test vector I learn about).
By the way, since you seem to work on Wycheproof: would you take a look at my pull request? The EdDSA test vectors would have saved me (and my users), but the front page didn't mention them, so I didn't know they even existed for over a year. I initially believed you were concentrating on other, even more error prone, primitives.
Others might be in my position: letting bugs through because they think Whycheproof is not relevant to their project. A pity, considering how amazing Whycheproof is (I'm now systematically integrating any new test vector I learn about).
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.
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.
I didn't say anything about gatekeeping. It's okay to make mistakes, that's one of the best way to learn.
I said if one isn't comfortable with the math, maybe don't try to roll one's own crypto and advertise or use it as production-grade crypto.
I said if one isn't comfortable with the math, maybe don't try to roll one's own crypto and advertise or use it as production-grade crypto.
It's difficult to assess one's "comfort" with the math. I've been working with crypto for more then 10 years and I wouldn't say that I'm perfectly "comfortable" (e.g. the Ristretto stuff). Should I stop working with it?
You should not implement Ristretto, and continue implementing stuff that you're comfortable with.
Crypto is deep. You can get involved at the levels you feel comfortable with.
Crypto is deep. You can get involved at the levels you feel comfortable with.
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).
Gate keeping is a double edged, and somewhat blunt, sword.
First, some Maverick is going to ignore what everyone says and implement crypto for serious applications. Like yours truly.
Second, I've seen it go a bit too far when I implemented Argon2i: there was a discrepancy between the specs and the reference implementations, and the authors haven't corrected the specs. I figured this was because not enough independent implementers bugged them about that. (Now, 3 years later, the specs still aren't fixed, so maybe the authors are really really busy. At least but the issue is still open: https://github.com/P-H-C/phc-winner-argon2/issues/183 )
First, some Maverick is going to ignore what everyone says and implement crypto for serious applications. Like yours truly.
Second, I've seen it go a bit too far when I implemented Argon2i: there was a discrepancy between the specs and the reference implementations, and the authors haven't corrected the specs. I figured this was because not enough independent implementers bugged them about that. (Now, 3 years later, the specs still aren't fixed, so maybe the authors are really really busy. At least but the issue is still open: https://github.com/P-H-C/phc-winner-argon2/issues/183 )
That simply does not work in the real world. Also, why does this only applies to crypto? A RCE vuln can have a much larger impact than mishandling cofactors. Should we have canonical implementations of every piece of software imaginable?
we should leave the task of left-padding a string to a popular, no doubt well-tested library
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
Wish ristretto folks added the library to their website though.
Wish ristretto folks added the library to their website though.
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.
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.
> 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.
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.
> 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.
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.
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-ristr...
[0] https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristr...
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.
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/3RRpX9hME5ErtAzCo...
[2] https://mailarchive.ietf.org/arch/msg/cfrg/wd8pprUfJoNhvEQE0...
[3] https://mailarchive.ietf.org/arch/msg/cfrg/pT2ML68BapPAcUiSk...
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/3RRpX9hME5ErtAzCo...
[2] https://mailarchive.ietf.org/arch/msg/cfrg/wd8pprUfJoNhvEQE0...
[3] https://mailarchive.ietf.org/arch/msg/cfrg/pT2ML68BapPAcUiSk...
Could you please describe the steps to generate key pairs with random public part using ristretto?
Er, TFA's description of EdDSA is incorrect. There are no nonces in EdDSA.
It's a simplified description of EdDSA (and as much is said in the article), taking out the deterministic part for a random nonce, effectively presenting key-prefixed Schnorr signatures instead.
Shouldn't it be
> 1 = 12 + 33 = 4.3 + 11.3
instead of
> 1 = 12 + 33 = 1.3 + 11.3
Neat read :) learned a bit!
> 1 = 12 + 33 = 4.3 + 11.3
instead of
> 1 = 12 + 33 = 1.3 + 11.3
Neat read :) learned a bit!
Oops, my bad. Correcting now, thanks.
tl;dr: the conclusion of the EdDSA part of the article is wrong. EdDSA has its problems, but malleability is not one of them, if one is following RFC 8032.
>There are several ways to sign a document with EdDSA, and produce a valid signature. The three sources of malleability are:
>We can add a multiple of L (the order of the prime subgroup) to s. Recall that B has order L as well, so it will absorb any cofactor. Basically everything happens modulo L, so adding L won't change a thing.
This is prevented in RFC 8032 by checking that 0 <= s < L. Tink [1] does this check, and therefore is malleability free.
>We can sign the same message with a different nonce r. This requires knowledge of the secret key a.
This proves that the signature of a message is not unique -- that is the signer can product multiple signatures -- but I haven't seen anyone calling this a malleability issue. Malleability is about taking a triple (public key, signature message) and tweaking bits to produce another valid triple.
>We can add a low order point to A, and subtract it from R. That way we produce a valid signature, but from a public key nobody vouches for. If the verifier checks the weaker equation, we can add a low order point to just R, and produce a "valid" signature with the same public key.
This is the second time I saw this claim. When I first saw it [2], I thought, wait, this test is missing in Wycheproof [3], but Bleichenbacher does NOT miss anything. That's when I knew it's wrong.
Modifying A or R instantly makes the signature invalid. Using the article's notation, the signature is validated by checking that
B.s.8 == R.8 + A.h.8, where h = SHA-512(R, A, M) and M is the message
Multiplying the cofactor or not doesn't matter, doesn't introduce any weakness, as implied by the article. If R or A is changed, h will change.
[1] https://github.com/google/tink
[2] https://github.com/dalek-cryptography/ed25519-dalek/issues/2...
[3] https://github.com/google/wycheproof. Wycheproof has tests for EdDSA malleability, but it only tests if s is not properly range checked.
>There are several ways to sign a document with EdDSA, and produce a valid signature. The three sources of malleability are:
>We can add a multiple of L (the order of the prime subgroup) to s. Recall that B has order L as well, so it will absorb any cofactor. Basically everything happens modulo L, so adding L won't change a thing.
This is prevented in RFC 8032 by checking that 0 <= s < L. Tink [1] does this check, and therefore is malleability free.
>We can sign the same message with a different nonce r. This requires knowledge of the secret key a.
This proves that the signature of a message is not unique -- that is the signer can product multiple signatures -- but I haven't seen anyone calling this a malleability issue. Malleability is about taking a triple (public key, signature message) and tweaking bits to produce another valid triple.
>We can add a low order point to A, and subtract it from R. That way we produce a valid signature, but from a public key nobody vouches for. If the verifier checks the weaker equation, we can add a low order point to just R, and produce a "valid" signature with the same public key.
This is the second time I saw this claim. When I first saw it [2], I thought, wait, this test is missing in Wycheproof [3], but Bleichenbacher does NOT miss anything. That's when I knew it's wrong.
Modifying A or R instantly makes the signature invalid. Using the article's notation, the signature is validated by checking that
B.s.8 == R.8 + A.h.8, where h = SHA-512(R, A, M) and M is the message
Multiplying the cofactor or not doesn't matter, doesn't introduce any weakness, as implied by the article. If R or A is changed, h will change.
[1] https://github.com/google/tink
[2] https://github.com/dalek-cryptography/ed25519-dalek/issues/2...
[3] https://github.com/google/wycheproof. Wycheproof has tests for EdDSA malleability, but it only tests if s is not properly range checked.
> malleability is not one of them, if one is following RFC 8032
This is like claiming Weierstrass curves don't have any problems if you follow the NIST/SECG standards. The whole point of the "SafeCurves" it to be easier to get them right, but you can still get them wrong.
This is like claiming Weierstrass curves don't have any problems if you follow the NIST/SECG standards. The whole point of the "SafeCurves" it to be easier to get them right, but you can still get them wrong.
If one implements EdDSA, but does not follow RFC 8032, one is doing it wrong on multiple levels.
Daniel J. Bernstein et al's original paper (High-Speed High-Security Signatures), didn't feel the need to take as many precautions as RFC 8032. For instance, they didn't care about malleability.
You seem to think they should have. May I ask why?
You seem to think they should have. May I ask why?
I'm interested in Thai's response to this question too, as I would be in any comment anyone managed to solicit from him about this topic, but an easy point to make here is that Bernstein was himself involved in RFC 8032, at least as a reviewer and contributor to the process, as you can quickly learn by reading the CFRG mailing list.
Oh, so DJB changed his mind then? Makes sense considering the application of EdDSA beyond signatures (I've heard malleability is a problem with zero-knowledge proofs, but I haven't studied that subject).
If one implements ECDSA, but does not follow SECG, one is also doing it wrong on multiple levels. Yet here we are.
> This is prevented in RFC 8032 by checking that 0 <= s < L
It is, but some libraries do not perform this check. Including TweetNaCl if I recall correctly.
> Modifying A or R instantly makes the signature invalid.
I was talking about modifying them together. Here's what I claim:
> Multiplying the cofactor or not doesn't matter
Perhaps I went over this a bit to fast. Recall that for any low order point P, P.8 = zero. Once you accept this fact, the rest follows pretty smoothly:
I'll add this explanation in the article, thanks for the feedback.
It is, but some libraries do not perform this check. Including TweetNaCl if I recall correctly.
> Modifying A or R instantly makes the signature invalid.
I was talking about modifying them together. Here's what I claim:
B.s = R + A.h
B.s = R + A.h + P - P
B.s =(R + P) + (A.h - P)
> Multiplying the cofactor or not doesn't matter
Perhaps I went over this a bit to fast. Recall that for any low order point P, P.8 = zero. Once you accept this fact, the rest follows pretty smoothly:
B.s = R + A.h
B.s.8 = (R + A.h).8
B.s.8 = R.8 + A.h.8
B.s.8 = R.8 + A.h.8 + zero
B.s.8 = R.8 + A.h.8 + P.8
B.s.8 = (R+P).8 + A.h.8
I'll add this explanation in the article, thanks for the feedback.
>It is, but some libraries do not perform this check. Including TweetNaCl if I recall correctly.
I'm not sure why TweetNaCl is even considered a serious crypto library. I guess that it can fit in tweets, but this is an optimization that is at best irrelevant at worst a bad software engineering practice.
Re malleability: instead of just thinking about this issue in an abstract way, I recommend writing an exploit. For example, Tink doesn't check R or A at all, try to see if you can produce a new signature from an existing one by modifying R or A as you said.
I'm not sure why TweetNaCl is even considered a serious crypto library. I guess that it can fit in tweets, but this is an optimization that is at best irrelevant at worst a bad software engineering practice.
Re malleability: instead of just thinking about this issue in an abstract way, I recommend writing an exploit. For example, Tink doesn't check R or A at all, try to see if you can produce a new signature from an existing one by modifying R or A as you said.
> Re malleability: instead of just thinking about this issue in an abstract way, I recommend writing an exploit.
Challenge accepted! Hmm, doesn't work. Let me think a bit more abou— <facepalm>
Of course: I totally forgot that h is a hash of R and A, not just the message. So if I change them in any way, h's main factor will change unpredictably, and the signature will fail. Looks like the only malleability left is `s`, and that has nothing to do with the cofactor. Let's take the whole section down.
Lesson learned: I should test my writings like I test my code.
---
If I may, you should have lead with "If R or A is changed, h will change." I let myself get worked up by your first comment¹, and failed to notice the single most important sentence near the bottom. I ended up having to reach the same conclusion independently. I almost missed my error.
[1]: You didn't address me directly, and you didn't start with my error. Regardless of your intentions, that felt mildly confrontational. Being nicer would have been more effective.
Challenge accepted! Hmm, doesn't work. Let me think a bit more abou— <facepalm>
Of course: I totally forgot that h is a hash of R and A, not just the message. So if I change them in any way, h's main factor will change unpredictably, and the signature will fail. Looks like the only malleability left is `s`, and that has nothing to do with the cofactor. Let's take the whole section down.
Lesson learned: I should test my writings like I test my code.
---
If I may, you should have lead with "If R or A is changed, h will change." I let myself get worked up by your first comment¹, and failed to notice the single most important sentence near the bottom. I ended up having to reach the same conclusion independently. I almost missed my error.
[1]: You didn't address me directly, and you didn't start with my error. Regardless of your intentions, that felt mildly confrontational. Being nicer would have been more effective.
> I'm not sure why TweetNaCl is even considered a serious crypto library.
Probably because its authors are all big-name people and their paper says:
> We have placed TweetNaCl into the public domain, and we encourage applications to make use of it.
Probably because its authors are all big-name people and their paper says:
> We have placed TweetNaCl into the public domain, and we encourage applications to make use of it.