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

[Jakob Bohm]

On 07/01/2016 15:52, Michael Wojcik wrote:
> 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.)
>

This has all been discussed to death.  On the compiler in
question, *both* versions work, but some particular
invocations of this function inlined into certain other
inline functions several levels deep triggers a compiler
bug where the compiler in question throws away a different
arithmetic operation elsewhere in the code and ends up
producing the wrong result.  Changing from the portable
implementation to the old non-portable implementation
happens to avoid that compiler bug, by pure chance.

Enjoy

Jakob
-- 
Jakob Bohm, CIO, Partner, WiseMo A/S.  https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark.  Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mta.openssl.org/pipermail/openssl-users/attachments/20160107/811f5107/attachment.html>