Attachment #167918 for bug #207783




 *
 */

#ifndef HEADER_BN_H
# define HEADER_BN_H

# include <limits.h>
# include <openssl/e_os2.h>
# ifndef OPENSSL_NO_FP_API
#  include <stdio.h>            /* FILE */
# endif
# include <openssl/ossl_typ.h>


const BIGNUM *BN_get0_nist_prime_256(void);
const BIGNUM *BN_get0_nist_prime_384(void);
const BIGNUM *BN_get0_nist_prime_521(void);

/* library internal functions */

# define bn_expand(a,bits) \
    ( \
        bits > (INT_MAX - BN_BITS2 + 1) ? \
            NULL \
        : \
            (((bits+BN_BITS2-1)/BN_BITS2) <= (a)->dmax) ? \
                (a) \
            : \
                bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2) \
    )

# define bn_wexpand(a,words) (((words) <= (a)->dmax)?(a):bn_expand2((a),(words)))
BIGNUM *bn_expand2(BIGNUM *a, int words);
# ifndef OPENSSL_NO_DEPRECATED
BIGNUM *bn_dup_expand(const BIGNUM *a, int words); /* unused */
# endif





 * (eay@cryptsoft.com).  This product includes software written by Tim
 * Hudson (tjh@cryptsoft.com).
 *
 */

#include "cryptlib.h"
#include "bn_lcl.h"

/* maximum precomputation table size for *variable* sliding windows */
/* maximum precomputation table size for *variable* sliding windows */
#define TABLE_SIZE      32

/* this one works - simple but works */

 * 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;
    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;

            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;
}

    /*
     * 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)

    } 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

    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




 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */

#include <stdio.h>
#include <ctype.h>
#include <limits.h>
#include "cryptlib.h"
#include <openssl/buffer.h>
#include "bn_lcl.h"

#include <stdio.h>
#include <ctype.h>
#include <limits.h>
#include "cryptlib.h"
#include <openssl/buffer.h>
#include "bn_lcl.h"

static const char Hex[] = "0123456789ABCDEF";

/* Must 'OPENSSL_free' the returned data */


    if (*a == '-') {
        neg = 1;
        a++;
    }

    for (i = 0; i <= (INT_MAX/4) && isxdigit((unsigned char)a[i]); i++)
        continue;

    if (i > INT_MAX/4)
        goto err;

    num = i + neg;
    if (bn == NULL)
        return (num);

    for (i = 0; i <= (INT_MAX/4) && isxdigit((unsigned char)a[i]); i++)
        continue;

    if (i > INT_MAX/4)
        goto err;

    num = i + neg;
    if (bn == NULL)
        return (num);

    /* a is the start of the hex digits, and it is 'i' long */
    if (*bn == NULL) {
        if ((ret = BN_new()) == NULL)

            return (0);
    } else {
        ret = *bn;
        BN_zero(ret);
    }

    /* i is the number of hex digits */
    if (bn_expand(ret, i * 4) == NULL)
        goto err;

    j = i;                      /* least significant 'hex' */
    m = 0;
    h = 0;

        return (0);
    if (*a == '-') {
        neg = 1;
        a++;
    }

    for (i = 0; i <= (INT_MAX/4) && isdigit((unsigned char)a[i]); i++)
        continue;

    if (i > INT_MAX/4)
        goto err;

    num = i + neg;
    if (bn == NULL)
        return (num);

    for (i = 0; i <= (INT_MAX/4) && isdigit((unsigned char)a[i]); i++)
        continue;

    if (i > INT_MAX/4)
        goto err;

    num = i + neg;
    if (bn == NULL)
        return (num);

    /*
     * a is the start of the digits, and it is 'i' long. We chop it into
     * BN_DEC_NUM digits at a time

            return (0);
    } else {
        ret = *bn;
        BN_zero(ret);
    }

    /* i is the number of digits, a bit of an over expand */
    if (bn_expand(ret, i * 4) == NULL)
        goto err;

    j = BN_DEC_NUM - (i % BN_DEC_NUM);
    if (j == BN_DEC_NUM)
        j = 0;

