src - OpenBSD base system

diff options


context:
space:
mode:

author	Bob Beck <beck@cvs.openbsd.org>	2017-01-21 10:38:30 +0000
committer	Bob Beck <beck@cvs.openbsd.org>	2017-01-21 10:38:30 +0000
commit	ff6c5b2d728313569b09c4ec269eb7f0fb2023e3 (patch)
tree	c4e87e40c7c000af9141ad1143b2dca18ec24c63 /lib/libcrypto/bn
parent	485104e2d443c36382923c3c23cc2f275e7ed81c (diff)

Split out BN_div and BN_mod into ct and nonct versions for Internal use.

ok jsing@

Diffstat (limited to 'lib/libcrypto/bn')

-rw-r--r--

lib/libcrypto/bn/bn.h

-rw-r--r--

lib/libcrypto/bn/bn_div.c

-rw-r--r--

lib/libcrypto/bn/bn_exp.c

-rw-r--r--

lib/libcrypto/bn/bn_exp2.c

-rw-r--r--

lib/libcrypto/bn/bn_gcd.c

-rw-r--r--

lib/libcrypto/bn/bn_lcl.h

-rw-r--r--

lib/libcrypto/bn/bn_mod.c

-rw-r--r--

lib/libcrypto/bn/bn_mont.c

-rw-r--r--

lib/libcrypto/bn/bn_prime.c

-rw-r--r--

lib/libcrypto/bn/bn_recp.c

10 files changed, 61 insertions, 33 deletions

diff --git a/lib/libcrypto/bn/bn.h b/lib/libcrypto/bn/bn.h
index 16ba8ae9810..fd9a62fe3f5 100644
--- a/lib/libcrypto/bn/bn.h
+++ b/lib/libcrypto/bn/bn.h

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn.h,v 1.33 2017/01/21 09:38:58 beck Exp $ */

+/* $OpenBSD: bn.h,v 1.34 2017/01/21 10:38:29 beck Exp $ */

@@ -387,9 +387,11 @@ void BN_set_negative(BIGNUM *b, int n);

#define BN_is_negative(a) ((a)->neg != 0)

+#ifndef LIBRESSL_INTERNAL

int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,

BN_CTX *ctx);

#define BN_mod(rem,m,d,ctx) BN_div(NULL,(rem),(m),(d),(ctx))

+#endif

int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx);

int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx);

int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m);

diff --git a/lib/libcrypto/bn/bn_div.c b/lib/libcrypto/bn/bn_div.c
index fefc53f9fad..a8f7c9f3841 100644
--- a/lib/libcrypto/bn/bn_div.c
+++ b/lib/libcrypto/bn/bn_div.c

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn_div.c,v 1.23 2015/02/09 15:49:22 jsing Exp $ */

+/* $OpenBSD: bn_div.c,v 1.24 2017/01/21 10:38:29 beck Exp $ */

@@ -116,9 +116,9 @@

* rm->neg == num->neg (unless the remainder is zero)

* If 'dv' or 'rm' is NULL, the respective value is not returned.

-int

-BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,

- BN_CTX *ctx)

+static int

+BN_div_internal(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,

+ BN_CTX *ctx, int ct)

{

int norm_shift, i, loop;

BIGNUM *tmp, wnum, *snum, *sdiv, *res;

@@ -137,10 +137,8 @@ BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,

bn_check_top(num);

- if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) ||

- (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)) {

+ if (ct)

no_branch = 1;

- }

bn_check_top(dv);

bn_check_top(rm);

@@ -379,3 +377,27 @@ err:

BN_CTX_end(ctx);

return (0);

}

+int

+BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,

+ BN_CTX *ctx)

+ int ct = ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) ||

+ (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0));

+ return BN_div_internal(dv, rm, num, divisor, ctx, ct);

+int

+BN_div_nonct(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,

+ BN_CTX *ctx)

+ return BN_div_internal(dv, rm, num, divisor, ctx, 0);

+int

+BN_div_ct(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,

+ BN_CTX *ctx)

+ return BN_div_internal(dv, rm, num, divisor, ctx, 1);

diff --git a/lib/libcrypto/bn/bn_exp.c b/lib/libcrypto/bn/bn_exp.c
index ed4bc666bf2..f650e94b09b 100644
--- a/lib/libcrypto/bn/bn_exp.c
+++ b/lib/libcrypto/bn/bn_exp.c

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn_exp.c,v 1.28 2017/01/21 09:38:58 beck Exp $ */

+/* $OpenBSD: bn_exp.c,v 1.29 2017/01/21 10:38:29 beck Exp $ */

