Why does a nonce prevent a replay attack? 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.
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 MACK(NA || 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.