HMAC: How unique does a nonce need to be if the Date is also part of the signature?

Question

In a HTTP scheme where the HMAC-SHA256 signature is sent as part of the Authorization header, and the message input contains:

• The request method
• URL
• Post data
• Nonce
• Date HTTP header

How unique does the nonce need to be, or, for how long should the nonce be disallowed to be re-used?

For example, if I enforce uniqueness of (Date, nonce) rather than enforcing absolute uniqueness of the nonce on its own, have I introduced any weakness to replay or other kinds of attack?

When another second of time elapses, the signature changes (due to the Date header), so if I re-use a nonce from 1 second ago, it should not be a problem, right?

Answer 1

You need to take in consideration the allowable time window (to compensate for Clock drift). If you allow Date's with a time window of plus/minus 10 minutes (total: 20 minutes) you need to use nonces that are unique on the whole time window, and you also need to store spent nonces from that time period.

To avoid a race situation where a nonce is being deleted from the "spent" list Before the Date: header of the used nonce has became invalid, it would be recommended to store the spent nonces from the last 40 minutes, and also use nonces that are unique for 40 minutes.

Then you have a practically a watertight solution.

In other Words, if you would allow a nonce to be reused after 1 second, a attacker can just resend the old request with the old date header, since if you allow a time window - which you must because you cannot ensure the client Clock is synced with the server, then you would accept a request with a spent nonce.

If you reallywant a good nonce, use H(Time, Nonce) where H is a decent hash function. Then you can use "non-unique" nonces as long as you dont generate 2 equal nonces the same second. Then you get unique hashes to use as nonces.

Answer 2

I don't mean to be blunt, but as you're inventing your own authentication algorithm, you'll almost certainly mess it up and it will be subject to many types of attacks. I strongly suggest you study the available research papers and known cryptographic authentication algorithms before you create your own so that you know what mistakes to not make. Start with Kerberos authentication, then Zero Knowledge Proofs, then SSL/PKI.

That said, to answer your question, both the client and the server should generate nonces that are likely (or guaranteed) to be used once for your time window. Nonces are to be used Once (number once). A sufficiently large random number serves that purpose and need not be stored. Having both client and server generate a nonce (2 different nonces) means that both reduce the chance of a replay attack from the other side.

In addition, you don't want your authentication server to become an Oracle (assist an attacking client with guessing user passwords) or a spoofed server breaking user passwords (trick a client into revealing it's password), so you need to be careful how you design your algorithm. The minimum number of steps required for an authentication algorithm is four.

1. c-s: hello, I'm client + nonce_c.
2. s-c: client-challenge + nonce_s.
3. c-s: client-response + server-challenge.
4. server-response.

See the above algorithm? Client says who it is (Step 1) which includes the client nonce, then (Step 2) server asks client to prove something the server generated using both the client's nonce, a stored client authenticator (password hash, for example) and a server generated nonce. Step 3 proves the client to the server. Step 4 (which most people forget) proves the server to the client; an important step to protect your clients from spoofed server attacks (man in the middle and dns spoofing).

With this type of algorithm, you need not store nonces or worry about reusing them within some time window. Instead, make them sufficiently large and random - together the client and server participate in the creation of a nonce with sufficiently secure properties.