Add a value barrier to constant-time selects.

Clang recognizes the (mask & a) | (~mask & b) pattern as a select. While
it often optimizes this into a cmov, it sometimes inserts branches
instead, particularly when it detects a string of cmovs with the same
condition.

In the long term, we need language-level support for expressing our
constraints. In the short term, introduce value barriers to prevent the
compiler from reasoning about our bit tricks. Thanks to Chandler Carruth
for suggesting this pattern. It should be reasonably robust, short of
value-based PGO or the compiler learning to reason about empty inline
assembly blocks.

Apply barriers to our various constant-time selects. We should invest
more in the valgrind-based tooling to figure out if there are other
instances.

Change-Id: Icc24ce36a61f7fec021a762c27197b9c5bd28c5d
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/36484
Reviewed-by: Chandler Carruth <chandlerc@google.com>
Reviewed-by: Adam Langley <agl@google.com>

1 files changed, 37 insertions, 1 deletions

diff --git a/crypto/internal.h b/crypto/internal.h
index b80f065..76a317a 100644
--- a/crypto/internal.h
+++ b/crypto/internal.h
@@ -240,6 +240,36 @@ typedef uint32_t crypto_word_t;
 #define CONSTTIME_TRUE_8 ((uint8_t)0xff)
 #define CONSTTIME_FALSE_8 ((uint8_t)0)
 
+// value_barrier_w returns |a|, but prevents GCC and Clang from reasoning about
+// the returned value. This is used to mitigate compilers undoing constant-time
+// code, until we can express our requirements directly in the language.
+//
+// Note the compiler is aware that |value_barrier_w| has no side effects and
+// always has the same output for a given input. This allows it to eliminate
+// dead code, move computations across loops, and vectorize.
+static inline crypto_word_t value_barrier_w(crypto_word_t a) {
+#if !defined(OPENSSL_NO_ASM) && (defined(__GNUC__) || defined(__clang__))
+  __asm__("" : "+r"(a) : /* no inputs */);
+#endif
+  return a;
+}
+
+// value_barrier_u32 behaves like |value_barrier_w| but takes a |uint32_t|.
+static inline uint32_t value_barrier_u32(uint32_t a) {
+#if !defined(OPENSSL_NO_ASM) && (defined(__GNUC__) || defined(__clang__))
+  __asm__("" : "+r"(a) : /* no inputs */);
+#endif
+  return a;
+}
+
+// value_barrier_u64 behaves like |value_barrier_w| but takes a |uint64_t|.
+static inline uint64_t value_barrier_u64(uint64_t a) {
+#if !defined(OPENSSL_NO_ASM) && (defined(__GNUC__) || defined(__clang__))
+  __asm__("" : "+r"(a) : /* no inputs */);
+#endif
+  return a;
+}
+
 // constant_time_msb_w returns the given value with the MSB copied to all the
 // other bits.
 static inline crypto_word_t constant_time_msb_w(crypto_word_t a) {
@@ -352,7 +382,13 @@ static inline uint8_t constant_time_eq_int_8(int a, int b) {
 static inline crypto_word_t constant_time_select_w(crypto_word_t mask,
                                                    crypto_word_t a,
                                                    crypto_word_t b) {
-  return (mask & a) | (~mask & b);
+  // Clang recognizes this pattern as a select. While it usually transforms it
+  // to a cmov, it sometimes further transforms it into a branch, which we do
+  // not want.
+  //
+  // Adding barriers to both |mask| and |~mask| breaks the relationship between
+  // the two, which makes the compiler stick with bitmasks.
+  return (value_barrier_w(mask) & a) | (value_barrier_w(~mask) & b);
 }
 
 // constant_time_select_8 acts like |constant_time_select| but operates on