Attachment #38361 for bug #86410

View | Details | Raw Unified | Return to bug 86410
Collapse All | Expand All





 Changes between 0.9.7g and 0.9.7h  [XX xxx XXXX]

  *) Make a new fixed-window mod_exp implementation the default for
     RSA, DSA, and DH private-key operations to mitigate the
     hyper-threading timing attacks pointed out by Colin Percival
     (http://www.daemonology.net/hyperthreading-considered-harmful/),
     and potential related attacks.

     BN_mod_exp_mont_consttime() is the new exponentiation implementation,
     and this is automatically used by BN_mod_exp_mont() if the new flag
     BN_FLG_EXP_CONSTTIME is set for the exponent.  RSA, DSA, and DH
     will use this BN flag for private exponents unless the flag
     RSA_FLAG_NO_EXP_CONSTTIME, DSA_FLAG_NO_EXP_CONSTTIME, or
     DH_FLAG_NO_EXP_CONSTTIME, respectively, is set.

     [Matthew D Wood (Intel Corp), with some changes by Bodo Moeller]

  *) Change the client implementation for SSLv23_method() and
     SSLv23_client_method() so that is uses the SSL 3.0/TLS 1.0
     Client Hello message format if the SSL_OP_NO_SSLv2 option is set.

Lines 1706-1712 Link Here

(-)apps/speed.c (-2 / +2 lines)
1706	k,rsa_bits[k],rsa_results[k][0],	1706	k,rsa_bits[k],rsa_results[k][0],
1707	rsa_results[k][1]);	1707	rsa_results[k][1]);
1708	else	1708	else
1709	fprintf(stdout,"rsa %4u bits %8.4fs %8.4fs %8.1f %8.1f\n",	1709	fprintf(stdout,"rsa %4u bits %8.6fs %8.6fs %8.1f %8.1f\n",
1710	rsa_bits[k],rsa_results[k][0],rsa_results[k][1],	1710	rsa_bits[k],rsa_results[k][0],rsa_results[k][1],
1711	1.0/rsa_results[k][0],1.0/rsa_results[k][1]);	1711	1.0/rsa_results[k][0],1.0/rsa_results[k][1]);
1712	}	1712	}
Lines 1725-1731 Link Here
1725	fprintf(stdout,"+F3:%u:%u:%f:%f\n",	1725	fprintf(stdout,"+F3:%u:%u:%f:%f\n",
1726	k,dsa_bits[k],dsa_results[k][0],dsa_results[k][1]);	1726	k,dsa_bits[k],dsa_results[k][0],dsa_results[k][1]);
1727	else	1727	else
1728	fprintf(stdout,"dsa %4u bits %8.4fs %8.4fs %8.1f %8.1f\n",	1728	fprintf(stdout,"dsa %4u bits %8.6fs %8.6fs %8.1f %8.1f\n",
1729	dsa_bits[k],dsa_results[k][0],dsa_results[k][1],	1729	dsa_bits[k],dsa_results[k][0],dsa_results[k][1],
1730	1.0/dsa_results[k][0],1.0/dsa_results[k][1]);	1730	1.0/dsa_results[k][0],1.0/dsa_results[k][1]);
1731	}	1731	}

Lines 225-234 Link Here

(-)crypto/bn/bn.h (+17 lines)
225		225
226	#define BN_FLG_MALLOCED 0x01	226	#define BN_FLG_MALLOCED 0x01
227	#define BN_FLG_STATIC_DATA 0x02	227	#define BN_FLG_STATIC_DATA 0x02
		228	#define BN_FLG_EXP_CONSTTIME 0x04 /* avoid leaking exponent information through timings
		229	* (BN_mod_exp_mont() will call BN_mod_exp_mont_consttime) */
228	#define BN_FLG_FREE 0x8000 /* used for debuging */	230	#define BN_FLG_FREE 0x8000 /* used for debuging */
229	#define BN_set_flags(b,n) ((b)->flags\|=(n))	231	#define BN_set_flags(b,n) ((b)->flags\|=(n))
230	#define BN_get_flags(b,n) ((b)->flags&(n))	232	#define BN_get_flags(b,n) ((b)->flags&(n))
231		233
		234	#define BN_with_flags(dest,b,n) ((dest)->d=(b)->d, \
		235	(dest)->top=(b)->top, \
		236	(dest)->dmax=(b)->dmax, \
		237	(dest)->neg=(b)->neg, \
		238	(dest)->flags=(((dest)->flags & BN_FLG_MALLOCED) \
		239	\| ((b)->flags & ~BN_FLG_MALLOCED) \
		240	\| BN_FLG_STATIC_DATA \
		241	\| (n)))
		242
232	typedef struct bignum_st	243	typedef struct bignum_st
233	{	244	{
234	BN_ULONG d; / Pointer to an array of 'BN_BITS2' bit chunks. */	245	BN_ULONG d; / Pointer to an array of 'BN_BITS2' bit chunks. */
Lines 378-383 Link Here
378	const BIGNUM m,BN_CTX ctx);	389	const BIGNUM m,BN_CTX ctx);
379	int BN_mod_exp_mont(BIGNUM r, const BIGNUM a, const BIGNUM *p,	390	int BN_mod_exp_mont(BIGNUM r, const BIGNUM a, const BIGNUM *p,
380	const BIGNUM m, BN_CTX ctx, BN_MONT_CTX *m_ctx);	391	const BIGNUM m, BN_CTX ctx, BN_MONT_CTX *m_ctx);
		392	int BN_mod_exp_mont_consttime(BIGNUM rr, const BIGNUM a, const BIGNUM *p,
		393	const BIGNUM m, BN_CTX ctx, BN_MONT_CTX *in_mont);
