Fix for CVE-2014-0076

Fix for the attack described in the paper "Recovering OpenSSL
ECDSA Nonces Using the FLUSH+RELOAD Cache Side-channel Attack"
by Yuval Yarom and Naomi Benger. Details can be obtained from:
http://eprint.iacr.org/2014/140

Thanks to Yuval Yarom and Naomi Benger for discovering this
flaw and to Yuval Yarom for supplying a fix.
(cherry picked from commit 2198be3483259de374f91e57d247d0fc667aef29)

Conflicts:

	CHANGES

diff --git a/CHANGES b/CHANGES
index 797c02118c11938899035b19b58ce9ae72034c1c..1b10b774a955999cebfd03f0b720bc7147c14a31 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -4,6 +4,15 @@
 
  Changes between 1.0.2 and 1.1.0  [xx XXX xxxx]
 
 
  Changes between 1.0.2 and 1.1.0  [xx XXX xxxx]
 

+  *) Fix for the attack described in the paper "Recovering OpenSSL
+     ECDSA Nonces Using the FLUSH+RELOAD Cache Side-channel Attack"
+     by Yuval Yarom and Naomi Benger. Details can be obtained from:
+     http://eprint.iacr.org/2014/140
+
+     Thanks to Yuval Yarom and Naomi Benger for discovering this
+     flaw and to Yuval Yarom for supplying a fix (CVE-2014-0076)
+     [Yuval Yarom and Naomi Benger]
+

   *) Use algorithm specific chains in SSL_CTX_use_certificate_chain_file():
      this fixes a limiation in previous versions of OpenSSL.
      [Steve Henson]
   *) Use algorithm specific chains in SSL_CTX_use_certificate_chain_file():
      this fixes a limiation in previous versions of OpenSSL.
      [Steve Henson]

diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
index 7c23c01c2f7f4e2e8809dcd2f57836ccc2bda74a..b3518cb3bad848d11aafe9d776bebbfe9dc67437 100644 (file)
--- a/crypto/bn/bn.h
+++ b/crypto/bn/bn.h
@@ -520,6 +520,8 @@ BIGNUM *BN_mod_inverse(BIGNUM *ret,
 BIGNUM *BN_mod_sqrt(BIGNUM *ret,
        const BIGNUM *a, const BIGNUM *n,BN_CTX *ctx);
 
 BIGNUM *BN_mod_sqrt(BIGNUM *ret,
        const BIGNUM *a, const BIGNUM *n,BN_CTX *ctx);
 

+void   BN_consttime_swap(BN_ULONG swap, BIGNUM *a, BIGNUM *b, int nwords);
+

 /* Deprecated versions */
 #ifndef OPENSSL_NO_DEPRECATED
 BIGNUM *BN_generate_prime(BIGNUM *ret,int bits,int safe,
 /* Deprecated versions */
 #ifndef OPENSSL_NO_DEPRECATED
 BIGNUM *BN_generate_prime(BIGNUM *ret,int bits,int safe,


@@ -762,11 +764,20 @@ int RAND_pseudo_bytes(unsigned char *buf,int num);
 
 #define bn_fix_top(a)          bn_check_top(a)
 
 
 #define bn_fix_top(a)          bn_check_top(a)
 

+#define bn_check_size(bn, bits) bn_wcheck_size(bn, ((bits+BN_BITS2-1))/BN_BITS2)
+#define bn_wcheck_size(bn, words) \
+       do { \
+               const BIGNUM *_bnum2 = (bn); \
+               assert(words <= (_bnum2)->dmax && words >= (_bnum2)->top); \
+       } while(0)
+

 #else /* !BN_DEBUG */
 
 #define bn_pollute(a)
 #define bn_check_top(a)
 #define bn_fix_top(a)          bn_correct_top(a)
 #else /* !BN_DEBUG */
 
 #define bn_pollute(a)
 #define bn_check_top(a)
 #define bn_fix_top(a)          bn_correct_top(a)

+#define bn_check_size(bn, bits)
+#define bn_wcheck_size(bn, words)

 
 #endif
 
 
 #endif
 

diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c
index f77fdb75fd9a075b625c0b39677f3342525a21c2..72da0735fd83ada70265c1dac87fba13fd931321 100644 (file)
--- a/crypto/bn/bn_lib.c
+++ b/crypto/bn/bn_lib.c
@@ -828,3 +828,55 @@ int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b,
                }
        return bn_cmp_words(a,b,cl);
        }
                }
        return bn_cmp_words(a,b,cl);
        }

