Change https://golang.org/cl/183039 mentions this issue: crypto/tls: reject low-order Curve25519 points

Curve25519 is covered by #32670, this issue is now about doing the check in crypto/ed25519.

Does the signature must also reject non-prime order points for the public keys and the R of signatures?

Changing the Ed25519 verification rules now would cause significant disruption downstream, as it would lead to forks in any cryptocurrency that relies on the crypto/ed25519 verification rules for consensus. (They should not do that and instead migrate to github.com/hdevalence/ed25519consensus, but it is what it is.)

While the contributory behavior of X25519 might be expected and is anyway easily achieved, the properties of Ed25519 that require low-order checks are not commonly understood to be signature properties. Moreover, no implementation in the ecosystem achieves them. libsodium makes an attempt but it's unclear if sufficient.

The original paper that led to #32670 is https://eprint.iacr.org/2019/526.pdf, with a live attack against Tendermint that would have failed with the new API. The paper that describes the Ed25519 properties is https://eprint.iacr.org/2019/779.pdf. You can read more at https://hdevalence.ca/blog/2020-10-04-its-25519am.

Instead, we'll lock in behavior with #40478.

Minor correction:

Moreover, no implementation in the ecosystem achieves them. libsodium makes an attempt but it's unclear if sufficient.

This is not the case -- libsodium provably achieves them. The details and proofs of the impact of checks (or lack thereof) were recently given here:

https://eprint.iacr.org/2020/823 (or S&P 2021)

(and in the previous, "Tamarin" should probably be something else, like a protocol, not a protocol analysis tool)

Minor correction:

Moreover, no implementation in the ecosystem achieves them. libsodium makes an attempt but it's unclear if sufficient.

This is not the case -- libsodium provably achieves them.

Ah, yes, thank you Cas! I was confusedly remembering the pre-1.0.16 behavior, where the check was not complete.

Looks like there's also ed25519-dalek’s verify_strict that applies the stricter checks, but in general it's still probably unwise of any protocol to assume the extra properties for Ed25519, so we should err on the side of avoiding breaking changes.

If an application really needs a VerifyStrict, it can start as an external module based on filippo.io/edwards25519 like github.com/hdevalence/ed25519consensus, and get promoted to the stdlib if it's widely adopted.

The details and proofs of the impact of checks (or lack thereof) were recently given here:

https://eprint.iacr.org/2020/823 (or S&P 2021)

I had that open in a tab but clearly haven't gotten to it yet! Glad it addresses this.

(and in the previous, "Tamarin" should probably be something else, like a protocol, not a protocol analysis tool)

Hah, "Tendermint" of course. Fixed.