I am working on an end-to-end encrypted messaging application as an educational activity with some of my extra time. I have chosen to use libsodium for the underlying crypto. I have run into a hang-up with how to properly implement replay safe mutual authentication between Alice and Bob.
Assume Alice and Bob know each others public keys in advance. My current (rudimentary) implementation has Alice and Bob construct a public crypto box via nacl.public.Box (implementation of Curve25519 + Poly1305) and use this for the initial exchange in the protocol.
The following communications are all via nacl's crypto-box public key encryption/MAC (with random nonces):
Alice --> Bob: Hello Bob: Decrypts Hello message and checks message authentication code to ensure it came from Alice Bob --> Alice: Hello Alice: Decrypts Hello message and checks message authentication code to ensure it came from Bob Alice <--> Bob: Agree on a symmetric key to use for the rest of this communication (they can recompute this periodically for forward secrecy)
The crypto box implementation uses random nonces by default, which I understand can theoretically be used to prevent replay attacks. However, this is where my confusion lies. Does Bob need to record every nonce that Alice has ever used to ensure that Eve does not replay an Alice "Hello" to convince Bob she is Alice? Could this limitation be overcome by having Alice and Bob each communicate with a random salutation message instead of "Hello" that they expect the other party to repeat back to them? Is there a standardized way to do this kind of thing that I am missing (I have looked around without success)?