@@ -735,7 +735,7 @@ BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,

/* prepare a^1 in Montgomery domain */

if (a->neg || BN_ucmp(a, m) >= 0) {

- if (!BN_mod(&am, a,m, ctx))

+ if (!BN_mod_ct(&am, a,m, ctx))

goto err;

if (!BN_to_montgomery(&am, &am, mont, ctx))

goto err;

@@ -924,7 +924,7 @@ BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, const BIGNUM *m,

#define BN_MOD_MUL_WORD(r, w, m) \

(BN_mul_word(r, (w)) && \

(/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \

- (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))

+ (BN_mod_ct(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))

/* BN_MOD_MUL_WORD is only used with 'w' large,

* so the BN_ucmp test is probably more overhead

* than always using BN_mod (which uses BN_copy if

diff --git a/lib/libcrypto/bn/bn_exp2.c b/lib/libcrypto/bn/bn_exp2.c
index 38bf467a38d..1d938d38182 100644
--- a/lib/libcrypto/bn/bn_exp2.c
+++ b/lib/libcrypto/bn/bn_exp2.c

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn_exp2.c,v 1.10 2015/02/09 15:49:22 jsing Exp $ */

+/* $OpenBSD: bn_exp2.c,v 1.11 2017/01/21 10:38:29 beck Exp $ */

@@ -175,7 +175,7 @@ BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1,

* Build table for a1: val1[i] := a1^(2*i + 1) mod m for i = 0 .. 2^(window1-1)

if (a1->neg || BN_ucmp(a1, m) >= 0) {

- if (!BN_mod(val1[0], a1, m, ctx))

+ if (!BN_mod_ct(val1[0], a1, m, ctx))

goto err;

a_mod_m = val1[0];

} else

@@ -206,7 +206,7 @@ BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1,

* Build table for a2: val2[i] := a2^(2*i + 1) mod m for i = 0 .. 2^(window2-1)

if (a2->neg || BN_ucmp(a2, m) >= 0) {

- if (!BN_mod(val2[0], a2, m, ctx))

+ if (!BN_mod_ct(val2[0], a2, m, ctx))

goto err;

a_mod_m = val2[0];

} else

diff --git a/lib/libcrypto/bn/bn_gcd.c b/lib/libcrypto/bn/bn_gcd.c
index da9c29a8e56..3c8ff5b405f 100644
--- a/lib/libcrypto/bn/bn_gcd.c
+++ b/lib/libcrypto/bn/bn_gcd.c

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn_gcd.c,v 1.10 2015/02/09 15:49:22 jsing Exp $ */

+/* $OpenBSD: bn_gcd.c,v 1.11 2017/01/21 10:38:29 beck Exp $ */

@@ -421,7 +421,7 @@ BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)

}

} else {

- if (!BN_div(D, M, A, B, ctx))

+ if (!BN_div_ct(D, M, A, B, ctx))

goto err;

}

@@ -605,7 +605,7 @@ BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n,

BN_with_flags(pA, A, BN_FLG_CONSTTIME);

/* (D, M) := (A/B, A%B) ... */

- if (!BN_div(D, M, pA, B, ctx))

+ if (!BN_div_ct(D, M, pA, B, ctx))

goto err;

/* Now

diff --git a/lib/libcrypto/bn/bn_lcl.h b/lib/libcrypto/bn/bn_lcl.h
index f8ce4bdc513..59d9036d018 100644
--- a/lib/libcrypto/bn/bn_lcl.h
+++ b/lib/libcrypto/bn/bn_lcl.h

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn_lcl.h,v 1.24 2017/01/21 09:38:58 beck Exp $ */

+/* $OpenBSD: bn_lcl.h,v 1.25 2017/01/21 10:38:29 beck Exp $ */

@@ -593,7 +593,11 @@ int BN_mod_exp_mont_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,

const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx);

int BN_mod_exp_mont_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,

const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx);

+int BN_div_nonct(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,

+ BN_CTX *ctx);

+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))

__END_HIDDEN_DECLS

#endif

diff --git a/lib/libcrypto/bn/bn_mod.c b/lib/libcrypto/bn/bn_mod.c
index eb2d5b072e7..4c30c098d48 100644
--- a/lib/libcrypto/bn/bn_mod.c
+++ b/lib/libcrypto/bn/bn_mod.c

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn_mod.c,v 1.10 2016/11/05 10:47:16 miod Exp $ */

+/* $OpenBSD: bn_mod.c,v 1.11 2017/01/21 10:38:29 beck Exp $ */

/* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>

* for the OpenSSL project. */

