Fix a SCA leak in BN_generate_dsa_nonce

[oweals/openssl.git] / crypto / bn / bn_prime.c

diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index 9295aeb625d30a54575120b3119218c36060d025..19b081f38eb7b2d744548c83daaa907df45a1f95 100644 (file)
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -1,7 +1,5 @@
 /*
- * WARNING: do not edit!
- * Generated by crypto/bn/bn_prime.pl
- * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -65,8 +63,12 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
         /* There are no prime numbers this small. */
         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
         return 0;
-    } else if (bits == 2 && safe) {
-        /* The smallest safe prime (7) is three bits. */
+    } else if (add == NULL && safe && bits < 6 && bits != 3) {
+        /*
+         * The smallest safe prime (7) is three bits.
+         * But the following two safe primes with less than 6 bits (11, 23)
+         * are unreachable for BN_rand with BN_RAND_TOP_TWO.
+         */
         BNerr(BN_F_BN_GENERATE_PRIME_EX, BN_R_BITS_TOO_SMALL);
         return 0;
     }
@@ -80,7 +82,7 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
         goto err;
     BN_CTX_start(ctx);
     t = BN_CTX_get(ctx);
-    if (!t)
+    if (t == NULL)
         goto err;
  loop:
     /* make a random number and set the top and bottom bits */
@@ -137,8 +139,7 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe,
     found = 1;
  err:
     OPENSSL_free(mods);
-    if (ctx != NULL)
-        BN_CTX_end(ctx);
+    BN_CTX_end(ctx);
     BN_CTX_free(ctx);
     bn_check_top(ret);
     return found;
@@ -156,20 +157,21 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
     int i, j, ret = -1;
     int k;
     BN_CTX *ctx = NULL;
-    BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
+    BIGNUM *A1, *A1_odd, *A3, *check; /* taken from ctx */
     BN_MONT_CTX *mont = NULL;
-    const BIGNUM *A = NULL;
 
-    if (BN_cmp(a, BN_value_one()) <= 0)
+    /* Take care of the really small primes 2 & 3 */
+    if (BN_is_word(a, 2) || BN_is_word(a, 3))
+        return 1;
+
+    /* Check odd and bigger than 1 */
+    if (!BN_is_odd(a) || BN_cmp(a, BN_value_one()) <= 0)
         return 0;
 
     if (checks == BN_prime_checks)
         checks = BN_prime_checks_for_size(BN_num_bits(a));
 
     /* first look for small factors */
-    if (!BN_is_odd(a))
-        /* a is even => a is prime if and only if a == 2 */
-        return BN_is_word(a, 2);
     if (do_trial_division) {
         for (i = 1; i < NUMPRIMES; i++) {
             BN_ULONG mod = BN_mod_word(a, primes[i]);
@@ -188,32 +190,19 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
         goto err;
     BN_CTX_start(ctx);
 
-    /* A := abs(a) */
-    if (a->neg) {
-        BIGNUM *t;
-        if ((t = BN_CTX_get(ctx)) == NULL)
-            goto err;
-        if (BN_copy(t, a) == NULL)
-            goto err;
-        t->neg = 0;
-        A = t;
-    } else
-        A = a;
     A1 = BN_CTX_get(ctx);
+    A3 = BN_CTX_get(ctx);
     A1_odd = BN_CTX_get(ctx);
     check = BN_CTX_get(ctx);
     if (check == NULL)
         goto err;
 
-    /* compute A1 := A - 1 */
-    if (!BN_copy(A1, A))
-        goto err;
-    if (!BN_sub_word(A1, 1))
+    /* compute A1 := a - 1 */
+    if (!BN_copy(A1, a) || !BN_sub_word(A1, 1))
         goto err;
-    if (BN_is_zero(A1)) {
-        ret = 0;
+    /* compute A3 := a - 3 */
+    if (!BN_copy(A3, a) || !BN_sub_word(A3, 3))
         goto err;
-    }
 
     /* write  A1  as  A1_odd * 2^k */
     k = 1;
@@ -222,21 +211,19 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
     if (!BN_rshift(A1_odd, A1, k))
         goto err;
 
-    /* Montgomery setup for computations mod A */
+    /* Montgomery setup for computations mod a */
     mont = BN_MONT_CTX_new();
     if (mont == NULL)
         goto err;
-    if (!BN_MONT_CTX_set(mont, A, ctx))
+    if (!BN_MONT_CTX_set(mont, a, ctx))
         goto err;
 
     for (i = 0; i < checks; i++) {
-        if (!BN_pseudo_rand_range(check, A1))
-            goto err;
-        if (!BN_add_word(check, 1))
+        /* 1 < check < a-1 */
+        if (!BN_priv_rand_range(check, A3) || !BN_add_word(check, 2))
             goto err;
-        /* now 1 <= check < A */
 
-        j = witness(check, A, A1, A1_odd, k, ctx, mont);
+        j = witness(check, a, A1, A1_odd, k, ctx, mont);
         if (j == -1)
             goto err;
         if (j) {
@@ -255,7 +242,7 @@ int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed,
     }
     BN_MONT_CTX_free(mont);
 
-    return (ret);
+    return ret;
 }
 
 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
@@ -293,8 +280,9 @@ static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
     char is_single_word = bits <= BN_BITS2;
 
  again:
-    if (!BN_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD))
-        return (0);
+    /* TODO: Not all primes are private */
+    if (!BN_priv_rand(rnd, bits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ODD))
+        return 0;
     /* we now have a random number 'rnd' to test. */
     for (i = 1; i < NUMPRIMES; i++) {
         BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
@@ -360,11 +348,11 @@ static int probable_prime(BIGNUM *rnd, int bits, prime_t *mods)
         }
     }
     if (!BN_add_word(rnd, delta))
-        return (0);
+        return 0;
     if (BN_num_bits(rnd) != bits)
         goto again;
     bn_check_top(rnd);
-    return (1);
+    return 1;
 }
 
 int bn_probable_prime_dh(BIGNUM *rnd, int bits,
@@ -413,7 +401,7 @@ int bn_probable_prime_dh(BIGNUM *rnd, int bits,
  err:
     BN_CTX_end(ctx);
     bn_check_top(rnd);
-    return (ret);
+    return ret;
 }
 
 static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
@@ -480,5 +468,5 @@ static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,
  err:
     BN_CTX_end(ctx);
     bn_check_top(p);
-    return (ret);
+    return ret;
 }