From 3afd537a3c2319f68280804004e9bf2e798a43f7 Mon Sep 17 00:00:00 2001
From: David Benjamin <davidben@google.com>
Date: Tue, 11 Sep 2018 13:49:28 -0700
Subject: [PATCH] Reduce inputs before the RSAZ code.

The RSAZ code requires the input be fully-reduced. To be consistent with the
other codepaths, move the BN_nnmod logic before the RSAZ check.

This fixes an oft-reported fuzzer bug.
https://github.com/google/oss-fuzz/issues/1761

Reviewed-by: Paul Dale <paul.dale@oracle.com>
(Merged from https://github.com/openssl/openssl/pull/7187)
---
 crypto/bn/bn_exp.c | 64 ++++++++++++++++++++++++----------------------
 test/bntest.c      | 25 ++++++++++++++++++
 2 files changed, 58 insertions(+), 31 deletions(-)

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index 83b0e5afee..9ea120be18 100644
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -648,34 +648,41 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
             goto err;
     }
 
+    if (a->neg || BN_ucmp(a, m) >= 0) {
+        BIGNUM *reduced = BN_CTX_get(ctx);
+        if (reduced == NULL
+            || !BN_nnmod(reduced, a, m, ctx)) {
+            goto err;
+        }
+        a = reduced;
+    }
+
 #ifdef RSAZ_ENABLED
-    if (!a->neg) {
-        /*
-         * If the size of the operands allow it, perform the optimized
-         * RSAZ exponentiation. For further information see
-         * crypto/bn/rsaz_exp.c and accompanying assembly modules.
-         */
-        if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024)
-            && rsaz_avx2_eligible()) {
-            if (NULL == bn_wexpand(rr, 16))
-                goto err;
-            RSAZ_1024_mod_exp_avx2(rr->d, a->d, p->d, m->d, mont->RR.d,
-                                   mont->n0[0]);
-            rr->top = 16;
-            rr->neg = 0;
-            bn_correct_top(rr);
-            ret = 1;
+    /*
+     * If the size of the operands allow it, perform the optimized
+     * RSAZ exponentiation. For further information see
+     * crypto/bn/rsaz_exp.c and accompanying assembly modules.
+     */
+    if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024)
+        && rsaz_avx2_eligible()) {
+        if (NULL == bn_wexpand(rr, 16))
             goto err;
-        } else if ((8 == a->top) && (8 == p->top) && (BN_num_bits(m) == 512)) {
-            if (NULL == bn_wexpand(rr, 8))
-                goto err;
-            RSAZ_512_mod_exp(rr->d, a->d, p->d, m->d, mont->n0[0], mont->RR.d);
-            rr->top = 8;
-            rr->neg = 0;
-            bn_correct_top(rr);
-            ret = 1;
+        RSAZ_1024_mod_exp_avx2(rr->d, a->d, p->d, m->d, mont->RR.d,
+                               mont->n0[0]);
+        rr->top = 16;
+        rr->neg = 0;
+        bn_correct_top(rr);
+        ret = 1;
+        goto err;
+    } else if ((8 == a->top) && (8 == p->top) && (BN_num_bits(m) == 512)) {
+        if (NULL == bn_wexpand(rr, 8))
             goto err;
-        }
+        RSAZ_512_mod_exp(rr->d, a->d, p->d, m->d, mont->n0[0], mont->RR.d);
+        rr->top = 8;
+        rr->neg = 0;
+        bn_correct_top(rr);
+        ret = 1;
+        goto err;
     }
 #endif
 
@@ -747,12 +754,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
         goto err;
 
     /* prepare a^1 in Montgomery domain */
-    if (a->neg || BN_ucmp(a, m) >= 0) {
-        if (!BN_nnmod(&am, a, m, ctx))
-            goto err;
-        if (!bn_to_mont_fixed_top(&am, &am, mont, ctx))
-            goto err;
-    } else if (!bn_to_mont_fixed_top(&am, a, mont, ctx))
+    if (!bn_to_mont_fixed_top(&am, a, mont, ctx))
         goto err;
 
 #if defined(SPARC_T4_MONT)
diff --git a/test/bntest.c b/test/bntest.c
index e760c64f7f..d042a3e2ba 100644
--- a/test/bntest.c
+++ b/test/bntest.c
@@ -519,6 +519,31 @@ static int test_modexp_mont5(void)
     if (!TEST_BN_eq(c, d))
         goto err;
 
+    /*
+     * rsaz_1024_mul_avx2 expects fully-reduced inputs.
+     * BN_mod_exp_mont_consttime should reduce the input first.
+     */
+    BN_hex2bn(&a,
+        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF");
+    BN_hex2bn(&b,
+        "1FA53F26F8811C58BE0357897AA5E165693230BC9DF5F01DFA6A2D59229EC69D"
+        "9DE6A89C36E3B6957B22D6FAAD5A3C73AE587B710DBE92E83D3A9A3339A085CB"
+        "B58F508CA4F837924BB52CC1698B7FDC2FD74362456A595A5B58E38E38E38E38"
+        "E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E");
+    BN_hex2bn(&n,
+        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF");
+    BN_MONT_CTX_set(mont, n, ctx);
+    BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont);
+    BN_zero(d);
+    if (!TEST_BN_eq(c, d))
+        goto err;
+
     /* Zero input */
     BN_bntest_rand(p, 1024, 0, 0);
     BN_zero(a);
-- 
2.25.1