381	int BN_mod_exp_mont_word(BIGNUM r, BN_ULONG a, const BIGNUM p,	394	int BN_mod_exp_mont_word(BIGNUM r, BN_ULONG a, const BIGNUM p,
382	const BIGNUM m, BN_CTX ctx, BN_MONT_CTX *m_ctx);	395	const BIGNUM m, BN_CTX ctx, BN_MONT_CTX *m_ctx);
383	int BN_mod_exp2_mont(BIGNUM r, const BIGNUM a1, const BIGNUM *p1,	396	int BN_mod_exp2_mont(BIGNUM r, const BIGNUM a1, const BIGNUM *p1,
Lines 512-522 Link Here
512	#define BN_F_BN_CTX_GET 116	525	#define BN_F_BN_CTX_GET 116
513	#define BN_F_BN_CTX_NEW 106	526	#define BN_F_BN_CTX_NEW 106
514	#define BN_F_BN_DIV 107	527	#define BN_F_BN_DIV 107
		528	#define BN_F_BN_EXP 123
515	#define BN_F_BN_EXPAND2 108	529	#define BN_F_BN_EXPAND2 108
516	#define BN_F_BN_EXPAND_INTERNAL 120	530	#define BN_F_BN_EXPAND_INTERNAL 120
517	#define BN_F_BN_MOD_EXP2_MONT 118	531	#define BN_F_BN_MOD_EXP2_MONT 118
518	#define BN_F_BN_MOD_EXP_MONT 109	532	#define BN_F_BN_MOD_EXP_MONT 109
		533	#define BN_F_BN_MOD_EXP_MONT_CONSTTIME 124
519	#define BN_F_BN_MOD_EXP_MONT_WORD 117	534	#define BN_F_BN_MOD_EXP_MONT_WORD 117
		535	#define BN_F_BN_MOD_EXP_RECP 125
		536	#define BN_F_BN_MOD_EXP_SIMPLE 126
520	#define BN_F_BN_MOD_INVERSE 110	537	#define BN_F_BN_MOD_INVERSE 110
521	#define BN_F_BN_MOD_LSHIFT_QUICK 119	538	#define BN_F_BN_MOD_LSHIFT_QUICK 119
522	#define BN_F_BN_MOD_MUL_RECIPROCAL 111	539	#define BN_F_BN_MOD_MUL_RECIPROCAL 111

Lines 56-62 Link Here

(-)crypto/bn/bn_exp.c (-2 / +242 lines)
56	* [including the GNU Public Licence.]	56	* [including the GNU Public Licence.]
57	*/	57	*/
58	/* ====================================================================	58	/* ====================================================================
59	* Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.	59	* Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
60	*	60	*
61	* Redistribution and use in source and binary forms, with or without	61	* Redistribution and use in source and binary forms, with or without
62	* modification, are permitted provided that the following conditions	62	* modification, are permitted provided that the following conditions
Lines 113-118 Link Here
113	#include "cryptlib.h"	113	#include "cryptlib.h"
114	#include "bn_lcl.h"	114	#include "bn_lcl.h"
115		115
		116	/* maximum precomputation table size for variable sliding windows */
116	#define TABLE_SIZE 32	117	#define TABLE_SIZE 32
117		118
118	/* this one works - simple but works */	119	/* this one works - simple but works */
Lines 121-126 Link Here
121	int i,bits,ret=0;	122	int i,bits,ret=0;
122	BIGNUM v,rr;	123	BIGNUM v,rr;
123		124
		125	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
		126	{
		127	/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
		128	BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
		129	return -1;
		130	}
		131
124	BN_CTX_start(ctx);	132	BN_CTX_start(ctx);
125	if ((r == a) \|\| (r == p))	133	if ((r == a) \|\| (r == p))
126	rr = BN_CTX_get(ctx);	134	rr = BN_CTX_get(ctx);
Lines 204-210 Link Here
204	if (BN_is_odd(m))	212	if (BN_is_odd(m))
205	{	213	{
206	# ifdef MONT_EXP_WORD	214	# ifdef MONT_EXP_WORD
207	if (a->top == 1 && !a->neg)	215	if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) == 0))
208	{	216	{
209	BN_ULONG A = a->d[0];	217	BN_ULONG A = a->d[0];
210	ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);	218	ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
Lines 234-239 Link Here
234	BIGNUM val[TABLE_SIZE];	242	BIGNUM val[TABLE_SIZE];
235	BN_RECP_CTX recp;	243	BN_RECP_CTX recp;
236		244
		245	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
		246	{
		247	/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
		248	BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
		249	return -1;
		250	}
		251
237	bits=BN_num_bits(p);	252	bits=BN_num_bits(p);
238		253
239	if (bits == 0)	254	if (bits == 0)
Lines 361-366 Link Here
361	BIGNUM val[TABLE_SIZE];	376	BIGNUM val[TABLE_SIZE];
362	BN_MONT_CTX *mont=NULL;	377	BN_MONT_CTX *mont=NULL;
363		378
		379	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
		380	{
		381	return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);
		382	}
		383
364	bn_check_top(a);	384	bn_check_top(a);
365	bn_check_top(p);	385	bn_check_top(p);
366	bn_check_top(m);	386	bn_check_top(m);
Lines 493-498 Link Here
493	return(ret);	513	return(ret);
494	}	514	}
495		515
		516
		517	/* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout
		518	* so that accessing any of these table values shows the same access pattern as far
		519	* as cache lines are concerned. The following functions are used to transfer a BIGNUM
		520	* from/to that table. */
		521
		522	static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM b, int top, unsigned char buf, int idx, int width)
		523	{
		524	size_t i, j;
		525
		526	if (bn_wexpand(b, top) == NULL)
		527	return 0;
		528	while (b->top < top)
		529	{
		530	b->d[b->top++] = 0;
		531	}
		532
		533	for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)
		534	{
		535	buf[j] = ((unsigned char*)b->d)[i];
		536	}
		537
		538	bn_fix_top(b);
		539	return 1;
		540	}
		541
		542	static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM b, int top, unsigned char buf, int idx, int width)
		543	{
		544	size_t i, j;
		545
		546	if (bn_wexpand(b, top) == NULL)
		547	return 0;
		548
		549	for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)
		550	{
		551	((unsigned char*)b->d)[i] = buf[j];
		552	}
		553
		554	b->top = top;
		555	bn_fix_top(b);
		556	return 1;
		557	}
		558
		559	/* Given a pointer value, compute the next address that is a cache line multiple. */
		560	#define MOD_EXP_CTIME_ALIGN(x_) \
		561	((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((BN_ULONG)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK))))
		562
		563	/* This variant of BN_mod_exp_mont() uses fixed windows and the special
		564	* precomputation memory layout to limit data-dependency to a minimum
		565	* to protect secret exponents (cf. the hyper-threading timing attacks
		566	* pointed out by Colin Percival,
		567	* http://www.daemonology.net/hyperthreading-considered-harmful/)
		568	*/
		569	int BN_mod_exp_mont_consttime(BIGNUM rr, const BIGNUM a, const BIGNUM *p,
		570	const BIGNUM m, BN_CTX ctx, BN_MONT_CTX *in_mont)
		571	{
		572	int i,bits,ret=0,idx,window,wvalue;
		573	int top;
		574	BIGNUM *r;
		575	const BIGNUM *aa;
		576	BN_MONT_CTX *mont=NULL;
		577
		578	int numPowers;
		579	unsigned char *powerbufFree=NULL;
580	int powerbufLen = 0;
581	unsigned char *powerbuf=NULL;
582	BIGNUM computeTemp=NULL, am=NULL;
583
584	bn_check_top(a);
585	bn_check_top(p);
586	bn_check_top(m);
587
588	top = m->top;
589
590	if (!(m->d[0] & 1))
591	{
592	BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS);
593	return(0);
594	}
595	bits=BN_num_bits(p);
596	if (bits == 0)
597	{
598	ret = BN_one(rr);
599	return ret;
600	}
601
602	/* Initialize BIGNUM context and allocate intermediate result */
603	BN_CTX_start(ctx);
604	r = BN_CTX_get(ctx);
605	if (r == NULL) goto err;
606
607	/* Allocate a montgomery context if it was not supplied by the caller.
608	* If this is not done, things will break in the montgomery part.
609	*/
610	if (in_mont != NULL)
611	mont=in_mont;
612	else
613	{
614	if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
615	if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
616	}
617
618	/* Get the window size to use with size of p. */
619	window = BN_window_bits_for_ctime_exponent_size(bits);
620
621	/* Allocate a buffer large enough to hold all of the pre-computed
622	* powers of a.
623	*/
624	numPowers = 1 << window;
625	powerbufLen = sizeof(m->d[0])topnumPowers;
626	if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL)
627	goto err;
628
629	powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree);
630	memset(powerbuf, 0, powerbufLen);
631
632	/* Initialize the intermediate result. Do this early to save double conversion,
633	* once each for a^0 and intermediate result.
634	*/
635	if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
636	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers)) goto err;
637
638	/* Initialize computeTemp as a^1 with montgomery precalcs */
639	computeTemp = BN_CTX_get(ctx);
640	am = BN_CTX_get(ctx);
641	if (computeTemp==NULL \|\| am==NULL) goto err;
642
643	if (a->neg \|\| BN_ucmp(a,m) >= 0)
644	{
645	if (!BN_mod(am,a,m,ctx))
646	goto err;
647	aa= am;
648	}
649	else
650	aa=a;
651	if (!BN_to_montgomery(am,aa,mont,ctx)) goto err;
652	if (!BN_copy(computeTemp, am)) goto err;
653	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers)) goto err;
654
655	/* If the window size is greater than 1, then calculate
656	* val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1)
657	* (even powers could instead be computed as (a^(i/2))^2
658	* to use the slight performance advantage of sqr over mul).
659	*/
660	if (window > 1)
661	{
662	for (i=2; i<numPowers; i++)
663	{
664	/* Calculate a^i = a^(i-1) * a */
665	if (!BN_mod_mul_montgomery(computeTemp,am,computeTemp,mont,ctx))
666	goto err;
667	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(computeTemp, top, powerbuf, i, numPowers)) goto err;
668	}
669	}
670
671	/* Adjust the number of bits up to a multiple of the window size.
672	* If the exponent length is not a multiple of the window size, then
673	* this pads the most significant bits with zeros to normalize the
674	* scanning loop to there's no special cases.
675	*
676	* * NOTE: Making the window size a power of two less than the native
677	* * word size ensures that the padded bits won't go past the last
678	* * word in the internal BIGNUM structure. Going past the end will
679	* * still produce the correct result, but causes a different branch
680	* * to be taken in the BN_is_bit_set function.
681	*/
682	bits = ((bits+window-1)/window)*window;
683	idx=bits-1; /* The top bit of the window */
684
685	/* Scan the exponent one window at a time starting from the most
686	* significant bits.
687	*/
688	while (idx >= 0)
689	{
690	wvalue=0; /* The 'value' of the window */
691
692	/* Scan the window, squaring the result as we go */
693	for (i=0; i<window; i++,idx--)
694	{
695	if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) goto err;
696	wvalue = (wvalue<<1)+BN_is_bit_set(p,idx);
697	}
698
699	/* Fetch the appropriate pre-computed value from the pre-buf */
700	if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(computeTemp, top, powerbuf, wvalue, numPowers)) goto err;
701
702	/* Multiply the result into the intermediate result */
703	if (!BN_mod_mul_montgomery(r,r,computeTemp,mont,ctx)) goto err;
704	}
705
706	/* Convert the final result from montgomery to standard format */
707	if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;
708	ret=1;
709	err:
710	if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
711	if (powerbuf!=NULL)
712	{
713	OPENSSL_cleanse(powerbuf,powerbufLen);
714	OPENSSL_free(powerbufFree);
715	}
716	if (am!=NULL) BN_clear(am);
717	if (computeTemp!=NULL) BN_clear(computeTemp);
718	BN_CTX_end(ctx);
719	return(ret);
720	}
721
496	int BN_mod_exp_mont_word(BIGNUM rr, BN_ULONG a, const BIGNUM p,	722	int BN_mod_exp_mont_word(BIGNUM rr, BN_ULONG a, const BIGNUM p,
497	const BIGNUM m, BN_CTX ctx, BN_MONT_CTX *in_mont)	723	const BIGNUM m, BN_CTX ctx, BN_MONT_CTX *in_mont)
498	{	724	{
Lines 517-522 Link Here
517	#define BN_TO_MONTGOMERY_WORD(r, w, mont) \	743	#define BN_TO_MONTGOMERY_WORD(r, w, mont) \
518	(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))	744	(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
519		745
		746	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
		747	{
		748	/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
		749	BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
		750	return -1;
		751	}
		752
520	bn_check_top(p);	753	bn_check_top(p);
521	bn_check_top(m);	754	bn_check_top(m);
522		755
Lines 644-649 Link Here
644	BIGNUM *d;	877	BIGNUM *d;
645	BIGNUM val[TABLE_SIZE];	878	BIGNUM val[TABLE_SIZE];
646		879
		880	if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
		881	{
		882	/* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
		883	BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
		884	return -1;
		885	}
		886
647	bits=BN_num_bits(p);	887	bits=BN_num_bits(p);
648		888
649	if (bits == 0)	889	if (bits == 0)







/* BN_mod_exp_mont_conttime is based on the assumption that the
 * L1 data cache line width of the target processor is at least
 * the following value.
 */
#define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH	( 64 )
#define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK	(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1)

/* Window sizes optimized for fixed window size modular exponentiation
 * algorithm (BN_mod_exp_mont_consttime).
 *
 * To achieve the security goals of BN_mode_exp_mont_consttime, the
 * maximum size of the window must not exceed
 * log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH). 
 *
 * Window size thresholds are defined for cache line sizes of 32 and 64,
 * cache line sizes where log_2(32)=5 and log_2(64)=6 respectively. A
 * window size of 7 should only be used on processors that have a 128
 * byte or greater cache line size.
 */
#if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64

#  define BN_window_bits_for_ctime_exponent_size(b) \
		((b) > 937 ? 6 : \
		 (b) > 306 ? 5 : \
		 (b) >  89 ? 4 : \
		 (b) >  22 ? 3 : 1)
#  define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE	(6)

#elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32

#  define BN_window_bits_for_ctime_exponent_size(b) \
		((b) > 306 ? 5 : \
		 (b) >  89 ? 4 : \
		 (b) >  22 ? 3 : 1)
#  define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE	(5)

#endif


/* Pentium pro 16,16,16,32,64 */
/* Alpha       16,16,16,16.64 */
#define BN_MULL_SIZE_NORMAL			(16) /* 32 */

Lines 86-91 Link Here

(-)crypto/bn/bntest.c (+56 lines)
86	int test_mod(BIO bp,BN_CTX ctx);	86	int test_mod(BIO bp,BN_CTX ctx);
87	int test_mod_mul(BIO bp,BN_CTX ctx);	87	int test_mod_mul(BIO bp,BN_CTX ctx);
88	int test_mod_exp(BIO bp,BN_CTX ctx);	88	int test_mod_exp(BIO bp,BN_CTX ctx);
		89	int test_mod_exp_mont_consttime(BIO bp,BN_CTX ctx);
89	int test_exp(BIO bp,BN_CTX ctx);	90	int test_exp(BIO bp,BN_CTX ctx);
90	int test_kron(BIO bp,BN_CTX ctx);	91	int test_kron(BIO bp,BN_CTX ctx);
91	int test_sqrt(BIO bp,BN_CTX ctx);	92	int test_sqrt(BIO bp,BN_CTX ctx);
Lines 213-218 Link Here
213	if (!test_mod_exp(out,ctx)) goto err;	214	if (!test_mod_exp(out,ctx)) goto err;
214	BIO_flush(out);	215	BIO_flush(out);
215		216
		217	message(out,"BN_mod_exp_mont_consttime");
		218	if (!test_mod_exp_mont_consttime(out,ctx)) goto err;
		219	BIO_flush(out);
		220
216	message(out,"BN_exp");	221	message(out,"BN_exp");
217	if (!test_exp(out,ctx)) goto err;	222	if (!test_exp(out,ctx)) goto err;
218	BIO_flush(out);	223	BIO_flush(out);
Lines 813-818 Link Here
813	return(1);	818	return(1);
814	}	819	}
815		820
		821	int test_mod_exp_mont_consttime(BIO bp, BN_CTX ctx)
		822	{
		823	BIGNUM a,b,c,d,*e;
		824	int i;
		825
		826	a=BN_new();
		827	b=BN_new();
		828	c=BN_new();
		829	d=BN_new();
		830	e=BN_new();
		831
		832	BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
		833	for (i=0; i<num2; i++)
		834	{
		835	BN_bntest_rand(a,20+i5,0,0); /*/
		836	BN_bntest_rand(b,2+i,0,0); /**/
		837
		838	if (!BN_mod_exp_mont_consttime(d,a,b,c,ctx,NULL))
		839	return(00);
		840
		841	if (bp != NULL)
		842	{
		843	if (!results)
		844	{
		845	BN_print(bp,a);
		846	BIO_puts(bp," ^ ");
		847	BN_print(bp,b);
		848	BIO_puts(bp," % ");
		849	BN_print(bp,c);
		850	BIO_puts(bp," - ");
		851	}
		852	BN_print(bp,d);
		853	BIO_puts(bp,"\n");
		854	}
		855	BN_exp(e,a,b,ctx);
		856	BN_sub(e,e,d);
		857	BN_div(a,b,e,c,ctx);
		858	if(!BN_is_zero(b))
		859	{
		860	fprintf(stderr,"Modulo exponentiation test failed!\n");
		861	return 0;
		862	}
		863	}
		864	BN_free(a);
		865	BN_free(b);
		866	BN_free(c);
		867	BN_free(d);
		868	BN_free(e);
		869	return(1);
		870	}
		871
816	int test_exp(BIO bp, BN_CTX ctx)	872	int test_exp(BIO bp, BN_CTX ctx)
817	{	873	{
818	BIGNUM a,b,d,e,*one;	874	BIGNUM a,b,d,e,*one;

Lines 321-327 Link Here

(-)crypto/bn/expspeed.c (-1 / +1 lines)
321	#else /* TEST_SQRT */	321	#else /* TEST_SQRT */
322	"2*sqrt [prime == %d (mod 64)] %4d %4d mod %4d"	322	"2*sqrt [prime == %d (mod 64)] %4d %4d mod %4d"
323	#endif	323	#endif
324	" -> %8.3fms %5.1f (%ld)\n",	324	" -> %8.6fms %5.1f (%ld)\n",
325	#ifdef TEST_SQRT	325	#ifdef TEST_SQRT
326	P_MOD_64,	326	P_MOD_64,
327	#endif	327	#endif




	BIO *out=NULL;
	int i,ret;
	unsigned char c;
	BIGNUM *r_mont,*r_mont_const,*r_recp,*r_simple,*a,*b,*m;

	RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_rand may fail, and we don't
	                                       * even check its return value

	ctx=BN_CTX_new();
	if (ctx == NULL) EXIT(1);
	r_mont=BN_new();
	r_mont_const=BN_new();
	r_recp=BN_new();
	r_simple=BN_new();
	a=BN_new();

			EXIT(1);
			}

		ret=BN_mod_exp_mont_consttime(r_mont_const,a,b,m,ctx,NULL);
		if (ret <= 0)
			{
			printf("BN_mod_exp_mont_consttime() problems\n");
			ERR_print_errors(out);
			EXIT(1);
			}

		if (BN_cmp(r_simple, r_mont) == 0
		    && BN_cmp(r_simple,r_recp) == 0
			&& BN_cmp(r_simple,r_mont_const) == 0)
			{
			printf(".");
			fflush(stdout);

		  	{
			if (BN_cmp(r_simple,r_mont) != 0)
				printf("\nsimple and mont results differ\n");
			if (BN_cmp(r_simple,r_mont) != 0)
				printf("\nsimple and mont const time results differ\n");
			if (BN_cmp(r_simple,r_recp) != 0)
				printf("\nsimple and recp results differ\n");


			printf("\nsimple   =");	BN_print(out,r_simple);
			printf("\nrecp     =");	BN_print(out,r_recp);
			printf("\nmont     ="); BN_print(out,r_mont);
			printf("\nmont_ct  ="); BN_print(out,r_mont_const);
			printf("\n");
			EXIT(1);
			}
		}
	BN_free(r_mont);
	BN_free(r_mont_const);
	BN_free(r_recp);
	BN_free(r_simple);
	BN_free(a);

Lines 70-76 Link Here

(-)crypto/dh/dh.h (-1 / +8 lines)
70	#include <openssl/crypto.h>	70	#include <openssl/crypto.h>
71	#include <openssl/ossl_typ.h>	71	#include <openssl/ossl_typ.h>
72		72
73	#define DH_FLAG_CACHE_MONT_P 0x01	73	#define DH_FLAG_CACHE_MONT_P 0x01
		74	#define DH_FLAG_NO_EXP_CONSTTIME 0x02 /* new with 0.9.7h; the built-in DH
		75	* implementation now uses constant time
		76	* modular exponentiation for secret exponents
		77	* by default. This flag causes the
		78	* faster variable sliding window method to
		79	* be used for all exponents.
		80	*/
74		81
75	#ifdef __cplusplus	82	#ifdef __cplusplus
76	extern "C" {	83	extern "C" {

Lines 143-150 Link Here

(-)crypto/dh/dh_key.c (-3 / +24 lines)
143	l = dh->length ? dh->length : BN_num_bits(dh->p)-1; /* secret exponent length */	143	l = dh->length ? dh->length : BN_num_bits(dh->p)-1; /* secret exponent length */
144	if (!BN_rand(priv_key, l, 0, 0)) goto err;	144	if (!BN_rand(priv_key, l, 0, 0)) goto err;
145	}	145	}
146	if (!dh->meth->bn_mod_exp(dh, pub_key, dh->g, priv_key,dh->p,ctx,mont))	146
147	goto err;	147	{
		148	BIGNUM local_prk;
		149	BIGNUM *prk;
		150
		151	if ((dh->flags & DH_FLAG_NO_EXP_CONSTTIME) == 0)
		152	{
		153	prk = &local_prk;
		154	BN_with_flags(prk, priv_key, BN_FLG_EXP_CONSTTIME);
		155	}
		156	else
		157	prk = priv_key;
		158
		159	if (!dh->meth->bn_mod_exp(dh, pub_key, dh->g, prk, dh->p, ctx, mont)) goto err;
		160	}
148		161
149	dh->pub_key=pub_key;	162	dh->pub_key=pub_key;
150	dh->priv_key=priv_key;	163	dh->priv_key=priv_key;
Lines 182-187 Link Here
182	mont = BN_MONT_CTX_set_locked(	195	mont = BN_MONT_CTX_set_locked(
183	(BN_MONT_CTX **)&dh->method_mont_p,	196	(BN_MONT_CTX **)&dh->method_mont_p,
184	CRYPTO_LOCK_DH, dh->p, ctx);	197	CRYPTO_LOCK_DH, dh->p, ctx);
		198	if ((dh->flags & DH_FLAG_NO_EXP_CONSTTIME) == 0)
		199	{
		200	/* XXX */
		201	BN_set_flags(dh->priv_key, BN_FLG_EXP_CONSTTIME);
		202	}
185	if (!mont)	203	if (!mont)
186	goto err;	204	goto err;
187	}	205	}
Lines 204-210 Link Here
204	const BIGNUM m, BN_CTX ctx,	222	const BIGNUM m, BN_CTX ctx,
205	BN_MONT_CTX *m_ctx)	223	BN_MONT_CTX *m_ctx)
206	{	224	{
207	if (a->top == 1)	225	/* If a is only one word long and constant time is false, use the faster
		226	* exponenentiation function.
		227	*/
		228	if (a->top == 1 && ((dh->flags & DH_FLAG_NO_EXP_CONSTTIME) != 0))
208	{	229	{
209	BN_ULONG A = a->d[0];	230	BN_ULONG A = a->d[0];
210	return BN_mod_exp_mont_word(r,A,p,m,ctx,m_ctx);	231	return BN_mod_exp_mont_word(r,A,p,m,ctx,m_ctx);

Lines 136-141 Link Here

(-)crypto/dh/dhtest.c (+4 lines)
136	b->g=BN_dup(a->g);	136	b->g=BN_dup(a->g);
137	if ((b->p == NULL) \|\| (b->g == NULL)) goto err;	137	if ((b->p == NULL) \|\| (b->g == NULL)) goto err;
138		138
		139	/* Set a to run with normal modexp and b to use constant time */
		140	a->flags &= ~DH_FLAG_NO_EXP_CONSTTIME;
		141	b->flags \|= DH_FLAG_NO_EXP_CONSTTIME;
		142
139	if (!DH_generate_key(a)) goto err;	143	if (!DH_generate_key(a)) goto err;
140	BIO_puts(out,"pri 1=");	144	BIO_puts(out,"pri 1=");
141	BN_print(out,a->priv_key);	145	BN_print(out,a->priv_key);

Lines 80-85 Link Here

(-)crypto/dsa/dsa.h (+7 lines)
80	#endif	80	#endif
81		81
82	#define DSA_FLAG_CACHE_MONT_P 0x01	82	#define DSA_FLAG_CACHE_MONT_P 0x01
		83	#define DSA_FLAG_NO_EXP_CONSTTIME 0x02 /* new with 0.9.7h; the built-in DSA
		84	* implementation now uses constant time
		85	* modular exponentiation for secret exponents
		86	* by default. This flag causes the
		87	* faster variable sliding window method to
		88	* be used for all exponents.
		89	*/
83		90
84	#if defined(OPENSSL_FIPS)	91	#if defined(OPENSSL_FIPS)
85	#define FIPS_DSA_SIZE_T int	92	#define FIPS_DSA_SIZE_T int

Lines 90-97 Link Here

(-)crypto/dsa/dsa_key.c (-1 / +14 lines)
90	}	90	}
91	else	91	else
92	pub_key=dsa->pub_key;	92	pub_key=dsa->pub_key;
		93
		94	{
		95	BIGNUM local_prk;
		96	BIGNUM *prk;
93		97
94	if (!BN_mod_exp(pub_key,dsa->g,priv_key,dsa->p,ctx)) goto err;	98	if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0)
		99	{
		100	prk = &local_prk;
		101	BN_with_flags(prk, priv_key, BN_FLG_EXP_CONSTTIME);
		102	}
		103	else
		104	prk = priv_key;
		105
		106	if (!BN_mod_exp(pub_key,dsa->g,prk,dsa->p,ctx)) goto err;
		107	}
95		108
96	dsa->priv_key=priv_key;	109	dsa->priv_key=priv_key;
97	dsa->pub_key=pub_key;	110	dsa->pub_key=pub_key;

Lines 197-202 Link Here

(-)crypto/dsa/dsa_ossl.c (+4 lines)
197	do	197	do
198	if (!BN_rand_range(&k, dsa->q)) goto err;	198	if (!BN_rand_range(&k, dsa->q)) goto err;
199	while (BN_is_zero(&k));	199	while (BN_is_zero(&k));
		200	if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0)
		201	{
		202	BN_set_flags(&k, BN_FLG_EXP_CONSTTIME);
		203	}
