When would you increment a nonce and when not?

Question

K is the shared key for encryption known by _Alice and _Bob. $N_A$ is a nonce created by Alice. The function f is the increment by 1 function.

(1) Alice -> Bob: $E_K(N_A)$

So Alice encrypts a nonce with the shared key and sends it to Bob.

(2) Bob -> Alice: $E_K(f(N_A))$

Bob receives it, I think first he needs to decrypt it, then increment it by 1, encrypts it again and then send it back to Alice.

The question is now, when and why would you use this use-case? What could be the scenario for these two steps?

I have seen these two steps for example in the Needham–Schroeder protocol, but I did not understand why they need these two.

My only idea is that Bob authenticates himself to Alice, because if Alice later decrypts it, Alice will see whether Bob was able to decrypt it. But why would you need to increment the nonce?

---

UPDATE: As my idea seems to be right according to otus, I have to ask for another use-case I've seen:

(1) Alice -> Bob: $N_A$

Alice sends the plain nonce to Bob.

(2) Bob -> Alice: $E_K(N_A)$

Bob encrypts it with the shared key and sends it back to Alice.

For this second use-case I was pretty sure that my idea for the first use-case would be right -> Just to authenticate Bob. So I thought the use-case with the increment function is for something else.

So are these two use-cases for the same purpose? Just to authenticate Bob to Alice? What is the difference between them? When would you apply which of these two and why?

Answer 1

My only idea is that B authenticates himself to A, because if A later decrypts it, A will see whether B was able to decrypt it. But why would you need to increment the nonce?

Correct, that's the idea.

If B didn't need to increment the nonce and just encrypted the same value, the message sent back would be the same that A sent, so an attacker would be able respond correctly without knowing how to decrypt it.

There are other ways to accomplish the same in other protocols that do not use increments. For example, B could encrypt it with another shared key.

So are these two use-cases for the same purpose? Just to authenticate Bob to Alice? What is the difference between them? When would you apply which of these two and why?

In terms of authentication there is no real difference. They both prove to Alice that Bob has the correct key.

The one with encryption and increment is slightly less efficient, due to requiring both parties to encrypt and decrypt the values. However, it has the advantage of not allowing an attacker to directly ask for encryptions of chosen plaintexts, with which they could attack other uses of the same key. This is not necessarily a problem if the key is only used for authentication, but in the case of Needham–Schroeder the objective is to establish a session key.

Answer 2

To answer your first question, the incrementation is required in order to prevent spoofing of that message. An attacker could send back the same encrypted nonce claiming to be Bob. However, if Bob incriments the nonce and sends it back encrypted, Alice would know for sure that Bob has received the nonce and has incremented it.

Now, Alice encrypting the nonce, and Bob decrypting-incrimenting-encrypting process is a tedious task. So, in order to achieve the same authentication faster, as otus sugested, Bob could simply encrypt Aice's nonce with a private key known only to the two of them.

To answer your second question: Yes, these two methods are done for the same authentication purposes, the difference is that different protocols use different implementations of the same idea.