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.

Sign up for GitHub

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: P256 ScalarBaseMult with order-34 yields point at infinity #60717

Open
guidovranken opened this issue Jun 10, 2023 · 9 comments
Open

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

guidovranken opened this issue Jun 10, 2023 · 9 comments
Assignees
@FiloSottile
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone
Go1.23

Comments

@guidovranken
Copy link

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

@FiloSottile @rolandshoemaker @golang/security

@dr2chase
Copy link
Contributor

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

@dr2chase dr2chase added this to the Go1.21 milestone Jun 10, 2023
@FiloSottile
Copy link
Contributor

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

@dmitshur dmitshur added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jun 10, 2023
@FiloSottile FiloSottile self-assigned this Jun 12, 2023
@FiloSottile
Copy link
Contributor

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

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

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

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

gopherbot pushed a commit that referenced this issue Jun 12, 2023
@FiloSottile @gopherbot
Revert "crypto/internal/nistec: refactor scalar multiplication"
a674c63 
This reverts CL 471256, except for its new tests, which are expanded to
cover the case in #60717.

Updates #60717

Change-Id: I712bbcd05bf3ea4a2c9aecc9e0f02841b21aadfa
Reviewed-on: https://go-review.googlesource.com/c/go/+/502477
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
Run-TryBot: Filippo Valsorda <filippo@golang.org>
Auto-Submit: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Roland Shoemaker <roland@golang.org>
@ssajal-wrl
Copy link

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

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.

@gopherbot gopherbot modified the milestones: Go1.21, Go1.22 Aug 8, 2023
@gopherbot gopherbot modified the milestones: Go1.22, Go1.23 Feb 6, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@FiloSottile FiloSottile

Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Milestone
Go1.23
Development

No branches or pull requests
7 participants
@FiloSottile @prattmic @dmitshur @dr2chase @guidovranken @gopherbot @ssajal-wrl