200		204
201	if (dsa->flags & DSA_FLAG_CACHE_MONT_P)	205	if (dsa->flags & DSA_FLAG_CACHE_MONT_P)
202	{	206	{

Lines 194-203 Link Here

(-)crypto/dsa/dsatest.c (+9 lines)
194	BIO_printf(bio_err,"g value is wrong\n");	194	BIO_printf(bio_err,"g value is wrong\n");
195	goto end;	195	goto end;
196	}	196	}
		197
		198	dsa->flags \|= DSA_FLAG_NO_EXP_CONSTTIME;
197	DSA_generate_key(dsa);	199	DSA_generate_key(dsa);
198	DSA_sign(0, str1, 20, sig, &siglen, dsa);	200	DSA_sign(0, str1, 20, sig, &siglen, dsa);
199	if (DSA_verify(0, str1, 20, sig, siglen, dsa) == 1)	201	if (DSA_verify(0, str1, 20, sig, siglen, dsa) == 1)
200	ret=1;	202	ret=1;
		203
		204	dsa->flags &= ~DSA_FLAG_NO_EXP_CONSTTIME;
		205	DSA_generate_key(dsa);
		206	DSA_sign(0, str1, 20, sig, &siglen, dsa);
		207	if (DSA_verify(0, str1, 20, sig, siglen, dsa) == 1)
		208	ret=1;
		209
