# How to properly guarantee authentication, confidentiality, and replay-resistance for multiple messages using a pre-shared key?

I have a device that needs to communicate with another host and exchange fixed-length messages. All traffic should be encrypted and authenticated, and it should be resistant to replay attacks. Unfortunately relying on TLS is not an option, so I need to implement some custom protocol. I have control of both devices so I can securely generate and distribute a shared key $$k$$.

I thought to use AEAD with block cypher to do the heavy lifting, for example AES in GCM mode. The problem I'm facing is that of preventing replay attacks and I came up with the following idea. Let's call the devices $$A$$ and $$B$$ and consider communication from $$A$$ to $$B$$ only.

• $$A$$ generates a random string $$a$$ and sends it to $$B$$.
• $$B$$ generates a random string $$b$$ and sends it to $$A$$.
• Both $$A$$ and $$B$$ compute $$h=H(k \Vert a \Vert b)$$ for some cryptographic hash function $$H$$, and use $$h$$ as the first initialization vector for the AEAD scheme.

Whenever $$A$$ needs to send a message $$m$$ to $$B$$, it encrypts $$m$$ to obtain the corresponding ciphertext $$c$$, computes the authentication tag $$t$$, and sends $$c \Vert t$$ to $$A$$ (messages have a fixed length so the length of $$c \Vert t$$ is constant). Then $$A$$ increments $$h$$ and re-initializes the AEAD scheme with the new IV $$h$$.

The decryption process is similar: $$B$$ receives $$c \Vert t$$, decrypts $$c$$ into $$m$$, authenticates the message using the tag $$t$$, increments $$h$$, and re-initializes the AEAD scheme with the new value of $$h$$.

Communication from $$B$$ to $$A$$ is completely symmetric, except that the initial IVs are $$H(k \Vert b \Vert a)$$.

Is there any obvious flaw with the above idea? Am I re-inventing the wheel? If so, what would be the go-to solution to tackle this problem?

• Little search replay attack countermeasure and see the end of the answer Jul 13 at 21:37
• I am aware that replay attacks can be avoided by adding timestamps or counters. However the device $A$ preserves no state between reboots (it's an embedded device) and has no internal clock (I don't want to rely on synchronizing the time over the internet as this would rely on having a working internet connection). Jul 13 at 21:41
• Then you need signatures... Jul 13 at 21:54
• Could you please elaborate on how signatures would help against replay attacks? Even if a message is signed, I would only be able to check its authenticity but not whether if it has been replayed. Moreover, the AEAD scheme I'm proposing should already be providing authenticity. Is there anything wrong with the scheme I'm proposing? It seems to me that $h$ should be guaranteed to be a random "per-session" secret shared between $A$ and $B$. Is there a problem with using $h$ to initialize the IVs and with incrementing the IV after each message? Jul 13 at 22:10
• Why strings? Why not fixed-length binary values? Why use a hash H instead of a proper keyed hash or MAC? Jul 14 at 3:31

• Thank you. I just want to make sure that I understood your proposed scheme properly. You are suggesting I perform a Diffie-Hellman key exchange while using the AEAD scheme with my pre-shared key to guarantee authentication (do I need encryption here?). Here the AEAD scheme would need to use some hardcoded IV. Nevertheless the negotiated DH key $k$ will be secret and different for each session. Then I can use $k$ as the session key for another AEAD scheme to exchange the actual messages. As I understand each message needs a different IV. In this case can I just use a counter starting from $0$? Jul 14 at 13:52
• Also, it seems that the whole 1st part of the protocol is performing a password authenticated key exchange. If this is the case, can we employ the idea sketched on Wikipedia? Namely, $A$ and $B$ already have a pre-shared secret $s$; they compute a session key $k$ using the DH key exchange. Then $A$ send $hash(s \Vert 0 \Vert k)$ to $B$ , which $B$ checks to authenticate $A$. Symmetrically $B$ sends $hash(s \Vert 1 \Vert k)$ to $A$. Communication proceeds using $k$ as the session key. Jul 14 at 13:53