[openssl-dev] [openssl.org #3852] bn_gfm2.c: in BN_GF2m_mod_arr() a check is optimized out

[Wim Lewis via RT]

On May 18, 2015, at 1:41 PM, Andy Polyakov via RT <rt at openssl.org> wrote:
>> Found by the https://github.com/xiw/stack tool and then I checked the
>> generated asm (gcc and clang) to confirm.
>> 
>> In the check "if (d0 && tmp_ulong)" tmp_ulong always evaluates to true
>> because the compiler optimizes out the tmp_ulong value to true because
>> (tmp_ulong = zz >> d1;) zz >> d1 has according to the compiler (LLVM)
>> a logical right-shift overflow.
> 
> What's right-shift overflow? In either case, are you sure about it being
> optimized away because it always evaluates to true? Thing is that if
> tmp_ulong is 0, then xor-ing with it won't have effect on result. I mean
> check for d0 alone would actually produce same outcome, wouldn't it?

Right-shifting by *equal to* or more than the width of the word produces undefined results in C (just like left-shifting); one expects that it produces zero, but the language spec says it’s undefined. Presumably, clang is taking advantage of the undefined behavior to eliminate the check: it notices that if, in this case, an excessive right shift always returns a nonzero value (which is allowed), then it can produce smaller code.

(From http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf section 6.5.7:  "If the value of the right operand is negative or is
greater than or equal to the width of the promoted left operand, the behavior is undefined." See also e.g.: http://blog.regehr.org/archives/213 )

I agree that the test for tmp_ulong being nonzero is redundant. And the shift overflow presumably only happens when d0 is zero anyway, so the undefined behavior can't affect the output. But it might make sense to move the right-shift into the if() as well.

Given the commit message was "don't write beyond buffer", though, I think there was possibly intended to be a different test there that makes more sense?