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

math/big: r.Exp(x, 1, m) wrong if r is initially non-zero #22830

Closed
karalabe opened this issue Nov 21, 2017 · 8 comments

Comments

@karalabe
Copy link
Contributor

commented Nov 21, 2017

For an exponent of 1, big.Int.Exp returns the correct value only for a 0 recipient, and an off-by-one result for all pre-allocated recipients.

package main

import (
	"fmt"
	"math/big"
)

func main() {
	base := new(big.Int)
	base.SetString("84555555300000000000", 10)

	mod := new(big.Int)
	mod.SetString("66666670001111111111", 10)

	fmt.Printf("%v\n", big.NewInt(0).Exp(base, big.NewInt(1), mod))
	fmt.Printf("%v\n", big.NewInt(1).Exp(base, big.NewInt(1), mod))
}

The result in both cases above should be the same, however, they are 17888885298888888889
vs. 17888885298888888888. Playground: https://play.golang.org/p/uSBvGkeGkN

Issue originally found by @guidovranken, no security implication according to @rsc.

@ALTree

This comment has been minimized.

Copy link
Member

commented Nov 21, 2017

This is caused by an aliasing issue in (z nat) divLarge(u, uIn, v nat). More specifically, divLarge does not protect itself against z and u aliasing each other.

This line:

q = z.make(m + 1)

will cause q and z to share the same backing array when m+1 <= cap(z).

Later, we do compute the quotient in pieces and set for several times q[j] = qhat, but this will modify u, because q and z share the same backing array and z aliases u, so modifying q will mess up u (this is not okay because at that point we are already storing computation state into u).

