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

[lwithers]

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

[griesemer]

@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]

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]

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]

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