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?

This is, I think, your most important point (from the comments):

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

Then per session, use a counter. Between sessions, use Diffie-Hellman key exchange over your shared-key symmetric encryption. This will also give you forward secrecy. I can't see much benefit to you proposed mechanism over this.

For completeness: the meaning of forward secrecy is that even if your shared key is compromised in the future, past communications cannot be decrypted. This is not a property your current mechanism offers.