How long should a random nonce be?

Question

NIST provides good guidelines on the length of keys and hashes for various algorithms. But I don't see anything specifically on the length of a random or pseudo-random nonce (number used once).

If there is a single good answer for a variety of uses, I'd love to see that. But to make this concrete, I'll use the common "password reset via email" situation, in which the server generates a URL with a pseudo-random path component. It seems a bit similar to HTTP Digest Authentication, in which the example in the RFC seems to have 136 bits (dcd98b7102dd2f0e8b11d0f600bfb0c093).

I note that many folks seem to use version 4 UUIDs (which provide 122 pseudo-random bits) or this, as discussed at Are GUIDs safe for one-time tokens?, though the user has to beware the use of previous much-more-predictable UUID versions, and nasty persistent local attacks on the Windows random number generator which were mostly patched by 2008.

But ignoring the riskiness of getting tangled up in UUID versions and implementations, how many pseudo-random bits should be incorporated in the URL?

Answer 1

A 64-bit nonce is likely more than sufficient for most practical purposes, if the 64 bits are crypto-quality randomness.

Why is 64 bits sufficient? Let me lay out the kind of reasoning you can use to answer this question. I'll assume this is a single-use time-limited URL; after it is used once, it is no longer valid, and after a little while (3 days, say), it expires and is no longer valid. Since the nonce is only meaningful to the server, the only way that an attacker can try a guess is to send the 64-bit guess to the server and see how the server responds. How many guesses can the attacker try in the time before the nonce expires? Let's say the attacker can make 1000 HTTP requests per second (that's a pretty beefy attacker); then the attacker can make about 1000*3600*24*3 = 2²⁸ guesses within a 3-day period. Each guess has a 1/2⁶⁴ chance of being right. Therefore, the attacker has at most a 1/2³⁶ chance of breaking the scheme. That should be more than secure enough for most settings.

Answer 2

First, estimate the maximum amount of uses your system will get (the amount of times a random nonce will be generated). Next, decide on an acceptable security level, that is, how improbable it must be that a nonce is a duplicate of an old one. Calculate the amount of uses in bits, double that and add the improbability you need in bits and you have your nonce length.

An example from AES-GCM with random IV. The number of invocations allowed with random IV for a certain key is 2³². The probability that an IV is reused must be less than 2^-32. The required nonce length for this is 32 × 2 + 32 == 96 bits.

If, hypothetically, you'd want to be able to generate 2⁹⁶ packets, each with a random nonce and would want the probability of a duplicate nonce be less than 2^-32, you'd need a nonce that is 96 × 2 + 32 == 224 bits long.

Comparing this to the above answer of 64 bits... if you have more than 2¹⁶ (65536) uses of your system, the probability of having a duplicate nonce in that time is more than 2^-32 (more than 1 in 4 billion, short scale). This might be quite acceptable, depending on your security requirements, or it might not be.

As a one size fits all answer - the random UUIDs mentioned are a pretty okay solution.

Do note that these values are approximations, and the more accurate calculations are much more complex.

Answer 3

For a password reset, you would use a salt rather than a nonce for the token. That is, you simply need to generate a salt, store it for a period of time associated with the user account, and wait for the user to click the link with that salt in it. You do not need to track these tokens to ensure they are never used more than once. Once a token has been used, simply delete it.

You should use at least 128 bits, generated by a cryptographically strong pseudo-random number generator. You do not need a UUID format - you just need a sufficiently long cryptorandom string.

For URLs, you can use either the base64url encoding or the hex encoding. The base64url encoding will be shorter, but will be case-sensitive. The base64url encoding is slightly different from the base64 encoding in that no terminating ='s are needed and the + and / are switched out for - and _, which characters do not need to be specially encoded for urls.