Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 4 more comments

1 Answer

up vote 4 down vote accepted

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.