From cd65852feeef2e6e8d8c06bbf037bc4d6372e93d Mon Sep 17 00:00:00 2001 From: =?utf8?q?R=C3=A9my=20Oudompheng?= Date: Thu, 5 Mar 2020 07:59:00 +0100 Subject: [PATCH] [release-branch.go1.14] math/big: correct off-by-one access in divBasic The divBasic function computes the quotient of big nats u/v word by word. It estimates each word qhat by performing a long division (top 2 words of u divided by top word of v), looks at the next word to correct the estimate, then perform a full multiplication (qhat*v) to catch any inaccuracy in the estimate. In the latter case, "negative" values appear temporarily and carries must be carefully managed, and the recursive division refactoring introduced a case where qhat*v has the same length as v, triggering an out-of-bounds write in the case it happens when computing the top word of the quotient. Fixes #37501 Change-Id: I15089da4a4027beda43af497bf6de261eb792f94 Reviewed-on: https://go-review.googlesource.com/c/go/+/221980 Reviewed-by: Robert Griesemer (cherry picked from commit ac1fd419b6d2af8b0e69b13fa5c794705095db0a) Reviewed-on: https://go-review.googlesource.com/c/go/+/227877 Run-TryBot: Emmanuel Odeke TryBot-Result: Gobot Gobot --- src/math/big/nat.go | 15 +++++++++++++-- src/math/big/nat_test.go | 18 ++++++++++++++++++ 2 files changed, 31 insertions(+), 2 deletions(-) diff --git a/src/math/big/nat.go b/src/math/big/nat.go index 1b771ca7c6..c31ec5156b 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -740,7 +740,8 @@ func (z nat) divLarge(u, uIn, vIn nat) (q, r nat) { // The remainder overwrites input u. // // Precondition: -// - len(q) >= len(u)-len(v) +// - q is large enough to hold the quotient u / v +// which has a maximum length of len(u)-len(v)+1. func (q nat) divBasic(u, v nat) { n := len(v) m := len(u) - n @@ -779,6 +780,8 @@ func (q nat) divBasic(u, v nat) { } // D4. + // Compute the remainder u - (q̂*v) << (_W*j). + // The subtraction may overflow if q̂ estimate was off by one. qhatv[n] = mulAddVWW(qhatv[0:n], v, qhat, 0) qhl := len(qhatv) if j+qhl > len(u) && qhatv[n] == 0 { @@ -787,7 +790,11 @@ func (q nat) divBasic(u, v nat) { c := subVV(u[j:j+qhl], u[j:], qhatv) if c != 0 { c := addVV(u[j:j+n], u[j:], v) - u[j+n] += c + // If n == qhl, the carry from subVV and the carry from addVV + // cancel out and don't affect u[j+n]. + if n < qhl { + u[j+n] += c + } qhat-- } @@ -827,6 +834,10 @@ func (z nat) divRecursive(u, v nat) { putNat(tmp) } +// divRecursiveStep computes the division of u by v. +// - z must be large enough to hold the quotient +// - the quotient will overwrite z +// - the remainder will overwrite u func (z nat) divRecursiveStep(u, v nat, depth int, tmp *nat, temps []*nat) { u = u.norm() v = v.norm() diff --git a/src/math/big/nat_test.go b/src/math/big/nat_test.go index 32f29e3876..89e913fc16 100644 --- a/src/math/big/nat_test.go +++ b/src/math/big/nat_test.go @@ -786,3 +786,21 @@ func TestNatDiv(t *testing.T) { } } } + +// TestIssue37499 triggers the edge case of divBasic where +// the inaccurate estimate of the first word's quotient +// happens at the very beginning of the loop. +func TestIssue37499(t *testing.T) { + // Choose u and v such that v is slightly larger than u >> N. + // This tricks divBasic into choosing 1 as the first word + // of the quotient. This works in both 32-bit and 64-bit settings. + u := natFromString("0x2b6c385a05be027f5c22005b63c42a1165b79ff510e1706b39f8489c1d28e57bb5ba4ef9fd9387a3e344402c0a453381") + v := natFromString("0x2b6c385a05be027f5c22005b63c42a1165b79ff510e1706c") + + q := nat(nil).make(8) + q.divBasic(u, v) + q = q.norm() + if s := string(q.utoa(16)); s != "fffffffffffffffffffffffffffffffffffffffffffffffb" { + t.Fatalf("incorrect quotient: %s", s) + } +} -- 2.48.1