+
+/* 
+ * Constant-time conditional swap of a and b.  
+ * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
+ * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
+ * and that no more than nwords are used by either a or b.
+ * a and b cannot be the same number
+ */
+void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
+       {
+       BN_ULONG t;
+       int i;
+
+       bn_wcheck_size(a, nwords);
+       bn_wcheck_size(b, nwords);
+
+       assert(a != b);
+       assert((condition & (condition - 1)) == 0);
+       assert(sizeof(BN_ULONG) >= sizeof(int));
+
+       condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
+
+       t = (a->top^b->top) & condition;
+       a->top ^= t;
+       b->top ^= t;
+
+#define BN_CONSTTIME_SWAP(ind) \
+       do { \
+               t = (a->d[ind] ^ b->d[ind]) & condition; \
+               a->d[ind] ^= t; \
+               b->d[ind] ^= t; \
+       } while (0)
+
+
+       switch (nwords) {
+       default:
+               for (i = 10; i < nwords; i++) 
+                       BN_CONSTTIME_SWAP(i);
+               /* Fallthrough */
+       case 10: BN_CONSTTIME_SWAP(9); /* Fallthrough */
+       case 9: BN_CONSTTIME_SWAP(8); /* Fallthrough */
+       case 8: BN_CONSTTIME_SWAP(7); /* Fallthrough */
+       case 7: BN_CONSTTIME_SWAP(6); /* Fallthrough */
+       case 6: BN_CONSTTIME_SWAP(5); /* Fallthrough */
+       case 5: BN_CONSTTIME_SWAP(4); /* Fallthrough */
+       case 4: BN_CONSTTIME_SWAP(3); /* Fallthrough */
+       case 3: BN_CONSTTIME_SWAP(2); /* Fallthrough */
+       case 2: BN_CONSTTIME_SWAP(1); /* Fallthrough */
+       case 1: BN_CONSTTIME_SWAP(0);
+       }
+#undef BN_CONSTTIME_SWAP
+}

diff --git a/crypto/ec/ec2_mult.c b/crypto/ec/ec2_mult.c
index f41665ac10bcbb8bc3065710506f7c97ed7a7854..06405d0716fff0c4d5c82af2b4f6967f0d87badf 100644 (file)
--- a/crypto/ec/ec2_mult.c
+++ b/crypto/ec/ec2_mult.c
@@ -210,11 +210,15 @@ static int gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, BIG
        return ret;
        }
 
        return ret;
        }
 

+

 /* Computes scalar*point and stores the result in r.
  * point can not equal r.
 /* Computes scalar*point and stores the result in r.
  * point can not equal r.

- * Uses algorithm 2P of
+ * Uses a modified algorithm 2P of

  *     Lopez, J. and Dahab, R.  "Fast multiplication on elliptic curves over 
  *     GF(2^m) without precomputation" (CHES '99, LNCS 1717).
  *     Lopez, J. and Dahab, R.  "Fast multiplication on elliptic curves over 
  *     GF(2^m) without precomputation" (CHES '99, LNCS 1717).

+ *
+ * To protect against side-channel attack the function uses constant time swap,
+ * avoiding conditional branches.

  */
 static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
        const EC_POINT *point, BN_CTX *ctx)
  */
 static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
        const EC_POINT *point, BN_CTX *ctx)


@@ -248,6 +252,11 @@ static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r,
        x2 = &r->X;
        z2 = &r->Y;
 
        x2 = &r->X;
        z2 = &r->Y;
 

+       bn_wexpand(x1, group->field.top);
+       bn_wexpand(z1, group->field.top);
+       bn_wexpand(x2, group->field.top);
+       bn_wexpand(z2, group->field.top);
+

        if (!BN_GF2m_mod_arr(x1, &point->X, group->poly)) goto err; /* x1 = x */
        if (!BN_one(z1)) goto err; /* z1 = 1 */
        if (!group->meth->field_sqr(group, z2, x1, ctx)) goto err; /* z2 = x1^2 = x^2 */
        if (!BN_GF2m_mod_arr(x1, &point->X, group->poly)) goto err; /* x1 = x */
        if (!BN_one(z1)) goto err; /* z1 = 1 */
        if (!group->meth->field_sqr(group, z2, x1, ctx)) goto err; /* z2 = x1^2 = x^2 */


@@ -272,16 +281,12 @@ static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r,
                word = scalar->d[i];
                while (mask)
                        {
                word = scalar->d[i];
                while (mask)
                        {

-                       if (word & mask)
-                               {
-                               if (!gf2m_Madd(group, &point->X, x1, z1, x2, z2, ctx)) goto err;
-                               if (!gf2m_Mdouble(group, x2, z2, ctx)) goto err;
-                               }
-                       else
-                               {
-                               if (!gf2m_Madd(group, &point->X, x2, z2, x1, z1, ctx)) goto err;
-                               if (!gf2m_Mdouble(group, x1, z1, ctx)) goto err;
-                               }
+                       BN_consttime_swap(word & mask, x1, x2, group->field.top);
+                       BN_consttime_swap(word & mask, z1, z2, group->field.top);
+                       if (!gf2m_Madd(group, &point->X, x2, z2, x1, z1, ctx)) goto err;
+                       if (!gf2m_Mdouble(group, x1, z1, ctx)) goto err;
+                       BN_consttime_swap(word & mask, x1, x2, group->field.top);
+                       BN_consttime_swap(word & mask, z1, z2, group->field.top);

                        mask >>= 1;
                        }
                mask = BN_TBIT;
                        mask >>= 1;
                        }
                mask = BN_TBIT;