Use of nonces in Kerberos and Needham–Schroeder protocols

Can you please explain me what is the reason of using nonces in the Needham-Schroeder and in the Kerberos protocols for Key Transport.

In particular :

• Can you explain me the use of $N_A$?

And also, I suppose $N_B$ is used for the scope of letting $B$ know that $A$ shares the same key $K_{AB}$ and was able to decipher the value of $N_B$, alter it and encrypt it back by using $K_{AB}$.

• Is this assumption correct?

And finally:

• How does the use of the nonces provide more security to the protocol?

Here you can find more details about the two protocols.

• No idea about the specific situation, but nonces are often used to prevent replay attacks. – CodesInChaos Jun 21 '12 at 22:13

For Needham-Schroeder, $N_A$ is used to prevent a replay attack. Look at the message from $S\to A$. Without a nonce, a malicious server could replay an old but valid response. The message would still decrypt, etc. Furthermore, the key $K_{AB}$ would be the same as a previously used key which could open up the system to more attacks.

It is the same for Kerberos.

You are correct with $N_B$. The only way Alice could return $N_B-1$ is if she knows $K_{AB}$. Thus it is to prove knowledge of the key.

The nonce $N_B'$ in Needham-Schroeder is used to prevent a replay attack with someone spoofing Alice to Bob.

How does the use of the nonces provide more security to the protocol?

It ties messages to specific sessions of the protocol. This ensures that all messages are "fresh" which prevents replay attacks.

• Thks for the answer, just one more doubt: I found an implementation of Needham-Schroeder with timestamps, aren't those much more secure and useful than nonces (since they also guarantee key freshness)? – Matteo Jun 22 '12 at 7:33
• @Matteo, Timestamps are also useful. Typically you would say any timestamp older than XX seconds is invalid. This has 2 problems. 1) The message can still be replayed in an XX second window. 2) The clocks of the sender and receiver must be fairly closely synchronized. I wouldn't say timestamps are more secure, but definitely an option with it's benefits and disadvantages. – mikeazo Jun 22 '12 at 11:37
• I'd say that nonces could indicate their own sort of purely local notion freshness (given reasonable assumptions about what it means to be a nonce). For example when an initiator generates a nonce in a particular session, and in the same session receives a cyphertext containing the nonce and some other stuff securely signed by the responder, the initiator can be reasonably certain that the cyphertext was securely signed by the responder in a recent run. – machine yearning Aug 30 '12 at 17:20
• To elaborate, as @Matteo mentioned, freshness is important not just for messages, but also for keys; if you use the above technique to, say, get a fresh key from a key server, you know that for the duration of the session that the key hasn't been compromised using cryptographic methods (again assuming some reasonable things about how long it takes to compromise a key using cryptographic methods relative to your session timeout). – machine yearning Aug 30 '12 at 17:30