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

crypto/elliptic: invalid handling for infinity point #37294

Open
catenacyber opened this issue Feb 19, 2020 · 4 comments
Open

crypto/elliptic: invalid handling for infinity point #37294

catenacyber opened this issue Feb 19, 2020 · 4 comments
Milestone

Comments

@catenacyber
Copy link

@catenacyber catenacyber commented Feb 19, 2020

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
Copy link
Contributor

@josharian josharian commented Feb 19, 2020

@FiloSottile FiloSottile changed the title Invalid handling for infinity point on elliptic curves crypto/elliptic: invalid handling for infinity point Feb 19, 2020
@FiloSottile FiloSottile added this to the Go1.15 milestone Feb 19, 2020
@catenacyber
Copy link
Author

@catenacyber catenacyber commented May 10, 2020

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
Copy link
Member

@FiloSottile FiloSottile commented May 11, 2020

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
Copy link
Author

@catenacyber catenacyber commented May 12, 2020

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)

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
3 participants
You can’t perform that action at this time.