Replay attack prevention under strict conditions

Question

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.

Answer 1

The standard solution would be to have the sender maintain a counter, and sending the value of that counter in each request (which is tied into the integrity check of the request). The receiver would remember the largest counter value that he has received a valid request for, and a bitmap showing which of the N requests prior to that he has actually seen. With 1kbyte of memory available on the receiver, you can have N=8000 or so, which means that we can do accurate replay detection, as long as we don't get a request that is older than 8000 requests previous to the most recent. If we do get such a request, we'll reject it, even if it is a previously-unseen request.

See RFC6479 for details on one possible method of implementing this.

As for how HTTPS does replay detection, well, each TLS record has a sequence number associated with it. Both sides maintain a copy of the counter, and it is included in the integrity check. So, if someone were to replay an HTTPS record (adjusting the TCP sequence numbers, if they don't do that, the TCP stack will assume that it's a retransmission and ignore it), the TLS sequence number of the receiver won't be the same as the sequence number that the sender used, and so the integrity check will fail, and the record will be rejected (and the session will be shut down; TLS can't recover from these sorts of errors).