[security] Comment on the use of nonces in OpenID Authentcation 2.0/d12

[Jose Kahan]

Hi,

Here are some first thoughts on OpenID 2.0/d12.  I'm not sure
if I'm sending them to the correct email address. Feel free
to forward elsewhere if needed. Also, I've not yet much
experience writing about OpenID, so please be tolerant if
my presentation is a bit rough.

In OpenId 2.0/d12, a positive assertion reply from the OP 
include an OP-generated nonce (openid.response_nonce, defined in 
section 10.1). Furthermore, section 11.3 states that "the agent
checking the signature keeps track of the nonce values included in 
positive assertions and never accepts the same value more than once
for the same OP Endpoint URL".

I'm concerned as to how well the use of these nonces will scale
on a highly demanded Relying Party. The RP will need to store all
those nonces for an indeterminate amount of time. In addition,
RP becomes dependent on the OP's clock values and may need
to require some rough clock synchronization. This also opens the
door to OPs that change their clock value, malicious or not. 
Finally, let's suppose we have a configuration with mirrored 
RPs, selected, say, by DNS round-robin (I'm not taking into account
how the association could be handled there). We don't know which 
of the RPs would end storing the OP nonce sent in the reply to
the checkid_setup message; if you replay the protocol, you may be
lucky and end getting access to one of the mirror RPs that didn't
store the nonce.

With all due respect, this seems to be a misuse of nonces to avoid
replays. Traditionally, party A includes a nonce in a message
sent to party B. Party B includes party's A nonce in its signed reply.
This allows party A to know that its message has not been replayed.
The value of this nonce is considered to be opaque to all except to
party A.

OpenId 2.0/d12 is using the nonce differently: Party B generates
a nonce that Party A must verify. Is there a document or note
available saying why this was specified as such?

The following paragraphs describe how OpenID could use RP-generated
nonces.

>From the implementation point of view, I think it would be make
much more sense if the Relying Party generated the nonce and have
the OP returns this nonce in its message. More precisely,
this means including the RP generated nonce in the request parameters
specified in Section 9.1. The RP needs to memorize it too, until
the OP replies. The OP needs to include this nonce 
in the Positive Assertion reply message specified in Section 10.1; 
the nonce also has to be part of the signed fields. Once the RP 
verifies the nonce, it can discard it.

Roughly, the use of the nonce starts when the RP sends the
30x redirect to the UA:

1. RP generates nonce (rpnonce) and memorizes it.

2. RP->UA
   openid.mode=checkid_setup 
   openid.assoc_handle=1234ABC
   openid_return_to=http://myrp.example.com
   ...
   openid_rpnonce=1234ABCD

3. UA->OP
   openid.mode=checkid_setup  
   openid.assoc_handle=1234ABC
   openid_return_to=http://myrp.example.com
   ...
   openid_rpnonce=1234ABCD

....

4. OP->UA
   openid.mode=id_res
   openid_assoc_handle=1234ABC
   openid_rpnonce=1234ABCD
   openid_signed=..., rpnonce, ....
   opendid_signed

5. UA->RP
   openid.mode=id_res
   openid_assoc_handle=1234ABC
   openid_rpnonce=1234ABCD
   openid_signed=..., rpnonce, ....
   opendid_signed

6. RP checks message for replay by comparing the rpnonce nonce
   against the copy it stored in memory; RP can then delete it
   from memory.

>From the above we can see that:

- RP is sure that the OP's reply is fresh because it includes
  the nonce it sent;

- RP doesn't have to worry anymore about having clock synchronization
   issues with the OP... or having to content with an OP changing
   its clock (backward or forward).

- The RP only has to memorize the nonce value until it gets the
  verified reply from the OP. Compare this with the current 
  d12 proposal, where the RP has to store the OP nonce for an 
  indefinite amount of time. This may become an issue when an RP
  handles thousands of openid transactions every hour.

- We don't need the OP nonce anymore.

But this is not yet enough to safely use RP Nonces. They should
also be binded with a signature to the request to avoid having
someone just do a cut and and paste of a valid Nonce to a replayed
message sent to the OP.

2. RP->UA
   openid.mode=checkid_setup
   openid.assoc_handle=1234ABC
   openid_return_to=http://myrp.example.com
   ...
   openid_rpnonce=1234ABCD
   openid_signed=assoc,return_to,rpnonce,...
   openid_rpsig=12345ABC

I've not given much thought to what fields would need to be signed.
As this signature and what it covers is basically part of the 
counter-measure against replay attacks, we can save some bytes
and just say that it's implementation-dependent and out-of scope. 
Indeed, the OP doesn't care about what fields were signed by the 
RP; only the RP needs to know it. It is only important that the answer
from the OP includes the same fields that were signed.

We could even have something in the end like this:

2. RP->UA
   openid.mode=checkid_setup
   openid.assoc_handle=1234ABC
   openid_return_to=http://myrp.example.com
   ...
   openid_rpnonce=2007-11-23T18:42:01Z:UNIQUE:SIGNATURE

Although this RP nonce proposal requires doing some slight 
extra processing on the RP server, I think that in the long term it 
offers an equivalent protection against replays and scales better
than the actual proposal 2.0/d12 nonce proposal. There's no need
to store state indefinitely on the RP or need to synchronize 
clocks.

On the other hand, a drawback is that the nonces have to be stored
on the RP side until the OP replies (or times out). This could be 
used as a DOS attack by making multiple requests on the RP.

A last word concerning the use of multiple mirrored RP servers.
Suppose we have the following RP pool,
RP1.example.org, RP2.example.org, ... selected thru the generic
DNS name RP.example.org. In the RP nonce proposal, the RP
has to store the nonce value. If we include the hostname (or IP@)
of the RP server in the openid_return_to field, we make sure
that the UA will always come back to the "correct" RP server:

2. RP->UA
   openid.mode=checkid_setup
   openid.assoc_handle=1234ABC
   openid_return_to=http://RP1.example.com
   ...
   openid_rpnonce=2007-11-23T18:42:01Z:UNIQUE:SIGNATURE

As before, I don't take into account how mirrored RPs could share 
the OP association. In general, I  think it would be interesting 
to see more notes on scalability and OpenID, e.g. how to setup 
multiple mirrored OpenID consumers, performance stats, and have a 
forum to discuss this with other developers.

Many thanks for your time. I'm looking forward to go deeper in my
exploration of OpenID consumers.

-jose