201	end:	210	end:
202	if (!ret)	211	if (!ret)
203	ERR_print_errors(bio_err);	212	ERR_print_errors(bio_err);




#define RSA_3	0x3L
#define RSA_F4	0x10001L

#define RSA_METHOD_FLAG_NO_CHECK	0x0001 /* don't check pub/private match */

#define RSA_FLAG_CACHE_PUBLIC		0x0002
#define RSA_FLAG_CACHE_PRIVATE		0x0004
#define RSA_FLAG_BLINDING		0x0008
#define RSA_FLAG_THREAD_SAFE		0x0010
/* This flag means the private key operations will be handled by rsa_mod_exp
 * and that they do not depend on the private key components being present:
 * for example a key stored in external hardware. Without this flag bn_mod_exp
 * gets called when private key components are absent.
 */
#define RSA_FLAG_EXT_PKEY		0x0020

/* This flag in the RSA_METHOD enables the new rsa_sign, rsa_verify functions.
 */
#define RSA_FLAG_SIGN_VER		0x0040

#define RSA_FLAG_NO_BLINDING		0x0080 /* new with 0.9.6j and 0.9.7b; the built-in
                                                * RSA implementation now uses blinding by
                                                * default (ignoring RSA_FLAG_BLINDING),
                                                * but other engines might not need it
                                                */
