[security] Widespread Timing Vulnerabilities in OpenID implementations

Taylor Nelson taylor at rootlabs.com
Tue Jul 13 20:32:50 UTC 2010


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.

Thanks,

-- 
Taylor Nelson
Root Labs :: www.rootlabs.com
+1 (510) 595-9505 / (510) 410-0066 mobile
Solving embedded security, kernel and crypto challenges



More information about the security mailing list