From fe079e35fb06df3a88ab51c361b95bad410702d7 Mon Sep 17 00:00:00 2001 From: "John M. Schanck" Date: Wed, 17 May 2023 16:59:04 +0000 Subject: Bug 1831983 - Add a constant time select function. r=mt Differential Revision: https://phabricator.services.mozilla.com/D177803 --- .../abi-check/expected-report-libnssutil3.so.txt | 5 ++ gtests/util_gtest/manifest.mn | 1 + gtests/util_gtest/util_gtest.gyp | 1 + gtests/util_gtest/util_select_unittest.cc | 55 ++++++++++++++++ lib/freebl/stubs.c | 13 ++++ lib/freebl/stubs.h | 1 + lib/util/nssutil.def | 6 ++ lib/util/secport.c | 77 ++++++++++++++++++++++ lib/util/secport.h | 1 + 9 files changed, 160 insertions(+) create mode 100644 gtests/util_gtest/util_select_unittest.cc 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 &dest, const std::vector &src0, + const std::vector &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 dest(32, 255); + std::vector src0(32, 0); + std::vector src1(32, 1); + test_select(dest, src0, src1, 0); + EXPECT_EQ(dest, src0); +} + +TEST_F(SelectTest, TestSelectOne) { + std::vector dest(32, 255); + std::vector src0(32, 0); + std::vector src1(32, 1); + test_select(dest, src0, src1, 1); + EXPECT_EQ(dest, src1); +} + +TEST_F(SelectTest, TestSelect170) { + std::vector dest(32, 255); + std::vector src0(32, 0); + std::vector src1(32, 1); + test_select(dest, src0, src1, 170); + EXPECT_EQ(dest, src1); +} + +TEST_F(SelectTest, TestSelect255) { + std::vector dest(32, 255); + std::vector src0(32, 0); + std::vector 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 -- cgit v1.2.1