Bug 1831983 - Add a constant time select function. r=mtHEADmaster

Differential Revision: https://phabricator.services.mozilla.com/D177803

9 files changed, 160 insertions, 0 deletions

diff --git a/automation/abi-check/expected-report-libnssutil3.so.txt b/automation/abi-check/expected-report-libnssutil3.so.txt
index e69de29bb..53459c96c 100644
--- a/automation/abi-check/expected-report-libnssutil3.so.txt
+++ b/automation/abi-check/expected-report-libnssutil3.so.txt
@@ -0,0 +1,5 @@
+
+1 Added function:
+
+  'function void NSS_SecureSelect(void*, void*, void*, size_t, unsigned char)'    {NSS_SecureSelect@@NSSUTIL_3.90}
+
diff --git a/gtests/util_gtest/manifest.mn b/gtests/util_gtest/manifest.mn
index 87ebdfb33..279e276ec 100644
--- a/gtests/util_gtest/manifest.mn
+++ b/gtests/util_gtest/manifest.mn
@@ -13,6 +13,7 @@ CPPSRCS = \
         util_memcmpzero_unittest.cc \
         util_pkcs11uri_unittest.cc \
         util_secasn1d_unittest.cc \
+        util_select_unittest.cc \
         util_utf8_unittest.cc \
         $(NULL)
 
diff --git a/gtests/util_gtest/util_gtest.gyp b/gtests/util_gtest/util_gtest.gyp
index e924df04f..df1a095dc 100644
--- a/gtests/util_gtest/util_gtest.gyp
+++ b/gtests/util_gtest/util_gtest.gyp
@@ -17,6 +17,7 @@
         'util_memcmpzero_unittest.cc',
         'util_pkcs11uri_unittest.cc',
         'util_secasn1d_unittest.cc',
+        'util_select_unittest.cc',
         'util_utf8_unittest.cc',
       ],
       'dependencies': [
diff --git a/gtests/util_gtest/util_select_unittest.cc b/gtests/util_gtest/util_select_unittest.cc
new file mode 100644
index 000000000..f62357c9b
--- /dev/null
+++ b/gtests/util_gtest/util_select_unittest.cc
@@ -0,0 +1,55 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "gtest/gtest.h"
+#include "scoped_ptrs_util.h"
+
+namespace nss_test {
+
+class SelectTest : public ::testing::Test {
+ protected:
+  void test_select(std::vector<uint8_t> &dest, const std::vector<uint8_t> &src0,
+                   const std::vector<uint8_t> &src1, unsigned char b) {
+    EXPECT_EQ(src0.size(), src1.size());
+    EXPECT_GE(dest.size(), src0.size());
+    return NSS_SecureSelect(dest.data(), src0.data(), src1.data(), src0.size(),
+                            b);
+  };
+};
+
+TEST_F(SelectTest, TestSelectZero) {
+  std::vector<uint8_t> dest(32, 255);
+  std::vector<uint8_t> src0(32, 0);
+  std::vector<uint8_t> src1(32, 1);
+  test_select(dest, src0, src1, 0);
+  EXPECT_EQ(dest, src0);
+}
+
+TEST_F(SelectTest, TestSelectOne) {
+  std::vector<uint8_t> dest(32, 255);
+  std::vector<uint8_t> src0(32, 0);
+  std::vector<uint8_t> src1(32, 1);
+  test_select(dest, src0, src1, 1);
+  EXPECT_EQ(dest, src1);
+}
+
+TEST_F(SelectTest, TestSelect170) {
+  std::vector<uint8_t> dest(32, 255);
+  std::vector<uint8_t> src0(32, 0);
+  std::vector<uint8_t> src1(32, 1);
+  test_select(dest, src0, src1, 170);
+  EXPECT_EQ(dest, src1);
+}
+
+TEST_F(SelectTest, TestSelect255) {
+  std::vector<uint8_t> dest(32, 255);
+  std::vector<uint8_t> src0(32, 0);
+  std::vector<uint8_t> src1(32, 1);
+  test_select(dest, src0, src1, 255);
+  EXPECT_EQ(dest, src1);
+}
+
+}  // namespace nss_test
diff --git a/lib/freebl/stubs.c b/lib/freebl/stubs.c
index 82b5b2e78..3697a7aff 100644
--- a/lib/freebl/stubs.c
+++ b/lib/freebl/stubs.c
@@ -86,6 +86,10 @@
     if (ptr_##fn) {                         \
         return ptr_##fn(a1, a2, a3, a4);    \
     }
+#define STUB_SAFE_CALL5(fn, a1, a2, a3, a4, a5) \
+    if (ptr_##fn) {                                 \
+        return ptr_##fn(a1, a2, a3, a4, a5);    \
+    }
 #define STUB_SAFE_CALL6(fn, a1, a2, a3, a4, a5, a6) \
     if (ptr_##fn) {                                 \
         return ptr_##fn(a1, a2, a3, a4, a5, a6);    \
@@ -177,6 +181,7 @@ STUB_DECLARE(void, SECITEM_ZfreeItem_Util, (SECItem * zap, PRBool freeit));
 STUB_DECLARE(SECOidTag, SECOID_FindOIDTag_Util, (const SECItem *oid));
 STUB_DECLARE(int, NSS_SecureMemcmp, (const void *a, const void *b, size_t n));
 STUB_DECLARE(unsigned int, NSS_SecureMemcmpZero, (const void *mem, size_t n));
+STUB_DECLARE(void, NSS_SecureSelect, (void *dest, const void *src0, const void *src1, size_t n, unsigned char b));
 
 #define PORT_ZNew_stub(type) (type *)PORT_ZAlloc_stub(sizeof(type))
 #define PORT_New_stub(type) (type *)PORT_Alloc_stub(sizeof(type))
@@ -700,6 +705,13 @@ NSS_SecureMemcmpZero_stub(const void *mem, size_t n)
     abort();
 }
 
+extern void
+NSS_SecureSelect_stub(void *dest, const void *src0, const void *src1, size_t n, unsigned char b)
+{
+    STUB_SAFE_CALL5(NSS_SecureSelect, dest, src0, src1, n, b);
+    abort();
+}
+
 #ifdef FREEBL_NO_WEAK
 
 static const char *nsprLibName = SHLIB_PREFIX "nspr4." SHLIB_SUFFIX;
@@ -753,6 +765,7 @@ freebl_InitNSSUtil(void *lib)
     STUB_FETCH_FUNCTION(SECOID_FindOIDTag_Util);
     STUB_FETCH_FUNCTION(NSS_SecureMemcmp);
     STUB_FETCH_FUNCTION(NSS_SecureMemcmpZero);
+    STUB_FETCH_FUNCTION(NSS_SecureSelect);
     return SECSuccess;
 }
 
diff --git a/lib/freebl/stubs.h b/lib/freebl/stubs.h
index e6d9ed03a..f773e1043 100644
--- a/lib/freebl/stubs.h
+++ b/lib/freebl/stubs.h
@@ -42,6 +42,7 @@
 #define SECOID_FindOIDTag SECOID_FindOIDTag_stub
 #define NSS_SecureMemcmp NSS_SecureMemcmp_stub
 #define NSS_SecureMemcmpZero NSS_SecureMemcmpZero_stub
+#define NSS_SecureSelect NSS_SecureSelect_stub
 
 #define PR_Assert PR_Assert_stub
 #define PR_Access PR_Access_stub
diff --git a/lib/util/nssutil.def b/lib/util/nssutil.def
index fa0373074..a48794e47 100644
--- a/lib/util/nssutil.def
+++ b/lib/util/nssutil.def
@@ -348,3 +348,9 @@ PK11URI_GetQueryAttributeItem;
 ;+    local:
 ;+       *;
 ;+};
+;+NSSUTIL_3.90 {         # NSS Utilities 3.90 release
+;+    global:
+NSS_SecureSelect;
+;+    local:
+;+       *;
+;+};
diff --git a/lib/util/secport.c b/lib/util/secport.c
index 8594072df..fb5223d64 100644
--- a/lib/util/secport.c
+++ b/lib/util/secport.c
@@ -800,3 +800,80 @@ NSS_SecureMemcmpZero(const void *mem, size_t n)
     /* 0 <= r < 256, so -r has bit 8 set when r != 0 */
     return 1 & (-r >> 8);
 }
+
+/*
+ * A "value barrier" prevents the compiler from making optimizations based on
+ * the value that a variable takes.
+ *
+ * Standard C does not have value barriers, so C implementations of them are
+ * compiler-specific and are not guaranteed to be effective. Thus, the value
+ * barriers here are a best-effort, defense-in-depth, strategy. They are not a
+ * substitute for standard constant-time programming discipline.
+ *
+ * Some implementations have a performance penalty, so value barriers should
+ * be used sparingly.
+ */
+static inline int
+value_barrier_int(int x)
+{
+#if defined(__GNUC__) || defined(__clang__)
+    /* This inline assembly trick from Chandler Carruth's CppCon 2015 talk
+     * generates no instructions.
+     *
+     * "+r"(x) means that x will be mapped to a register that is both an input
+     * and an output to the assembly routine (""). The compiler will not
+     * inspect the assembly routine itself, so it cannot assume anything about
+     * the value of x after this line.
+     */
+    __asm__(""
+            : "+r"(x)
+            : /* no other inputs */);
+    return x;
+#else
+    /* If the compiler does not support the inline assembly trick above, we can
+     * put x in `volatile` storage and read it out again. This will generate
+     * explict store and load instructions, and possibly more depending on the
+     * target.
+     */
+    volatile int y = x;
+    return y;
+#endif
+}
+
+/*
+ * A branch-free implementation of
+ *      if (!b) {
+ *           memmove(dest, src0, n);
+ *      } else {
+ *           memmove(dest, src1, n);
+ *      }
+ *
+ * The memmove is performed with src0 if `b == 0` and with src1
+ * otherwise.
+ *
+ * As with memmove, the selected src can overlap dest.
+ *
+ * Each of dest, src0, and src1 must point to an allocated buffer
+ * of at least n bytes.
+ */
+void
+NSS_SecureSelect(void *dest, const void *src0, const void *src1, size_t n, unsigned char b)
+
+{
+    // This value barrier makes it safe for the compiler to inline
+    // NSS_SecureSelect into a routine where it could otherwise infer something
+    // about the value of b, e.g. that b is 0/1 valued.
+    int w = value_barrier_int(b);
+
+    // 0 <= b < 256, and int is at least 16 bits, so -w has bits 8-15
+    // set when w != 0.
+    unsigned char mask = 0xff & (-w >> 8);
+
+    for (size_t i = 0; i < n; ++i) {
+        unsigned char s0i = ((unsigned char *)src0)[i];
+        unsigned char s1i = ((unsigned char *)src1)[i];
+        // if mask == 0 this simplifies to s0 ^ 0
+        // if mask == -1 this simplifies to s0 ^ s0 ^ s1
+        ((unsigned char *)dest)[i] = s0i ^ (mask & (s0i ^ s1i));
+    }
+}
diff --git a/lib/util/secport.h b/lib/util/secport.h
index fc1e1f538..fa587b28a 100644
--- a/lib/util/secport.h
+++ b/lib/util/secport.h
@@ -261,6 +261,7 @@ extern int NSS_PutEnv(const char *envVarName, const char *envValue);
 
 extern int NSS_SecureMemcmp(const void *a, const void *b, size_t n);
 extern unsigned int NSS_SecureMemcmpZero(const void *mem, size_t n);
+extern void NSS_SecureSelect(void *dest, const void *src0, const void *src1, size_t n, unsigned char b);
 
 /*
  * Load a shared library called "newShLibName" in the same directory as