Return to bug 207783

Lines 69-81 Link Here

(-)crypto/openssl/crypto/bn/bn.h (-24 / +24 lines)
69	*	69	*
70	*/	70	*/
71		71
72	#ifndef HEADER_BN_H	72	#ifndef HEADER_BN_H
73	# define HEADER_BN_H	73	# define HEADER_BN_H
74		74
75	# include <limits.h>	75	# include <limits.h>
76	# include <openssl/e_os2.h>	76	# include <openssl/e_os2.h>
77	# ifndef OPENSSL_NO_FP_API	77	# ifndef OPENSSL_NO_FP_API
78	# include <stdio.h> /* FILE */	78	# include <stdio.h> /* FILE */
79	# endif	79	# endif
80	# include <openssl/ossl_typ.h>	80	# include <openssl/ossl_typ.h>
81		81
Lines 702-724 const BIGNUM *BN_get0_nist_prime_224(void); Link Here
702	const BIGNUM *BN_get0_nist_prime_256(void);	702	const BIGNUM *BN_get0_nist_prime_256(void);
703	const BIGNUM *BN_get0_nist_prime_384(void);	703	const BIGNUM *BN_get0_nist_prime_384(void);
704	const BIGNUM *BN_get0_nist_prime_521(void);	704	const BIGNUM *BN_get0_nist_prime_521(void);
705		705
706	/* library internal functions */	706	/* library internal functions */
707		707
708	# define bn_expand(a,bits) \	708	# define bn_expand(a,bits) \
709	( \	709	( \
710	bits > (INT_MAX - BN_BITS2 + 1) ? \	710	bits > (INT_MAX - BN_BITS2 + 1) ? \
711	NULL \	711	NULL \
712	: \	712	: \
713	(((bits+BN_BITS2-1)/BN_BITS2) <= (a)->dmax) ? \	713	(((bits+BN_BITS2-1)/BN_BITS2) <= (a)->dmax) ? \
714	(a) \	714	(a) \
715	: \	715	: \
716	bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2) \	716	bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2) \
717	)	717	)
718		718
719	# define bn_wexpand(a,words) (((words) <= (a)->dmax)?(a):bn_expand2((a),(words)))	719	# define bn_wexpand(a,words) (((words) <= (a)->dmax)?(a):bn_expand2((a),(words)))
720	BIGNUM bn_expand2(BIGNUM a, int words);	720	BIGNUM bn_expand2(BIGNUM a, int words);
721	# ifndef OPENSSL_NO_DEPRECATED	721	# ifndef OPENSSL_NO_DEPRECATED
722	BIGNUM bn_dup_expand(const BIGNUM a, int words); /* unused */	722	BIGNUM bn_dup_expand(const BIGNUM a, int words); /* unused */
723	# endif	723	# endif
724		724

Lines 107-119 Link Here

