Fix variable reuse in BN_mod_inverse()

The somewhat strange calculation m = a^{-1} (mod m) can return 0. This
breaks because of BN_nnmod() having delicate semantics of which variable
can be reused. BN_nnmod(a, a, m, ctx) works and the library relies on that.

Here, the code ends up doing BN_nnmod(m, a, m, ctx) and this doesn't work.
If the result of the initial BN_mod() is negative, then BN_nnmod() will
return 0.

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

This code is well covered by regress, but it does not currently have
explicit test coverage. Such will be added soon.

ok beck jsing

1 files changed, 15 insertions, 21 deletions

diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c
index c44b933260..6b3d8a3cb9 100644
--- a/src/lib/libcrypto/bn/bn_gcd.c
+++ b/src/lib/libcrypto/bn/bn_gcd.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_gcd.c,v 1.27 2023/04/09 18:38:59 tb Exp $ */
+/* $OpenBSD: bn_gcd.c,v 1.28 2023/06/02 17:15:30 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -497,19 +497,16 @@ BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,
         }
         /* Now  Y*a  ==  A  (mod |n|).  */
 
-        if (BN_is_one(A)) {
-                /* Y*a == 1  (mod |n|) */
-                if (!Y->neg && BN_ucmp(Y, n) < 0) {
-                        if (!bn_copy(R, Y))
-                                goto err;
-                } else {
-                        if (!BN_nnmod(R, Y, n, ctx))
-                                goto err;
-                }
-        } else {
+        if (!BN_is_one(A)) {
                 BNerror(BN_R_NO_INVERSE);
                 goto err;
         }
+
+        if (!BN_nnmod(Y, Y, n, ctx))
+                goto err;
+        if (!bn_copy(R, Y))
+                goto err;
+
         ret = R;
 
  err:
@@ -785,19 +782,16 @@ BN_mod_inverse_internal(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ct
         }
         /* Now  Y*a  ==  A  (mod |n|).  */
 
-        if (BN_is_one(A)) {
-                /* Y*a == 1  (mod |n|) */
-                if (!Y->neg && BN_ucmp(Y, n) < 0) {
-                        if (!bn_copy(R, Y))
-                                goto err;
-                } else {
-                        if (!BN_nnmod(R, Y,n, ctx))
-                                goto err;
-                }
-        } else {
+        if (!BN_is_one(A)) {
                 BNerror(BN_R_NO_INVERSE);
                 goto err;
         }
+
+        if (!BN_nnmod(Y, Y, n, ctx))
+                goto err;
+        if (!bn_copy(R, Y))
+                goto err;
+
         ret = R;
 
  err: