Add ct and nonct versions of BN_mod_inverse for internal use

ok jsing@

13 files changed, 67 insertions, 36 deletions

diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h
index fd9a62fe3f..5d5de7e43a 100644
--- a/src/lib/libcrypto/bn/bn.h
+++ b/src/lib/libcrypto/bn/bn.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn.h,v 1.34 2017/01/21 10:38:29 beck Exp $ */
+/* $OpenBSD: bn.h,v 1.35 2017/01/21 11:00:46 beck Exp $ */
 /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -454,8 +454,10 @@ int 	BN_dec2bn(BIGNUM **a, const char *str);
 int     BN_asc2bn(BIGNUM **a, const char *str);
 int     BN_gcd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
 int     BN_kronecker(const BIGNUM *a,const BIGNUM *b,BN_CTX *ctx); /* returns -2 for error */
+#ifndef LIBRESSL_INTERNAL
 BIGNUM *BN_mod_inverse(BIGNUM *ret,
     const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx);
+#endif
 BIGNUM *BN_mod_sqrt(BIGNUM *ret,
     const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx);
 
diff --git a/src/lib/libcrypto/bn/bn_blind.c b/src/lib/libcrypto/bn/bn_blind.c
index 01874f6208..28c6276751 100644
--- a/src/lib/libcrypto/bn/bn_blind.c
+++ b/src/lib/libcrypto/bn/bn_blind.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_blind.c,v 1.15 2017/01/21 09:38:58 beck Exp $ */
+/* $OpenBSD: bn_blind.c,v 1.16 2017/01/21 11:00:46 beck Exp $ */
 /* ====================================================================
  * Copyright (c) 1998-2006 The OpenSSL Project.  All rights reserved.
  *
@@ -351,7 +351,7 @@ BN_BLINDING_create_param(BN_BLINDING *b, const BIGNUM *e, BIGNUM *m,
         do {
                 if (!BN_rand_range(ret->A, ret->mod))
                         goto err;
-                if (BN_mod_inverse(ret->Ai, ret->A, ret->mod, ctx) == NULL) {
+                if (BN_mod_inverse_ct(ret->Ai, ret->A, ret->mod, ctx) == NULL) {
                         /* this should almost never happen for good RSA keys */
                         unsigned long error = ERR_peek_last_error();
                         if (ERR_GET_REASON(error) == BN_R_NO_INVERSE) {
diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c
index 3c8ff5b405..4eab1b36d2 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.11 2017/01/21 10:38:29 beck Exp $ */
+/* $OpenBSD: bn_gcd.c,v 1.12 2017/01/21 11:00:46 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -231,17 +231,16 @@ err:
 static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a,
     const BIGNUM *n, BN_CTX *ctx);
 
-BIGNUM *
-BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
+static BIGNUM *
+BN_mod_inverse_internal(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,
+    int ct)
 {
         BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
         BIGNUM *ret = NULL;
         int sign;
 
-        if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) ||
-            (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) {
+        if (ct)
                 return BN_mod_inverse_no_branch(in, a, n, ctx);
-        }
 
         bn_check_top(a);
         bn_check_top(n);
@@ -524,6 +523,25 @@ err:
         return (ret);
 }
 
+BIGNUM *
+BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
+{
+        int ct = ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) ||
+            (BN_get_flags(n, BN_FLG_CONSTTIME) != 0));
+        return BN_mod_inverse_internal(in, a, n, ctx, ct);
+}
+
+BIGNUM *
+BN_mod_inverse_nonct(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
+{
+        return BN_mod_inverse_internal(in, a, n, ctx, 0);
+}
+
+BIGNUM *
+BN_mod_inverse_ct(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
+{
+        return BN_mod_inverse_internal(in, a, n, ctx, 1);
+}
 
 /* BN_mod_inverse_no_branch is a special version of BN_mod_inverse.
  * It does not contain branches that may leak sensitive information.
diff --git a/src/lib/libcrypto/bn/bn_lcl.h b/src/lib/libcrypto/bn/bn_lcl.h
index 59d9036d01..75c35499a8 100644
--- a/src/lib/libcrypto/bn/bn_lcl.h
+++ b/src/lib/libcrypto/bn/bn_lcl.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_lcl.h,v 1.25 2017/01/21 10:38:29 beck Exp $ */
+/* $OpenBSD: bn_lcl.h,v 1.26 2017/01/21 11:00:46 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -599,5 +599,9 @@ int BN_div_ct(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
     BN_CTX *ctx);
 #define BN_mod_ct(rem,m,d,ctx) BN_div_ct(NULL,(rem),(m),(d),(ctx))
 #define BN_mod_nonct(rem,m,d,ctx) BN_div_nonct(NULL,(rem),(m),(d),(ctx))
+BIGNUM *BN_mod_inverse_ct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,
+    BN_CTX *ctx);
+BIGNUM *BN_mod_inverse_nonct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,
+    BN_CTX *ctx);
 __END_HIDDEN_DECLS
 #endif
diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c
index 3496502435..eeac046826 100644
--- a/src/lib/libcrypto/bn/bn_mont.c
+++ b/src/lib/libcrypto/bn/bn_mont.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_mont.c,v 1.25 2017/01/21 10:38:29 beck Exp $ */
+/* $OpenBSD: bn_mont.c,v 1.26 2017/01/21 11:00:46 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -400,7 +400,7 @@ BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
                 if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
                         tmod.top = 2;
 
-                if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
+                if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
                         goto err;
                 if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
                         goto err; /* R*Ri */
@@ -433,7 +433,7 @@ BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
                 buf[1] = 0;
                 tmod.top = buf[0] != 0 ? 1 : 0;
                 /* Ri = R^-1 mod N*/
-                if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
+                if ((BN_mod_inverse_ct(Ri, R, &tmod, ctx)) == NULL)
                         goto err;
                 if (!BN_lshift(Ri, Ri, BN_BITS2))
                         goto err; /* R*Ri */
@@ -461,7 +461,7 @@ BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
                 if (!BN_set_bit(R, mont->ri))
                         goto err;  /* R = 2^ri */
                 /* Ri = R^-1 mod N*/
-                if ((BN_mod_inverse(Ri, R, &mont->N, ctx)) == NULL)
+                if ((BN_mod_inverse_ct(Ri, R, &mont->N, ctx)) == NULL)
                         goto err;
                 if (!BN_lshift(Ri, Ri, mont->ri))
                         goto err; /* R*Ri */
diff --git a/src/lib/libcrypto/bn/bn_x931p.c b/src/lib/libcrypto/bn/bn_x931p.c
index 1948bc8e71..84c998d4e1 100644
--- a/src/lib/libcrypto/bn/bn_x931p.c
+++ b/src/lib/libcrypto/bn/bn_x931p.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_x931p.c,v 1.8 2015/04/29 00:11:12 doug Exp $ */
+/* $OpenBSD: bn_x931p.c,v 1.9 2017/01/21 11:00:46 beck Exp $ */
 /* Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL
  * project 2005.
  */
@@ -59,6 +59,8 @@
 #include <stdio.h>
 #include <openssl/bn.h>
 
+#include "bn_lcl.h"
+
 /* X9.31 routines for prime derivation */
 
 /* X9.31 prime derivation. This is used to generate the primes pi
@@ -134,13 +136,13 @@ BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, const BIGNUM *Xp,
 
         /* First set p to value of Rp */
 
-        if (!BN_mod_inverse(p, p2, p1, ctx))
+        if (!BN_mod_inverse_ct(p, p2, p1, ctx))
                 goto err;
 
         if (!BN_mul(p, p, p2, ctx))
                 goto err;
 
-        if (!BN_mod_inverse(t, p1, p2, ctx))
+        if (!BN_mod_inverse_ct(t, p1, p2, ctx))
                 goto err;
 
         if (!BN_mul(t, t, p1, ctx))
diff --git a/src/lib/libcrypto/dsa/dsa_ossl.c b/src/lib/libcrypto/dsa/dsa_ossl.c
index 4177557d0e..f806cd645a 100644
--- a/src/lib/libcrypto/dsa/dsa_ossl.c
+++ b/src/lib/libcrypto/dsa/dsa_ossl.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: dsa_ossl.c,v 1.28 2017/01/21 10:38:29 beck Exp $ */
+/* $OpenBSD: dsa_ossl.c,v 1.29 2017/01/21 11:00:46 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -248,7 +248,7 @@ dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
                 goto err;
 
         /* Compute  part of 's = inv(k) (m + xr) mod q' */
-        if ((kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx)) == NULL)
+        if ((kinv = BN_mod_inverse_ct(NULL, &k, dsa->q, ctx)) == NULL)
                 goto err;
 
         BN_clear_free(*kinvp);