(-)crypto/openssl/crypto/bn/bn_exp.c (-99 / +60 lines)
107	* (eay@cryptsoft.com). This product includes software written by Tim	107	* (eay@cryptsoft.com). This product includes software written by Tim
108	* Hudson (tjh@cryptsoft.com).	108	* Hudson (tjh@cryptsoft.com).
109	*	109	*
110	*/	110	*/
111		111
112	#include "cryptlib.h"	112	#include "cryptlib.h"
113	#include "constant_time_locl.h"	113	#include "bn_lcl.h"
114	#include "bn_lcl.h"	114
115		115	/* maximum precomputation table size for variable sliding windows */
116	/* maximum precomputation table size for variable sliding windows */
117	#define TABLE_SIZE 32	116	#define TABLE_SIZE 32
118		117
119	/* this one works - simple but works */	118	/* this one works - simple but works */
Lines 521-599 int BN_mod_exp_mont(BIGNUM rr, const BIGNUM a, c Link Here
521	* pattern as far as cache lines are concerned. The following functions are	520	* pattern as far as cache lines are concerned. The following functions are
522	* used to transfer a BIGNUM from/to that table.	521	* used to transfer a BIGNUM from/to that table.
523	*/	522	*/
524		523
525	static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top,	524	static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top,
526	unsigned char *buf, int idx,	525	unsigned char *buf, int idx,
527	int window)	526	int width)
528	{	527	{
529	int i, j;	528	size_t i, j;
530	int width = 1 << window;	529
531	BN_ULONG table = (BN_ULONG )buf;	530	if (bn_wexpand(b, top) == NULL)
532		531	return 0;
533	if (bn_wexpand(b, top) == NULL)
534	return 0;
535	while (b->top < top) {	532	while (b->top < top) {
536	b->d[b->top++] = 0;	533	b->d[b->top++] = 0;
537	}	534	}
538		535
539	for (i = 0, j = idx; i < top; i++, j += width) {	536	for (i = 0, j = idx; i < top * sizeof b->d[0]; i++, j += width) {
540	table[j] = b->d[i];	537	buf[j] = ((unsigned char *)b->d)[i];
541	}	538	}
542		539
543	bn_correct_top(b);	540	bn_correct_top(b);
544	return 1;	541	return 1;
545	}	542	}
546		543
547	static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top,	544	static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top,
548	unsigned char *buf, int idx,	545	unsigned char *buf, int idx,
549	int window)	546	int width)
550	{	547	{
551	int i, j;	548	size_t i, j;
552	int width = 1 << window;	549
553	volatile BN_ULONG table = (volatile BN_ULONG )buf;	550	if (bn_wexpand(b, top) == NULL)
554		551	return 0;
555	if (bn_wexpand(b, top) == NULL)	552
556	return 0;	553	for (i = 0, j = idx; i < top * sizeof b->d[0]; i++, j += width) {
557		554	((unsigned char *)b->d)[i] = buf[j];
558	if (window <= 3) {	555	}
559	for (i = 0; i < top; i++, table += width) {	556
560	BN_ULONG acc = 0;	557	b->top = top;
561
562	for (j = 0; j < width; j++) {
563	acc \|= table[j] &
564	((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));
565	}
566
567	b->d[i] = acc;
568	}
569	} else {
570	int xstride = 1 << (window - 2);
571	BN_ULONG y0, y1, y2, y3;
572
573	i = idx >> (window - 2); /* equivalent of idx / xstride */
574	idx &= xstride - 1; /* equivalent of idx % xstride */
575
576	y0 = (BN_ULONG)0 - (constant_time_eq_int(i,0)&1);
577	y1 = (BN_ULONG)0 - (constant_time_eq_int(i,1)&1);
578	y2 = (BN_ULONG)0 - (constant_time_eq_int(i,2)&1);
579	y3 = (BN_ULONG)0 - (constant_time_eq_int(i,3)&1);
580
581	for (i = 0; i < top; i++, table += width) {
582	BN_ULONG acc = 0;
583
584	for (j = 0; j < xstride; j++) {
585	acc \|= ( (table[j + 0 * xstride] & y0) \|
586	(table[j + 1 * xstride] & y1) \|
587	(table[j + 2 * xstride] & y2) \|
588	(table[j + 3 * xstride] & y3) )
589	& ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));
590	}
591
592	b->d[i] = acc;
593	}
594	}
595
596	b->top = top;
597	bn_correct_top(b);	558	bn_correct_top(b);
598	return 1;	559	return 1;
599	}	560	}
Lines 684-696 int BN_mod_exp_mont_consttime(BIGNUM *rr, const BI Link Here
684	/*	645	/*
685	* Initialize the intermediate result. Do this early to save double	646	* Initialize the intermediate result. Do this early to save double
686	* conversion, once each for a^0 and intermediate result.	647	* conversion, once each for a^0 and intermediate result.
687	*/	648	*/
688	if (!BN_to_montgomery(r, BN_value_one(), mont, ctx))	649	if (!BN_to_montgomery(r, BN_value_one(), mont, ctx))
689	goto err;	650	goto err;
690	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, window))	651	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers))
691	goto err;	652	goto err;
692		653
693	/* Initialize computeTemp as a^1 with montgomery precalcs */	654	/* Initialize computeTemp as a^1 with montgomery precalcs */
694	computeTemp = BN_CTX_get(ctx);	655	computeTemp = BN_CTX_get(ctx);
695	am = BN_CTX_get(ctx);	656	am = BN_CTX_get(ctx);
696	if (computeTemp == NULL \|\| am == NULL)	657	if (computeTemp == NULL \|\| am == NULL)
Lines 703-715 int BN_mod_exp_mont_consttime(BIGNUM *rr, const BI Link Here
703	} else	664	} else
704	aa = a;	665	aa = a;
705	if (!BN_to_montgomery(am, aa, mont, ctx))	666	if (!BN_to_montgomery(am, aa, mont, ctx))
706	goto err;	667	goto err;
707	if (!BN_copy(computeTemp, am))	668	if (!BN_copy(computeTemp, am))
708	goto err;	669	goto err;
709	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, window))	670	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers))
710	goto err;	671	goto err;
711		672
712	/*	673	/*
713	* If the window size is greater than 1, then calculate	674	* If the window size is greater than 1, then calculate
714	* val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) (even powers	675	* val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) (even powers
715	* could instead be computed as (a^(i/2))^2 to use the slight performance	676	* could instead be computed as (a^(i/2))^2 to use the slight performance
Lines 718-731 int BN_mod_exp_mont_consttime(BIGNUM *rr, const BI Link Here
718	if (window > 1) {	679	if (window > 1) {
719	for (i = 2; i < numPowers; i++) {	680	for (i = 2; i < numPowers; i++) {
720	/* Calculate a^i = a^(i-1) * a */	681	/* Calculate a^i = a^(i-1) * a */
721	if (!BN_mod_mul_montgomery	682	if (!BN_mod_mul_montgomery
722	(computeTemp, am, computeTemp, mont, ctx))	683	(computeTemp, am, computeTemp, mont, ctx))
723	goto err;	684	goto err;
724	if (!MOD_EXP_CTIME_COPY_TO_PREBUF(computeTemp, top, powerbuf, i,	685	if (!MOD_EXP_CTIME_COPY_TO_PREBUF
725	window))	686	(computeTemp, top, powerbuf, i, numPowers))
726	goto err;	687	goto err;
727	}	688	}
728	}	689	}
729		690
730	/*	691	/*
731	* Adjust the number of bits up to a multiple of the window size. If the	692	* Adjust the number of bits up to a multiple of the window size. If the

Lines 55-68 Link Here

(-)crypto/openssl/crypto/bn/bn_print.c (-45 / +45 lines)
55	* copied and put under another distribution licence	55	* copied and put under another distribution licence
56	* [including the GNU Public Licence.]	56	* [including the GNU Public Licence.]
57	*/	57	*/
58
59	#include <stdio.h>
60	#include <ctype.h>
61	#include <limits.h>
62	#include "cryptlib.h"
63	#include <openssl/buffer.h>
64	#include "bn_lcl.h"
65		58
		59	#include <stdio.h>
		60	#include <ctype.h>
		61	#include <limits.h>
		62	#include "cryptlib.h"
		63	#include <openssl/buffer.h>
		64	#include "bn_lcl.h"
		65
