From 9018f3ce0f9fd57e65d8e7d43741f08797811766 Mon Sep 17 00:00:00 2001 From: Rich Salz Date: Tue, 20 Jun 2017 15:21:21 -0400 Subject: [PATCH] Add constant-time 64 Standardize comments. Reviewed-by: Andy Polyakov (Merged from https://github.com/openssl/openssl/pull/3727) --- include/internal/constant_time_locl.h | 57 ++++++++++++-------- test/constant_time_test.c | 77 ++++++++++++++++++++++++--- 2 files changed, 105 insertions(+), 29 deletions(-) diff --git a/include/internal/constant_time_locl.h b/include/internal/constant_time_locl.h index be2730ea95..dad6d8cb99 100644 --- a/include/internal/constant_time_locl.h +++ b/include/internal/constant_time_locl.h @@ -21,17 +21,14 @@ extern "C" { * The boolean methods return a bitmask of all ones (0xff...f) for true * and 0 for false. This is useful for choosing a value based on the result * of a conditional in constant time. For example, - * - * if (a < b) { - * c = a; - * } else { - * c = b; - * } - * + * if (a < b) { + * c = a; + * } else { + * c = b; + * } * can be written as - * - * unsigned int lt = constant_time_lt(a, b); - * c = constant_time_select(lt, a, b); + * unsigned int lt = constant_time_lt(a, b); + * c = constant_time_select(lt, a, b); */ /* @@ -41,35 +38,31 @@ extern "C" { * replace this with something else on odd CPUs. */ static ossl_inline unsigned int constant_time_msb(unsigned int a); +/* Convenience method for uint64_t. */ +static ossl_inline uint64_t constant_time_msb_64(uint64_t a); -/* - * Returns 0xff..f if a < b and 0 otherwise. - */ +/* Returns 0xff..f if a < b and 0 otherwise. */ static ossl_inline unsigned int constant_time_lt(unsigned int a, unsigned int b); /* Convenience method for getting an 8-bit mask. */ static ossl_inline unsigned char constant_time_lt_8(unsigned int a, unsigned int b); +/* Convenience method for uint64_t. */ +static ossl_inline uint64_t constant_time_lt_64(uint64_t a, uint64_t b); -/* - * Returns 0xff..f if a >= b and 0 otherwise. - */ +/* Returns 0xff..f if a >= b and 0 otherwise. */ static ossl_inline unsigned int constant_time_ge(unsigned int a, unsigned int b); /* Convenience method for getting an 8-bit mask. */ static ossl_inline unsigned char constant_time_ge_8(unsigned int a, unsigned int b); -/* - * Returns 0xff..f if a == 0 and 0 otherwise. - */ +/* Returns 0xff..f if a == 0 and 0 otherwise. */ static ossl_inline unsigned int constant_time_is_zero(unsigned int a); /* Convenience method for getting an 8-bit mask. */ static ossl_inline unsigned char constant_time_is_zero_8(unsigned int a); -/* - * Returns 0xff..f if a == b and 0 otherwise. - */ +/* Returns 0xff..f if a == b and 0 otherwise. */ static ossl_inline unsigned int constant_time_eq(unsigned int a, unsigned int b); /* Convenience method for getting an 8-bit mask. */ @@ -94,15 +87,24 @@ static ossl_inline unsigned int constant_time_select(unsigned int mask, static ossl_inline unsigned char constant_time_select_8(unsigned char mask, unsigned char a, unsigned char b); +/* Convenience method for uint64_t. */ +static ossl_inline uint64_t constant_time_select_64(uint64_t mask, uint64_t a, + uint64_t b); /* Convenience method for signed integers. */ static ossl_inline int constant_time_select_int(unsigned int mask, int a, int b); + static ossl_inline unsigned int constant_time_msb(unsigned int a) { return 0 - (a >> (sizeof(a) * 8 - 1)); } +static ossl_inline uint64_t constant_time_msb_64(uint64_t a) +{ + return 0 - (a >> 63); +} + static ossl_inline size_t constant_time_msb_s(size_t a) { return 0 - (a >> (sizeof(a) * 8 - 1)); @@ -125,6 +127,11 @@ static ossl_inline unsigned char constant_time_lt_8(unsigned int a, return (unsigned char)(constant_time_lt(a, b)); } +static ossl_inline uint64_t constant_time_lt_64(uint64_t a, uint64_t b) +{ + return constant_time_msb_64(a ^ ((a ^ b) | ((a - b) ^ b))); +} + static ossl_inline unsigned int constant_time_ge(unsigned int a, unsigned int b) { @@ -227,6 +234,12 @@ static ossl_inline int constant_time_select_int_s(size_t mask, int a, int b) (unsigned)(b))); } +static ossl_inline uint64_t constant_time_select_64(uint64_t mask, uint64_t a, + uint64_t b) +{ + return (mask & a) | (~mask & b); +} + #ifdef __cplusplus } #endif diff --git a/test/constant_time_test.c b/test/constant_time_test.c index 3e3542e864..422c04ca27 100644 --- a/test/constant_time_test.c +++ b/test/constant_time_test.c @@ -21,6 +21,8 @@ static const unsigned char CONSTTIME_TRUE_8 = 0xff; static const unsigned char CONSTTIME_FALSE_8 = 0; static const size_t CONSTTIME_TRUE_S = ~((size_t)0); static const size_t CONSTTIME_FALSE_S = 0; +static uint64_t CONSTTIME_TRUE_64 = (uint64_t)(~(uint64_t)0); +static uint64_t CONSTTIME_FALSE_64 = 0; static int test_binary_op(unsigned int (*op) (unsigned int a, unsigned int b), const char *op_name, unsigned int a, unsigned int b, @@ -56,6 +58,25 @@ static int test_binary_op_s(size_t (*op) (size_t a, size_t b), return 1; } +static int test_binary_op_64(uint64_t (*op)(uint64_t a, uint64_t b), + const char *op_name, uint64_t a, uint64_t b, + int is_true) +{ + uint64_t c = op(a, b); + + if (is_true && c != CONSTTIME_TRUE_64) { + TEST_error("TRUE %s op failed", op_name); + BIO_printf(bio_err, "a=%jx b=%jx\n", a, b); + return 0; + } else if (!is_true && c != CONSTTIME_FALSE_64) { + TEST_error("FALSE %s op failed", op_name); + BIO_printf(bio_err, "a=%jx b=%jx\n", a, b); + return 0; + } + return 1; +} + + static int test_is_zero(unsigned int a) { if (a == 0 && !TEST_uint_eq(constant_time_is_zero(a), CONSTTIME_TRUE)) @@ -110,6 +131,23 @@ static int test_select_s(unsigned char a, unsigned char b) return 1; } +static int test_select_64(uint64_t a, uint64_t b) +{ + uint64_t selected = constant_time_select_64(CONSTTIME_TRUE_64, a, b); + + if (selected != a) { + TEST_error("test_select_64 TRUE failed"); + BIO_printf(bio_err, "a=%jx b=%jx got %jx wanted a\n", a, b, selected); + return 0; + } + selected = constant_time_select_64(CONSTTIME_FALSE_64, a, b); + if (selected != b) { + BIO_printf(bio_err, "a=%jx b=%jx got %jx wanted b\n", a, b, selected); + return 0; + } + return 1; +} + static int test_select_int(int a, int b) { if (!TEST_int_eq(constant_time_select_int(CONSTTIME_TRUE, a, b), a)) @@ -146,26 +184,33 @@ static int test_eq_int(int a, int b) return 1; } -static unsigned int test_values[] = - { 0, 1, 1024, 12345, 32000, UINT_MAX / 2 - 1, +static unsigned int test_values[] = { + 0, 1, 1024, 12345, 32000, UINT_MAX / 2 - 1, UINT_MAX / 2, UINT_MAX / 2 + 1, UINT_MAX - 1, UINT_MAX }; -static unsigned char test_values_8[] = - { 0, 1, 2, 20, 32, 127, 128, 129, 255 }; +static unsigned char test_values_8[] = { + 0, 1, 2, 20, 32, 127, 128, 129, 255 +}; -static int signed_test_values[] = { 0, 1, -1, 1024, -1024, 12345, -12345, +static int signed_test_values[] = { + 0, 1, -1, 1024, -1024, 12345, -12345, 32000, -32000, INT_MAX, INT_MIN, INT_MAX - 1, INT_MIN + 1 }; -static size_t test_values_s[] = - { 0, 1, 1024, 12345, 32000, SIZE_MAX / 2 - 1, +static size_t test_values_s[] = { + 0, 1, 1024, 12345, 32000, SIZE_MAX / 2 - 1, SIZE_MAX / 2, SIZE_MAX / 2 + 1, SIZE_MAX - 1, SIZE_MAX }; +static uint64_t test_values_64[] = { + 0, 1, 1024, 12345, 32000, 32000000, 32000000001, UINT64_MAX / 2, + UINT64_MAX / 2 + 1, UINT64_MAX - 1, UINT64_MAX +}; + static int test_sizeofs(void) { if (!TEST_uint_eq(OSSL_NELEM(test_values), OSSL_NELEM(test_values_s))) @@ -264,6 +309,23 @@ static int test_8values(int i) return ret; } +static int test_64values(int i) +{ + uint64_t g = test_values_64[i]; + int j, ret = 1; + + for (j = i + 1; j < (int)OSSL_NELEM(test_values_64); j++) { + uint64_t h = test_values_64[j]; + + if (!test_binary_op_64(&constant_time_lt_64, "constant_time_lt_64", + g, h, g < h) + || !test_select_64(g, h)) { + TEST_info("test_64values failed i=%d j=%d", i, j); + ret = 0; + } + } + return ret; +} void register_tests(void) { @@ -271,4 +333,5 @@ void register_tests(void) ADD_ALL_TESTS(test_binops, OSSL_NELEM(test_values)); ADD_ALL_TESTS(test_signed, OSSL_NELEM(signed_test_values)); ADD_ALL_TESTS(test_8values, sizeof(test_values_8)); + ADD_ALL_TESTS(test_64values, sizeof(test_values_64)); } -- 2.25.1