#define RSA_FLAG_NO_EXP_CONSTTIME	0x0100 /* new with 0.9.7h; the built-in RSA
                                                * implementation now uses constant time
                                                * modular exponentiation for secret exponents
                                                * by default. This flag causes the
                                                * faster variable sliding window method to
                                                * be used for all exponents.
                                                */

#define RSA_PKCS1_PADDING	1
#define RSA_SSLV23_PADDING	2

Lines 314-323 Link Here

(-)crypto/rsa/rsa_eay.c (-7 / +60 lines)
314	(rsa->dmp1 != NULL) &&	314	(rsa->dmp1 != NULL) &&
315	(rsa->dmq1 != NULL) &&	315	(rsa->dmq1 != NULL) &&
316	(rsa->iqmp != NULL)) )	316	(rsa->iqmp != NULL)) )
317	{ if (!rsa->meth->rsa_mod_exp(&ret,&f,rsa)) goto err; }	317	{
		318	if (!rsa->meth->rsa_mod_exp(&ret,&f,rsa)) goto err;
		319	}
318	else	320	else
319	{	321	{
320	if (!rsa->meth->bn_mod_exp(&ret,&f,rsa->d,rsa->n,ctx,NULL)) goto err;	322	BIGNUM local_d;
		323	BIGNUM *d = NULL;
		324
		325	if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
		326	{
		327	d = &local_d;
		328	BN_with_flags(d, rsa->d, BN_FLG_EXP_CONSTTIME);
		329	}
		330	else
		331	d = rsa->d;
		332	if (!rsa->meth->bn_mod_exp(&ret,&f,d,rsa->n,ctx,NULL)) goto err;
321	}	333	}
322		334
323	if (blinding)	335	if (blinding)
Lines 427-436 Link Here
427	(rsa->dmp1 != NULL) &&	439	(rsa->dmp1 != NULL) &&
428	(rsa->dmq1 != NULL) &&	440	(rsa->dmq1 != NULL) &&
429	(rsa->iqmp != NULL)) )	441	(rsa->iqmp != NULL)) )
430	{ if (!rsa->meth->rsa_mod_exp(&ret,&f,rsa)) goto err; }	442	{
		443	if (!rsa->meth->rsa_mod_exp(&ret,&f,rsa)) goto err;
		444	}