66	static const char Hex[] = "0123456789ABCDEF";	66	static const char Hex[] = "0123456789ABCDEF";
67		67
68	/* Must 'OPENSSL_free' the returned data */	68	/* Must 'OPENSSL_free' the returned data */
Lines 187-205 int BN_hex2bn(BIGNUM *bn, const char a) Link Here
187		187
188	if (*a == '-') {	188	if (*a == '-') {
189	neg = 1;	189	neg = 1;
190	a++;	190	a++;
191	}	191	}
192
193	for (i = 0; i <= (INT_MAX/4) && isxdigit((unsigned char)a[i]); i++)
194	continue;
195
196	if (i > INT_MAX/4)
197	goto err;
198
199	num = i + neg;
200	if (bn == NULL)
201	return (num);
202		192
		193	for (i = 0; i <= (INT_MAX/4) && isxdigit((unsigned char)a[i]); i++)
		194	continue;
		195
		196	if (i > INT_MAX/4)
		197	goto err;
		198
		199	num = i + neg;
		200	if (bn == NULL)
		201	return (num);
		202
203	/* a is the start of the hex digits, and it is 'i' long */	203	/* a is the start of the hex digits, and it is 'i' long */
204	if (*bn == NULL) {	204	if (*bn == NULL) {
205	if ((ret = BN_new()) == NULL)	205	if ((ret = BN_new()) == NULL)
Lines 206-218 int BN_hex2bn(BIGNUM *bn, const char a) Link Here
206	return (0);	206	return (0);
207	} else {	207	} else {
208	ret = *bn;	208	ret = *bn;
209	BN_zero(ret);	209	BN_zero(ret);
210	}	210	}
211		211
212	/* i is the number of hex digits */	212	/* i is the number of hex digits */
213	if (bn_expand(ret, i * 4) == NULL)	213	if (bn_expand(ret, i * 4) == NULL)
214	goto err;	214	goto err;
215		215
216	j = i; /* least significant 'hex' */	216	j = i; /* least significant 'hex' */
217	m = 0;	217	m = 0;
218	h = 0;	218	h = 0;
Lines 262-280 int BN_dec2bn(BIGNUM *bn, const char a) Link Here
262	return (0);	262	return (0);
263	if (*a == '-') {	263	if (*a == '-') {
264	neg = 1;	264	neg = 1;
265	a++;	265	a++;
266	}	266	}
267
268	for (i = 0; i <= (INT_MAX/4) && isdigit((unsigned char)a[i]); i++)
269	continue;
270
271	if (i > INT_MAX/4)
272	goto err;
273
274	num = i + neg;
275	if (bn == NULL)
276	return (num);
277		267
		268	for (i = 0; i <= (INT_MAX/4) && isdigit((unsigned char)a[i]); i++)
		269	continue;
		270
		271	if (i > INT_MAX/4)
		272	goto err;
		273
		274	num = i + neg;
		275	if (bn == NULL)
		276	return (num);
		277
278	/*	278	/*
279	* a is the start of the digits, and it is 'i' long. We chop it into	279	* a is the start of the digits, and it is 'i' long. We chop it into
280	* BN_DEC_NUM digits at a time	280	* BN_DEC_NUM digits at a time
Lines 284-296 int BN_dec2bn(BIGNUM *bn, const char a) Link Here
284	return (0);	284	return (0);
285	} else {	285	} else {
286	ret = *bn;	286	ret = *bn;
287	BN_zero(ret);	287	BN_zero(ret);
288	}	288	}
289		289
290	/* i is the number of digits, a bit of an over expand */	290	/* i is the number of digits, a bit of an over expand */
291	if (bn_expand(ret, i * 4) == NULL)	291	if (bn_expand(ret, i * 4) == NULL)
292	goto err;	292	goto err;
293		293
294	j = BN_DEC_NUM - (i % BN_DEC_NUM);	294	j = BN_DEC_NUM - (i % BN_DEC_NUM);
295	if (j == BN_DEC_NUM)	295	if (j == BN_DEC_NUM)
296	j = 0;	296	j = 0;