6 files changed, 106 insertions, 26 deletions

diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h
index f34248ec4f..21a1a3fe35 100644
--- a/src/lib/libcrypto/bn/bn.h
+++ b/src/lib/libcrypto/bn/bn.h
@@ -538,6 +538,8 @@ BIGNUM *BN_mod_inverse(BIGNUM *ret,
 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,
@@ -774,11 +776,20 @@ int RAND_pseudo_bytes(unsigned char *buf,int num);
 
 #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)
+#define bn_check_size(bn, bits)
+#define bn_wcheck_size(bn, words)
 
 #endif
 
diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c
index 52b3304293..7b2403185e 100644
--- a/src/lib/libcrypto/bn/bn_div.c
+++ b/src/lib/libcrypto/bn/bn_div.c
@@ -141,6 +141,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
     *
     *                                   <appro@fy.chalmers.se>
     */
+#undef bn_div_words
 #  define bn_div_words(n0,n1,d0)                \
         ({  asm volatile (                      \
                 "divl   %4"                     \
@@ -155,6 +156,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
     * Same story here, but it's 128-bit by 64-bit division. Wow!
     *                                   <appro@fy.chalmers.se>
     */
+#  undef bn_div_words
 #  define bn_div_words(n0,n1,d0)                \
         ({  asm volatile (                      \
                 "divq   %4"                     \
diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c
index 4a352119ba..a808f53178 100644
--- a/src/lib/libcrypto/bn/bn_gcd.c
+++ b/src/lib/libcrypto/bn/bn_gcd.c
@@ -205,6 +205,7 @@ err:
 /* solves ax == 1 (mod n) */
 static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in,
         const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx);
+
 BIGNUM *BN_mod_inverse(BIGNUM *in,
         const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
         {
diff --git a/src/lib/libcrypto/bn/bn_lcl.h b/src/lib/libcrypto/bn/bn_lcl.h
index eecfd8cc99..817c773b65 100644
--- a/src/lib/libcrypto/bn/bn_lcl.h
+++ b/src/lib/libcrypto/bn/bn_lcl.h
@@ -282,16 +282,23 @@ extern "C" {
 #  endif
 # elif defined(__mips) && (defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG))
 #  if defined(__GNUC__) && __GNUC__>=2
-#   define BN_UMULT_HIGH(a,b)   ({      \
+#   if __GNUC__>=4 && __GNUC_MINOR__>=4 /* "h" constraint is no more since 4.4 */
+#     define BN_UMULT_HIGH(a,b)          (((__uint128_t)(a)*(b))>>64)
+#     define BN_UMULT_LOHI(low,high,a,b) ({     \
+        __uint128_t ret=(__uint128_t)(a)*(b);   \
+        (high)=ret>>64; (low)=ret;       })
+#   else
+#     define BN_UMULT_HIGH(a,b) ({      \
         register BN_ULONG ret;          \
         asm ("dmultu    %1,%2"          \
              : "=h"(ret)                \
              : "r"(a), "r"(b) : "l");   \
         ret;                    })
-#   define BN_UMULT_LOHI(low,high,a,b)  \
+#     define BN_UMULT_LOHI(low,high,a,b)\
         asm ("dmultu    %2,%3"          \
              : "=l"(low),"=h"(high)     \
              : "r"(a), "r"(b));
+#    endif
 #  endif
 # endif         /* cpu */
 #endif          /* OPENSSL_NO_ASM */
diff --git a/src/lib/libcrypto/bn/bn_lib.c b/src/lib/libcrypto/bn/bn_lib.c
index 7a5676de69..5461e6ee7d 100644
--- a/src/lib/libcrypto/bn/bn_lib.c
+++ b/src/lib/libcrypto/bn/bn_lib.c
@@ -824,3 +824,55 @@ int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b,
                 }
         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/src/lib/libcrypto/bn/bn_nist.c b/src/lib/libcrypto/bn/bn_nist.c
index 43caee4770..e22968d4a3 100644
--- a/src/lib/libcrypto/bn/bn_nist.c
+++ b/src/lib/libcrypto/bn/bn_nist.c
@@ -286,26 +286,25 @@ const BIGNUM *BN_get0_nist_prime_521(void)
         }
 
 
-static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max)
+static void nist_cp_bn_0(BN_ULONG *dst, const BN_ULONG *src, int top, int max)
         {
         int i;
-        BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
 
 #ifdef BN_DEBUG
         OPENSSL_assert(top <= max);
 #endif
-        for (i = (top); i != 0; i--)
-                *_tmp1++ = *_tmp2++;
-        for (i = (max) - (top); i != 0; i--)
-                *_tmp1++ = (BN_ULONG) 0;
+        for (i = 0; i < top; i++)
+                dst[i] = src[i];
+        for (; i < max; i++)
+                dst[i] = 0;
         }
 
-static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top)
+static void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top)
         { 
         int i;
-        BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
-        for (i = (top); i != 0; i--)
-                *_tmp1++ = *_tmp2++;
+
+        for (i = 0; i < top; i++)
+                dst[i] = src[i];
         }
 
 #if BN_BITS2 == 64
@@ -451,8 +450,9 @@ int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
          */
         mask  = 0-(PTR_SIZE_INT)bn_sub_words(c_d,r_d,_nist_p_192[0],BN_NIST_192_TOP);
         mask &= 0-(PTR_SIZE_INT)carry;