431	else	445	else
432	{	446	{
433	if (!rsa->meth->bn_mod_exp(&ret,&f,rsa->d,rsa->n,ctx,NULL))	447	BIGNUM local_d;
		448	BIGNUM *d = NULL;
		449
		450	if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
		451	{
		452	d = &local_d;
		453	BN_with_flags(d, rsa->d, BN_FLG_EXP_CONSTTIME);
		454	}
		455	else
		456	d = rsa->d;
		457	if (!rsa->meth->bn_mod_exp(&ret,&f,d,rsa->n,ctx,NULL))
434	goto err;	458	goto err;
435	}	459	}
436		460
Lines 561-566 Link Here
561	static int RSA_eay_mod_exp(BIGNUM r0, const BIGNUM I, RSA *rsa)	585	static int RSA_eay_mod_exp(BIGNUM r0, const BIGNUM I, RSA *rsa)
562	{	586	{
563	BIGNUM r1,m1,vrfy;	587	BIGNUM r1,m1,vrfy;
		588	BIGNUM local_dmp1, local_dmq1;
		589	BIGNUM dmp1, dmq1;
564	int ret=0;	590	int ret=0;
565	BN_CTX *ctx;	591	BN_CTX *ctx;
566		592
Lines 580-590 Link Here
580	}	606	}
581		607
582	if (!BN_mod(&r1,I,rsa->q,ctx)) goto err;	608	if (!BN_mod(&r1,I,rsa->q,ctx)) goto err;
583	if (!rsa->meth->bn_mod_exp(&m1,&r1,rsa->dmq1,rsa->q,ctx,	609	if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
		610	{
		611	dmq1 = &local_dmq1;
		612	BN_with_flags(dmq1, rsa->dmq1, BN_FLG_EXP_CONSTTIME);
		613	}
		614	else
		615	dmq1 = rsa->dmq1;
		616	if (!rsa->meth->bn_mod_exp(&m1,&r1,dmq1,rsa->q,ctx,
584	rsa->_method_mod_q)) goto err;	617	rsa->_method_mod_q)) goto err;
585		618
586	if (!BN_mod(&r1,I,rsa->p,ctx)) goto err;	619	if (!BN_mod(&r1,I,rsa->p,ctx)) goto err;
587	if (!rsa->meth->bn_mod_exp(r0,&r1,rsa->dmp1,rsa->p,ctx,	620	if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
		621	{
		622	dmp1 = &local_dmp1;
		623	BN_with_flags(dmp1, rsa->dmp1, BN_FLG_EXP_CONSTTIME);
		624	}
		625	else
		626	dmp1 = rsa->dmp1;
		627	if (!rsa->meth->bn_mod_exp(r0,&r1,dmp1,rsa->p,ctx,
588	rsa->_method_mod_p)) goto err;	628	rsa->_method_mod_p)) goto err;
589		629
590	if (!BN_sub(r0,r0,&m1)) goto err;	630	if (!BN_sub(r0,r0,&m1)) goto err;
Lines 619-628 Link Here
619	if (vrfy.neg)	659	if (vrfy.neg)
620	if (!BN_add(&vrfy, &vrfy, rsa->n)) goto err;	660	if (!BN_add(&vrfy, &vrfy, rsa->n)) goto err;
621	if (!BN_is_zero(&vrfy))	661	if (!BN_is_zero(&vrfy))
		662	{
622	/* 'I' and 'vrfy' aren't congruent mod n. Don't leak	663	/* 'I' and 'vrfy' aren't congruent mod n. Don't leak
623	* miscalculated CRT output, just do a raw (slower)	664	* miscalculated CRT output, just do a raw (slower)
624	* mod_exp and return that instead. */	665	* mod_exp and return that instead. */
625	if (!rsa->meth->bn_mod_exp(r0,I,rsa->d,rsa->n,ctx,NULL)) goto err;	666
		667	BIGNUM local_d;
		668	BIGNUM *d = NULL;
		669
		670	if (!(rsa->flags & RSA_FLAG_NO_EXP_CONSTTIME))
		671	{
		672	d = &local_d;
		673	BN_with_flags(d, rsa->d, BN_FLG_EXP_CONSTTIME);
		674	}
		675	else
		676	d = rsa->d;
		677	if (!rsa->meth->bn_mod_exp(r0,I,d,rsa->n,ctx,NULL)) goto err;
		678	}
