How to prevent a signed request from being used again?

Question

Let's say Bob sent this HTTP request to an API to update his email:

/user/update?email=bob@example.com&userid=1234&sig=x1zz645

Now a sniffer named Zerocool recorded this request for later use.

After a few days later, Bob updated his email again to email=newbob@example.com.

Few hours later Zerocool now decides to use what he sniffed a few days ago and runs the request:

/user/update?email=bob@example.com&userid=1234&sig=x1zz645

The server accepts it and Bob is now confused why is the old email back.

How can we prevent this from happening without using SSL?

Answer 1

Keep a log of recent requests. Embed a timestamp into such requests, and reject any that are present in the log or older than the log. For good measure, sign the timestamps with a private md5 checksum, so they can't be fabricated.

Answer 2

Use SSL as stated in your tags. It is already immune to both sniffing and replay attacks. It exists. Using it is free. It works. It's done.

If you can't use SSL please remove it from your tags.

Answer 3

You can use Hash based message authentication code (HMAC) to secure the API so that replay attacks like the one you mentioned can be avoided. Both the server and the client will have a shared secret API key.

Amazon S3 Rest API uses the same procedure to Authenticate and Validate requests. See the Documentation here.

UPDATE: As Bruno pointed out HMAC itself cannot prevent replay attacks. You will have to include some unique identifier signed with secret key with the message and validate it at the server.