I am using custom security scheme to verify communication between client and server.

Both client and server have same secret hash phrase.

1. Client builds a message, combines it with hash phrase and calculates SHA512 hash, and sends both message and hash to server
2. Server receives a message, combines it with hash phrase and calculates SHA512 hash, and then verifies that hash is the same as the one sent by client

This scheme works fine, but allows man in the middle to sniff the message and send it again, again and again to server.

Now, I know how to solve this, for example, by assigning unique id to each message and rejecting duplicates - but these unique ids must be stored somewhere (database, session, ...)

Is there some more stateless approach that can solve this problem?