[security] Widespread Timing Vulnerabilities in OpenID implementations

[John Bradley]

Inline
On 2010-07-14, at 1:53 AM, Nate Lawson wrote:

> John,
> 
> Let's not let this discussion cloud what we are announcing: all OpenID
> libraries we reviewed leak timing information about the correct HMAC.
> This is a security bug and should be fixed, just like it has been in
> Ruby on Rails, Java JCE, Google Keyczar, etc.
> 
Agreed

> The fix is simple. There is no performance impact. (Short-circuiting an
> HMAC compare is only optimizing for an attacker.) Our original email
> listed references to other advisories to help maintainers understand the
> problem.
> 
> With that out of the way, all that's left to discuss are exploit
> scenarios. We purposefully left out details in this public discussion as
> we figured the security ramifications of an HMAC timing attack would be
> clear. However, we can discuss exploit scenarios before our talk if it's
> helpful to you.
> 
> I fail to see how OpenID specification language about the RP checking
> nonces prevents the attack as you suggest it does. The nonce is there to
> prevent replays of valid assertions that an attacker sniffed between the
> RP and OP.
> 
The nonce limits the time that the assertion is valid.   Given that this attack relies on the assertion being replayed with different signatures it limits the time an attacker has to perform the compromise.

> If you're depending on order of operations, there is no specification
> requirement that the RP validate nonces before the HMAC signature is
> verified. An implementation can return a "signature failed" error for a
> message with a fixed nonce multiple times, enabling this timing attack.
> 
True,  I need to look at if we should be more specific about that in the ICAM profile.

Checking the nonce/timestamp before the signature limits the effectiveness of this and perhaps future attacks against HMAC.

> Quoting portions of section 11.3 of the OpenID 2.0 spec:
> 
> ###
> When the Relying Party checks the signature on an assertion, the Relying
> Party SHOULD ensure that an assertion has not yet been accepted with the
> same value for "openid.response_nonce" from the same OP Endpoint URL.
> 
> The time-stamp MAY be used to reject responses that are too far away
> from the current time, limiting the amount of time that nonces must be
> stored to prevent attacks.
> ###
> 
> As you can see, the vague language in the first part ("When the RP
> checks the signature...") means an implementation can check the nonce
> either before or after the signature. If it does so after, it is
> exploitable. The attacker can choose a timestamp a few days in the
> future, perform the timing attack, and then save the correct
> Authentication Response until it becomes valid.
> 
> We reviewed the implementations mentioned in Taylor's initial mail
> before contacting this list. The JOpenID implementation does not
> validate nonces at all ("TODO"). The Python and Ruby implementations
> (http://www.janrain.com/openid-enabled) validate nonces, but do it
> *after* checking the signature.

As I said the quality of  openID libraries varies widely.  I have found more than one that completely failed to check the signature.
As well as OP's that did not sign all of the required elements.

The ICAM profile of openID 2.0 is available at:
http://idmanagement.gov/drilldown.cfm?action=openID_openGOV

We will look at tightening up the language for nonce checking, as well as guidance on the timing attack.

Likely that is covered in FIPS guidelines, but it is unlikely that openID authors have read all of those guidelines.

> 
> Here is a trimmed version of the appropriate function in the Python
> consumer.py:
> 
>    def _doIdRes(self, message, endpoint, return_to):
>        # Checks for presence of appropriate fields (and checks
>        # signed list fields)
>        self._idResCheckForFields(message)
> 
>        if not self._checkReturnTo(message, return_to):
>            raise ProtocolError(...)
> 
>        # Verify discovery information:
>        endpoint = self._verifyDiscoveryResults(message, endpoint)
> 
>        self._idResCheckSignature(message, endpoint.server_url)
> 
>        # Will raise a ProtocolError if the nonce is bad
>        self._idResCheckNonce(message, endpoint)
> 
> Here's the similar code for Ruby:
>      def id_res
>        check_for_fields
>        verify_return_to
>        verify_discovery_results
>        check_signature
>        check_nonce
>      end
> 
> As you can see, the various fields are checked, signature is checked,
> and lastly the nonce is checked. This is perfectly valid according to
> the OpenID 2.0 spec. However, it allows a timing attack to proceed
> because the attacker can send the RP many copies of the forged
> Authentication Response, iteratively guessing the correct HMAC for it.
> The response_nonce field can be held constant.
> 
> Side channel attacks are tricky business. We've spent most of our
> careers working with them, in areas other than web security. Given how
> simple the fix is, we think it is better not to rely on this timing
> attack accidentally not being exploitable in a given implementation.
> 
> Additionally, we think it would be good to provide additional
> specification guidance to implementers on the need to avoid leaking info
> about the HMAC and to validate the nonce before the signature.
> 
> Thanks,
> Nate
> 
Agreed,  However socializing this with the library maintainers will be much faster than trying to get the openID 2.0 spec updated.

Regards
John Bradley

> 
> John Bradley wrote:
>> Thanks for the clarification.
>> 
>> For the ICAM profile we require the RP to perform nonce validation.
>> 
>> That would effectively stop this attack.
>> 
>> While all RP should perform nonce checking per the openID 2.0 spec some may not and would be vulnerable.
>> 
>> Regards
>> John Bradley
>> 
>> 
>> On 2010-07-13, at 7:36 PM, Nate Lawson wrote:
>> 
>>> 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
>>> 
> 
> -- 
> Nate Lawson
> Root Labs :: www.rootlabs.com
> +1 (510) 595-9505 / (415) 305-5638 mobile
> Solving embedded security, kernel and crypto challenges
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4767 bytes
Desc: not available
URL: <http://lists.openid.net/pipermail/openid-security/attachments/20100714/2564c81e/attachment.bin>