Security scheme that prevents duplicate message attacks

Question

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?

• GregRos: I don't think this is logically possible. The only way that a machine can respond differently to the same message a second time, is if its internal state changes.
• Kilian Foth: This is an obvious case of X/Y trouble. Why do you assume you need to come with a "stateless" solution?
• Bart van Ingen Schenau: Take a look at en.wikipedia.org/wiki/Replay_attack for possible solutions.
• user7043: Let's give OP the benefit of the doubt and parse "more stateless" as "needing far less state". There are certainly defenses against replay attacks that only need a tiny number of bits per connection (e.g. TLS apparently includes a MAC built from a sequence number among other things). The real question is why you're implementing custom crypto. What is the nature of this communication and why can't you use a ready-made, peer-reviewed protocol for it?
• Dusan: @GregRos Yes, you are correct, that was so obvious

Answer 1

Nonce is used for just that

it's a number, possibly passed in the message header and it can be only used once and the subsequent requests with the same number are rejected by the serve.

For details on how the value is determined please have a look at the article.

• Marcin: Nonce, plus watch out how you combine secret/nonce/message so you're not subject to hash extention attacks.

Answer 2

Presuming the "hash phrase" is client-unique, your integration already entails a level of statefulness. It's not much more of a leap to provide the client with unique request tokens. The server can issue replacement token(s) as part of the response for each request.

The unique request tokens can either be/replace the "hash phrase" itself, or simply operate as an additional request identifier/authorization.