@@ -312,7 +312,7 @@ dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa)
 
         /* Calculate W = inv(S) mod Q
          * save W in u2 */
-        if ((BN_mod_inverse(&u2, sig->s, dsa->q, ctx)) == NULL)
+        if ((BN_mod_inverse_ct(&u2, sig->s, dsa->q, ctx)) == NULL)
                 goto err;
 
         /* save M in u1 */
diff --git a/src/lib/libcrypto/ec/ecp_smpl.c b/src/lib/libcrypto/ec/ecp_smpl.c
index f6db4dc9b1..f497657463 100644
--- a/src/lib/libcrypto/ec/ecp_smpl.c
+++ b/src/lib/libcrypto/ec/ecp_smpl.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ecp_smpl.c,v 1.15 2015/02/09 15:49:22 jsing Exp $ */
+/* $OpenBSD: ecp_smpl.c,v 1.16 2017/01/21 11:00:47 beck Exp $ */
 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
  * for the OpenSSL project.
  * Includes code written by Bodo Moeller for the OpenSSL project.
@@ -64,6 +64,7 @@
 
 #include <openssl/err.h>
 
+#include "bn_lcl.h"
 #include "ec_lcl.h"
 
 const EC_METHOD *
@@ -581,7 +582,7 @@ ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP * group, const EC_POIN
                         }
                 }
         } else {
-                if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) {
+                if (!BN_mod_inverse_ct(Z_1, Z_, &group->field, ctx)) {
                         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
                         goto err;
                 }
@@ -1311,7 +1312,7 @@ ec_GFp_simple_points_make_affine(const EC_GROUP * group, size_t num, EC_POINT *
 
         /* invert heap[1] */
         if (!BN_is_zero(heap[1])) {
-                if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx)) {
+                if (!BN_mod_inverse_ct(heap[1], heap[1], &group->field, ctx)) {
                         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
                         goto err;
                 }
diff --git a/src/lib/libcrypto/ecdsa/ecs_ossl.c b/src/lib/libcrypto/ecdsa/ecs_ossl.c
index 26158a001b..637da6535f 100644
--- a/src/lib/libcrypto/ecdsa/ecs_ossl.c
+++ b/src/lib/libcrypto/ecdsa/ecs_ossl.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ecs_ossl.c,v 1.7 2017/01/05 13:25:52 jsing Exp $ */
+/* $OpenBSD: ecs_ossl.c,v 1.8 2017/01/21 11:00:47 beck Exp $ */
 /*
  * Written by Nils Larsch for the OpenSSL project
  */
@@ -58,11 +58,13 @@
 
 #include <openssl/opensslconf.h>
 
-#include "ecs_locl.h"
 #include <openssl/err.h>
 #include <openssl/obj_mac.h>
 #include <openssl/bn.h>
 
+#include "bn_lcl.h"
+#include "ecs_locl.h"
+
 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen,
     const BIGNUM *, const BIGNUM *, EC_KEY *eckey);
 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
@@ -176,7 +178,7 @@ ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
         } while (BN_is_zero(r));
 
         /* compute the inverse of k */
