crypto/elliptic: invalid handling for infinity point

[catenacyber]

What did you do?

I have been doing differential fuzzing on elliptic curve cryptography.
I am adding golang crypto/elliptic to my fuzzer : https://github.com/catenacyber/elliptic-curve-differential-fuzzer
And I found one inconsistency.
The infinity point is not encoded with a single 0 byte as it could be. But I did not find a standard for this encoding used by other libraries.

Worse : the infinity point is not considered to be on the curve... Any scalar multiplication of a point on the curve must be on the curve.

Reproducer code is here :
https://play.golang.org/p/kvjqBssEGTv

package main

import (
	"crypto/elliptic"
	"fmt"
	"math/big"
)

func main() {
	curve := elliptic.P224()
	coordx := []byte{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf6, 0xfe, 0xff, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x52, 0xfa}
	coordy := []byte{0x45, 0x6d, 0xcc, 0xc3, 0x3f, 0x1d, 0x63, 0x41, 0x6, 0xfd, 0xa9, 0x12, 0x44, 0xbf, 0x70, 0x4f, 0x3d, 0xab, 0x96, 0x50, 0x61, 0x6d, 0xa, 0xc3, 0xb, 0xc0, 0x56, 0x50}
	scalar := []byte{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x16, 0xa2, 0xe0, 0xb8, 0xf0, 0x3e, 0x13, 0xdd, 0x29, 0x45, 0x5c, 0x5c, 0x2a, 0x3d}

	px := new(big.Int)
	px.SetBytes(coordx)
	py := new(big.Int)
	py.SetBytes(coordy)

	rx, ry := curve.ScalarMult(px, py, scalar)
	res := elliptic.Marshal(curve, rx, ry)
	/* Quick fix
	if rx.BitLen() == 0 && ry.BitLen() == 0 {
		res[0] = 0
		res = res[:1]
	*/
	fmt.Printf("infinity %#+v\n", res)
	fmt.Printf("infinity on curve %#+v %#+v\n", curve.IsOnCurve(px, py), curve.IsOnCurve(rx, ry))
}

What did you expect to see?

The reproducer code should output

infinity []byte{0x0}
infinity on curve true true

What did you see instead?

infinity []byte{0x4, 0x0, 0x0, 0x0, 0x0, 0x0...
infinity on curve true false

Does this issue reproduce with the latest release (go1.13.8)?

Yes with go version go1.13.8 linux/amd64

System details

go version go1.12.9 darwin/amd64
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/catena/Library/Caches/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOOS="darwin"
GOPATH="/Users/catena/go"
GOPROXY=""
GORACE=""
GOROOT="/usr/local/go"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GCCGO="gccgo"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD=""
GOROOT/bin/go version: go version go1.12.9 darwin/amd64
GOROOT/bin/go tool compile -V: compile version go1.12.9
uname -v: Darwin Kernel Version 17.7.0: Thu Jan 23 07:05:23 PST 2020; root:xnu-4570.71.69~1/RELEASE_X86_64
ProductName:	Mac OS X
ProductVersion:	10.13.6
BuildVersion:	17G11023
lldb --version: lldb-1000.11.38.2
  Swift-4.2
gdb --version: GNU gdb (GDB) 8.1.1

[josharian]

cc @FiloSottile

[catenacyber]

By the way, should I have considered this a security bug and followed the guidelines from https://golang.org/security ?
(same question for #37499)

[FiloSottile]

Thank you for raising this. I spent some time thinking about this while implementing MarshalCompressed and UnmarshalCompressed, and I came to the conclusion that the API is almost consistent as is, in that it does not have a valid representation of the zero value.

In abelian coordinates (x, y) there is no valid representation of the infinity point. (0, 0) is not a valid point on the curve, it's just adopted by convention in many APIs. An API can just as well decide not to represent it at all, if it's not required for its use cases.

If we accept that (0, 0) is not a valid point in our API, Unmarshal correctly will never generate such an invalid representation, IsOnCurve correctly returns false, and Marshal is not expected to support it.

The unfortunate part is that the arithmetic functions can return an invalid representation if fed specific inputs. That's definitely bad. It would be dangerous to change the API to support (0, 0) now, because there might be applications that rely on IsOnCurve returning false, so that's not an option. I think the only two things we can do are making them return nil, trading a potential key fixing vulnerability for a potential DoS, or document it and recommend applications run IsOnCurve on the outputs.

Not a fan of either. @agl any opinions?

(@catenacyber it's always ok to be conservative and email security@, I think this one is ok to discuss publicly.)

[catenacyber]

Ok, I will be conservative next time (I had not noticed this security email the first time)

So, I understand the problem about backward compatibility.
Documentation is a good way to go then.
You can also add new APIs using not big.Int but a new structure elliptic.Point which could handle the infinity point better (that is what most APIs I have seen do)

[gopherbot]

Change https://golang.org/cl/239562 mentions this issue: crypto/elliptic: document and test that IsOnCurve(∞) == false