Fix for CVE-2014-3570. (With minor bn/generic.c revamp.) (Imported from upstream's 56df92efb6893abe323307939425957ce878c8f0) Change-Id: I9d85cfde4dfb29e64ff7417f781d0c9f1685e905 Reviewed-on: https://boringssl-review.googlesource.com/2780 Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/bn/asm/x86_64-gcc.c b/crypto/bn/asm/x86_64-gcc.c index 1de0f42..4b3062a 100644 --- a/crypto/bn/asm/x86_64-gcc.c +++ b/crypto/bn/asm/x86_64-gcc.c
@@ -292,80 +292,45 @@ /* sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number c=(c2,c1,c0) */ -#if 0 -/* original macros are kept for reference purposes */ -#define mul_add_c(a, b, c0, c1, c2) \ - { \ - BN_ULONG ta = (a), tb = (b); \ - t1 = ta * tb; \ - t2 = BN_UMULT_HIGH(ta, tb); \ - c0 += t1; \ - t2 += (c0 < t1) ? 1 : 0; \ - c1 += t2; \ - c2 += (c1 < t2) ? 1 : 0; \ - } - -#define mul_add_c2(a, b, c0, c1, c2) \ - { \ - BN_ULONG ta = (a), tb = (b), t0; \ - t1 = BN_UMULT_HIGH(ta, tb); \ - t0 = ta * tb; \ - t2 = t1 + t1; \ - c2 += (t2 < t1) ? 1 : 0; \ - t1 = t0 + t0; \ - t2 += (t1 < t0) ? 1 : 0; \ - c0 += t1; \ - t2 += (c0 < t1) ? 1 : 0; \ - c1 += t2; \ - c2 += (c1 < t2) ? 1 : 0; \ - } -#else -#define mul_add_c(a, b, c0, c1, c2) \ - do { \ +/* Keep in mind that carrying into high part of multiplication result can not + * overflow, because it cannot be all-ones. */ +#define mul_add_c(a, b, c0, c1, c2) \ + do { \ + BN_ULONG t1, t2; \ asm("mulq %3" : "=a"(t1), "=d"(t2) : "a"(a), "m"(b) : "cc"); \ - asm("addq %2,%0; adcq %3,%1" \ - : "+r"(c0), "+d"(t2) \ - : "a"(t1), "g"(0) \ - : "cc"); \ - asm("addq %2,%0; adcq %3,%1" \ - : "+r"(c1), "+r"(c2) \ - : "d"(t2), "g"(0) \ - : "cc"); \ + asm("addq %3,%0; adcq %4,%1; adcq %5,%2" \ + : "+r"(c0), "+r"(c1), "+r"(c2) \ + : "r"(t1), "r"(t2), "g"(0) \ + : "cc"); \ } while (0) -#define sqr_add_c(a, i, c0, c1, c2) \ - do { \ +#define sqr_add_c(a, i, c0, c1, c2) \ + do { \ + BN_ULONG t1, t2; \ asm("mulq %2" : "=a"(t1), "=d"(t2) : "a"(a[i]) : "cc"); \ - asm("addq %2,%0; adcq %3,%1" \ - : "+r"(c0), "+d"(t2) \ - : "a"(t1), "g"(0) \ - : "cc"); \ - asm("addq %2,%0; adcq %3,%1" \ - : "+r"(c1), "+r"(c2) \ - : "d"(t2), "g"(0) \ - : "cc"); \ + asm("addq %3,%0; adcq %4,%1; adcq %5,%2" \ + : "+r"(c0), "+r"(c1), "+r"(c2) \ + : "r"(t1), "r"(t2), "g"(0) \ + : "cc"); \ } while (0) -#define mul_add_c2(a, b, c0, c1, c2) \ - do { \ +#define mul_add_c2(a, b, c0, c1, c2) \ + do { \ + BN_ULONG t1, t2; \ asm("mulq %3" : "=a"(t1), "=d"(t2) : "a"(a), "m"(b) : "cc"); \ - asm("addq %0,%0; adcq %2,%1" : "+d"(t2), "+r"(c2) : "g"(0) : "cc"); \ - asm("addq %0,%0; adcq %2,%1" : "+a"(t1), "+d"(t2) : "g"(0) : "cc"); \ - asm("addq %2,%0; adcq %3,%1" \ - : "+r"(c0), "+d"(t2) \ - : "a"(t1), "g"(0) \ - : "cc"); \ - asm("addq %2,%0; adcq %3,%1" \ - : "+r"(c1), "+r"(c2) \ - : "d"(t2), "g"(0) \ - : "cc"); \ + asm("addq %3,%0; adcq %4,%1; adcq %5,%2" \ + : "+r"(c0), "+r"(c1), "+r"(c2) \ + : "r"(t1), "r"(t2), "g"(0) \ + : "cc"); \ + asm("addq %3,%0; adcq %4,%1; adcq %5,%2" \ + : "+r"(c0), "+r"(c1), "+r"(c2) \ + : "r"(t1), "r"(t2), "g"(0) \ + : "cc"); \ } while (0) -#endif #define sqr_add_c2(a, i, j, c0, c1, c2) mul_add_c2((a)[i], (a)[j], c0, c1, c2) void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b) { - BN_ULONG t1, t2; BN_ULONG c1, c2, c3; c1 = 0; @@ -468,7 +433,6 @@ } void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b) { - BN_ULONG t1, t2; BN_ULONG c1, c2, c3; c1 = 0; @@ -507,7 +471,6 @@ } void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a) { - BN_ULONG t1, t2; BN_ULONG c1, c2, c3; c1 = 0; @@ -582,7 +545,6 @@ } void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a) { - BN_ULONG t1, t2; BN_ULONG c1, c2, c3; c1 = 0;
diff --git a/crypto/bn/bn_test.c b/crypto/bn/bn_test.c index 11b3c62..0fa5155 100644 --- a/crypto/bn/bn_test.c +++ b/crypto/bn/bn_test.c
@@ -653,40 +653,98 @@ } int test_sqr(BIO *bp, BN_CTX *ctx) { - BIGNUM a, c, d, e; - int i; + BIGNUM *a, *c, *d, *e; + int i, ret = 0; - BN_init(&a); - BN_init(&c); - BN_init(&d); - BN_init(&e); + a = BN_new(); + c = BN_new(); + d = BN_new(); + e = BN_new(); + if (a == NULL || c == NULL || d == NULL || e == NULL) { + goto err; + } for (i = 0; i < num0; i++) { - BN_rand(&a, 40 + i * 10, 0, 0); - a.neg = rand_neg(); - BN_sqr(&c, &a, ctx); + BN_rand(a, 40 + i * 10, 0, 0); + a->neg = rand_neg(); + BN_sqr(c, a, ctx); if (bp != NULL) { if (!results) { - BN_print(bp, &a); + BN_print(bp, a); BIO_puts(bp, " * "); - BN_print(bp, &a); + BN_print(bp, a); BIO_puts(bp, " - "); } - BN_print(bp, &c); + BN_print(bp, c); BIO_puts(bp, "\n"); } - BN_div(&d, &e, &c, &a, ctx); - BN_sub(&d, &d, &a); - if (!BN_is_zero(&d) || !BN_is_zero(&e)) { + BN_div(d, e, c, a, ctx); + BN_sub(d, d, a); + if (!BN_is_zero(d) || !BN_is_zero(e)) { fprintf(stderr, "Square test failed!\n"); - return 0; + goto err; } } - BN_free(&a); - BN_free(&c); - BN_free(&d); - BN_free(&e); - return (1); + + /* Regression test for a BN_sqr overflow bug. */ + BN_hex2bn(&a, + "80000000000000008000000000000001FFFFFFFFFFFFFFFE0000000000000000"); + BN_sqr(c, a, ctx); + if (bp != NULL) { + if (!results) { + BN_print(bp, a); + BIO_puts(bp, " * "); + BN_print(bp, a); + BIO_puts(bp, " - "); + } + BN_print(bp, c); + BIO_puts(bp, "\n"); + } + BN_mul(d, a, a, ctx); + if (BN_cmp(c, d)) { + fprintf(stderr, + "Square test failed: BN_sqr and BN_mul produce " + "different results!\n"); + goto err; + } + + /* Regression test for a BN_sqr overflow bug. */ + BN_hex2bn(&a, + "80000000000000000000000080000001FFFFFFFE000000000000000000000000"); + BN_sqr(c, a, ctx); + if (bp != NULL) { + if (!results) { + BN_print(bp, a); + BIO_puts(bp, " * "); + BN_print(bp, a); + BIO_puts(bp, " - "); + } + BN_print(bp, c); + BIO_puts(bp, "\n"); + } + BN_mul(d, a, a, ctx); + if (BN_cmp(c, d)) { + fprintf(stderr, + "Square test failed: BN_sqr and BN_mul produce " + "different results!\n"); + goto err; + } + ret = 1; + +err: + if (a != NULL) { + BN_free(a); + } + if (c != NULL) { + BN_free(c); + } + if (d != NULL) { + BN_free(d); + } + if (e != NULL) { + BN_free(e); + } + return ret; }
diff --git a/crypto/bn/generic.c b/crypto/bn/generic.c index 53b5ce1..8b3b0f8 100644 --- a/crypto/bn/generic.c +++ b/crypto/bn/generic.c
@@ -659,175 +659,194 @@ /* sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number c=(c2,c1,c0) */ #ifdef BN_LLONG -#define mul_add_c(a, b, c0, c1, c2) \ - t = (BN_ULLONG)a * b; \ - t1 = (BN_ULONG)Lw(t); \ - t2 = (BN_ULONG)Hw(t); \ - c0 = (c0 + t1) & BN_MASK2; \ - if ((c0) < t1) \ - t2++; \ - c1 = (c1 + t2) & BN_MASK2; \ - if ((c1) < t2) \ - c2++; -#define mul_add_c2(a, b, c0, c1, c2) \ - t = (BN_ULLONG)a * b; \ - tt = (t + t) & BN_MASK; \ - if (tt < t) \ - c2++; \ - t1 = (BN_ULONG)Lw(tt); \ - t2 = (BN_ULONG)Hw(tt); \ - c0 = (c0 + t1) & BN_MASK2; \ - if ((c0 < t1) && (((++t2) & BN_MASK2) == 0)) \ - c2++; \ - c1 = (c1 + t2) & BN_MASK2; \ - if ((c1) < t2) \ - c2++; +/* Keep in mind that additions to multiplication result can not overflow, + * because its high half cannot be all-ones. */ +#define mul_add_c(a, b, c0, c1, c2) \ + do { \ + BN_ULONG hi; \ + BN_ULLONG t = (BN_ULLONG)(a) * (b); \ + t += c0; /* no carry */ \ + c0 = (BN_ULONG)Lw(t); \ + hi = (BN_ULONG)Hw(t); \ + c1 = (c1 + hi) & BN_MASK2; \ + if (c1 < hi) \ + c2++; \ + } while (0) -#define sqr_add_c(a, i, c0, c1, c2) \ - t = (BN_ULLONG)a[i] * a[i]; \ - t1 = (BN_ULONG)Lw(t); \ - t2 = (BN_ULONG)Hw(t); \ - c0 = (c0 + t1) & BN_MASK2; \ - if ((c0) < t1) \ - t2++; \ - c1 = (c1 + t2) & BN_MASK2; \ - if ((c1) < t2) \ - c2++; +#define mul_add_c2(a, b, c0, c1, c2) \ + do { \ + BN_ULONG hi; \ + BN_ULLONG t = (BN_ULLONG)(a) * (b); \ + BN_ULLONG tt = t + c0; /* no carry */ \ + c0 = (BN_ULONG)Lw(tt); \ + hi = (BN_ULONG)Hw(tt); \ + c1 = (c1 + hi) & BN_MASK2; \ + if (c1 < hi) \ + c2++; \ + t += c0; /* no carry */ \ + c0 = (BN_ULONG)Lw(t); \ + hi = (BN_ULONG)Hw(t); \ + c1 = (c1 + hi) & BN_MASK2; \ + if (c1 < hi) \ + c2++; \ + } while (0) + +#define sqr_add_c(a, i, c0, c1, c2) \ + do { \ + BN_ULONG hi; \ + BN_ULLONG t = (BN_ULLONG)a[i] * a[i]; \ + t += c0; /* no carry */ \ + c0 = (BN_ULONG)Lw(t); \ + hi = (BN_ULONG)Hw(t); \ + c1 = (c1 + hi) & BN_MASK2; \ + if (c1 < hi) \ + c2++; \ + } while (0) #define sqr_add_c2(a, i, j, c0, c1, c2) mul_add_c2((a)[i], (a)[j], c0, c1, c2) #elif defined(BN_UMULT_LOHI) +/* Keep in mind that additions to hi can not overflow, because the high word of + * a multiplication result cannot be all-ones. */ #define mul_add_c(a, b, c0, c1, c2) \ - { \ + do { \ BN_ULONG ta = (a), tb = (b); \ - BN_UMULT_LOHI(t1, t2, ta, tb); \ - c0 += t1; \ - t2 += (c0 < t1) ? 1 : 0; \ - c1 += t2; \ - c2 += (c1 < t2) ? 1 : 0; \ - } + BN_ULONG lo, hi; \ + BN_UMULT_LOHI(lo, hi, ta, tb); \ + c0 += lo; \ + hi += (c0 < lo) ? 1 : 0; \ + c1 += hi; \ + c2 += (c1 < hi) ? 1 : 0; \ + } while (0) #define mul_add_c2(a, b, c0, c1, c2) \ - { \ - BN_ULONG ta = (a), tb = (b), t0; \ - BN_UMULT_LOHI(t0, t1, ta, tb); \ - t2 = t1 + t1; \ - c2 += (t2 < t1) ? 1 : 0; \ - t1 = t0 + t0; \ - t2 += (t1 < t0) ? 1 : 0; \ - c0 += t1; \ - t2 += (c0 < t1) ? 1 : 0; \ - c1 += t2; \ - c2 += (c1 < t2) ? 1 : 0; \ - } + do { \ + BN_ULONG ta = (a), tb = (b); \ + BN_ULONG lo, hi, tt; \ + BN_UMULT_LOHI(lo, hi, ta, tb); \ + c0 += lo; \ + tt = hi + ((c0 < lo) ? 1 : 0); \ + c1 += tt; \ + c2 += (c1 < tt) ? 1 : 0; \ + c0 += lo; \ + hi += (c0 < lo) ? 1 : 0; \ + c1 += hi; \ + c2 += (c1 < hi) ? 1 : 0; \ + } while (0) #define sqr_add_c(a, i, c0, c1, c2) \ - { \ + do { \ BN_ULONG ta = (a)[i]; \ - BN_UMULT_LOHI(t1, t2, ta, ta); \ - c0 += t1; \ - t2 += (c0 < t1) ? 1 : 0; \ - c1 += t2; \ - c2 += (c1 < t2) ? 1 : 0; \ - } + BN_ULONG lo, hi; \ + BN_UMULT_LOHI(lo, hi, ta, ta); \ + c0 += lo; \ + hi += (c0 < lo) ? 1 : 0; \ + c1 += hi; \ + c2 += (c1 < hi) ? 1 : 0; \ + } while (0) #define sqr_add_c2(a, i, j, c0, c1, c2) mul_add_c2((a)[i], (a)[j], c0, c1, c2) #elif defined(BN_UMULT_HIGH) -#define mul_add_c(a, b, c0, c1, c2) \ - { \ - BN_ULONG ta = (a), tb = (b); \ - t1 = ta * tb; \ - t2 = BN_UMULT_HIGH(ta, tb); \ - c0 += t1; \ - t2 += (c0 < t1) ? 1 : 0; \ - c1 += t2; \ - c2 += (c1 < t2) ? 1 : 0; \ - } +/* Keep in mind that additions to hi can not overflow, because + * the high word of a multiplication result cannot be all-ones. */ +#define mul_add_c(a, b, c0, c1, c2) \ + do { \ + BN_ULONG ta = (a), tb = (b); \ + BN_ULONG lo = ta * tb; \ + BN_ULONG hi = BN_UMULT_HIGH(ta, tb); \ + c0 += lo; \ + hi += (c0 < lo) ? 1 : 0; \ + c1 += hi; \ + c2 += (c1 < hi) ? 1 : 0; \ + } while (0) -#define mul_add_c2(a, b, c0, c1, c2) \ - { \ - BN_ULONG ta = (a), tb = (b), t0; \ - t1 = BN_UMULT_HIGH(ta, tb); \ - t0 = ta * tb; \ - t2 = t1 + t1; \ - c2 += (t2 < t1) ? 1 : 0; \ - t1 = t0 + t0; \ - t2 += (t1 < t0) ? 1 : 0; \ - c0 += t1; \ - t2 += (c0 < t1) ? 1 : 0; \ - c1 += t2; \ - c2 += (c1 < t2) ? 1 : 0; \ - } +#define mul_add_c2(a, b, c0, c1, c2) \ + do { \ + BN_ULONG ta = (a), tb = (b), tt; \ + BN_ULONG lo = ta * tb; \ + BN_ULONG hi = BN_UMULT_HIGH(ta, tb); \ + c0 += lo; \ + tt = hi + ((c0 < lo) ? 1 : 0); \ + c1 += tt; \ + c2 += (c1 < tt) ? 1 : 0; \ + c0 += lo; \ + hi += (c0 < lo) ? 1 : 0; \ + c1 += hi; \ + c2 += (c1 < hi) ? 1 : 0; \ + } while (0) -#define sqr_add_c(a, i, c0, c1, c2) \ - { \ - BN_ULONG ta = (a)[i]; \ - t1 = ta * ta; \ - t2 = BN_UMULT_HIGH(ta, ta); \ - c0 += t1; \ - t2 += (c0 < t1) ? 1 : 0; \ - c1 += t2; \ - c2 += (c1 < t2) ? 1 : 0; \ - } +#define sqr_add_c(a, i, c0, c1, c2) \ + do { \ + BN_ULONG ta = (a)[i]; \ + BN_ULONG lo = ta * ta; \ + BN_ULONG hi = BN_UMULT_HIGH(ta, ta); \ + c0 += lo; \ + hi += (c0 < lo) ? 1 : 0; \ + c1 += hi; \ + c2 += (c1 < hi) ? 1 : 0; \ + } while (0) #define sqr_add_c2(a, i, j, c0, c1, c2) mul_add_c2((a)[i], (a)[j], c0, c1, c2) #else /* !BN_LLONG */ -#define mul_add_c(a, b, c0, c1, c2) \ - t1 = LBITS(a); \ - t2 = HBITS(a); \ - bl = LBITS(b); \ - bh = HBITS(b); \ - mul64(t1, t2, bl, bh); \ - c0 = (c0 + t1) & BN_MASK2; \ - if ((c0) < t1) \ - t2++; \ - c1 = (c1 + t2) & BN_MASK2; \ - if ((c1) < t2) \ - c2++; -#define mul_add_c2(a, b, c0, c1, c2) \ - t1 = LBITS(a); \ - t2 = HBITS(a); \ - bl = LBITS(b); \ - bh = HBITS(b); \ - mul64(t1, t2, bl, bh); \ - if (t2 & BN_TBIT) \ - c2++; \ - t2 = (t2 + t2) & BN_MASK2; \ - if (t1 & BN_TBIT) \ - t2++; \ - t1 = (t1 + t1) & BN_MASK2; \ - c0 = (c0 + t1) & BN_MASK2; \ - if ((c0 < t1) && (((++t2) & BN_MASK2) == 0)) \ - c2++; \ - c1 = (c1 + t2) & BN_MASK2; \ - if ((c1) < t2) \ - c2++; +/* Keep in mind that additions to hi can not overflow, because + * the high word of a multiplication result cannot be all-ones. */ + +#define mul_add_c(a, b, c0, c1, c2) \ + do { \ + BN_ULONG lo = LBITS(a), hi = HBITS(a); \ + BN_ULONG bl = LBITS(b), bh = HBITS(b); \ + mul64(lo, hi, bl, bh); \ + c0 = (c0 + lo) & BN_MASK2; \ + if (c0 < lo) \ + hi++; \ + c1 = (c1 + hi) & BN_MASK2; \ + if (c1 < hi) \ + c2++; \ + } while (0) + +#define mul_add_c2(a, b, c0, c1, c2) \ + do { \ + BN_ULONG tt; \ + BN_ULONG lo = LBITS(a), hi = HBITS(a); \ + BN_ULONG bl = LBITS(b), bh = HBITS(b); \ + mul64(lo, hi, bl, bh); \ + tt = hi; \ + c0 = (c0 + lo) & BN_MASK2; \ + if (c0 < lo) \ + tt++; \ + c1 = (c1 + tt) & BN_MASK2; \ + if (c1 < tt) \ + c2++; \ + c0 = (c0 + lo) & BN_MASK2; \ + if (c0 < lo) \ + hi++; \ + c1 = (c1 + hi) & BN_MASK2; \ + if (c1 < hi) \ + c2++; \ + } while (0) #define sqr_add_c(a, i, c0, c1, c2) \ - sqr64(t1, t2, (a)[i]); \ - c0 = (c0 + t1) & BN_MASK2; \ - if ((c0) < t1) \ - t2++; \ - c1 = (c1 + t2) & BN_MASK2; \ - if ((c1) < t2) \ - c2++; + do { \ + BN_ULONG lo, hi; \ + sqr64(lo, hi, (a)[i]); \ + c0 = (c0 + lo) & BN_MASK2; \ + if (c0 < lo) \ + hi++; \ + c1 = (c1 + hi) & BN_MASK2; \ + if (c1 < hi) \ + c2++; \ + } while (0) #define sqr_add_c2(a, i, j, c0, c1, c2) mul_add_c2((a)[i], (a)[j], c0, c1, c2) #endif /* !BN_LLONG */ void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b) { -#if defined(BN_LLONG) - BN_ULLONG t; -#elif !defined(BN_UMULT_LOHI) && !defined(BN_UMULT_HIGH) - BN_ULONG bl, bh; -#endif - BN_ULONG t1, t2; BN_ULONG c1, c2, c3; c1 = 0; @@ -930,12 +949,6 @@ } void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b) { -#if defined(BN_LLONG) - BN_ULLONG t; -#elif !defined(BN_UMULT_LOHI) && !defined(BN_UMULT_HIGH) - BN_ULONG bl, bh; -#endif - BN_ULONG t1, t2; BN_ULONG c1, c2, c3; c1 = 0; @@ -974,12 +987,6 @@ } void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a) { -#if defined(BN_LLONG) - BN_ULLONG t, tt; -#elif !defined(BN_UMULT_LOHI) && !defined(BN_UMULT_HIGH) - BN_ULONG bl, bh; -#endif - BN_ULONG t1, t2; BN_ULONG c1, c2, c3; c1 = 0; @@ -1054,12 +1061,6 @@ } void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a) { -#if defined(BN_LLONG) - BN_ULLONG t, tt; -#elif !defined(BN_UMULT_LOHI) && !defined(BN_UMULT_HIGH) - BN_ULONG bl, bh; -#endif - BN_ULONG t1, t2; BN_ULONG c1, c2, c3; c1 = 0;