[security] Widespread Timing Vulnerabilities in OpenID implementations

Wed Jul 14 19:31:38 UTC 2010

On Wed, Jul 14, 2010 at 12:21, John Bradley <ve7jtb at ve7jtb.com> wrote:
> I would be happy if the nonce were marked as used independent of the signature verifying.
>
> I agree 100% the timing attack issue needs to be addressed.
>
> Even without the timing attack it is always theoretically possible though difficult brute force a HMAC.

Yes, but the theoretical bound on the minimal amount of work to
brute-force a 256-bit HMAC would probably require harnessing the
energy of a space-time wormhole or something, while the attack
discussed here based on timing can be successfully executed by a
careful programmer with access to a few machines.

>
> It is always preferable to deny any information,  so we may want to consider making a recommendation on order.

If the nonce is more predictable than the MAC, exposing a
nonce-checking endpoint might open to DoS risk. I think a good,
time-insensitive implementation of HMAC verification is probably the
best thing to run first, because it makes fewest assumptions about the
whole protocol execution environment.

>
> John B.
> On 2010-07-14, at 12:25 PM, Breno de Medeiros wrote:
>
>> I agree with Nate's assessment about the risk.
>>
>> Timing attacks over networks have been shown to be effective (at least
>> under favorable circumstances).
>>
>> Relying on the nonce to prevent this attack is not effective. The
>> security of the HMAC verification step should be independent of
>> higher-level protocol constructs.  The HMAC verification step and the
>> nonce step are implemented at different levels of abstraction (one is
>> a core cryptographic operation, the other a high-level enforcement of
>> protocol security semantics) and there is no obvious order in which to
>> apply these steps. Nonce verification performed after signature
>> verification is a correct protocol implementation and there is no
>> reason to discourage it.
>>
>> Cheers,
>>
>> --Breno.
>>
>> On Wed, Jul 14, 2010 at 09:19, Nate Lawson <nate at rootlabs.com> wrote:
>>> John Bradley wrote:
>>>> On 2010-07-14, at 1:53 AM, Nate Lawson wrote:
>>>>> 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
>>>
>>> Great, hopefully maintainers can figure out the fix. We're happy to
>>> review patches if they have them.
>>>
>>>>> 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.
>>>
>>> This brings up a problem in the OpenID spec: confusion between "nonce"
>>> and "timestamp", two very different protocol features. Really, the
>>> "response_nonce" field should be named "response_timestamp_and_nonce"
>>> except for brevity.
>>>
>>> The timestamp portion can limit the time an assertion is valid if an RP
>>> chooses to do so (spec says "MAY", ICAM says "RECOMMENDED"). The nonce
>>> portion prevents replay by extending the resolution of the timestamp, so
>>> that even two parallel responses have a unique value (spec says
>>> "SHOULD", ICAM says "MUST").
>>>
>>>>> 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.
>>>
>>> Yes, the nonce only prevents replay of operations AFTER the point at
>>> which it is checked. All operations before it is checked are subject to
>>> replay.
>>>
>>>>> 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.
>>>
>>> I don't think this can be blamed on the OpenID libraries we pointed out.
>>> Neither the specification nor ICAM require an order here, so
>>> implementations are free to do it in whatever order they want.
>>>
>>>> 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.
>>>
>>> That would be great. Which FIPS are you referring to, 140-2?
>>>
>>>>> 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.
>>>>>
>>>> Agreed,  However socializing this with the library maintainers will be much faster than trying to get the openID 2.0 spec updated.
>>>
>>> Yes, that is what we were trying to do here. However, it would be good
>>> if the spec was updated eventually as well. OpenID has a pretty strong
>>> separation between specification and numerous implementations, so we
>>> want to make sure future implementations that appear benefit from this
>>> guidance.
>>>
>>> --
>>> Nate Lawson
>>> Root Labs :: www.rootlabs.com
>>> +1 (510) 595-9505 / (415) 305-5638 mobile
>>> Solving embedded security, kernel and crypto challenges
>>>
>>> _______________________________________________
>>> security mailing list
>>> security at lists.openid.net
>>> http://lists.openid.net/mailman/listinfo/openid-security
>>>
>
>

-- 
--Breno

+1 (650) 214-1007 desk
+1 (408) 212-0135 (Grand Central)
MTV-41-3 : 383-A
PST (GMT-8) / PDT(GMT-7)