Merging upstream version 115.9.0esr.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 283 insertions, 17 deletions

diff --git a/security/nss/lib/freebl/mpi/mpi.c b/security/nss/lib/freebl/mpi/mpi.c
index 2e6cd84664..7749dc710f 100644
--- a/security/nss/lib/freebl/mpi/mpi.c
+++ b/security/nss/lib/freebl/mpi/mpi.c
@@ -10,6 +10,8 @@
 #include "mpi-priv.h"
 #include "mplogic.h"
 
+#include <assert.h>
+
 #if defined(__arm__) && \
     ((defined(__thumb__) && !defined(__thumb2__)) || defined(__ARM_ARCH_3__))
 /* 16-bit thumb or ARM v3 doesn't work inlined assember version */
@@ -802,15 +804,18 @@ CLEANUP:
 
 /* }}} */
 
-/* {{{ mp_mul(a, b, c) */
+/* {{{ s_mp_mulg(a, b, c) */
 
 /*
-  mp_mul(a, b, c)
+  s_mp_mulg(a, b, c)
 
-  Compute c = a * b.  All parameters may be identical.
+  Compute c = a * b.  All parameters may be identical. if constantTime is set,
+  then the operations are done in constant time. The original is mostly
+  constant time as long as s_mpv_mul_d_add() is constant time. This is true
+  of the x86 assembler, as well as the current c code.
  */
 mp_err
-mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
+s_mp_mulg(const mp_int *a, const mp_int *b, mp_int *c, int constantTime)
 {
     mp_digit *pb;
     mp_int tmp;
@@ -846,7 +851,14 @@ mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
         goto CLEANUP;
 
 #ifdef NSS_USE_COMBA
-    if ((MP_USED(a) == MP_USED(b)) && IS_POWER_OF_2(MP_USED(b))) {
+    /* comba isn't constant time because it clamps! If we cared
+     * (we needed a constant time version of multiply that was 'faster'
+     * we could easily pass constantTime down to the comba code and
+     * get it to skip the clamp... but here are assembler versions
+     * which add comba to platforms that can't compile the normal
+     * comba's imbedded assembler which would also need to change, so
+     * for now we just skip comba when we are running constant time. */
+    if (!constantTime && (MP_USED(a) == MP_USED(b)) && IS_POWER_OF_2(MP_USED(b))) {
         if (MP_USED(a) == 4) {
             s_mp_mul_comba_4(a, b, c);
             goto CLEANUP;
@@ -876,13 +888,15 @@ mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
         mp_digit b_i = *pb++;
 
         /* Inner product:  Digits of a */
-        if (b_i)
+        if (constantTime || b_i)
             s_mpv_mul_d_add(MP_DIGITS(a), useda, b_i, MP_DIGITS(c) + ib);
         else
             MP_DIGIT(c, ib + useda) = b_i;
     }
 
-    s_mp_clamp(c);
+    if (!constantTime) {
+        s_mp_clamp(c);
+    }
 
     if (SIGN(a) == SIGN(b) || s_mp_cmp_d(c, 0) == MP_EQ)
         SIGN(c) = ZPOS;
@@ -892,10 +906,54 @@ mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
 CLEANUP:
     mp_clear(&tmp);
     return res;
+} /* end smp_mulg() */
+
+/* }}} */
+
+/* {{{ mp_mul(a, b, c) */
+
+/*
+  mp_mul(a, b, c)
+
+  Compute c = a * b.  All parameters may be identical.
+ */
+
+mp_err
+mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
+{
+    return s_mp_mulg(a, b, c, 0);
 } /* end mp_mul() */
 
 /* }}} */
 
+/* {{{ mp_mulCT(a, b, c) */
+
+/*
+  mp_mulCT(a, b, c)
+
+  Compute c = a * b. In constant time. Parameters may not be identical.
+  NOTE: a and b may be modified.
+ */
+
+mp_err
+mp_mulCT(mp_int *a, mp_int *b, mp_int *c, mp_size setSize)
+{
+    mp_err res;
+
+    /* make the multiply values fixed length so multiply
+     * doesn't leak the length. at this point all the
+     * values are blinded, but once we finish we want the
+     * output size to be hidden (so no clamping the out put) */
+    MP_CHECKOK(s_mp_pad(a, setSize));
+    MP_CHECKOK(s_mp_pad(b, setSize));
+    MP_CHECKOK(s_mp_pad(c, 2 * setSize));
+    MP_CHECKOK(s_mp_mulg(a, b, c, 1));
+CLEANUP:
+    return res;
+} /* end mp_mulCT() */
+
+/* }}} */
+
 /* {{{ mp_sqr(a, sqr) */
 
 #if MP_SQUARE
@@ -1268,6 +1326,138 @@ mp_mod(const mp_int *a, const mp_int *m, mp_int *c)
 
 /* }}} */
 
+/* {{{ s_mp_subCT_d(a, b, borrow, c) */
+
+/*
+  s_mp_subCT_d(a, b, borrow, c)
+
+  Compute c = (a -b) - subtract in constant time. returns borrow
+ */
+mp_digit
+s_mp_subCT_d(mp_digit a, mp_digit b, mp_digit borrow, mp_digit *ret)
+{
+    *ret = a - b - borrow;
+    return MP_CT_LTU(a, *ret) | (MP_CT_EQ(a, *ret) & borrow);
+} /*  s_mp_subCT_d() */
+
+/* }}} */
+
+/* {{{ mp_subCT(a, b, ret, borrow) */
+
+/* return ret= a - b and borrow in borrow. done in constant time.
+ * b could be modified.
+ */
+mp_err
+mp_subCT(const mp_int *a, mp_int *b, mp_int *ret, mp_digit *borrow)
+{
+    mp_size used_a = MP_USED(a);
+    mp_size i;
+    mp_err res;
+
+    MP_CHECKOK(s_mp_pad(b, used_a));
+    MP_CHECKOK(s_mp_pad(ret, used_a));
+    *borrow = 0;
+    for (i = 0; i < used_a; i++) {
+        *borrow = s_mp_subCT_d(MP_DIGIT(a, i), MP_DIGIT(b, i), *borrow,
+                               &MP_DIGIT(ret, i));
+    }
+
+    res = MP_OKAY;
+CLEANUP:
+    return res;
+} /*  end mp_subCT() */
+
+/* }}} */
+
+/* {{{ mp_selectCT(cond, a, b, ret) */
+
+/*
+ * return ret= cond ? a : b; cond should be either 0 or 1
+ */
+mp_err
+mp_selectCT(mp_digit cond, const mp_int *a, const mp_int *b, mp_int *ret)
+{
+    mp_size used_a = MP_USED(a);
+    mp_err res;
+    mp_size i;
+
+    cond *= MP_DIGIT_MAX;
+
+    /* we currently require these to be equal on input,
+     * we could use pad to extend one of them, but that might
+     * leak data as it wouldn't be constant time */
+    if (used_a != MP_USED(b)) {
+        return MP_BADARG;
+    }
+
+    MP_CHECKOK(s_mp_pad(ret, used_a));
+    for (i = 0; i < used_a; i++) {
+        MP_DIGIT(ret, i) = MP_CT_SEL_DIGIT(cond, MP_DIGIT(a, i), MP_DIGIT(b, i));
+    }
+    res = MP_OKAY;
+CLEANUP:
+    return res;
+} /* end mp_selectCT() */
+
+/* {{{ mp_reduceCT(a, m, c) */
+
+/*
+  mp_reduceCT(a, m, c)
+
+  Compute c = aR^-1 (mod m) in constant time.
+   input should be in montgomery form. If input is the
+   result of a montgomery multiply then out put will be
+   in mongomery form.
+   Result will be reduced to MP_USED(m), but not be
+   clamped.
+ */
+
+mp_err
+mp_reduceCT(const mp_int *a, const mp_int *m, mp_digit n0i, mp_int *c)
+{
+    mp_size used_m = MP_USED(m);
+    mp_size used_c = used_m * 2 + 1;
+    mp_digit *m_digits, *c_digits;
+    mp_size i;
+    mp_digit borrow, carry;
+    mp_err res;
+    mp_int sub;
+
+    MP_DIGITS(&sub) = 0;
+    MP_CHECKOK(mp_init_size(&sub, used_m));
+
+    if (a != c) {
+        MP_CHECKOK(mp_copy(a, c));
+    }
+    MP_CHECKOK(s_mp_pad(c, used_c));
+    m_digits = MP_DIGITS(m);
+    c_digits = MP_DIGITS(c);
+    for (i = 0; i < used_m; i++) {
+        mp_digit m_i = MP_DIGIT(c, i) * n0i;
+        s_mpv_mul_d_add_propCT(m_digits, used_m, m_i, c_digits++, used_c--);
+    }
+    s_mp_rshd(c, used_m);
+    /* MP_USED(c) should be used_m+1 with the high word being any carry
+     * from the previous multiply, save that carry and drop the high
+     * word for the substraction below */
+    carry = MP_DIGIT(c, used_m);
+    MP_DIGIT(c, used_m) = 0;
+    MP_USED(c) = used_m;
+    /* mp_subCT wants c and m to be the same size, we've already
+     * guarrenteed that in the previous statement, so mp_subCT won't actually
+     * modify m, so it's safe to recast */
+    MP_CHECKOK(mp_subCT(c, (mp_int *)m, &sub, &borrow));
+
+    /* we return c-m if c >= m no borrow or there was a borrow and a carry */
+    MP_CHECKOK(mp_selectCT(borrow ^ carry, c, &sub, c));
+    res = MP_OKAY;
+CLEANUP:
+    mp_clear(&sub);
+    return res;
+} /* end mp_reduceCT() */
+
+/* }}} */
+
 /* {{{ mp_mod_d(a, d, c) */
 
 /*
@@ -1384,6 +1574,37 @@ mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c)
 
 /* }}} */
 
+/* {{{ mp_mulmontmodCT(a, b, m, c) */
+
+/*
+  mp_mulmontmodCT(a, b, m, c)
+
+  Compute c = (a * b) mod m in constant time wrt a and b. either a or b
+  should be in montgomery form and the output is native. If both a and b
+  are in montgomery form, then the output will also be in montgomery form
+  and can be recovered with an mp_reduceCT call.
+  NOTE: a and b may be modified.
+ */
+
+mp_err
+mp_mulmontmodCT(mp_int *a, mp_int *b, const mp_int *m, mp_digit n0i,
+                mp_int *c)
+{
+    mp_err res;
+
+    ARGCHK(a != NULL && b != NULL && m != NULL && c != NULL, MP_BADARG);
+
+    if ((res = mp_mulCT(a, b, c, MP_USED(m))) != MP_OKAY)
+        return res;
+
+    if ((res = mp_reduceCT(c, m, n0i, c)) != MP_OKAY)
+        return res;
+
+    return MP_OKAY;
+}
+
+/* }}} */
+
 /* {{{ mp_sqrmod(a, m, c) */
 
 #if MP_SQUARE
@@ -3941,14 +4162,62 @@ s_mp_mul(mp_int *a, const mp_int *b)
         a1b0 = (a >> MP_HALF_DIGIT_BIT) * (b & MP_HALF_DIGIT_MAX); \
         a1b0 += a0b1;                                              \
         Phi += a1b0 >> MP_HALF_DIGIT_BIT;                          \
-        if (a1b0 < a0b1)                                           \
-            Phi += MP_HALF_RADIX;                                  \
+        Phi += (MP_CT_LTU(a1b0, a0b1)) << MP_HALF_DIGIT_BIT;       \
         a1b0 <<= MP_HALF_DIGIT_BIT;                                \
         Plo += a1b0;                                               \
-        if (Plo < a1b0)                                            \
-            ++Phi;                                                 \
+        Phi += MP_CT_LTU(Plo, a1b0);                               \
+    }
+#endif
+
+/* Constant time version of s_mpv_mul_d_add_prop.
+ * Presently, this is only used by the Constant time Montgomery arithmetic code. */
+/* c += a * b */
+void
+s_mpv_mul_d_add_propCT(const mp_digit *a, mp_size a_len, mp_digit b,
+                       mp_digit *c, mp_size c_len)
+{
+#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_MUL_WORD)
+    mp_digit d = 0;
+
+    c_len -= a_len;
+    /* Inner product:  Digits of a */
+    while (a_len--) {
+        mp_word w = ((mp_word)b * *a++) + *c + d;
+        *c++ = ACCUM(w);
+        d = CARRYOUT(w);
+    }
+
+    /* propagate the carry to the end, even if carry is zero */
+    while (c_len--) {
+        mp_word w = (mp_word)*c + d;
+        *c++ = ACCUM(w);
+        d = CARRYOUT(w);
+    }
+#else
+    mp_digit carry = 0;
+    c_len -= a_len;
+    while (a_len--) {
+        mp_digit a_i = *a++;
+        mp_digit a0b0, a1b1;
+        MP_MUL_DxD(a_i, b, a1b1, a0b0);
+
+        a0b0 += carry;
+        a1b1 += MP_CT_LTU(a0b0, carry);
+        a0b0 += a_i = *c;
+        a1b1 += MP_CT_LTU(a0b0, a_i);
+
+        *c++ = a0b0;
+        carry = a1b1;
+    }
+    /* propagate the carry to the end, even if carry is zero */
+    while (c_len--) {
+        mp_digit c_i = *c;
+        carry += c_i;
+        *c++ = carry;
+        carry = MP_CT_LTU(carry, c_i);
     }
 #endif
+}
 
 #if !defined(MP_ASSEMBLY_MULTIPLY)
 /* c = a * b */
@@ -3974,8 +4243,7 @@ s_mpv_mul_d(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *c)
         MP_MUL_DxD(a_i, b, a1b1, a0b0);
 
         a0b0 += carry;
-        if (a0b0 < carry)
-            ++a1b1;
+        a1b1 += MP_CT_LTU(a0b0, carry);
         *c++ = a0b0;
         carry = a1b1;
     }
@@ -4007,11 +4275,9 @@ s_mpv_mul_d_add(const mp_digit *a, mp_size a_len, mp_digit b,
         MP_MUL_DxD(a_i, b, a1b1, a0b0);
 
         a0b0 += carry;
-        if (a0b0 < carry)
-            ++a1b1;
+        a1b1 += MP_CT_LTU(a0b0, carry);
         a0b0 += a_i = *c;
-        if (a0b0 < a_i)
-            ++a1b1;
+        a1b1 += MP_CT_LTU(a0b0, a_i);
         *c++ = a0b0;
         carry = a1b1;
     }