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: panic when signing with unusual RSA key sizes #13973

Closed
lwithers opened this issue Jan 15, 2016 · 4 comments
Closed

math/big: panic when signing with unusual RSA key sizes #13973

lwithers opened this issue Jan 15, 2016 · 4 comments
Milestone

Comments

@lwithers
Copy link

Go version 1.5.3, reproduced both with official go1.5.3.linux-amd64.tar.gz package and toolchain built from source also on Linux/AMD64.

When I use an RSA key with an unusual size, say 1028 or 1032 bits, I often encounter a panic in math/big: math/big: mismatched montgomery number lengths. The frequency of the occurrence seems to depend on the keysize but many such panics can be observed in 100 runs.

This does not occur with more common key sizes, say powers of two or small integer multiples of 256. I have attached a small program that can be used to observe and reproduce the issue.
mont.zip

@ianlancetaylor ianlancetaylor changed the title panic in math/big when signing with unusual RSA key sizes math/big: panic when signing with unusual RSA key sizes Jan 15, 2016
@ianlancetaylor ianlancetaylor added this to the Go1.7 milestone Jan 15, 2016
@griesemer
Copy link
Contributor

@rsc is this a new issue that was not backported to 1.5.3? At least for go on tip I can not reproduce a crash with the attached program.

@davecgh
Copy link

davecgh commented Feb 4, 2016

Here is some code that triggers this panic Go 1.5.3 every time, but not on current tip or Go 1.5.2:

package main

import (
    "fmt"
    "math/big"
)

func main() {
    x, _ := new(big.Int).SetString("fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd00000000000000000000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000000000000000000006", 16)
    y, _ := new(big.Int).SetString("3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c", 16)
    m, _ := new(big.Int).SetString("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f", 16)
    r := new(big.Int).Exp(x, y, m)
    fmt.Printf("%x\n", r)
}

Go 1.5.3:

$ go run mont.go
panic: math/big: mismatched montgomery number lengths

goroutine 1 [running]:
math/big.nat.montgomery(0x0, 0x0, 0x0, 0xc08205a000, 0x2, 0x11, 0xc08200a230, 0x4, 0xe, 0xc082058030, ...)
        D:/go/src/math/big/nat.go:234 +0x42b
math/big.nat.expNNMontgomery(0xc082056080, 0xc, 0x10, 0xc08205a000, 0x2, 0x11, 0xc082058000, 0x4, 0x5, 0xc082058030, ...)
        D:/go/src/math/big/nat.go:1126 +0x686
math/big.nat.expNN(0xc082056080, 0xc, 0x10, 0xc082056000, 0xc, 0xf, 0xc082058000, 0x4, 0x5, 0xc082058030, ...)
        D:/go/src/math/big/nat.go:952 +0x58b
math/big.(*Int).Exp(0xc082004880, 0xc08202ff18, 0xc08202fef8, 0xc08202fed8, 0xc08202fed8)
        D:/go/src/math/big/int.go:420 +0x128
main.main()
        D:/Projects/mygo/src/github.com/btcsuite/btcd/misctests/mont/mont.go:12 +0x170
exit status 2

Go 1.5.2:

$ go run mont.go
cffa06ff4034fff9758fae127c07ddb78317fc054f8997f3ae6080ac33494239

Go tip (1f7e3cf):

$ go run mont.go
cffa06ff4034fff9758fae127c07ddb78317fc054f8997f3ae6080ac33494239

@dajohi
Copy link

dajohi commented Feb 4, 2016

If i edit the panic message:

 panic: math/big: mismatched montgomery number lengths: len(x):2 len(y):4 len(m):4 n:4

len(x) != n

@griesemer
Copy link
Contributor

This is fixed in 1.6 and at tip; it appears to occur in 1.5.3 and 1.5.4. See below for a diff for a local fix if desired. The diff is basically the backport of changes to the Montgomery code. Closing.

diff --git a/src/math/big/nat.go b/src/math/big/nat.go
index 6c242c8..d716ace 100644
--- a/src/math/big/nat.go
+++ b/src/math/big/nat.go
@@ -233,25 +233,25 @@ func (z nat) montgomery(x, y, m nat, k Word, n int) nat {
        if len(x) != n || len(y) != n || len(m) != n {
                panic("math/big: mismatched montgomery number lengths")
        }
-       var c1, c2, c3 Word
        z = z.make(n)
        z.clear()
+       var c Word
        for i := 0; i < n; i++ {
                d := y[i]
-               c2 = addMulVVW(z, x, d)
+               c2 := addMulVVW(z, x, d)
                t := z[0] * k
-               c3 = addMulVVW(z, m, t)
+               c3 := addMulVVW(z, m, t)
                copy(z, z[1:])
-               cx := c1 + c2
+               cx := c + c2
                cy := cx + c3
                z[n-1] = cy
                if cx < c2 || cy < c3 {
-                       c1 = 1
+                       c = 1
                } else {
-                       c1 = 0
+                       c = 0
                }
        }
-       if c1 != 0 {
+       if c != 0 {
                subVV(z, z, m)
        }
        return z
@@ -1076,26 +1076,22 @@ func (z nat) expNNWindowed(x, y, m nat) nat {
 // expNNMontgomery calculates x**y mod m using a fixed, 4-bit window.
 // Uses Montgomery representation.
 func (z nat) expNNMontgomery(x, y, m nat) nat {
-       var zz, one, rr, RR nat
-
        numWords := len(m)

        // We want the lengths of x and m to be equal.
+       // It is OK if x >= m as long as len(x) == len(m).
        if len(x) > numWords {
-               _, rr = rr.div(rr, x, m)
-       } else if len(x) < numWords {
-               rr = rr.make(numWords)
-               rr.clear()
-               for i := range x {
-                       rr[i] = x[i]
-               }
-       } else {
-               rr = x
+               _, x = nat(nil).div(nil, x, m)
+               // Note: now len(x) <= numWords, not guaranteed ==.
+       }
+       if len(x) < numWords {
+               rr := make(nat, numWords)
+               copy(rr, x)
+               x = rr
        }
-       x = rr

        // Ideally the precomputations would be performed outside, and reused
-       // k0 = -mˆ-1 mod 2ˆ_W. Algorithm from: Dumas, J.G. "On Newton–Raphson
+       // k0 = -m**-1 mod 2**_W. Algorithm from: Dumas, J.G. "On Newton–Raphson
        // Iteration for Multiplicative Inverses Modulo Prime Powers".
        k0 := 2 - m[0]
        t := m[0] - 1
@@ -1105,9 +1101,9 @@ func (z nat) expNNMontgomery(x, y, m nat) nat {
        }
        k0 = -k0

-       // RR = 2ˆ(2*_W*len(m)) mod m
-       RR = RR.setWord(1)
-       zz = zz.shl(RR, uint(2*numWords*_W))
+       // 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)
        if len(RR) < numWords {
                zz = zz.make(numWords)
@@ -1115,8 +1111,7 @@ func (z nat) expNNMontgomery(x, y, m nat) nat {
                RR = zz
        }
        // one = 1, with equal length to that of m
-       one = one.make(numWords)
-       one.clear()
+       one := make(nat, numWords)
        one[0] = 1

        const n = 4

@golang golang locked and limited conversation to collaborators Apr 20, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

6 participants