# Replay attack prevention under strict conditions

Say I have a request-response protocol and the task to make it immune to replay attacks. The requirements are as follows:

1. The defense mechanism cannot rely on the clocks of the parties.
2. The defense mechanism should work even when requests are not sequential.
3. No party can store more than 1KB of data at any given time for the purposes of replay attack prevention (per session - see below).
4. No requests must be sent for the purposes of replay attack prevention.

Given that:

1. Before the defense mechanism is used, another protocol is used to authenticate the first party and create a session. The session ID is included in every request of the above protocol.
2. During the authentication protocol, up to 1KB of data can be sent to the first party for the purpose of replay attack prevention on the above protocol.

In what way does HTTPS handle replay attack prevention? How can this (the first described) protocol be made immune to replay attacks?

Considered Idea #1:

1. A 256-bit secret is shared by the two parties during the authentication protocol.
2. When party 1 makes a request, they include this secret in their message.
3. Party 2 checks that this is the same value they have stored. If so, it is included in the response and this value is hashed and stored, replacing the previous value.
4. Should the response be valid and contain the value sent, party 1 hashes the value sent and stores it, replacing the previous value.
5. Steps 2-4 are repeated for every request and response.

The problem with this is that requests need to be sequential.

Considered Idea #2:

1. Every time party 1 makes a request, a nonce is included.
2. Party 2 checks if this nonce has been used before with this session id, if yes, it denies the request, if not, this value is stored. Party 2 includes this nonce in the response.
3. Party 1 checks if the sent nonce is included in the response.

The problem with this is the large storage space needed.

-
What exactly do you mean by not sequential? And why do you need that? –  CodesInChaos Jun 1 '12 at 15:08
I'd use your idea 2 with a counter as nonce. Then you can add a rule that any counter that's smaller by 8000 or more than the largest counter received so far are invalid. Not sure if that falls under your "sequential" rule. –  CodesInChaos Jun 1 '12 at 15:14
By not sequential I mean that requests should be able to be sent in parallel without errors caused by the defense mechanism. I have considered a similar idea to the one you proposed, unfortunately both violate the "sequential rule". Say I send a request A, and then a request B. There is no guarantee that request A will arrive before request B (request A might be orders of magnitude larger), hence this will cause errors. Leaving space for these errors is, by definition, bound to cause replay attack opportunities. –  Chris Smith Jun 1 '12 at 15:24
The solution I sketched allows 8000 outstanding requests without allowing a replay attack. That should be enough for most situations. –  CodesInChaos Jun 1 '12 at 16:01
My apologies @CodeInChaos, it seems I initially misunderstood your concept. Thank you everyone for the help. –  Chris Smith Jun 1 '12 at 17:05