[security] Widespread Timing Vulnerabilities in OpenID implementations

[Phillip Hallam-Baker]

It really is hard to predict what the loop unroll logic of a future
compiler is going to produce. There are optimizing compilers that do
have the intelligence to eliminate evaluation of expressions of the
form (true OR f(x)).

To make the code robust I think you have to have a #pragma nooptimize
type capability. And I am not even sure if those exist or are
respected in many of the current compilers.

One very simple way of improving the robustness of the code would be
to do the compare in 64 or 32 bit chunks. That way the chance of
leaving an exploitable timing hole is much smaller. It also speeds up
the code considerably.


On Thu, Jul 15, 2010 at 1:19 PM, Nate Lawson <nate at rootlabs.com> wrote:
> Phillip Hallam-Baker wrote:
>> On 15 Jul 2010, at 12:41, Nate Lawson <nate at rootlabs.com> wrote:
>>> We're talking 6 lines of code for the constant time implementation (not
>>> counting comments). I'll paste it again just to be clear:
>>>
>>> /*
>>> * Constant time compare for secret values.
>>> * Returns 0 if they are equal, non-zero if they aren't.
>>> */
>>> int
>>> secret_cmp(uint8_t *a, uint8_t *b, size_t n)
>>> {
>>>    int result = 0;
>>>
>>>    // Catch bad programming case of zero length
>>>    if (n == 0)
>>>        return 1;
>>>
>>>    // Compare all bytes of array, accumulating differences
>>>    while (n--)
>>>        result |= *a++ ^ *b++;
>>>
>>>    return result != 0;
>>> }
>>>
>>> I can't even imagine how a pseudorandom implementation can be as simple
>>> or obviously correct/secure. Please enlighten me.
>>
>> What if the compiler unrolls the loop during optimization
>>
>> Once unrolled it will be optimized back to the original
>
> That makes no difference. Assume you're comparing two HMACs that are 20
> bytes long. Then you will have 20 XORs in a row. That has no impact on
> whether the logic is constant-time or not.
>
> It *is* hard to guarantee timing in high-level languages. But even with
> C, you have cache and branch prediction behavior that require deep
> awareness of the platform to eliminate.
>
> However, the above function does not have any logical flaws that
> introduce timing leaks. It isn't remotely exploitable on any of the
> platforms we analyzed. Isn't it better to start from there rather than
> introducing vulnerabilities?
>
> --
> Nate Lawson
> Root Labs :: www.rootlabs.com
> +1 (510) 595-9505 / (415) 305-5638 mobile
> Solving embedded security, kernel and crypto challenges
>
>



-- 
Website: http://hallambaker.com/