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

Jump to bottom

crypto/elliptic: invalid handling for infinity point #37294

Closed
catenacyber opened this issue Feb 19, 2020 · 5 comments
Closed

crypto/elliptic: invalid handling for infinity point #37294

catenacyber opened this issue Feb 19, 2020 · 5 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone
Go1.15

Comments

@catenacyber
Copy link
Contributor

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

cc @FiloSottile

@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 the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Feb 19, 2020
@FiloSottile FiloSottile added this to the Go1.15 milestone Feb 19, 2020
@catenacyber
Copy link
Contributor Author

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
Contributor

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
Contributor Author

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)

@FiloSottile FiloSottile self-assigned this Jun 23, 2020
@gopherbot
Copy link

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

@golang golang locked and limited conversation to collaborators Jun 24, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Milestone
Go1.15
Development

No branches or pull requests
4 participants
@josharian @FiloSottile @gopherbot @catenacyber