1

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)?

2

Does Bob need to record every nonce (...)?

No.

You're right that a nonce must not be used twice. However, bookkeeping nonces is not the way to go. The usual approach is to include a timestamp in its value and/or to generate random nonces with enough random bits. This doesn't garantuee double use but makes it highly unlikely.

May I recommend crypto.SE for questions regarding the implementation of cryptographic protocols?

3
  • How about extending your system to keeping a sliding window of nonces used in the past X seconds? This way, the timestamp ensures that old nonces can't be replayed after a while and recent nonces are captured by the sliding window – Limit Jun 7 '20 at 0:09
  • The timestamp solution (and sliding window) make sense to me as a possibility. One thing that strikes me as not ideal about this, however, is if system time gets changed for any reason in the middle of a conversation. Regarding "generate random nonces with enough random bits", that doesn't seem like a solution by itself since if Eve replays the message, it doesn't matter how many bits are in the nonce, if Bob accepted the message before, he'll accept it now (unless he is recording previously used nonces or timestamps) – RenderedNonsense Jun 8 '20 at 21:45
  • FWIW I didn't post this in the crypto SE since I thought its answer would be fairly high level, but I guess we've gotten in the weeds enough that I might post it over there. – RenderedNonsense Jun 8 '20 at 22:35
1

Nonce just need to not repeat. They don't have to be unpredictable.

Instead of using random nonces, you can agree on an initial nonce, and simply increment it after each message.

The first benefit of this approach is that you don't need to send nonces any longer. Senders and recipients both increment nonces after having sent or received a message, so their counters are always in sync without having to transmit them.

Another benefit is that if a message with the wrong nonce is received, decryption will fail. So you get protection against replay attacks.

9
  • What happens when Eve drops a random message in between? How do you get back in sync? – Limit Jun 7 '20 at 0:08
  • Eve’s message will not verify, so you don’t increment the nonce. – Frank Denis Jun 7 '20 at 0:09
  • By drop, I meant Eve blocking a message from Alice to Bob. Now Alice's counter is at a number that Bob hasn't caught upto yet. If Alice sends another message before Bob catching up to her, Bob will ignore that message as it doesn't match the expected nonce. – Limit Jun 7 '20 at 0:11
  • 1
    That’s usually what you want, or else messages could be reordered. If you are using unreliable transport and really need to handle unordered messages, see doc.libsodium.org/secret-key_cryptography/encrypted-messages – Frank Denis Jun 7 '20 at 0:19
  • 1
    Yeah. On second thoughts, it does make sense to drop the messages that are out of order. – Limit Jun 7 '20 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.