A nonce is a unique value chosen by an entity in a protocol, and it is used to protect that entity against attacks which fall under the very large umbrella of "replay".
For instance, consider a password-based authentication protocol which goes like this:
- server sends a "challenge" (a supposedly random value c) to the client
- client shall respond by sending h(c || p) where h is a secure hash function (e.g. SHA-256), p is the user password, and '||' denotes concatenation
- server looks up the password in its own database, recomputes the expected client response, and sees if it matches what the client sent
Passwords are secret values which fits in human brains; as such, they cannot be very complex, and it is possible to build a big dictionary which will contain the user password with high probability. By "big" I mean "can be enumerated with a medium-scale cluster in a few weeks". For the current discussion, we accept than an attacker will be able to break a single password by spending a few weeks of computation; this is the security level that we want to achieve.
Imagine a passive attacker: the attacker eavesdrops but does not alter the messages. He sees c and h(c || p), so he can use his cluster to enumerate potential passwords until a match is found. This will be expensive for him. If the attacker wants to attack two passwords then he must do the job twice. The attacker would like to have a bit of cost sharing between the two attack instances, using precomputed tables ("rainbow tables" are just a kind of precomputed table with optimized storage; but building a rainbow table still requires enumerating the complete dictionary and hashing each password). However, the random challenge defeats the attacker: since each instance involves a new challenge, the hash function input will be different for every session, even if the same password is used. Thus, the attacker cannot build useful precomputed tables, in particular rainbow tables.
Now suppose that the attacker becomes active. Instead of simply observing the messages, he will actively alter messages, dropping some, duplicating others, or inserting messages of its own. The attacker can now intercept a connection attempt from the client. The attacker chooses and sends his own challenge (c') and waits for the client response (h(c' || p)). Note that the true server is not contacted; the attacker just drops the connection abruptly immediately after the client response, so as to simulate a benign network error. In this attack model, the attacker has made a big improvement: he still has a challenge c' and the corresponding response, but the challenge is a value that the attacker has chosen as he saw fit. What the attacker will do is always server the same challenge c'. Using the same challenge every time allows the attacker to perform precomputations: he can build precomputed tables (i.e. rainbow tables) which use that special "challenge". Now the attacker can attack several distinct passwords without incurring the dictionary-enumeration cost for each.
A client nonce avoids this issue. The protocol becomes:
- server sends a random challenge c
- client chooses a nonce n (should be distinct every time)
- client sends n || h(c || n || p)
- server recomputes h(c || n || p) (using the p from its database) and sees if this value matches what the client sent
Since the client includes a new random value (the "nonce") in the hash function input for each session, the hash function input will be distinct every time, even if the attacker can choose the challenge. This defeats precomputed (rainbow) tables and restores our intended security level.
A crude emulation of a unique nonce is the user name. Two distinct users within the same system will have distinct names. However, the user will keep his name when he changes his password; and two distinct users may have the same name on two distinct systems (e.g. every Unix-like system has a "root" user). So the user name is not a good nonce (but it is still better than having no client nonce at all).
To sum up, the client nonce is about protecting the client from a replay attack (the "server" being in fact an attacker, who will send the same challenge to every client he wishes to attack). This is not needed if the challenge is executed over a channel which includes strong server authentication (such as SSL). Password Authenticated Key Exchange are advanced protocols which ensure mutual password-based authentication between client and server, without needing some a priori trust (the "root certificates" when a SSL client authenticates the SSL server certificate) and protecting against active and passive attackers (including the "cluster-for-two-weeks" attack on a single password, so that's strictly better than the protocol above, nonce or no nonce).
