Go programming language invalid modular exponentiation result (Exp() in math/big pkg)Nmap Announce Nmap Dev Full Disclosure Security Lists Internet Issues Open Source Dev

oss-sec mailing list archives

Go programming language invalid modular exponentiation result (Exp() in math/big pkg)

From: Guido Vranken <guidovranken () gmail com>
Date: Wed, 22 Nov 2017 00:30:08 +0100

Dear list,

I've written a bignum fuzzer that compares the results of mathematical
operations (addtion, subtraction, multiplication, ...) across multiple
bignum libraries. Among these is the Go programming language,
specifically the "math/big" package [1]. Recently, the fuzzer found a
problem in its exponentiation operation [2]. This was reported to the
Go security address, and according to developer Russ Cox there are no
security implications. While I take his word for it as far as internal
Go libraries go, this is no guarantee that all external
(cryptographic) libraries or programs that use the math/big package
are unaffected.

The bug manifests under specific circumstances. To quote Russ Cox:
"[...] it only affects the case e = 1 with m != nil and a
pre-allocated non-zero receiver."

My co-worker Péter Szilágyi has created a public Github issue [3] with
a proof-of-concept, reproduced below for posterity.

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

I am reporting it to this list because bignums are an important (and
ideally infallible) foundation for cryptographic software, and so that
affected programs, if any, are more likely to learn about this issue.

[1] https://golang.org/pkg/math/big/
[2] https://golang.org/pkg/math/big/#Int.Exp
[3] https://github.com/golang/go/issues/22830

Current thread: