crypto/elliptic: Cannot add a negative point (Regression)

[rixtox]

What version of Go are you using (go version)?

$ go version
go version go1.19.2 windows/amd64

Does this issue reproduce with the latest release?

Yes. But it was working on go1.18, so I believe it's a regression.

What did you do?

package main

import (
	"crypto/elliptic"
	"crypto/rand"
	"log"
)

func main() {
	curve := elliptic.P256()
	// generate two random points on the curve
	a, _ := rand.Int(rand.Reader, curve.Params().P)
	b, _ := rand.Int(rand.Reader, curve.Params().P)
	x1, y1 := curve.ScalarBaseMult(a.Bytes())
	x2, y2 := curve.ScalarBaseMult(b.Bytes())
	if !curve.IsOnCurve(x1, y1) {
		log.Fatalf("x1: %#v, y1: %#v not on curve", x1, y1)
	}
	if !curve.IsOnCurve(x2, y2) {
		log.Fatalf("x2: %#v, y2: %#v not on curve", x2, y2)
	}

	// invert one point
	y2 = y2.Neg(y2)

	// do addition on the curve
	x3, y3 := curve.Add(x1, y1, x2, y2)
	if !curve.IsOnCurve(x3, y3) {
		log.Fatalf("x3: %#v, y3: %#v not on curve", x3, y3)
	}
}

What did you expect to see?

No error.

What did you see instead?

panic: crypto/elliptic: Add was called on an invalid point

Some further debugging showed that the actual underlying error happened in this check:

// src/crypto/elliptic/nistec.go
func (curve *nistCurve[Point]) pointFromAffine(x, y *big.Int) (p Point, err error) {
	// ...

	// Reject values that would not get correctly encoded.
	if x.Sign() < 0 || y.Sign() < 0 {
		return p, errors.New("negative coordinate") // <<<<  errored here
	}

	// ...
}

Point inversion is a very common operation in many elliptic-curve cryptographic algorithms. Golang should support it.

[seankhliao]

cc @golang/security

[rixtox]

This is actually related to #51815

The workaround here is to perform a point normalization after the inversion:

package main

import (
	"crypto/elliptic"
	"crypto/rand"
	"log"
)

func main() {
	curve := elliptic.P256()
	// generate two random points on the curve
	a, _ := rand.Int(rand.Reader, curve.Params().P)
	b, _ := rand.Int(rand.Reader, curve.Params().P)
	x1, y1 := curve.ScalarBaseMult(a.Bytes())
	x2, y2 := curve.ScalarBaseMult(b.Bytes())
	if !curve.IsOnCurve(x1, y1) {
		log.Fatalf("x1: %#v, y1: %#v not on curve", x1, y1)
	}
	if !curve.IsOnCurve(x2, y2) {
		log.Fatalf("x2: %#v, y2: %#v not on curve", x2, y2)
	}

	// invert one point
	y2 = y2.Neg(y2)

	// point normalization
	y2 = y2.Mod(y2, curve.Params().P)

	// do addition on the curve
	x3, y3 := curve.Add(x1, y1, x2, y2)
	if !curve.IsOnCurve(x3, y3) {
		log.Fatalf("x3: %#v, y3: %#v not on curve", x3, y3)
	}
}

I think the Add() method should handle point normalization inside to allow old code to run without error.

[FiloSottile]

Negative integers are not valid field elements, as field elements are integers between 0 and P-1, and a point is represented by two field elements, so that's not a valid point. As you found out, you can get the opposite of a field element by calling Neg and Mod.

The behavior of negative values was an undocumented accident and wasn't actually reliable across curves and architectures. In some cases -x was just interpreted as x and the sign dropped.

The Add function is now deprecated with the addition of the crypto/ecdh package (#52182) exactly because of issues like this. If you're doing something more complex than ECDH or ECDSA, the standard library is not designed for it, but you can use the filippo.io/nistec package which is just an unofficial re-exported version of the crypto/internal/nistec package which is now the backend of crypto/elliptic.