+
+/* 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);
+ }
+
projects / openssl.git / commitdiff