Attached is a patch that makes all the arithmetic in constant-time operations unsigned. This avoids two sources of unspecified behavior in the C standard:
- Signed right shifts, when the sign bit is 1, are implementation-defined (C99 §6.5.7/5); - Converting an unsigned integer to signed when out of signed range is also implementation-defined, and may trap (C99 §6.3.1.3/3). The code and formulas are based off of https://gist.github.com/sneves/10845247, and all the formulas have been computer-verified, using a SAT solver, to be correct. The formula for "less than" is essentially the same as the current one, but optimized to use 5 instead of 7 bitwise operations; the formula for "greater or equal" is simply the negation of "less than", and can be simplified as such. Generating masks using -(unsigned >> 31) requires one more operation than the arithmetic shift version, but compilers seem to be pretty good at recognizing and generating the arithmetic shift anyway, where available.
>From 5e78c9653bb473e9ad3ac015b755f08750b9a651 Mon Sep 17 00:00:00 2001 From: Samuel Neves <[email protected]> Date: Sat, 4 Oct 2014 00:13:36 +0100 Subject: [PATCH] Use only unsigned arithmetic in constant-time operations --- crypto/constant_time_locl.h | 16 +++------------- 1 file changed, 3 insertions(+), 13 deletions(-) diff --git a/crypto/constant_time_locl.h b/crypto/constant_time_locl.h index c048393..6ec4a0c 100644 --- a/crypto/constant_time_locl.h +++ b/crypto/constant_time_locl.h @@ -129,17 +129,12 @@ static inline int constant_time_select_int(unsigned int mask, int a, int b); static inline unsigned int constant_time_msb(unsigned int a) { - return (unsigned int)((int)(a) >> (sizeof(int) * 8 - 1)); + return -(a >> (sizeof(unsigned int) * 8 - 1)); } 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); + return constant_time_msb(a^((a^b)|((a-b)^b))); } static inline unsigned char constant_time_lt_8(unsigned int a, unsigned int b) @@ -149,12 +144,7 @@ static inline unsigned char constant_time_lt_8(unsigned int a, unsigned int b) 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); + return ~constant_time_lt(a, b); } static inline unsigned char constant_time_ge_8(unsigned int a, unsigned int b) -- 1.9.3