This does not happen when z is zero because in that case z.make(m+1) won't reuse z's backing array (because there isn't one).

I think we can fix this by checking for z and u aliasing in divLarge and acting accordingly.

@ALTree ALTree added the NeedsFix label Nov 21, 2017

@ALTree ALTree added this to the Go1.10 milestone Nov 21, 2017

@gopherbot

This comment has been minimized.

Copy link

commented Nov 21, 2017

Change https://golang.org/cl/78995 mentions this issue: math/big: protect aganist aliasing in nat.divLarge

@rsc rsc changed the title math/big: wrong exponentiation on power of 1 and non-zero receiver math/big: r.Exp(x, 1, m) wrong if r is initially non-zero Nov 22, 2017

@rsc

This comment has been minimized.

Copy link
Contributor

commented Nov 22, 2017

To expand on the “no security implication” note:

Thanks to @karalabe for reporting this to us first at security@golang.org. We investigated and found that this only affects (1) calls that reuse a pre-allocated receiver, and (2) the specific case Exp(x, 1, m), that is, x^1 mod m.

Most crypto code uses new(big.Int).Exp(x, y, m) instead of reusing receivers. Most crypto code is also written so that a modular exponentiation with an exponent of 1 is either completely impossible or exceedingly unlikely. We examined all the uses in the standard library and believe they are unaffected, for either the first or the second reason.

In x/crypto, openpgp and ssh are clearly fine (they only use new(big.Int).Exp).

x/crypto/bn256 and x/crypto/otr may need closer examination.

@karalabe

This comment has been minimized.

Copy link
Contributor Author

commented Nov 22, 2017

@rsc We've investigated x/crypto/bn256 even before opening the bug report and couldn't find anything obviously wrong with it (that's not to say there isn't, but Exp isn't a common operation there).

@p-kraszewski

This comment has been minimized.

Copy link

commented Nov 23, 2017

The big question is: do applications using crypto.tls or crypto.x509 - and facing the Internet - need recompilation upon patching of math/big?

@gopherbot

This comment has been minimized.

Copy link

commented Nov 30, 2017

Change https://golang.org/cl/81055 mentions this issue: math/big: clean up z.div(z, x, y) calls

@gopherbot gopherbot closed this in ff534e2 Nov 30, 2017

jeffallen added a commit to dedis/kyber that referenced this issue Dec 1, 2017
Work around incorrect Exp
The consequences of golang/go#22830 could be serious, so out of an abundance
of caution fix these up.
ineiti added a commit to dedis/kyber that referenced this issue Dec 4, 2017
Work around incorrect Exp (#255)
The consequences of golang/go#22830 could be serious, so out of an abundance
of caution fix these up.
@gopherbot

This comment has been minimized.

Copy link

commented Jan 18, 2018

Change https://golang.org/cl/88322 mentions this issue: [release-branch.go1.9] math/big: protect against aliasing in nat.divLarge

gopherbot pushed a commit that referenced this issue Jan 22, 2018
[release-branch.go1.9] math/big: protect against aliasing in nat.divL…
…arge

In nat.divLarge (having signature (z nat).divLarge(u, uIn, v nat)),
we check whether z aliases uIn or v, but aliasing is currently not
checked for the u parameter.

Unfortunately, z and u aliasing each other can in some cases cause
errors in the computation.

The q return parameter (which will hold the result's quotient), is
unconditionally initialized as

    q = z.make(m + 1)

When cap(z) ≥ m+1, z.make() will reuse z's backing array, causing q
and z to share the same backing array. If then z aliases u, setting q
during the quotient computation will then corrupt u, which at that
point already holds computation state.

To fix this, we add an alias(z, u) check at the beginning of the
function, taking care of aliasing the same way we already do for uIn
and v.

Fixes #22830

Change-Id: I3ab81120d5af6db7772a062bb1dfc011de91f7ad
Reviewed-on: https://go-review.googlesource.com/78995
Run-TryBot: Alberto Donizetti <alb.donizetti@gmail.com>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Reviewed-on: https://go-review.googlesource.com/88322
Run-TryBot: Andrew Bonventre <andybons@golang.org>
@gopherbot

This comment has been minimized.

Copy link

commented Jan 23, 2018

Change https://golang.org/cl/89156 mentions this issue: [release-branch.go1.8] math/big: protect against aliasing in nat.divLarge

gopherbot pushed a commit that referenced this issue Jan 23, 2018
[release-branch.go1.8] math/big: protect against aliasing in nat.divL…
…arge

In nat.divLarge (having signature (z nat).divLarge(u, uIn, v nat)),
we check whether z aliases uIn or v, but aliasing is currently not
checked for the u parameter.

Unfortunately, z and u aliasing each other can in some cases cause
errors in the computation.

The q return parameter (which will hold the result's quotient), is
unconditionally initialized as

    q = z.make(m + 1)

When cap(z) ≥ m+1, z.make() will reuse z's backing array, causing q
and z to share the same backing array. If then z aliases u, setting q
during the quotient computation will then corrupt u, which at that
point already holds computation state.

To fix this, we add an alias(z, u) check at the beginning of the
function, taking care of aliasing the same way we already do for uIn
and v.

Fixes #22830

Change-Id: I3ab81120d5af6db7772a062bb1dfc011de91f7ad
Reviewed-on: https://go-review.googlesource.com/78995
Run-TryBot: Alberto Donizetti <alb.donizetti@gmail.com>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Reviewed-on: https://go-review.googlesource.com/89156
Run-TryBot: Andrew Bonventre <andybons@golang.org>
Reviewed-by: Andrew Bonventre <andybons@golang.org>
gopherbot pushed a commit that referenced this issue Apr 5, 2018
math/big: clean up z.div(z, x, y) calls
Updates #22830

Due to not checking if the output slices alias in divLarge,
calls of the form z.div(z, x, y) caused the slice z
to attempt to be used to store both the quotient and the
remainder of the division.  CL 78995 applies an alias
check to correct that error.  This CL cleans up the
additional div calls that attempt to supply the same slice
to hold both the quotient and remainder.

Note that the call in expNN was responsible for the reported
error in r.Exp(x, 1, m) when r was initialized to a non-zero value.

The second instance in expNNMontgomery did not result in an error
due to the size of the arguments.

	// RR = 2**(2*_W*len(m)) mod m
	RR := nat(nil).setWord(1)
	zz := nat(nil).shl(RR, uint(2*numWords*_W))
	_, RR = RR.div(RR, zz, m)

Specifically,

cap(RR) == 5 after setWord(1) due to const e = 4 in z.make(1)
len(zz) == 2*len(m) + 1 after shifting left, numWords = len(m)

Reusing the backing array for z and z2 in div was only triggered if
cap(RR) >= len(zz) + 1 and len(m) > 1 so that divLarge was called.

But, 5 < 2*len(m) + 2 if len(m) > 1, so new arrays were allocated
and the error was never triggered in this case.

Change-Id: Iedac80dbbde13216c94659e84d28f6f4be3aaf24
Reviewed-on: https://go-review.googlesource.com/81055
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

@golang golang locked and limited conversation to collaborators Jan 23, 2019

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
5 participants
You can’t perform that action at this time.