crypto/elliptic: IsOnCurve returns false

[tscholl2]

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

$ go version
1.18beta2

Does this issue reproduce with the latest release?

No

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
I'm not sure, whatever the playground uses

What did you do?

https://go.dev/play/p/xqk_POfNLOS?v=gotip

package main

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

func main() {
	C := elliptic.P521()
	x, _ := new(big.Int).SetString("2737143173246958931206810462877117168076362833635660944391153871821844541609039224874181160979387481718586024475545267128963897341959205744927077947677747267", 10)
	y, _ := new(big.Int).SetString("-4462147686175933957488329012758410305312221082622057784173820750323982928915257404955462165095926112019622265253432971920064280282117429671186357325281355718", 10)
	fmt.Println(C.IsOnCurve(x, y))
	y.Mod(y, C.Params().P)
	fmt.Println(C.IsOnCurve(x, y))
}

What did you expect to see?

true
true

This is what I select "GO release".

What did you see instead?

false
true

This is likely the cause of this real world issue: schollz/pake#7

Edit: fixed the output, I had copied it wrong.

[magical]

Related: #50974. Likely not directly caused by the fix for that issue (since it was resolved after beta2), but it sounds like this is the intended behavior going forward.

[seankhliao]

cc @golang/security

[FiloSottile]

-4462147686175933957488329012758410305312221082622057784173820750323982928915257404955462165095926112019622265253432971920064280282117429671186357325281355718 is not a valid P-521 field element, as field elements are integers in the range [0, P). IsOnCurve returning false is the correct behavior, and is being backported to all curves with #50974. The behavior of different curves when operating on negative integers can be incorrect (see #50974), so you might be affected by it as a security vulnerability.

[FiloSottile]

@tscholl2 I am curious though, how did this point get generated, and how is it used? P-256 on amd64/arm64 and P-224 on Go 1.17 will drop the sign when operating on it, so I'm surprised it worked.

[tscholl2]

@tscholl2 I am curious though, how did this point get generated, and how is it used? P-256 on amd64/arm64 and P-224 on Go 1.17 will drop the sign when operating on it, so I'm surprised it worked.

That explains more! It came up debugging a failed test. I think P-256 was passing, so that lines up with what you said. The library used a negative number when computing the negative of a point in Weierstrass form: https://github.com/schollz/pake/blob/master/pake.go#L196
Seems like instead of using -y was a little too wishful, it should have used something like y == 0 ? y : p-y.

[FiloSottile]

That explains more! It came up debugging a failed test. I think P-256 was passing, so that lines up with what you said.

The reason P-256 was passing and P-521 was failing with Go 1.18 is that P-521 (and P-384 and P-224) started returning random points when asked to operate on invalid points in Go 1.18, like at the line you linked. (We decided to make it an explicit panic in Go 1.19 to avoid painful debugging sessions like the one we caused you, sorry, but it was too late for Go 1.18.) P-256 instead accepts it but ignores the sign so you were not actually operating on (x, -y) as you'd expect but on (x, y). What I am curious about is how that worked in the first place.

[tscholl2]

points in Go 1.18, like at the line you linked. (We decided to make it an explicit panic in Go 1.19 to avoid painful debugging sessions like the one we caused you, sorry, but it was too late for Go 1.18.) P-256 instead accepts it but ignores the sign so you were not actually operating on (x, -y) as you'd expect but on (x, y). What I am curious about is how that worked in the first place.

I only had to find where the API failed, you did a lot more work! That's a good question about how it was working. I am certain it was passing tests before, which I believe would be highly unlikely if any curve operations were incorrect. I'll have to try and dig up some of the tests on an old version of go (is that possible? did the patch get backported to older versions of go?).

Edit: I just realized the way the library works, it may be possible that if the curve arithmetic failed consistently, it may also have passed.

EditEdit: If P256 was dropping the sign, shouldn't this fail? https://go.dev/play/p/UGFPYcqc5q9

[FiloSottile]

Ah, I just realized why it's not dropping the sign: ScalarMult on amd64/arm64 will drop the sign, but Add falls back to the generic (slow, variable-time, big.Int based) implementation which will reduce the value modulo P.

So yeah, it looks like that code got lucky that it only used operations that reduce the input. Still, it's undefined behavior, and it will break intentionally in Go 1.18 and Go 1.19.

[tscholl2]

Ah, I just realized why it's not dropping the sign: ScalarMult on amd64/arm64 will drop the sign, but Add falls back to the generic (slow, variable-time, big.Int based) implementation which will reduce the value modulo P.

So yeah, it looks like that code got lucky that it only used operations that reduce the input. Still, it's undefined behavior, and it will break intentionally in Go 1.18 and Go 1.19.

Ha! Lucky indeed. The library I referenced is already aware and either has patched or is about to. Thanks for figuring all that out and letting everyone know!