/* ====================================================================

@@ -121,7 +121,7 @@ BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)

/* like BN_mod, but returns non-negative remainder

* (i.e., 0 <= r < |d| always holds) */

- if (!(BN_mod(r, m,d, ctx)))

+ if (!(BN_mod_ct(r, m,d, ctx)))

return 0;

if (!r->neg)

return 1;

@@ -212,7 +212,7 @@ BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)

if (!BN_sqr(r, a, ctx))

return 0;

/* r->neg == 0, thus we don't need BN_nnmod */

- return BN_mod(r, r, m, ctx);

+ return BN_mod_ct(r, r, m, ctx);

}

int

diff --git a/lib/libcrypto/bn/bn_mont.c b/lib/libcrypto/bn/bn_mont.c
index 3eb9913a9ed..34965024354 100644
--- a/lib/libcrypto/bn/bn_mont.c
+++ b/lib/libcrypto/bn/bn_mont.c

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn_mont.c,v 1.24 2015/02/09 15:49:22 jsing Exp $ */

+/* $OpenBSD: bn_mont.c,v 1.25 2017/01/21 10:38:29 beck Exp $ */

@@ -418,7 +418,7 @@ BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)

Ri->d[1] = BN_MASK2;

Ri->top = 2;

}

- if (!BN_div(Ri, NULL, Ri, &tmod, ctx))

+ if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))

goto err;

/* Ni = (R*Ri-1)/N,

* keep only couple of least significant words: */

@@ -446,7 +446,7 @@ BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)

if (!BN_set_word(Ri, BN_MASK2))

goto err; /* Ri-- (mod word size) */

}

- if (!BN_div(Ri, NULL, Ri, &tmod, ctx))

+ if (!BN_div_ct(Ri, NULL, Ri, &tmod, ctx))

goto err;

/* Ni = (R*Ri-1)/N,

* keep only least significant word: */

@@ -468,7 +468,7 @@ BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)

if (!BN_sub_word(Ri, 1))

goto err;

/* Ni = (R*Ri-1) / N */

- if (!BN_div(&(mont->Ni), NULL, Ri, &mont->N, ctx))

+ if (!BN_div_ct(&(mont->Ni), NULL, Ri, &mont->N, ctx))

goto err;

}

#endif

@@ -477,7 +477,7 @@ BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)

BN_zero(&(mont->RR));

if (!BN_set_bit(&(mont->RR), mont->ri*2))

goto err;

- if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx))

+ if (!BN_mod_ct(&(mont->RR), &(mont->RR), &(mont->N), ctx))

goto err;

ret = 1;

diff --git a/lib/libcrypto/bn/bn_prime.c b/lib/libcrypto/bn/bn_prime.c
index b2f32684e4a..ec8217ef697 100644
--- a/lib/libcrypto/bn/bn_prime.c
+++ b/lib/libcrypto/bn/bn_prime.c

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn_prime.c,v 1.16 2017/01/21 09:38:58 beck Exp $ */

+/* $OpenBSD: bn_prime.c,v 1.17 2017/01/21 10:38:29 beck Exp $ */

@@ -443,7 +443,7 @@ probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem,

/* we need ((rnd-rem) % add) == 0 */

- if (!BN_mod(t1, rnd, add, ctx))

+ if (!BN_mod_ct(t1, rnd, add, ctx))

goto err;

if (!BN_sub(rnd, rnd, t1))

goto err;

@@ -500,7 +500,7 @@ probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd,

goto err;

/* we need ((rnd-rem) % add) == 0 */

- if (!BN_mod(t1, q,qadd, ctx))

+ if (!BN_mod_ct(t1, q,qadd, ctx))

goto err;

if (!BN_sub(q, q, t1))

goto err;

diff --git a/lib/libcrypto/bn/bn_recp.c b/lib/libcrypto/bn/bn_recp.c
index b0bd0aa4dfe..aae7c7ef856 100644
--- a/lib/libcrypto/bn/bn_recp.c
+++ b/lib/libcrypto/bn/bn_recp.c

@@ -1,4 +1,4 @@

-/* $OpenBSD: bn_recp.c,v 1.13 2015/04/29 00:11:12 doug Exp $ */

+/* $OpenBSD: bn_recp.c,v 1.14 2017/01/21 10:38:29 beck Exp $ */

@@ -251,7 +251,7 @@ BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)

if (!BN_set_bit(t, len))

goto err;

- if (!BN_div(r, NULL, t,m, ctx))

+ if (!BN_div_ct(r, NULL, t,m, ctx))

goto err;

ret = len;