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

Follow @Openwall on Twitter for new release announcements and other news

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAO5O-ELaS6a9jPqxZeuEYX3nhT1k2X8hWkz2D6=1G+mBW14BPw@mail.gmail.com>
Date: Wed, 22 Nov 2017 00:30:08 +0100
From: Guido Vranken <guidovranken@...il.com>
To: oss-security@...ts.openwall.com
Subject: Go programming language invalid modular exponentiation result (Exp()
 in math/big pkg)

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

Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.