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

Moritz Schmitt
  • 799
  • 3
  • 11
RenderedNonsense
  • 13
  • 2

2 Answers2

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?

Moritz Schmitt
  • 799
  • 3
  • 11
  • 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 07 '20 at 00: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 08 '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 08 '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.

Frank Denis
  • 273
  • 1
  • 4
  • What happens when Eve drops a random message in between? How do you get back in sync? – Limit Jun 07 '20 at 00:08
  • Eve’s message will not verify, so you don’t increment the nonce. – Frank Denis Jun 07 '20 at 00: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 07 '20 at 00: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 https://doc.libsodium.org/secret-key_cryptography/encrypted-messages – Frank Denis Jun 07 '20 at 00:19
  • 1
    Yeah. On second thoughts, it does make sense to drop the messages that are out of order. – Limit Jun 07 '20 at 00:43
  • This sounds like it could work, but I want to be sure I work it out correctly. How can I get Alice and Bob to agree on a nonce without Eve being able to replay Alice or Bob's messages from a previous conversation with the intent of causing them to agree on the same nonce value again. Perhaps Alice and Bob each contribute half of the bits of the initial nonce, so even if Eve replays Alice's nonce contribution from a previous conversation, Bob's contribution will still be out of her control? Is there a better way? – RenderedNonsense Jun 08 '20 at 22:21
  • @RenderedNonsense Start with 0 on both sides and increment it (if you are using one key per direction, as returned by libsodium's `crypto_kx` API), or set the high bit on one side, not the other if you are using a single key. Or use even nonces in one direction, odd nonces in the other. – Frank Denis Jun 10 '20 at 09:56
  • @FrankDenis If you always start with the same nonce (0), doesn't that mean Eve can easily replay messages, since the same nonces are used frequently? – RenderedNonsense Jun 13 '20 at 17:57
  • This assumes that ephemeral keys are used. – Frank Denis Jun 13 '20 at 18:02