X-Git-Url: https://git.openssl.org/?a=blobdiff_plain;f=crypto%2Fbn%2Fbn_exp.c;h=8f8c694481911cdc8a71115bdc0ef65abfa555bc;hb=46a643763de6d8e39ecf6f76fa79b4d04885aa59;hp=d6bb2b4397cc91a1cad003bba0595f904849ab21;hpb=92c44685724c0d993ea8920577680f3c0a1d79c8;p=openssl.git

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index d6bb2b4397..8f8c694481 100644
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -56,7 +56,7 @@
  * [including the GNU Public Licence.]
  */
 /* ====================================================================
- * Copyright (c) 1998-2000 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -113,6 +113,7 @@
 #include "cryptlib.h"
 #include "bn_lcl.h"
 
+/* maximum precomputation table size for *variable* sliding windows */
 #define TABLE_SIZE	32
 
 /* this one works - simple but works */
@@ -121,6 +122,13 @@ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 	int i,bits,ret=0;
 	BIGNUM *v,*rr;
 
+	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
+		{
+		/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
+		BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+		return -1;
+		}
+
 	BN_CTX_start(ctx);
 	if ((r == a) || (r == p))
 		rr = BN_CTX_get(ctx);
@@ -205,7 +213,7 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
 	if (BN_is_odd(m))
 		{
 #  ifdef MONT_EXP_WORD
-		if (a->top == 1 && !a->neg)
+		if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) == 0))
 			{
 			BN_ULONG A = a->d[0];
 			ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
@@ -237,6 +245,13 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
 	BIGNUM *val[TABLE_SIZE];
 	BN_RECP_CTX recp;
 
+	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
+		{
+		/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
+		BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+		return -1;
+		}
+
 	bits=BN_num_bits(p);
 
 	if (bits == 0)
@@ -364,6 +379,11 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 	BIGNUM *val[TABLE_SIZE];
 	BN_MONT_CTX *mont=NULL;
 
+	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
+		{
+		return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);
+		}
+
 	bn_check_top(a);
 	bn_check_top(p);
 	bn_check_top(m);
@@ -495,6 +515,212 @@ err:
 	return(ret);
 	}
 
