add constant-time MOD_EXP_CTIME_COPY_FROM_PREBUF.

Patch based on OpenSSL commit d7a854c055ff22fb7da80c3b0e7cb08d248591d0

"Performance penalty varies from platform to platform, and even
key length. For rsa2048 sign it was observed to reach almost 10%."

CVE-2016-0702
ok beck@

1 files changed, 55 insertions, 16 deletions

diff --git a/lib/libcrypto/bn/bn_exp.c b/lib/libcrypto/bn/bn_exp.c
index 87b5775886b..64c8cbf3756 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.25 2016/09/03 17:21:38 bcook Exp $ */
+/* $OpenBSD: bn_exp.c,v 1.26 2016/09/03 17:26:29 bcook Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -115,6 +115,7 @@
 #include <openssl/err.h>
 
 #include "bn_lcl.h"
+#include "constant_time_locl.h"
 
 /* maximum precomputation table size for *variable* sliding windows */
 #define TABLE_SIZE	32
@@ -541,14 +542,17 @@ err:
 
 static int
 MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top, unsigned char *buf,
-    int idx, int width)
+    int idx, int window)
 {
-	size_t i, j;
+	int i, j;
+	int width = 1 << window;
+	BN_ULONG *table = (BN_ULONG *)buf;
 
 	if (top > b->top)
 		top = b->top; /* this works because 'buf' is explicitly zeroed */
-	for (i = 0, j = idx; i < top * sizeof b->d[0]; i++, j += width) {
-		buf[j] = ((unsigned char*)b->d)[i];
+
+	for (i = 0, j = idx; i < top; i++, j += width) {
+		table[j] = b->d[i];
 	}
 
 	return 1;
@@ -556,17 +560,52 @@ MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top, unsigned char *buf,
 
 static int
 MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx,
-    int width)
+    int window)
 {
-	size_t i, j;
+	int i, j;
+	int width = 1 << window;
+	volatile BN_ULONG *table = (volatile BN_ULONG *)buf;
 
 	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];
-	}
+	if (window <= 3) {
+		for (i = 0; i < top; i++, table += width) {
+		    BN_ULONG acc = 0;
+
+		    for (j = 0; j < width; j++) {
+			acc |= table[j] &
+			       ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));
+		    }
+
+		    b->d[i] = acc;
+		}
+	} else {
+		int xstride = 1 << (window - 2);
+		BN_ULONG y0, y1, y2, y3;
 
+		i = idx >> (window - 2);        /* equivalent of idx / xstride */
+		idx &= xstride - 1;             /* equivalent of idx % xstride */
+
+		y0 = (BN_ULONG)0 - (constant_time_eq_int(i,0)&1);
+		y1 = (BN_ULONG)0 - (constant_time_eq_int(i,1)&1);
+		y2 = (BN_ULONG)0 - (constant_time_eq_int(i,2)&1);
+		y3 = (BN_ULONG)0 - (constant_time_eq_int(i,3)&1);
+
+		for (i = 0; i < top; i++, table += width) {
+		    BN_ULONG acc = 0;
+
+		    for (j = 0; j < xstride; j++) {
+			acc |= ( (table[j + 0 * xstride] & y0) |
+				 (table[j + 1 * xstride] & y1) |
+				 (table[j + 2 * xstride] & y2) |
+				 (table[j + 3 * xstride] & y3) )
+			       & ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));
+		    }
+
+		    b->d[i] = acc;
+		}
+	}
 	b->top = top;
 	bn_correct_top(b);
 	return 1;
@@ -772,10 +811,10 @@ BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 #endif
 	{
 		if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 0,
-		    numPowers))
+		    window))
 			goto err;
 		if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&am,  top, powerbuf, 1,
-		    numPowers))
+		    window))
 			goto err;
 
 		/* If the window size is greater than 1, then calculate
@@ -787,7 +826,7 @@ BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 			if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx))
 				goto err;
 			if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf,
-			    2, numPowers))
+			    2, window))
 				goto err;
 			for (i = 3; i < numPowers; i++) {
 				/* Calculate a^i = a^(i-1) * a */
@@ -795,7 +834,7 @@ BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 				    mont, ctx))
 					goto err;
 				if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top,
-				    powerbuf, i, numPowers))
+				    powerbuf, i, window))
 					goto err;
 			}
 		}
@@ -804,7 +843,7 @@ BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 		for (wvalue = 0, i = bits % window; i >= 0; i--, bits--)
 			wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
 		if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&tmp, top, powerbuf,
-		    wvalue, numPowers))
+		    wvalue, window))
 			goto err;
 
 		/* Scan the exponent one window at a time starting from the most
@@ -823,7 +862,7 @@ BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
 
 			/* Fetch the appropriate pre-computed value from the pre-buf */
 			if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&am, top, powerbuf,
-			    wvalue, numPowers))
+			    wvalue, window))
 				goto err;
 
 			/* Multiply the result into the intermediate result */