-        if (!BN_mod_inverse(k, k, order, ctx)) {
+        if (!BN_mod_inverse_ct(k, k, order, ctx)) {
                 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
                 goto err;
         }
@@ -360,7 +362,7 @@ ecdsa_do_verify(const unsigned char *dgst, int dgst_len, const ECDSA_SIG *sig,
                 goto err;
         }
         /* calculate tmp1 = inv(S) mod order */
-        if (!BN_mod_inverse(u2, sig->s, order, ctx)) {
+        if (!BN_mod_inverse_ct(u2, sig->s, order, ctx)) {
                 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
                 goto err;
         }
diff --git a/src/lib/libcrypto/gost/gostr341001.c b/src/lib/libcrypto/gost/gostr341001.c
index 5fb494009c..39749394af 100644
--- a/src/lib/libcrypto/gost/gostr341001.c
+++ b/src/lib/libcrypto/gost/gostr341001.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: gostr341001.c,v 1.5 2017/01/21 10:38:29 beck Exp $ */
+/* $OpenBSD: gostr341001.c,v 1.6 2017/01/21 11:00:47 beck Exp $ */
 /*
  * Copyright (c) 2014 Dmitry Eremin-Solenikov <dbaryshkov@gmail.com>
  * Copyright (c) 2005-2006 Cryptocom LTD
@@ -294,7 +294,7 @@ gost2001_do_verify(BIGNUM *md, ECDSA_SIG *sig, GOST_KEY *ec)
                 goto err;
         if (BN_is_zero(e))
                 BN_one(e);
-        if ((v = BN_mod_inverse(v, e, order, ctx)) == NULL)
+        if ((v = BN_mod_inverse_ct(v, e, order, ctx)) == NULL)
                 goto err;
         if (BN_mod_mul(z1, sig->s, v, order, ctx) == 0)
                 goto err;
diff --git a/src/lib/libcrypto/rsa/rsa_chk.c b/src/lib/libcrypto/rsa/rsa_chk.c
index efe9431f2d..91616d17cb 100644
--- a/src/lib/libcrypto/rsa/rsa_chk.c
+++ b/src/lib/libcrypto/rsa/rsa_chk.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: rsa_chk.c,v 1.10 2017/01/21 10:38:29 beck Exp $ */
+/* $OpenBSD: rsa_chk.c,v 1.11 2017/01/21 11:00:47 beck Exp $ */
 /* ====================================================================
  * Copyright (c) 1999 The OpenSSL Project.  All rights reserved.
  *
@@ -191,7 +191,7 @@ RSA_check_key(const RSA *key)
                 }
 
                 /* iqmp = q^-1 mod p? */
-                if (!BN_mod_inverse(i, key->q, key->p, ctx)) {
+                if (!BN_mod_inverse_ct(i, key->q, key->p, ctx)) {
                         ret = -1;
                         goto err;
                 }
diff --git a/src/lib/libcrypto/rsa/rsa_crpt.c b/src/lib/libcrypto/rsa/rsa_crpt.c
index ccb677c12b..8063a83263 100644
--- a/src/lib/libcrypto/rsa/rsa_crpt.c
+++ b/src/lib/libcrypto/rsa/rsa_crpt.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: rsa_crpt.c,v 1.16 2016/07/07 11:53:12 bcook Exp $ */
+/* $OpenBSD: rsa_crpt.c,v 1.17 2017/01/21 11:00:47 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -66,6 +66,8 @@
 #include <openssl/lhash.h>
 #include <openssl/rsa.h>
 
+#include "bn_lcl.h"
+
 #ifndef OPENSSL_NO_ENGINE
 #include <openssl/engine.h>
 #endif
@@ -160,7 +162,7 @@ rsa_get_public_exp(const BIGNUM *d, const BIGNUM *p, const BIGNUM *q,
         if (!BN_mul(r0, r1, r2, ctx))
                 goto err;
 
-        ret = BN_mod_inverse(NULL, d, r0, ctx);
+        ret = BN_mod_inverse_ct(NULL, d, r0, ctx);
 err:
         BN_CTX_end(ctx);
         return ret;
diff --git a/src/lib/libcrypto/rsa/rsa_gen.c b/src/lib/libcrypto/rsa/rsa_gen.c
index 817f177e96..300b292b7b 100644
--- a/src/lib/libcrypto/rsa/rsa_gen.c
+++ b/src/lib/libcrypto/rsa/rsa_gen.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: rsa_gen.c,v 1.19 2017/01/21 10:38:29 beck Exp $ */
+/* $OpenBSD: rsa_gen.c,v 1.20 2017/01/21 11:00:47 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -197,7 +197,7 @@ rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
 
         BN_with_flags(&pr0, r0, BN_FLG_CONSTTIME);
 
-        if (!BN_mod_inverse(rsa->d, rsa->e, &pr0, ctx)) /* d */
+        if (!BN_mod_inverse_ct(rsa->d, rsa->e, &pr0, ctx)) /* d */
                 goto err;
 
         /* set up d for correct BN_FLG_CONSTTIME flag */
@@ -213,7 +213,7 @@ rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
 
         /* calculate inverse of q mod p */
         BN_with_flags(&p, rsa->p, BN_FLG_CONSTTIME);
-        if (!BN_mod_inverse(rsa->iqmp, rsa->q, &p, ctx))
+        if (!BN_mod_inverse_ct(rsa->iqmp, rsa->q, &p, ctx))
                 goto err;
 
         ok = 1;