57
oss-sec: Go programming language invalid modular exponentiation result (Exp() in...
source link: http://seclists.org/oss-sec/2017/q4/307
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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:
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK