# What are the requirements of a nonce?

Sometimes I read that a nonce has to be a random number but I disagree. A nonce just can't repeat itself. You could increase in by 1 every time if you are sure it would never repeat.

-
en.wikipedia.org/wiki/Cryptographic_nonce - "In security engineering, nonce is an arbitrary number used only once in a cryptographic communication" –  Henrick Hellström May 30 '13 at 18:41
So defining it as a random number is wrong? Wikipedia is not a source. –  Smit Johnth May 30 '13 at 18:45
In this case Wikipedia is right. Nonce = number used once. It does not have to be generated at random, in fact, generating at random might cause repetitions, with a probability that is a function of the bit length of nonce. –  Henrick Hellström May 30 '13 at 18:55
Is there a real source for that? Our professor has given it as a random number on his lection. –  Smit Johnth May 30 '13 at 19:02
The link on the Wikipedia page is good: cs.ucdavis.edu/~rogaway/papers/nonce.pdf The example in the introduction of that paper is to use a counter as nonce. –  Henrick Hellström May 30 '13 at 19:07

Yes, a nonce is a number not used more than once. In its purest sense there should be no other requirements than this, i.e. randomness or unpredictability should not be necessary.

However, in certain settings stronger requirements are put on the nonces; like for instance in the CBC-mode of operation for block ciphers the IV (nonce) needs to be unpredictable (a requirement, when not followed, actually have led to real-life problems in the SSL/TLS-protocol: Why is CBC with predictable IV considered insecure against CPA).

See also: What's is the main difference between a key, an IV and a nonce? for a more comprehensive discussion of the properties of nonces and IV's.

-
I'm confused: does it mean "nonce actually don't have to be random, but sometimes yes"? –  Smit Johnth May 30 '13 at 19:11
A common way to generate an unpredictable IV for CBC is to simply encrypt the counter value before using it as IV. The IV doesn't have to be random; pseudo-random is fine. –  Henrick Hellström May 30 '13 at 19:15
You asked for a definition of a nonce, and I provided what I consider to be the "right" notion; namely a value which is simply not used more than once (that's it!). Unfortunately there's much ambiguity in how the terms nonce and IV's are used in practice. So you might see several sources calling the first input to CBC-mode a nonce, whereas I would have preferred calling it an IV. –  hakoja May 30 '13 at 19:16
...what I'm trying to say is that, I think that a definition of a nonce should not impose ANY other requirements other than that it should not be used more than once. This does not forbid you from putting additional constraints on it. –  hakoja May 30 '13 at 19:21

Definition 10.9 in Chapter 10 of Handbook of Applied Cryptography.

A nonce is a value used no more than once for the same purpose. It typically serves to prevent (undetectable) replay.

Continuing on, there is some additional info that you might find interesting.

The term nonce is most often used to refer to a “random” number in a challenge-response protocol, but the required randomness properties vary.

-

There may be some particular scenarios where an unpredictable nonce is better than just a unique nonce.

For example suppose you have access to an oracle that can generate the correct response to an authentication request that involves a nonce, but you don't have real time access; in particular by the time you get the response from the oracle, the challenge will have expired.

If you can predict what the nonce is going to be (e.g. prev nonce + 1), then you can use the oracle to establish the correct response in advance, then run the protocol against the victim and have the response ready.

An example where this could be realistic is if your challenge-response protocol is cryptographically weak and can be brute-forced, but it takes a long time (e.g. days with the attacker's resources) to do the brute-forcing. An unpredictable nonce would have prevented the vulnerability from being exploitable.

-

If you have many clients accessing a server then the clients can't really just increment by one because they wouldn't know which numbers have been sent. You could attempt to coordinate and enforce that their numbers don't intersect, but this is additional work.

In this case, I think a long, random nonce is very beneficial. Clients can just generate nonces without any worry about overlapping. The server only has to record and ensure the same nonce doesn't appear twice.

GUID's or UUID's work well for these scenarios because the statistical probability of collisions is so low. In addition some implementations of a GUID will be based off the MAC address, time, and some random bits. This ensures that

1. Two computers will never generate the same nonce (different MAC address)
2. The same computer will never generate the same nonce (timestamp + random)

They are also easy to generate as most languages will already have an implementation you can use.

So I agree with your argument that nonces don't need to RANDOM, but they do need to be UNIQUE. And while auto incrementing may be just fine if there is a single client talking to a single server there are many scenarios where this is not practical.

-
If the clients have different keys, they can each use the same nonce (once). –  otus Jun 10 '14 at 6:46