+        res   = c_d;
         res   = (BN_ULONG *)
-         (((PTR_SIZE_INT)c_d&~mask) | ((PTR_SIZE_INT)r_d&mask));
+         (((PTR_SIZE_INT)res&~mask) | ((PTR_SIZE_INT)r_d&mask));
         nist_cp_bn(r_d, res, BN_NIST_192_TOP);
         r->top = BN_NIST_192_TOP;
         bn_correct_top(r);
@@ -479,8 +479,11 @@ int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
         int     top = a->top, i;
         int     carry;
         BN_ULONG *r_d, *a_d = a->d;
-        BN_ULONG buf[BN_NIST_224_TOP],
-                 c_d[BN_NIST_224_TOP],
+        union   {
+                BN_ULONG        bn[BN_NIST_224_TOP];
+                unsigned int    ui[BN_NIST_224_TOP*sizeof(BN_ULONG)/sizeof(unsigned int)];
+                } buf;
+        BN_ULONG c_d[BN_NIST_224_TOP],
                 *res;
         PTR_SIZE_INT mask;
         union { bn_addsub_f f; PTR_SIZE_INT p; } u;
@@ -519,18 +522,18 @@ int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
         /* copy upper 256 bits of 448 bit number ... */
         nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP-1), top - (BN_NIST_224_TOP-1), BN_NIST_224_TOP);
         /* ... and right shift by 32 to obtain upper 224 bits */
-        nist_set_224(buf, c_d, 14, 13, 12, 11, 10, 9, 8);
+        nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8);
         /* truncate lower part to 224 bits too */
         r_d[BN_NIST_224_TOP-1] &= BN_MASK2l;
 #else
-        nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, BN_NIST_224_TOP);
+        nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, BN_NIST_224_TOP);
 #endif
 
 #if defined(NIST_INT64) && BN_BITS2!=64
         {
         NIST_INT64              acc;    /* accumulator */
         unsigned int            *rp=(unsigned int *)r_d;
-        const unsigned int      *bp=(const unsigned int *)buf;
+        const unsigned int      *bp=(const unsigned int *)buf.ui;
 
         acc  = rp[0];   acc -= bp[7-7];
                         acc -= bp[11-7]; rp[0] = (unsigned int)acc; acc >>= 32;
@@ -565,13 +568,13 @@ int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
         {
         BN_ULONG t_d[BN_NIST_224_TOP];
 
-        nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0);
+        nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0);
         carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
-        nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0);
+        nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0);
         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
-        nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7);
+        nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7);
         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
-        nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11);
+        nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11);
         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
 
 #if BN_BITS2==64
@@ -606,7 +609,8 @@ int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
         /* otherwise it's effectively same as in BN_nist_mod_192... */
         mask  = 0-(PTR_SIZE_INT)(*u.f)(c_d,r_d,_nist_p_224[0],BN_NIST_224_TOP);
         mask &= 0-(PTR_SIZE_INT)carry;
-        res   = (BN_ULONG *)(((PTR_SIZE_INT)c_d&~mask) |
+        res   = c_d;
+        res   = (BN_ULONG *)(((PTR_SIZE_INT)res&~mask) |
          ((PTR_SIZE_INT)r_d&mask));
         nist_cp_bn(r_d, res, BN_NIST_224_TOP);
         r->top = BN_NIST_224_TOP;
@@ -805,7 +809,8 @@ int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 
         mask  = 0-(PTR_SIZE_INT)(*u.f)(c_d,r_d,_nist_p_256[0],BN_NIST_256_TOP);
         mask &= 0-(PTR_SIZE_INT)carry;
-        res   = (BN_ULONG *)(((PTR_SIZE_INT)c_d&~mask) |
+        res   = c_d;
+        res   = (BN_ULONG *)(((PTR_SIZE_INT)res&~mask) |
          ((PTR_SIZE_INT)r_d&mask));
         nist_cp_bn(r_d, res, BN_NIST_256_TOP);
         r->top = BN_NIST_256_TOP;
@@ -1026,7 +1031,8 @@ int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 
         mask  = 0-(PTR_SIZE_INT)(*u.f)(c_d,r_d,_nist_p_384[0],BN_NIST_384_TOP);
         mask &= 0-(PTR_SIZE_INT)carry;
-        res   = (BN_ULONG *)(((PTR_SIZE_INT)c_d&~mask) |
+        res   = c_d;
+        res   = (BN_ULONG *)(((PTR_SIZE_INT)res&~mask) |
          ((PTR_SIZE_INT)r_d&mask));
         nist_cp_bn(r_d, res, BN_NIST_384_TOP);
         r->top = BN_NIST_384_TOP;
@@ -1092,7 +1098,8 @@ int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
 
         bn_add_words(r_d,r_d,t_d,BN_NIST_521_TOP);
         mask = 0-(PTR_SIZE_INT)bn_sub_words(t_d,r_d,_nist_p_521,BN_NIST_521_TOP);
-        res  = (BN_ULONG *)(((PTR_SIZE_INT)t_d&~mask) |
+        res  = t_d;
+        res  = (BN_ULONG *)(((PTR_SIZE_INT)res&~mask) |
          ((PTR_SIZE_INT)r_d&mask));
         nist_cp_bn(r_d,res,BN_NIST_521_TOP);
         r->top = BN_NIST_521_TOP;