626	}	679	}
627	ret=1;	680	ret=1;
628	err:	681	err:





    plen = sizeof(ptext_ex) - 1;

    for (v = 0; v < 6; v++)
	{
	key = RSA_new();
	switch (v%3) {
    case 0:
	clen = key1(key, ctext_ex);
	break;

	clen = key3(key, ctext_ex);
	break;
	}
	if (v/3 > 1) key->flags |= RSA_FLAG_NO_EXP_CONSTTIME;

	num = RSA_public_encrypt(plen, ptext_ex, ctext, key,
				 RSA_PKCS1_PADDING);

Lines 2875-2877 Link Here

(-)util/libeay.num (+1 lines)
2875	EVP_sha256 3315 EXIST::FUNCTION:SHA	2875	EVP_sha256 3315 EXIST::FUNCTION:SHA
2876	FIPS_selftest_hmac 3316 EXIST:OPENSSL_FIPS:FUNCTION:	2876	FIPS_selftest_hmac 3316 EXIST:OPENSSL_FIPS:FUNCTION:
2877	FIPS_corrupt_rng 3317 EXIST:OPENSSL_FIPS:FUNCTION:	2877	FIPS_corrupt_rng 3317 EXIST:OPENSSL_FIPS:FUNCTION:
		2878	BN_mod_exp_mont_consttime 3318 EXIST::FUNCTION:

Return to bug 86410

Lines 4-9 Link Here

(-)CHANGES (+15 lines)
4		4
5	Changes between 0.9.7g and 0.9.7h [XX xxx XXXX]	5	Changes between 0.9.7g and 0.9.7h [XX xxx XXXX]
6		6
		7	*) Make a new fixed-window mod_exp implementation the default for
		8	RSA, DSA, and DH private-key operations to mitigate the
		9	hyper-threading timing attacks pointed out by Colin Percival
		10	(http://www.daemonology.net/hyperthreading-considered-harmful/),
		11	and potential related attacks.
		12
		13	BN_mod_exp_mont_consttime() is the new exponentiation implementation,
		14	and this is automatically used by BN_mod_exp_mont() if the new flag
		15	BN_FLG_EXP_CONSTTIME is set for the exponent. RSA, DSA, and DH
		16	will use this BN flag for private exponents unless the flag
		17	RSA_FLAG_NO_EXP_CONSTTIME, DSA_FLAG_NO_EXP_CONSTTIME, or
		18	DH_FLAG_NO_EXP_CONSTTIME, respectively, is set.
		19
		20	[Matthew D Wood (Intel Corp), with some changes by Bodo Moeller]
		21
7	*) Change the client implementation for SSLv23_method() and	22	*) Change the client implementation for SSLv23_method() and
8	SSLv23_client_method() so that is uses the SSL 3.0/TLS 1.0	23	SSLv23_client_method() so that is uses the SSL 3.0/TLS 1.0
9	Client Hello message format if the SSL_OP_NO_SSLv2 option is set.	24	Client Hello message format if the SSL_OP_NO_SSLv2 option is set.

Lines 79-89 Link Here

(-)crypto/bn/bn_err.c (+4 lines)
79	{ERR_FUNC(BN_F_BN_CTX_GET), "BN_CTX_get"},	79	{ERR_FUNC(BN_F_BN_CTX_GET), "BN_CTX_get"},
80	{ERR_FUNC(BN_F_BN_CTX_NEW), "BN_CTX_new"},	80	{ERR_FUNC(BN_F_BN_CTX_NEW), "BN_CTX_new"},
81	{ERR_FUNC(BN_F_BN_DIV), "BN_div"},	81	{ERR_FUNC(BN_F_BN_DIV), "BN_div"},
		82	{ERR_FUNC(BN_F_BN_EXP), "BN_exp"},
82	{ERR_FUNC(BN_F_BN_EXPAND2), "bn_expand2"},	83	{ERR_FUNC(BN_F_BN_EXPAND2), "bn_expand2"},
83	{ERR_FUNC(BN_F_BN_EXPAND_INTERNAL), "BN_EXPAND_INTERNAL"},	84	{ERR_FUNC(BN_F_BN_EXPAND_INTERNAL), "BN_EXPAND_INTERNAL"},
84	{ERR_FUNC(BN_F_BN_MOD_EXP2_MONT), "BN_mod_exp2_mont"},	85	{ERR_FUNC(BN_F_BN_MOD_EXP2_MONT), "BN_mod_exp2_mont"},
85	{ERR_FUNC(BN_F_BN_MOD_EXP_MONT), "BN_mod_exp_mont"},	86	{ERR_FUNC(BN_F_BN_MOD_EXP_MONT), "BN_mod_exp_mont"},
		87	{ERR_FUNC(BN_F_BN_MOD_EXP_MONT_CONSTTIME), "BN_mod_exp_mont_consttime"},
86	{ERR_FUNC(BN_F_BN_MOD_EXP_MONT_WORD), "BN_mod_exp_mont_word"},	88	{ERR_FUNC(BN_F_BN_MOD_EXP_MONT_WORD), "BN_mod_exp_mont_word"},
		89	{ERR_FUNC(BN_F_BN_MOD_EXP_RECP), "BN_mod_exp_recp"},
		90	{ERR_FUNC(BN_F_BN_MOD_EXP_SIMPLE), "BN_mod_exp_simple"},
87	{ERR_FUNC(BN_F_BN_MOD_INVERSE), "BN_mod_inverse"},	91	{ERR_FUNC(BN_F_BN_MOD_INVERSE), "BN_mod_inverse"},
88	{ERR_FUNC(BN_F_BN_MOD_LSHIFT_QUICK), "BN_mod_lshift_quick"},	92	{ERR_FUNC(BN_F_BN_MOD_LSHIFT_QUICK), "BN_mod_lshift_quick"},
89	{ERR_FUNC(BN_F_BN_MOD_MUL_RECIPROCAL), "BN_mod_mul_reciprocal"},	93	{ERR_FUNC(BN_F_BN_MOD_MUL_RECIPROCAL), "BN_mod_mul_reciprocal"},

Lines 177-182 Link Here

(-)crypto/bn/bn_lcl.h (+39 lines)
177		177
178		178
179		179
		180	/* BN_mod_exp_mont_conttime is based on the assumption that the
		181	* L1 data cache line width of the target processor is at least
		182	* the following value.
		183	*/
		184	#define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH ( 64 )
		185	#define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1)
		186
		187	/* Window sizes optimized for fixed window size modular exponentiation
		188	* algorithm (BN_mod_exp_mont_consttime).
		189	*
		190	* To achieve the security goals of BN_mode_exp_mont_consttime, the
		191	* maximum size of the window must not exceed
		192	* log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH).
		193	*
		194	* Window size thresholds are defined for cache line sizes of 32 and 64,
		195	* cache line sizes where log_2(32)=5 and log_2(64)=6 respectively. A
		196	* window size of 7 should only be used on processors that have a 128
		197	* byte or greater cache line size.
		198	*/
		199	#if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64
		200
		201	# define BN_window_bits_for_ctime_exponent_size(b) \
		202	((b) > 937 ? 6 : \
		203	(b) > 306 ? 5 : \
		204	(b) > 89 ? 4 : \
		205	(b) > 22 ? 3 : 1)
		206	# define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (6)
		207
		208	#elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32
		209
		210	# define BN_window_bits_for_ctime_exponent_size(b) \
		211	((b) > 306 ? 5 : \
		212	(b) > 89 ? 4 : \
		213	(b) > 22 ? 3 : 1)
		214	# define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (5)
		215
		216	#endif
		217
		218
180	/* Pentium pro 16,16,16,32,64 */	219	/* Pentium pro 16,16,16,32,64 */
181	/* Alpha 16,16,16,16.64 */	220	/* Alpha 16,16,16,16.64 */
182	#define BN_MULL_SIZE_NORMAL (16) /* 32 */	221	#define BN_MULL_SIZE_NORMAL (16) /* 32 */

Lines 77-83 Link Here

