6
$\begingroup$

I am using RSA to encrypt some data but I would like to eliminate the possibility of message replay. By message replay I mean sending a valid message multiple times to the original recipient. It is obvious that an attacker can capture a valid message without knowing its contents and replaying it.

Is there any efficient way for the recipient to determine if a given message has been replayed or avoid the problem altogether?

The only things I can think from the top of my head are: including an expiration time in the message (rather insecure) or hashing the message, storing it and checking if future messages have the same hash value (can consume a lot of memory).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Why would including the expiration time in the message be insecure? $\endgroup$
    – Ethan Heilman
    Commented Sep 27, 2011 at 16:38
  • 2
    $\begingroup$ For my purposes, the expiration time is time+5 seconds. That gives an attacker a 5 second window to attack. For my system, a single replay can be destructive. $\endgroup$
    – Chris Smith
    Commented Sep 27, 2011 at 16:40

3 Answers 3

Reset to default
7
$\begingroup$

You could use some combination of:

  • an expiration timeout (i.e. if the message does not arrive until the timeout, we don't accept it)
  • storing previous values of a nonce.

You only have to store those nonce values whose timeout didn't yet expire.

If the messages arrive all in order, you can instead use a simple counter (which always goes up) and reject every message which has a counter value smaller or equal than the last received one.

Improve this answer
$\endgroup$
0
$\begingroup$

Typically this is solved by including signed random value, called a nonce, in the message.

  1. The nonce is signed so no one but the sender can create new nonces
  2. The nonce is random and never repeated so an attacker can't use previous communications (no replays attacks).

Note that such a system assumes a mechanism, such as padding, to prevent an attacker from altering the message using the homomorphic properties of RSA.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ How will including a signed random value solve the problem? How does the recipient know that the nonce hasn't been repeated without storing every previous nonce? $\endgroup$
    – Chris Smith
    Commented Sep 27, 2011 at 17:02
  • 1
    $\begingroup$ @ChrisSmith Good point! We have three options: (1) as you pointed out storing the previous nonces works, (2). the first time a connection happens the nonce is generated and sent, each subsequent connection the nonce is incremented by 1 (since the attacker doesn't know the value of the nonce the attacker can't predict the new value of the nonce). (3). nonces passed between both parties and combined to generate new nonces (similar to the way syn cookies work en.wikipedia.org/wiki/…). $\endgroup$
    – Ethan Heilman
    Commented Sep 27, 2011 at 17:31
0
$\begingroup$

You could use the hashing method, but use a bloom filter to lessen the storage requirements. With a bloom filter, false positives are possible (i.e., a message could be flagged as a replay when it really isn't), but false negatives are impossible. Furthermore, the probability of a false positive is tunable, but the lower the probability, the more storage the system would require.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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