[security] Widespread Timing Vulnerabilities in OpenID implementations

[Nate Lawson]

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