Constant-time utilities.
Pull constant-time methods out to a separate header, add tests.
(Imported from upstream's 9a9b0c0401cae443f115ff19921d347b20aa396b and
27739e92659d38cdefa21e51b7f52b81a7ac3388)
Change-Id: Id570f5c531aca791112929e6258989f43c8a78d7
diff --git a/crypto/CMakeLists.txt b/crypto/CMakeLists.txt
index d820e82..a42d92d 100644
--- a/crypto/CMakeLists.txt
+++ b/crypto/CMakeLists.txt
@@ -166,5 +166,13 @@
$<TARGET_OBJECTS:pkcs8>
)
+add_executable(
+ constant_time_test
+
+ constant_time_test.c
+)
+
+target_link_libraries(constant_time_test crypto)
+
perlasm(cpu-x86_64-asm.${ASM_EXT} cpu-x86_64-asm.pl)
perlasm(cpu-x86-asm.${ASM_EXT} cpu-x86-asm.pl)
diff --git a/crypto/internal.h b/crypto/internal.h
index ffac2d5..a63f7a7 100644
--- a/crypto/internal.h
+++ b/crypto/internal.h
@@ -149,6 +149,88 @@
void OPENSSL_cpuid_setup(void);
#endif
+#if !defined(inline)
+#define inline __inline
+#endif
+
+
+/* Constant-time utility functions.
+ *
+ * The following 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;
+ * }
+ *
+ * can be written as
+ *
+ * unsigned int lt = constant_time_lt(a, b);
+ * c = a & lt | b & ~lt; */
+
+/* constant_time_msb returns the given value with the MSB copied to all the
+ * other bits. Uses the fact that arithmetic shift shifts-in the sign bit.
+ * However, this is not ensured by the C standard so you may need to replace
+ * this with something else on odd CPUs. */
+static inline unsigned int constant_time_msb(unsigned int a) {
+ return (unsigned int)((int)(a) >> (sizeof(int) * 8 - 1));
+}
+
+/* constant_time_lt returns 0xff..f if a < b and 0 otherwise. */
+static inline unsigned int constant_time_lt(unsigned int a, unsigned int b) {
+ unsigned int lt;
+ /* Case 1: msb(a) == msb(b). a < b iff the MSB of a - b is set.*/
+ lt = ~(a ^ b) & (a - b);
+ /* Case 2: msb(a) != msb(b). a < b iff the MSB of b is set. */
+ lt |= ~a & b;
+ return constant_time_msb(lt);
+}
+
+/* constant_time_lt_8 acts like |constant_time_lt| but returns an 8-bit mask. */
+static inline uint8_t constant_time_lt_8(unsigned int a, unsigned int b) {
+ return (uint8_t)(constant_time_lt(a, b));
+}
+
+/* constant_time_gt returns 0xff..f if a >= b and 0 otherwise. */
+static inline unsigned int constant_time_ge(unsigned int a, unsigned int b) {
+ unsigned int ge;
+ /* Case 1: msb(a) == msb(b). a >= b iff the MSB of a - b is not set.*/
+ ge = ~((a ^ b) | (a - b));
+ /* Case 2: msb(a) != msb(b). a >= b iff the MSB of a is set. */
+ ge |= a & ~b;
+ return constant_time_msb(ge);
+}
+
+/* constant_time_ge_8 acts like |constant_time_ge| but returns an 8-bit mask. */
+static inline uint8_t constant_time_ge_8(unsigned int a, unsigned int b) {
+ return (uint8_t)(constant_time_ge(a, b));
+}
+
+/* constant_time_is_zero returns 0xff..f if a == 0 and 0 otherwise. */
+static inline unsigned int constant_time_is_zero(unsigned int a) {
+ return constant_time_msb(~a & (a - 1));
+}
+
+/* constant_time_is_zero_8 acts like constant_time_is_zero but returns an 8-bit
+ * mask. */
+static inline uint8_t constant_time_is_zero_8(unsigned int a) {
+ return (uint8_t)(constant_time_is_zero(a));
+}
+
+/* constant_time_eq returns 0xff..f if a == b and 0 otherwise. */
+static inline unsigned int constant_time_eq(unsigned int a, unsigned int b) {
+ return constant_time_is_zero(a ^ b);
+}
+
+/* constant_time_eq_8 acts like constant_time_eq but returns an 8-bit mask. */
+static inline uint8_t constant_time_eq_8(unsigned int a, unsigned int b) {
+ return (uint8_t)(constant_time_eq(a, b));
+}
+
+
#if defined(__cplusplus)
} /* extern C */
#endif
diff --git a/ssl/s3_cbc.c b/ssl/s3_cbc.c
index 6a0de9c..04bfd6d 100644
--- a/ssl/s3_cbc.c
+++ b/ssl/s3_cbc.c
@@ -55,6 +55,7 @@
#include <openssl/obj.h>
#include <openssl/sha.h>
+#include "../crypto/internal.h"
#include "ssl_locl.h"
@@ -67,37 +68,6 @@
* supported by TLS.) */
#define MAX_HASH_BLOCK_SIZE 128
-/* Some utility functions are needed:
- *
- * These macros return the given value with the MSB copied to all the other
- * bits. They use the fact that arithmetic shift shifts-in the sign bit.
- * However, this is not ensured by the C standard so you may need to replace
- * them with something else on odd CPUs. */
-#define DUPLICATE_MSB_TO_ALL(x) ( (unsigned)( (int)(x) >> (sizeof(int)*8-1) ) )
-#define DUPLICATE_MSB_TO_ALL_8(x) ((unsigned char)(DUPLICATE_MSB_TO_ALL(x)))
-
-/* constant_time_lt returns 0xff if a<b and 0x00 otherwise. */
-static unsigned constant_time_lt(unsigned a, unsigned b)
- {
- a -= b;
- return DUPLICATE_MSB_TO_ALL(a);
- }
-
-/* constant_time_ge returns 0xff if a>=b and 0x00 otherwise. */
-static unsigned constant_time_ge(unsigned a, unsigned b)
- {
- a -= b;
- return DUPLICATE_MSB_TO_ALL(~a);
- }
-
-/* constant_time_eq_8 returns 0xff if a==b and 0x00 otherwise. */
-static unsigned char constant_time_eq_8(unsigned a, unsigned b)
- {
- unsigned c = a ^ b;
- c--;
- return DUPLICATE_MSB_TO_ALL_8(c);
- }
-
/* ssl3_cbc_remove_padding removes padding from the decrypted, SSLv3, CBC
* record in |rec| by updating |rec->length| in constant time.
*
@@ -181,7 +151,7 @@
for (i = 0; i < to_check; i++)
{
- unsigned char mask = constant_time_ge(padding_length, i);
+ unsigned char mask = constant_time_ge_8(padding_length, i);
unsigned char b = rec->data[rec->length-1-i];
/* The final |padding_length+1| bytes should all have the value
* |padding_length|. Therefore the XOR should be zero. */
@@ -189,14 +159,8 @@
}
/* If any of the final |padding_length+1| bytes had the wrong value,
- * one or more of the lower eight bits of |good| will be cleared. We
- * AND the bottom 8 bits together and duplicate the result to all the
- * bits. */
- good &= good >> 4;
- good &= good >> 2;
- good &= good >> 1;
- good <<= sizeof(good)*8-1;
- good = DUPLICATE_MSB_TO_ALL(good);
+ * one or more of the lower eight bits of |good| will be cleared. */
+ good = constant_time_eq(0xff, good & 0xff);
padding_length = good & (padding_length+1);
rec->length -= padding_length;
@@ -269,8 +233,8 @@
memset(rotated_mac, 0, md_size);
for (i = scan_start, j = 0; i < orig_len; i++)
{
- unsigned char mac_started = constant_time_ge(i, mac_start);
- unsigned char mac_ended = constant_time_ge(i, mac_end);
+ unsigned char mac_started = constant_time_ge_8(i, mac_start);
+ unsigned char mac_ended = constant_time_ge_8(i, mac_end);
unsigned char b = rec->data[i];
rotated_mac[j++] |= b & mac_started & ~mac_ended;
j &= constant_time_lt(j,md_size);
@@ -593,8 +557,8 @@
b = data[k-header_length];
k++;
- is_past_c = is_block_a & constant_time_ge(j, c);
- is_past_cp1 = is_block_a & constant_time_ge(j, c+1);
+ is_past_c = is_block_a & constant_time_ge_8(j, c);
+ is_past_cp1 = is_block_a & constant_time_ge_8(j, c+1);
/* If this is the block containing the end of the
* application data, and we are at the offset for the
* 0x80 value, then overwrite b with 0x80. */
