Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/crypto/curve25519,crypto/ed25519: reject low order points #31846

Closed
FiloSottile opened this issue May 5, 2019 · 6 comments
Closed

x/crypto/curve25519,crypto/ed25519: reject low order points #31846

FiloSottile opened this issue May 5, 2019 · 6 comments
Assignees
Milestone

Comments

@FiloSottile
Copy link
Member

@FiloSottile FiloSottile commented May 5, 2019

Rejecting low order points is not strictly necessary, but it helps root out behaviors that can come unexpected to protocol designers (like non-contributory DH, or signature:message:key not being 1:1:1). libsodium already does indiscriminately, and we should too.

https://github.com/jedisct1/libsodium/blob/cec56d867f741e66f78b9fde37d9081643599a2a/src/libsodium/crypto_scalarmult/curve25519/ref10/x25519_ref10.c#L90

This was suggested by Cas Cremers and Dennis Jackson as part of their upcoming work on revisiting small subgroup and invalid curve attacks.

@gopherbot
Copy link

@gopherbot gopherbot commented Jun 19, 2019

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

gopherbot pushed a commit that referenced this issue Jun 20, 2019
The RFC recommends checking the X25519 output to ensure it's not the
zero value, to guard against peers trying to remove contributory
behavior.

In TLS there should be enough transcript involvement to mitigate any
attack, and the RSA key exchange would suffer from the same issues by
design, so not proposing a backport.

See #31846

Change-Id: I8e657f8ee8aa72c3f8ca3b124555202638c53f5e
Reviewed-on: https://go-review.googlesource.com/c/go/+/183039
Run-TryBot: Filippo Valsorda <filippo@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Adam Langley <agl@golang.org>
@andybons andybons modified the milestones: Go1.13, Go1.14 Jul 8, 2019
@FiloSottile FiloSottile changed the title x/crypto/curve25519,x/crypto/ed25519: reject low order points crypto/ed25519: reject low order points Oct 1, 2019
@FiloSottile
Copy link
Member Author

@FiloSottile FiloSottile commented Oct 1, 2019

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

@armfazh
Copy link

@armfazh armfazh commented Jun 9, 2020

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

@FiloSottile FiloSottile changed the title crypto/ed25519: reject low order points x/crypto/curve25519,crypto/ed25519: reject low order points Dec 12, 2020
@FiloSottile
Copy link
Member Author

@FiloSottile FiloSottile commented Dec 12, 2020

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.

@cascremers
Copy link

@cascremers cascremers commented Dec 12, 2020

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)

@FiloSottile
Copy link
Member Author

@FiloSottile FiloSottile commented Dec 12, 2020

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants
You can’t perform that action at this time.