(-)crypto/bn/exptest.c (-2 / +16 lines)
77	BIO *out=NULL;	77	BIO *out=NULL;
78	int i,ret;	78	int i,ret;
79	unsigned char c;	79	unsigned char c;
80	BIGNUM r_mont,r_recp,r_simple,a,b,m;	80	BIGNUM r_mont,r_mont_const,r_recp,r_simple,a,b,*m;
81		81
82	RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_rand may fail, and we don't	82	RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_rand may fail, and we don't
83	* even check its return value	83	* even check its return value
Lines 88-93 Link Here
88	ctx=BN_CTX_new();	88	ctx=BN_CTX_new();
89	if (ctx == NULL) EXIT(1);	89	if (ctx == NULL) EXIT(1);
90	r_mont=BN_new();	90	r_mont=BN_new();
		91	r_mont_const=BN_new();
91	r_recp=BN_new();	92	r_recp=BN_new();
92	r_simple=BN_new();	93	r_simple=BN_new();
93	a=BN_new();	94	a=BN_new();
Lines 143-150 Link Here
143	EXIT(1);	144	EXIT(1);
144	}	145	}
145		146
		147	ret=BN_mod_exp_mont_consttime(r_mont_const,a,b,m,ctx,NULL);
		148	if (ret <= 0)
		149	{
		150	printf("BN_mod_exp_mont_consttime() problems\n");
		151	ERR_print_errors(out);
		152	EXIT(1);
		153	}
		154
146	if (BN_cmp(r_simple, r_mont) == 0	155	if (BN_cmp(r_simple, r_mont) == 0
147	&& BN_cmp(r_simple,r_recp) == 0)	156	&& BN_cmp(r_simple,r_recp) == 0
		157	&& BN_cmp(r_simple,r_mont_const) == 0)
148	{	158	{
149	printf(".");	159	printf(".");
150	fflush(stdout);	160	fflush(stdout);
Lines 153-158 Link Here
153	{	163	{
154	if (BN_cmp(r_simple,r_mont) != 0)	164	if (BN_cmp(r_simple,r_mont) != 0)
155	printf("\nsimple and mont results differ\n");	165	printf("\nsimple and mont results differ\n");
		166	if (BN_cmp(r_simple,r_mont) != 0)
		167	printf("\nsimple and mont const time results differ\n");
156	if (BN_cmp(r_simple,r_recp) != 0)	168	if (BN_cmp(r_simple,r_recp) != 0)
157	printf("\nsimple and recp results differ\n");	169	printf("\nsimple and recp results differ\n");
158		170
Lines 162-172 Link Here
162	printf("\nsimple ="); BN_print(out,r_simple);	174	printf("\nsimple ="); BN_print(out,r_simple);
163	printf("\nrecp ="); BN_print(out,r_recp);	175	printf("\nrecp ="); BN_print(out,r_recp);
164	printf("\nmont ="); BN_print(out,r_mont);	176	printf("\nmont ="); BN_print(out,r_mont);
		177	printf("\nmont_ct ="); BN_print(out,r_mont_const);
165	printf("\n");	178	printf("\n");
166	EXIT(1);	179	EXIT(1);
167	}	180	}
168	}	181	}
169	BN_free(r_mont);	182	BN_free(r_mont);
		183	BN_free(r_mont_const);
170	BN_free(r_recp);	184	BN_free(r_recp);
171	BN_free(r_simple);	185	BN_free(r_simple);
172	BN_free(a);	186	BN_free(a);

Lines 157-184 Link Here

(-)crypto/rsa/rsa.h (-12 / +19 lines)
157	#define RSA_3 0x3L	157	#define RSA_3 0x3L
158	#define RSA_F4 0x10001L	158	#define RSA_F4 0x10001L
159		159
160	#define RSA_METHOD_FLAG_NO_CHECK 0x01 /* don't check pub/private match */	160	#define RSA_METHOD_FLAG_NO_CHECK 0x0001 /* don't check pub/private match */
161		161
162	#define RSA_FLAG_CACHE_PUBLIC 0x02	162	#define RSA_FLAG_CACHE_PUBLIC 0x0002
163	#define RSA_FLAG_CACHE_PRIVATE 0x04	163	#define RSA_FLAG_CACHE_PRIVATE 0x0004
164	#define RSA_FLAG_BLINDING 0x08	164	#define RSA_FLAG_BLINDING 0x0008
165	#define RSA_FLAG_THREAD_SAFE 0x10	165	#define RSA_FLAG_THREAD_SAFE 0x0010
166	/* This flag means the private key operations will be handled by rsa_mod_exp	166	/* This flag means the private key operations will be handled by rsa_mod_exp
167	* and that they do not depend on the private key components being present:	167	* and that they do not depend on the private key components being present:
168	* for example a key stored in external hardware. Without this flag bn_mod_exp	168	* for example a key stored in external hardware. Without this flag bn_mod_exp
169	* gets called when private key components are absent.	169	* gets called when private key components are absent.
170	*/	170	*/
171	#define RSA_FLAG_EXT_PKEY 0x20	171	#define RSA_FLAG_EXT_PKEY 0x0020
172		172
173	/* This flag in the RSA_METHOD enables the new rsa_sign, rsa_verify functions.	173	/* This flag in the RSA_METHOD enables the new rsa_sign, rsa_verify functions.
174	*/	174	*/
175	#define RSA_FLAG_SIGN_VER 0x40	175	#define RSA_FLAG_SIGN_VER 0x0040
176		176
177	#define RSA_FLAG_NO_BLINDING 0x80 /* new with 0.9.6j and 0.9.7b; the built-in	177	#define RSA_FLAG_NO_BLINDING 0x0080 /* new with 0.9.6j and 0.9.7b; the built-in
178	* RSA implementation now uses blinding by	178	* RSA implementation now uses blinding by
179	* default (ignoring RSA_FLAG_BLINDING),	179	* default (ignoring RSA_FLAG_BLINDING),
180	* but other engines might not need it	180	* but other engines might not need it
181	*/	181	*/
		182	#define RSA_FLAG_NO_EXP_CONSTTIME 0x0100 /* new with 0.9.7h; the built-in RSA
		183	* implementation now uses constant time
		184	* modular exponentiation for secret exponents
		185	* by default. This flag causes the
		186	* faster variable sliding window method to
		187	* be used for all exponents.
		188	*/
182		189
183	#define RSA_PKCS1_PADDING 1	190	#define RSA_PKCS1_PADDING 1
184	#define RSA_SSLV23_PADDING 2	191	#define RSA_SSLV23_PADDING 2

Lines 227-236 Link Here

(-)crypto/rsa/rsa_test.c (-2 / +3 lines)
227		227
228	plen = sizeof(ptext_ex) - 1;	228	plen = sizeof(ptext_ex) - 1;
229		229
230	for (v = 0; v < 3; v++)	230	for (v = 0; v < 6; v++)
231	{	231	{
232	key = RSA_new();	232	key = RSA_new();
233	switch (v) {	233	switch (v%3) {
234	case 0:	234	case 0:
235	clen = key1(key, ctext_ex);	235	clen = key1(key, ctext_ex);
236	break;	236	break;
Lines 241-246 Link Here
241	clen = key3(key, ctext_ex);	241	clen = key3(key, ctext_ex);
242	break;	242	break;
243	}	243	}
		244	if (v/3 > 1) key->flags \|= RSA_FLAG_NO_EXP_CONSTTIME;
244		245
245	num = RSA_public_encrypt(plen, ptext_ex, ctext, key,	246	num = RSA_public_encrypt(plen, ptext_ex, ctext, key,
246	RSA_PKCS1_PADDING);	247	RSA_PKCS1_PADDING);