commit b0341041b03ea71d8371a9692aedae263fc06ee9
author Theo Buehler <theorbuehler@gmail.com> Fri Jun 02 11:46:21 2023 +0200
committer Boringssl LUCI CQ <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com> Fri Jun 02 18:16:40 2023 +0000
tree 6a059a2214de31509ca1bbb62537cbf3b6eebcef
parent e106b536ee6233fec2e8876a16686d10607911c5

Make BN_mod_inverse() deal with repeated arguments

BN_nnmod() can deal with the situation that the first and the second
arguments are the same, but it cannot deal with the first and the
second argument being equal. In that situation, if BN_mod(x, y, x, ctx)
results in a negative x, then the result of BN_nnmod() is zero. This
breaks the strange BN_mod_inverse(m, a, m, ctx).

Reported by Guido Vranken in
https://github.com/openssl/openssl/issues/21110

Change-Id: I8584720660f214f172b3b33716a5e3b29e8f2fd8
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/60365
Reviewed-by: Bob Beck <bbe@google.com>
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: David Benjamin <davidben@google.com>

crypto/fipsmodule/bn/bn_test.cc

diff --git a/crypto/fipsmodule/bn/bn_test.cc b/crypto/fipsmodule/bn/bn_test.cc
index e4720b1..92da5f2 100644
--- a/crypto/fipsmodule/bn/bn_test.cc
+++ b/crypto/fipsmodule/bn/bn_test.cc
@@ -909,6 +909,14 @@
       bn_mod_inverse_consttime(ret.get(), &no_inverse, a.get(), m.get(), ctx));
   EXPECT_BIGNUMS_EQUAL("inv(A) (mod M) (constant-time)", mod_inv.get(),
                        ret.get());
+
+  ASSERT_TRUE(BN_copy(ret.get(), m.get()));
+  ASSERT_TRUE(BN_mod_inverse(ret.get(), a.get(), ret.get(), ctx));
+  EXPECT_BIGNUMS_EQUAL("inv(A) (mod M) (ret == m)", mod_inv.get(), ret.get());
+
+  ASSERT_TRUE(BN_copy(ret.get(), a.get()));
+  ASSERT_TRUE(BN_mod_inverse(ret.get(), ret.get(), m.get(), ctx));
+  EXPECT_BIGNUMS_EQUAL("inv(A) (mod M) (ret == a)", mod_inv.get(), ret.get());
 }
 
 static void TestGCD(BIGNUMFileTest *t, BN_CTX *ctx) {

crypto/fipsmodule/bn/gcd.c

diff --git a/crypto/fipsmodule/bn/gcd.c b/crypto/fipsmodule/bn/gcd.c
index e8cc764..df12569 100644
--- a/crypto/fipsmodule/bn/gcd.c
+++ b/crypto/fipsmodule/bn/gcd.c
@@ -263,14 +263,13 @@
   // Now  Y*a  ==  A  (mod |n|).
 
   // Y*a == 1  (mod |n|)
-  if (!Y->neg && BN_ucmp(Y, n) < 0) {
-    if (!BN_copy(R, Y)) {
+  if (Y->neg || BN_ucmp(Y, n) >= 0) {
+    if (!BN_nnmod(Y, Y, n, ctx)) {
       goto err;
     }
-  } else {
-    if (!BN_nnmod(R, Y, n, ctx)) {
-      goto err;
-    }
+  }
+  if (!BN_copy(R, Y)) {
+    goto err;
   }
 
   ret = 1;