crypto/elliptic: P256 ScalarBaseMult with order-34 yields point at infinity

[guidovranken]

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

Latest Go development branch

Does this issue reproduce with the latest release?

No. Tested latest using latest binary releases of Go 1.19 and 1.20; not affected, hence I'm creating a public bug report for this.

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

Linux x64

What did you do?

package main

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

func main() {
	curve := elliptic.P256()
	priv, _ := new(big.Int).SetString("115792089210356248762697446949407573529996955224135760342422259061068512044335", 10)
	x, y := curve.ScalarBaseMult(priv.Bytes())
	fmt.Println(x, ",", y)
}

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

What did you expect to see?

21538630073048560509735576007149539115526969787353231629118474871518563178910 , 60188232952792585766986390787318113745120282298037326219660563054891997721808

What did you see instead?

0, 0

[dr2chase]

@FiloSottile @rolandshoemaker @golang/security

[dr2chase]

Lacking other information, this looks bad. Not sure if it blocks RC1 or not.

[FiloSottile]

Yeah, this looks like a repeat of #58647, which is definitely weird. Will look at it today or tomorrow.

[FiloSottile]

I can reproduce it (annoyingly, by just extending the test added for #58647 beyond [-32, +32]...) and I'll mail a fix hopefully by morning. (Getting on a transatlantic flight right now.)

[FiloSottile]

Ok, it's again incomplete formula, this time in ScalarBaseMult. The issue is that with Booth encoding there's both additions and subtractions, so while the positive entries in the table can never match the partial result (because it always grows), the negatives can.

The final addition of a -34 chain is -17, and if x - 17 = -34, then x = -17, and we're again doing an addition of two equal values, which break the formula used by P-256 assembly.

Now, the question is whether this was actually introduced by https://go.dev/cl/471256, in which case we can revert, or if it just changed things around making it easier to find by chance. I suspect it might be the latter, because CL 471256 changed the order of the addition chain, making the last addition a small value (easy to find by a dedicated fuzzer). But maybe there was some other undocumented load-bearing poster. I'll try to get to an answer today.

P.S. Anyway, in Go 1.22 we're getting rid of the incomplete formula, no matter what.

P.P.S. This would be fun to prove correct / find test cases for with a constraint solver.

[FiloSottile]

Alright, a full investigation is going to take me some time, but there are two options:

1. the refactor in CL 471256 violated some undocumented invariant
2. Go 1.20 and earlier are broken too, but CL 471256 surfaced the bug

In both cases, a revert CL 471256 is the fastest way to unblock Go 1.21. If it's (1) it fixes the issue, and if it's (2) it restores the status quo, letting us fix Go 1.20 and Go 1.21 at the same time with a minor release once we have a full understanding of the issue.

(And/or, in Go 1.22 I just drop these footgun-shaped formula.)

[gopherbot]

Change https://go.dev/cl/502477 mentions this issue: Revert "crypto/internal/nistec: refactor scalar multiplication"

[ssajal-wrl]

Reading the comments above and since #58647 is mentioned in this issue, I am assuming CVE-2023-24532 affects older go releases as well, specifically go1.17.13? (since go1.19.7 is the oldest release with the backport of the fix 203e59a), can someone please confirm?

[FiloSottile]

We don't analyze whether unsupported versions are affected by security issues. However, note that the fix you link to is about a similar but different bug, #58647.