On 10/12/2015 19:13, Benjamin Kaduk wrote:
> On 12/10/2015 12:09 PM, openssl-users at dukhovni.org wrote:
>>> On Dec 10, 2015, at 12:45 PM, Jakob Bohm <jb-openssl at wisemo.com> wrote:
>>>
>>> On 10/12/2015 18:33, Viktor Dukhovni wrote:
>>>> On Thu, Dec 10, 2015 at 04:55:29AM -0700, Jayalakshmi bhat wrote:
>>>>
>>>>
>>>>> 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))));
>>>>> }
>>>>>
>>>> The replacement is not right. This function is supposed to return
>>>> 0xfffffff for inputs with the high bit set, and 0x0000000 for inputs
>>>> with the high bit not set. Could you try:
>>>>
>>>> static inline unsigned int constant_time_msb(unsigned int a) {
>>>> return 0 - (a >> ((int)(sizeof(a) * 8 - 1)));
>>>> }
>>>>
>>>> Just in case the compiler is promoting "a" to the (larger?) size
>>>> of sizeof(a), which would cause an unsigned "a" to get a zero MSB,
>>>> while a signed "a" would be promoted "correctly".
>>>>
>>> Look again, he is casting a to signed, then doing an
>>> arithmetic right shift to extend the msb (sign bit)
>>> to the rest of the word. This works on 3 conditions:
>> I saw what he's doing. casting (a) to an int, instead of leaving
>> it unsigned is not an improvement. On the assumption that it made
>> a difference for this compiler, I proposed an alternative that tests
>> whether promotion to the type of the shift's right operand is taking
>> place. It would be good to know whether explicitly casting the shift
>> width to an int helps. Also that 8 could be replaced by CHAR_BIT
>> just in case.
>>
> Yeah, sizeof returning a size_t that is wider than int, causing
> promotion of the left argument of the shift operator prior to evaluation
> seems a plausible explanation for this behavior.
Please stop the misinformed guesswork and read the
disassembly posted.
The compiler in question gets confused by the long
sequence of nested inline expressions and looses the
truncation from 32 bit unsigned to 8 bit unsigned
char in the shuffle.
Changing back to the old form of constant_time_msb
simplifies the parse tree just enough to avoid the bug.
Unfortunately, as a comment in the 1.0.2 source code
explains, the old form relies on a language feature
not guaranteed by the C standard, which is probably
why the implementation was changed to the one
currently in 1.0.2.
And to those who still don't understand how the old
implementation worked:
1. By casting the unsigned a to a signed int, the msb
of interest becomes the sign bit.
2. By shifting right the 2's complement signed int by
the number of non-sign bits (31 on this target),
the sign bit gets replicated to the other bits so
negative values (those with the msb set) become -1,
while positive values (those with the msb clear)
become +0.
3. Casting back to unsigned int results in the
desired value of 0xFFFFFFFF or 0x00000000 .
On the ARM platform, shifting right by 31 bits can be
done to the second input of any arithmetic
instruction, thus making it execute in 0.5 instruction
time if combined with some other operation. Thus the
compiler moves the shift backwards through some
arithmetic steps in the zero testing, resulting in the
code you see in the posted disassembly.
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/20151210/c1c266ce/attachment-0001.html>
