Question
Is the message integrity scheme based on HMAC susceptible to playback attacks? If so, how can a nonce be incorporated into the scheme to remove this susceptibility?
Answer
HMAC does not prevent replay attacks. You can use several techniques to come up with a common nonce on both the sender and receiver.
1. Use a sequential counter value and check the counter before accepting a message. A more complicated scheme might be to run diffie hellman for every message on both the sender and receiver to obtain a common value and use it as a nonce which will probably be more random than a sequential counter. You can then use the nonce by appending it to the message before you hash it to generate the HMAC and send it across the wire. The receiver can use the same nonce to check the validity of the HMAC.
2.You can optimize and then using another well known scheme for example chained hashing to generate future nonce values without message exchanges