How long should a random nonce be?

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?

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 = 228 guesses within a 3-day period. Each guess has a 1/264 chance of being right. Therefore, the attacker has at most a 1/236 chance of breaking the scheme. That should be more than secure enough for most settings.

• I want to drive a stake thru this idea that a version 4 GUID has more than 6 guessable bits. If you disagree with the references I cited, please be specific about why. Jan 31, 2011 at 16:02
• @nealmcb, Sorry if my mention of GUIDs took us on a tangent. I've deleted all mention of GUIDs. I think the question of how many random bits are contained in a GUID should be reserved for a separate question / separate page on this site (as I think your original framing of the question wisely anticipates).
– D.W.
Feb 1, 2011 at 7:13
• The answer is quite correct if the only use of the "nonce" is to be a token that the attacker must supply correctly for an attack. In this case, there is no harm in getting duplicates for this nonce, hence the number doesn't need to be unique, or used only once. If there are other security concerns involved (for example if the username is not incorporated in the reset link), a 64-bit nonce is likely to be just a tad bit iffy - although it's probably still more likely to win in the lottery than to get any problems. Aug 11, 2011 at 20:51

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 232. 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 296 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 216 (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.

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.

• There's nothing wrong with @nealmcb's question; it's perfectly reasonable to think of this as a nonce. The distinction you're trying to draw between a salt vs a nonce makes no sense to me. 128 bits would be more than enough, but you can usually get by with less; see my answer elsewhere for the calculation.
– D.W.
Jan 31, 2011 at 6:00