From b7862891fed4cfb5ec36a31d35e14b51bf26d01e Mon Sep 17 00:00:00 2001
From: Andy Polyakov <appro@openssl.org>
Date: Fri, 6 Jul 2018 15:02:29 +0200
Subject: [PATCH] bn/bn_lib.c: add BN_FLG_FIXED_TOP flag.

The new flag marks vectors that were not treated with bn_correct_top,
in other words such vectors are permitted to be zero padded. For now
it's BN_DEBUG-only flag, as initial use case for zero-padded vectors
would be controlled Montgomery multiplication/exponentiation, not
general purpose. For general purpose use another type might be more
appropriate. Advantage of this suggestion is that it's possible to
back-port it...

bn/bn_div.c: fix memory sanitizer problem.
bn/bn_sqr.c: harmonize with BN_mul.

Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6707)

(cherry picked from commit 305b68f1a2b6d4d0aa07a6ab47ac372f067a40bb)

Resolved conflicts:
	crypto/bn/bn_lcl.h
---
 crypto/bn/bn_div.c |  1 +
 crypto/bn/bn_lcl.h | 18 +++++++++++++++---
 crypto/bn/bn_lib.c | 15 +++++++++++----
 crypto/bn/bn_sqr.c | 10 ++--------
 4 files changed, 29 insertions(+), 15 deletions(-)

diff --git a/crypto/bn/bn_div.c b/crypto/bn/bn_div.c
index 5e620b2096..aa13ce603c 100644
--- a/crypto/bn/bn_div.c
+++ b/crypto/bn/bn_div.c
@@ -240,6 +240,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
     wnum.neg = 0;
     wnum.d = &(snum->d[loop]);
     wnum.top = div_n;
+    wnum.flags = BN_FLG_STATIC_DATA;
     /*
      * only needed when BN_ucmp messes up the values between top and max
      */
diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h
index 5fb3814554..6c35ea66f8 100644
--- a/crypto/bn/bn_lcl.h
+++ b/crypto/bn/bn_lcl.h
@@ -145,7 +145,16 @@ extern "C" {
  */
 
 # ifdef BN_DEBUG
-
+/*
+ * The new BN_FLG_FIXED_TOP flag marks vectors that were not treated with
+ * bn_correct_top, in other words such vectors are permitted to have zeros
+ * in most significant limbs. Such vectors are used internally to achieve
+ * execution time invariance for critical operations with private keys.
+ * It's BN_DEBUG-only flag, because user application is not supposed to
+ * observe it anyway. Moreover, optimizing compiler would actually remove
+ * all operations manipulating the bit in question in non-BN_DEBUG build.
+ */
+#  define BN_FLG_FIXED_TOP 0x10000
 #  ifdef BN_DEBUG_RAND
 /* To avoid "make update" cvs wars due to BN_DEBUG, use some tricks */
 #   ifndef RAND_bytes
@@ -177,8 +186,10 @@ int RAND_bytes(unsigned char *buf, int num);
         do { \
                 const BIGNUM *_bnum2 = (a); \
                 if (_bnum2 != NULL) { \
-                        OPENSSL_assert(((_bnum2->top == 0) && !_bnum2->neg) || \
-                                (_bnum2->top && (_bnum2->d[_bnum2->top - 1] != 0))); \
+                        int _top = _bnum2->top; \
+                        OPENSSL_assert((_top == 0 && !_bnum2->neg) || \
+                               (_top && ((_bnum2->flags & BN_FLG_FIXED_TOP) \
+                                         || _bnum2->d[_top - 1] != 0))); \
                         bn_pollute(_bnum2); \
                 } \
         } while(0)
@@ -197,6 +208,7 @@ int RAND_bytes(unsigned char *buf, int num);
 
 # else                          /* !BN_DEBUG */
 
+#  define BN_FLG_FIXED_TOP 0
 #  define bn_pollute(a)
 #  define bn_check_top(a)
 #  define bn_fix_top(a)           bn_correct_top(a)
diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c
index 6c57a53869..25eac396e0 100644
--- a/crypto/bn/bn_lib.c
+++ b/crypto/bn/bn_lib.c
@@ -375,15 +375,17 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
     memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
 #endif
 
-    a->top = b->top;
     a->neg = b->neg;
+    a->top = b->top;
+    a->flags |= b->flags & BN_FLG_FIXED_TOP;
     bn_check_top(a);
     return (a);
 }
 
 #define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \
                                     | BN_FLG_CONSTTIME   \
-                                    | BN_FLG_SECURE))
+                                    | BN_FLG_SECURE      \
+                                    | BN_FLG_FIXED_TOP))
 #define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED))
 
 void BN_swap(BIGNUM *a, BIGNUM *b)
@@ -424,8 +426,9 @@ void BN_clear(BIGNUM *a)
     bn_check_top(a);
     if (a->d != NULL)
         OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
-    a->top = 0;
     a->neg = 0;
+    a->top = 0;
+    a->flags &= ~BN_FLG_FIXED_TOP;
 }
 
 BN_ULONG BN_get_word(const BIGNUM *a)
@@ -446,6 +449,7 @@ int BN_set_word(BIGNUM *a, BN_ULONG w)
     a->neg = 0;
     a->d[0] = w;
     a->top = (w ? 1 : 0);
+    a->flags &= ~BN_FLG_FIXED_TOP;
     bn_check_top(a);
     return (1);
 }
@@ -687,6 +691,7 @@ int BN_set_bit(BIGNUM *a, int n)
         for (k = a->top; k < i + 1; k++)
             a->d[k] = 0;
         a->top = i + 1;
+        a->flags &= ~BN_FLG_FIXED_TOP;
     }
 
     a->d[i] |= (((BN_ULONG)1) << j);
@@ -919,8 +924,9 @@ int BN_security_bits(int L, int N)
 
 void BN_zero_ex(BIGNUM *a)
 {
-    a->top = 0;
     a->neg = 0;
+    a->top = 0;
+    a->flags &= ~BN_FLG_FIXED_TOP;
 }
 
 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
@@ -1044,5 +1050,6 @@ void bn_correct_top(BIGNUM *a)
     }
     if (a->top == 0)
         a->neg = 0;
+    a->flags &= ~BN_FLG_FIXED_TOP;
     bn_pollute(a);
 }
diff --git a/crypto/bn/bn_sqr.c b/crypto/bn/bn_sqr.c
index 44e7332acf..737123218c 100644
--- a/crypto/bn/bn_sqr.c
+++ b/crypto/bn/bn_sqr.c
@@ -82,14 +82,8 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
     }
 
     rr->neg = 0;
-    /*
-     * If the most-significant half of the top word of 'a' is zero, then the
-     * square of 'a' will max-1 words.
-     */
-    if (a->d[al - 1] == (a->d[al - 1] & BN_MASK2l))
-        rr->top = max - 1;
-    else
-        rr->top = max;
+    rr->top = max;
+    bn_correct_top(rr);
     if (r != rr && BN_copy(r, rr) == NULL)
         goto err;
 
-- 
2.25.1