Fix CVE-2014-3570: properly calculate the square of a BIGNUM value.

See https://www.openssl.org/news/secadv_20150108.txt for a more detailed
discussion.

Original OpenSSL patch here:
https://github.com/openssl/openssl/commit/a7a44ba55cb4f884c6bc9ceac90072dea38e66d0

The regression test is modified a little for KNF.
ok miod@

1 files changed, 123 insertions, 120 deletions

diff --git a/src/lib/libcrypto/bn/bn_asm.c b/src/lib/libcrypto/bn/bn_asm.c
index c6efd2513a..49f0ba5d7b 100644
--- a/src/lib/libcrypto/bn/bn_asm.c
+++ b/src/lib/libcrypto/bn/bn_asm.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_asm.c,v 1.13 2014/07/11 08:44:47 jsing Exp $ */
+/* $OpenBSD: bn_asm.c,v 1.14 2015/02/25 15:39:49 bcook Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -495,116 +495,143 @@ bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
 /* 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++;
-
-#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++;
+/*
+ * 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 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)
-
-#define mul_add_c(a,b,c0,c1,c2) {       \
-        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;    \
-        }
-
-#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;    \
-        }
-
-#define sqr_add_c(a,i,c0,c1,c2) {       \
-        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;    \
-        }
+/*
+ * 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, 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)        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_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;    \
-        }
-
-#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 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;    \
-        }
+/*
+ * 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)        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)         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++;
-
-#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++;
+/*
+ * 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)         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)
@@ -613,12 +640,6 @@ bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
 void
 bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 {
-#ifdef 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;
@@ -723,12 +744,6 @@ bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 void
 bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 {
-#ifdef 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;
@@ -769,12 +784,6 @@ bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
 void
 bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
 {
-#ifdef 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;
@@ -851,12 +860,6 @@ bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
 void
 bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
 {
-#ifdef 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;