[security] Widespread Timing Vulnerabilities in OpenID implementations

[Nate Lawson]

Hi John. Thanks for the response. I think you're misunderstanding the
attack.

The goal is not to guess the server's master secret. You're correct this
particular attack would not work for that. The goal is to discover the
correct HMAC for an arbitrary token.

Since the server has to generate the correct HMAC over a token to
compare against the HMAC it supplied, the correct answer is always known
by the server. It is extremely important that the server keep that data
secret.

By timing how long it takes the server to reject the token, the attacker
can incrementally discover the correct HMAC a byte at a time. The
attacker keeps resubmitting the token, iterating over its HMAC value
until the server finally accepts it.

The timing attack must be repeated for each token the attacker wants to
forge. However, getting access to an administrator token, for example,
is often game over and no further attacks need to be performed.

While this attack does not reveal the server's master secret, it can
just be repeated for any tokens the attacker wants to forge. I hope this
clears things up.

Thanks,
Nate

John Bradley wrote:
> Interesting,
> 
> I see the timing attack on the comparison, however I don't see that this can be used to shorten the time it would take to recover the shared secret for a HMAC-SHA256
> 
> Remember that HMAC algorithm XOR's the secret with ipad (string of 36) then concatenates the message and hashes that.  
> It then XORs the secret with opad (string 5c ) and concatenates that with the previous hash value and reapplies the hash function over the new string.
> 
> The examples you site presuppose that if you generate a HMAC with the correct first byte that the output HMAC will have the correct first byte in the comparison.
> 
> If you were hashing the string and XORing it with the secret that would be the case.
> 
> For the ICAM profile of openID we limit association to 24h to force key rotation and use HMAC-SHA256 to increase the difficulty of brute force attacks.
> 
> That said I agree that using a constant time comparison is preferable.
> 
> However I don't want people panicking and thinking openID security is broken across all implementations.
> 
> I look forward to your paper.  
> 
> Regards
> John Bradley
> 
> On 2010-07-13, at 4:32 PM, Taylor Nelson wrote:
> 
>> Every OpenID implementation I have checked this far has contained timing dependent compares in the HMAC verification, allowing a remote attacker to forge valid tokens.
>>
>> In JOpenId:
>> There is a timing vulnerability in thegetAuthentication  function in trunk/JOpenId/src/org/expressme/openid/OpenIdManager.java
>>
>> In janrain python/ruby implementations:
>> There is a timing vulnerability in the checkMessageSignature function in association.py
>> There is a timing vulnerability in the check_message_signature function in lib/openid/association.rb
>>
>> The ==, equals(), and their equivalent functions in other languages terminate early,
>> allowing an attacker to incrementally guess the correct HMAC for an arbitrary message by
>> repeatedly sending a bogus message with a given HMAC and measuring how
>> long it takes for the server to terminate the connection. Since the
>> comparison takes longer the more bytes an attacker gets correct, this
>> allows a client to forge messages with arbitrary contents that will be
>> accepted as valid by the server.
>>
>> The fix is simple -- implement a function that is timing-independent for
>> comparing secret values. Here is one example in C:
>>
>> /*
>> * 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;
>> }
>>
>> Be careful about implementing this function, particularly in other
>> languages, as some code still has data-dependent branches. For example,
>> the C ternary operator (x == y ? 0 : 1) introduces a branch. Here's an
>> article that gives more info on what to avoid:
>>
>> http://rdist.root.org/2010/01/07/timing-independent-array-comparison/
>>
>> We'll be giving a talk at Blackhat USA on July 28 regarding the
>> exploitability of remote timing attacks. It will analyze how small a
>> timing delta can be distinguished from various vantage points (WAN, LAN,
>> guest-to-guest VMs, etc.) It will also analyze how distinguishable
>> comparison loops are in various languages (C, Java, Python, Ruby).
>>
>> Here are some other advisories for this flaw in other systems:
>>
>> http://rdist.root.org/2009/05/28/timing-attack-in-google-keyczar-library/
>> http://codahale.com/a-lesson-in-timing-attacks/
>>
>> If you have any other questions about the bug or how to fix it, please
>> let us know.


-- 
Nate Lawson
Root Labs :: www.rootlabs.com
+1 (510) 595-9505 / (415) 305-5638 mobile
Solving embedded security, kernel and crypto challenges