+
+/* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout
+ * so that accessing any of these table values shows the same access pattern as far
+ * as cache lines are concerned.  The following functions are used to transfer a BIGNUM
+ * from/to that table. */
+
+static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width)
+	{
+	size_t i, j;
+
+	if (bn_wexpand(b, top) == NULL)
+		return 0;
+	while (b->top < top)
+		{
+		b->d[b->top++] = 0;
+		}
+	
+	for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)
+		{
+		buf[j] = ((unsigned char*)b->d)[i];
+		}
+
+	bn_correct_top(b);
+	return 1;
+	}
+
+static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width)
+	{
+	size_t i, j;
+
+	if (bn_wexpand(b, top) == NULL)
+		return 0;
+
+	for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)
+		{
+		((unsigned char*)b->d)[i] = buf[j];
+		}
+
+	b->top = top;
+	bn_correct_top(b);
+	return 1;
+	}	
+
+/* Given a pointer value, compute the next address that is a cache line multiple. */
+#define MOD_EXP_CTIME_ALIGN(x_) \
+	((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((BN_ULONG)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK))))
+
+/* This variant of BN_mod_exp_mont() uses fixed windows and the special
+ * precomputation memory layout to limit data-dependency to a minimum
+ * to protect secret exponents (cf. the hyper-threading timing attacks
+ * pointed out by Colin Percival,
+ * http://www.daemonology.net/hyperthreading-considered-harmful/)
+ */
+int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
+		    const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
+	{
+	int i,bits,ret=0,idx,window,wvalue;
+	int top;
+ 	BIGNUM *r;
+	const BIGNUM *aa;
+	BN_MONT_CTX *mont=NULL;
+
+	int numPowers;
+	unsigned char *powerbufFree=NULL;
+	int powerbufLen = 0;
+	unsigned char *powerbuf=NULL;
+	BIGNUM *computeTemp=NULL, *am=NULL;
+
+	bn_check_top(a);
+	bn_check_top(p);
+	bn_check_top(m);
+
+	top = m->top;
+
+	if (!(m->d[0] & 1))
+		{
+		BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS);
+		return(0);
+		}
+	bits=BN_num_bits(p);
+	if (bits == 0)
+		{
+		ret = BN_one(rr);
+		return ret;
+		}
+
+ 	/* Initialize BIGNUM context and allocate intermediate result */
+	BN_CTX_start(ctx);
+	r = BN_CTX_get(ctx);
+	if (r == NULL) goto err;
+
+	/* Allocate a montgomery context if it was not supplied by the caller.
+	 * If this is not done, things will break in the montgomery part.
+ 	 */
+	if (in_mont != NULL)
+		mont=in_mont;
+	else
+		{
+		if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
+		if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
+		}
+
+	/* Get the window size to use with size of p. */
+	window = BN_window_bits_for_ctime_exponent_size(bits);
+
+	/* Allocate a buffer large enough to hold all of the pre-computed
+	 * powers of a.
+	 */
+	numPowers = 1 << window;
+	powerbufLen = sizeof(m->d[0])*top*numPowers;
+	if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL)
+		goto err;
+		
+	powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree);
+	memset(powerbuf, 0, powerbufLen);
+
+ 	/* Initialize the intermediate result. Do this early to save double conversion,
+	 * once each for a^0 and intermediate result.
+	 */
+ 	if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
+	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers)) goto err;
+
+	/* Initialize computeTemp as a^1 with montgomery precalcs */
+	computeTemp = BN_CTX_get(ctx);
+	am = BN_CTX_get(ctx);
+	if (computeTemp==NULL || am==NULL) goto err;
+
+	if (a->neg || BN_ucmp(a,m) >= 0)
+		{
+		if (!BN_mod(am,a,m,ctx))
+			goto err;
+		aa= am;
+		}
+	else
+		aa=a;
+	if (!BN_to_montgomery(am,aa,mont,ctx)) goto err;
+	if (!BN_copy(computeTemp, am)) goto err;
+	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers)) goto err;
+
+	/* If the window size is greater than 1, then calculate
+	 * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1)
+	 * (even powers could instead be computed as (a^(i/2))^2
+	 * to use the slight performance advantage of sqr over mul).
+	 */
+	if (window > 1)
+		{
+		for (i=2; i<numPowers; i++)
+			{
+			/* Calculate a^i = a^(i-1) * a */
+			if (!BN_mod_mul_montgomery(computeTemp,am,computeTemp,mont,ctx))
+				goto err;
+			if (!MOD_EXP_CTIME_COPY_TO_PREBUF(computeTemp, top, powerbuf, i, numPowers)) goto err;
+			}
+		}
+
+ 	/* Adjust the number of bits up to a multiple of the window size.
+ 	 * If the exponent length is not a multiple of the window size, then
+ 	 * this pads the most significant bits with zeros to normalize the
+ 	 * scanning loop to there's no special cases.
+ 	 *
+ 	 * * NOTE: Making the window size a power of two less than the native
+	 * * word size ensures that the padded bits won't go past the last
+ 	 * * word in the internal BIGNUM structure. Going past the end will
+ 	 * * still produce the correct result, but causes a different branch
+ 	 * * to be taken in the BN_is_bit_set function.
+ 	 */
+ 	bits = ((bits+window-1)/window)*window;
+ 	idx=bits-1;	/* The top bit of the window */
+
+ 	/* Scan the exponent one window at a time starting from the most
+ 	 * significant bits.
+ 	 */
+ 	while (idx >= 0)
+  		{
+ 		wvalue=0; /* The 'value' of the window */
+ 		
+ 		/* Scan the window, squaring the result as we go */
+ 		for (i=0; i<window; i++,idx--)
+ 			{
+			if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))	goto err;
+			wvalue = (wvalue<<1)+BN_is_bit_set(p,idx);
+  			}
+ 		
+		/* Fetch the appropriate pre-computed value from the pre-buf */
+		if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(computeTemp, top, powerbuf, wvalue, numPowers)) goto err;
+
+ 		/* Multiply the result into the intermediate result */
+ 		if (!BN_mod_mul_montgomery(r,r,computeTemp,mont,ctx)) goto err;
+  		}
+
+ 	/* Convert the final result from montgomery to standard format */
+	if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;
+	ret=1;
+err:
+	if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
+	if (powerbuf!=NULL)
+		{
+		OPENSSL_cleanse(powerbuf,powerbufLen);
+		OPENSSL_free(powerbufFree);
+		}
+ 	if (am!=NULL) BN_clear(am);
+ 	if (computeTemp!=NULL) BN_clear(computeTemp);
+	BN_CTX_end(ctx);
+	return(ret);
+	}
+
 int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
                          const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
 	{
@@ -519,6 +745,13 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
 #define BN_TO_MONTGOMERY_WORD(r, w, mont) \
 		(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
 
+	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
+		{
+		/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
+		BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+		return -1;
+		}
+
 	bn_check_top(p);
 	bn_check_top(m);
 
@@ -648,6 +881,13 @@ int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
 	/* Table of variables obtained from 'ctx' */
 	BIGNUM *val[TABLE_SIZE];
 
+	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
+		{
+		/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
+		BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+		return -1;
+		}
+
 	bits=BN_num_bits(p);
 
 	if (bits == 0)