[openssl-users] CBC ciphers + TLS 1.0 protocol does not work in OpenSSL 1.0.2d

[Michael Wojcik]

The proposed change:

------
static inline unsigned int constant_time_msb(unsigned int a)
{
-    return 0 - (a >> (sizeof(a) * 8 - 1));
+   return (((unsigned)((int)(a) >> (sizeof(int) * 8 - 1))));
}
-----

produces an implementation-defined value in C99. See the final sentence of ISO 9899-1999 6.5.7 #5:

    The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type
    or if E1 has a signed type and a nonnegative value, the value of the result is the integral
    part of the quotient of E1 / 2**E2. If E1 has a signed type and a negative value, the
    resulting value is implementation-defined.

Some implementations fill with the sign bit in this case; some fill with 0. It's possible the standard allows some other behavior.

Ignoring the CHAR_BITS issue, the shift portion of the original version looks correct to me, assuming no padding bits. (The latter assumption might as well be made, because it's unlikely the other bit-fiddling constant-time functions work under an implementation with padding bits, and such implementations are uncommon.) For an unsigned left operand, that right-shift should produce either 0 or 1, corresponding to the value of the MSB.

That leaves us (in the original code) with the "0 -" part. The intent here is to have the function return either 0 (if the shift operation results in 0) or high-values (i.e., an unsigned int with all bits set). Your new code could return 1 under some implementations for values with the MSB set, so it's not equivalent.

Should the "0 -" part work correctly? The usual arithmetic conversions (6.3.1.8 #1) convert the 0 to 0U (i.e., 0 as an unsigned int), because int and unsigned int have the same rank. So we either 0U - 0U, which is trivially 0, or 0U - 1U. The result of the latter is -1, which is outside the range of unsigned int; so the resulting value is computed by adding UINT_MAX+1 to it (notionally - this addition is per the normal rules of arithmetic, not constrained by the C implementation). The result is UINT_MAX, which is within the range of unsigned integer.

So if you see incorrect values from the original code, that looks like another compiler bug, unless I'm missing something in the standard, or your implementation doesn't conform to C99. (I don't think the relevant sections where changed by C11, but I could be wrong.) Unfortunately, while your alternative might work around it for some cases, it isn't guaranteed to produce the correct result on all implementations.

Note also that changing "sizeof(a)" to "sizeof(int)" has no effect. Each unsigned integer type has the same width as the corresponding integer type. That change just makes the code longer and more fragile if the type of "a" is changed later. (And the parentheses around "a" in the original are unnecessary - sizeof is an operator, not a function.)

-- 
Michael Wojcik
Technology Specialist, Micro Focus