crypto/elliptic: IsOnCurve returns true for invalid field elements

[FiloSottile]

Guido Vranken reported to us a pair of big.Int coordinates that returns true from IsOnCurve, and then causes a panic in ScalarMult. Our investigation concluded that there is a broader issue with big.Ints that are invalid representations of a field element.

Background

First, a bit of context of how we got here. crypto/elliptic implements elliptic curves over prime-order finite fields, meaning coordinates are elements of the field composed of the integers from zero to P-1 for some prime P. Integers below zero (negative) or equal to or higher than P (overflowing) are as meaningless as coordinates as float64(1.5) or string("hi") would be.

Regrettably, the crypto/elliptic API allows passing negative or overflowing big.Ints as coordinates.

Similarly, an arbitrary pair of field elements (x, y) is not a valid point if they don't satisfy the curve equation, and doing group operations (like a scalar multiplication) on them is meaningless. (Worse, it's called an invalid curve attack and can leak bits of the scalar that an attacker can plug into the evergreen Chinese Remainder Theorem.)

As you probably guessed, dear reader, crypto/elliptic will let us call ScalarMult on any pair of big.Ints. Adding insult to injury, neither elliptic.Marshal nor the group operations (Add, Double, ScalarMult) return an error, giving us no opportunity to reject nonsensical or radioactive inputs.

The (implicit in Go 1.17, made explicit in Go 1.18 by my recent refactor) contract of crypto/elliptic is: you shall pass input points though IsOnCurve (Unmarshal will do it for you); if it returns true, then all group operations will work and return valid points. If IsOnCurve returns false, behavior is undefined.

(With one footnote: (0, 0) is not a valid point, Unmarshal will not return it, IsOnCurve will return false, and Marshal will behave incorrectly, but it's what group operations return if the output is the point at infinity, which can't be represented with two abelian coordinates. Again, exposing the coordinates in the API is a mistake. See this Go 1.15 change and the linked issue for more info.)

Current status

Cool. Now, let's look at what the actual behavior is for some invalid inputs: https://go.dev/play/p/GBMkROJLtDX

The results might look all over the place, especially in that they change at tip, but here are the patterns:

• IsOnCurve behaves according to the backend implementation.
  • The generic IsOnCurve, the P-256 one, and the Go 1.17 fiat-crypto ones accept coordinates of any sign or size (such as (x - 1000P, y), (x - P, y), or (x + 1000P, y)), as long as they reduce to a valid coordinate.
    • This is bad because we can't claim undefined behavior on how these inputs behave.
  • The Go 1.17 P-224 IsOnCurve returns false, but unintentionally, due to dropping the sign and the overflow. Go 1.18 is fixed for overflowing values but not negative ones.
    • This is also bad, as it's trivial to find invalid inputs that pass the check.
  • The new Go 1.18 fiat-crypto/nistec backend returns false intentionally for overflowing values, but returns false unintentionally for negative values because it drops the sign.
    • This is unintended, but it shouldn't lead to attacks, because the group operations will not run on invalid points (see below).
• Marshal panics on anything bigger than P in absolute value (by enough to overflow the slice length rounded up to the nearest byte), and it encodes the wrong value (P-x instead of x) for a small but negative value.
• ScalarMult also behaves according to the backend implementation.
  • The generic and the Go 1.17 fiat-crypto implementations treat negative and overflowing values as (x, y).
  • P-256 will panic on large negative values, drop the sign and return a point not on the curve on small negative values, and treat overflowing values as (x, y).
    • The panic is the original issue that was reported to us. The scenario where an input that passed IsOnCurve leads to an off-curve output is also very bad, as it leads to invalid curve attacks.
  • Go 1.17's P-224 returns invalid points for all inputs, as it drops the sign and truncates the overflow.
  • The new Go 1.18 fiat-crypto/nistec backend intentionally returns random points.
    • This is intentional, because a random point was the safest output I could think of when implementing the old API (which can't return an error), in terms of the new API, which just won't operate on invalid points.

Remediation

First, we will fix IsOnCurve as a security issue (CVE-2022-23806) to always return false for negative and overflowing values, because that's the function behaving inconsistently and the only one for which these inputs shouldn't be undefined behavior. I expect next to no one will get broken by this, because the rest of the operations rarely behave correctly on the values that incorrectly return true.

This issue is being fixed on the PUBLIC track, since we found no paths for negative elements to get deserialized (ASN.1, Unmarshal, popular JOSE libraries) and the only curve where large positive elements lead to invalid curve operations is P-224, which is rarely used.

Next, we need to decide what Marshal and the group operations should do for invalid field elements, and more broadly for invalid points (which are not discussed above, but generally will always return invalid outputs except for Go 1.18's nistec backend, which returns random values). I opened a separate issue (#50975) for that, which we will discuss for Go 1.19, as all that is undefined behavior once IsOnCurve behaves correctly.

[FiloSottile]

@gopherbot please open backport issues for this security fix. /cc @golang/security

[gopherbot]

Backport issue(s) opened: #50977 (for 1.16), #50978 (for 1.17).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://golang.org/wiki/MinorReleases.

[gopherbot]

Change https://golang.org/cl/382455 mentions this issue: crypto/elliptic: make IsOnCurve return false for invalid field elements

[gopherbot]

Change https://golang.org/cl/382854 mentions this issue: [release-branch.go1.17] crypto/elliptic: make IsOnCurve return false for invalid field elements

[gopherbot]

Change https://golang.org/cl/382855 mentions this issue: [release-branch.go1.16] crypto/elliptic: make IsOnCurve return false for invalid field elements