Why does a nonce prevent a replay attack?

Question

I have a question about a cryptographic nonce. I understand the use of a nonce, however there is one particular part that I don't understand. Please consider the picture below.

I don't really understand why a replay attack is impossible, if the nonce is not encrypted. Because, if it isn't encrypted and I (as an attacker) know the nonce, then I can predict the next number (N + 1) and send that to Bob. Obviously I can't generate a MAC by myself (well, I can but Bob won't trust it) - I don't have the corresponding key; but I can send the MAC, who is previously generated by Alice, again with a "new" nonce (N + 1)..?

Could someone explain why this won't work?

Thanks in advance.

Answer 1

Given no knowledge of the MAC key and that M1 != M2, it is not possible to compute MAC(K, M2) from MAC(K, M1).

More generally, it isn't possible to determine the MAC of any message you haven't already seen. (Again, without the key.) The definition of a nonce is a number which is only used once with a given key.

Bob ensures that nonces are only used once by rejecting requests unless the nonce value Alice submits is strictly increasing.

---

There are other problems with this protocol. I assume it's meant to be used to authenticate users. No information is transmitted besides what is basically just proof that Alice knows K.

The protocol functions a lot like a one time password scheme and has the same limitations. It doesn't prevent MITM attacks, session hijacking, or server impersonation. It is not a full communication protocol.

Sometimes people comes up with schemes like this to control locks or appliances. It is unsafe to use such a protocol with "toggle" signals. An authentication request could be blocked, leaving a user's device in the state opposite from the state they believe it is in.

It is also possible to combine blocking Alice's requests with a replay attack. One could block Alice's request to engage a lock, trespass, then play back Alice's message to make it look like the lock was engaged the whole time.

Delayed playback can be solved by Alice instead sending MAC_K(N_A || timestamp). (As long as Alice and Bob have trusted synchronized clocks.) An acknowledgment message could allow Bob to tell Alice that the command was received. The ack would needs its own authentication tag, otherwise it could be spoofed.

Answer 2

A nonce on its own does not prevent replay attacks. It is just a number, it doesn't do anything, it can't give any guarantees. You could define a protocol with a nonce, that has no cryptographic functions at all - and it's fairly obvious, that is not secure in any sense.

It all comes down to how you use the nonce in a protocol and what kind of security property your function gives: If it is hard (in the cryptographic sense) to compute $f(x,n_1)$ from $f(x,n_2)$, then using a nonce in the second parameter means, everytime a different second parameter is used - and an attacker can not use past interactions to forge something.

In your example, you mix that with the concept of a counter. It isn't impossible to combine those, but your protocol is vulnerable and does not actually do what it is intended to do: Alice increase her "counter" every time she sends a message, Bob updates his "counter" every time he receives one. An attacker with control of the network can basically twist and spin those values as much as he likes. And since nothing else is used in the MAC, they are not bound to anything.