2
$\begingroup$

I've recently looked into fundamentals of RSA and think I understand how it works. However, there's one basic problem I can't seem to figure out. If someone received ciphertext for a given message, what is to stop them from sending the same message/ciphertext to other nodes in a network and pretending to be the private key holder?

For example, suppose Alice is a general and commands soldiers Bob, Sue, and Jerry. Alice generates private key (n, d) and public key (n, e) and sends (n, e) to all soldiers. The soldiers wait for Alice's instructions every day, which is either "attack" or "don't attack". Alice sends encrypted message "attack" to the soldiers via RSA as ciphertext to all soldiers. Now suppose one of the soldiers is malicious and has hacked Alice's delivery method (e.g. email), but not her private key. And on a separate day sends the same "attack" encrypted cypher text to all other soldiers. What's to prevent this from happening (even if you use padding which will always result in decrypted message "attack")?

I suppose one way is to add a timestamp to all messages and soldiers must make sure the date matches with current day. But it still doesn't seem right that someone can send the same exact message to others by just having the cyphertext... Or am I missing something?

$\endgroup$
3
$\begingroup$

If Alice is sending the encrypted messages then her public key isn't involved at all. She encrypts the messages for each recipient's $(n, e)$ pair individually, and sends them tailored messages.

In reality she probably sends the message encrypted with AES and only uses RSA to send each recipient their copy of the decryption key, a la PKCS#7's EnvelopedData.

The recipients have no way of knowing that the message actually came from Alice in this scheme. What she needs to do is sign the message (post-encryption, for best results), which does use her private key.

At this point, as you observe, there's still a replay vector. So the message would need to contain some way of identifying its freshness. A monotonic time stamp is an easy way, a monotonic message counter is another, or some sort of pre-arranged keyword from a shared code book (if you like whimsey).

So the recipient does:

  • Verify the integrity of the ciphertext and encrypted key using Alice's public key. (Prove it was sent by Alice)
  • Decrypt/derive the message encryption key using their private key.
  • Decrypt the ciphertext to reveal the original message.
  • Verify the time stamp / counter. (Prove it isn't a replay)
  • Respond appropriately to the contents.

The time stamp could have been signed but not encrypted, it just depends on whether or not that is itself sensitive data.

$\endgroup$
  • $\begingroup$ In the situation, a monotonic message counter seems less safe than a timestamp. Say: during a period when attack is unlikely, an adversary learns that Sue returns from leave, and sabotages her train so that she arrives one day late. The attacker intercepts messages from Alice to Sue, and replaces them with the previous day's message. Having lost track of the counter, and given the lack of political tension, Sue may not care on the first day. If so, the adversary gains one day of delay before Sue attacks should hostilities start later. $\endgroup$ – fgrieu Sep 4 '17 at 7:47
3
$\begingroup$

I will try to extend answer of bartonjs and provide an analogy.

What you've described is call a replay attack. While the message is encrypted (using a public key of the addressee), only the addressee should be able to read it. Sending the same message to other parties should be no thread.

Let's assume some man in the middle able to retransmit the same message (even encrypted as it is). So even the intended addressee have to be sure the message is current. If the message is not encrypted, only signed, the message can be sent to any unit listening to Alice. This gives me analogy with SAML authentication. The SAML messages are very often plain (not encrypted) and signed.

What is commonly used to mitigate the replay attack is using the nonce cache with limited time-validity. Usually the SAML ticked is valid for a short time (5 mins – 1 hour) and the nonces are cached for logged-in users (or — should be). The service provider must check:

  • sender's identity
  • addressee
  • timestamp
  • signature

So for your case — check the timestamp of the command (allow some small delay) and remember the nonces (message id, counter, random seed) for the time-window for already processed messages.

$\endgroup$
0
$\begingroup$

One typical method is missing from the answers so far is that challenge-response mechanisms can be used in interactive scenarios, such as a network between nodes.

For the example: The soldiers choose a random number each day and make it public. Alice then has to use that number somehow in her message – before encryption.

Btw.: RSA, and any public key encryption scheme, works the other way around – everyone with the public key can encrypt, and only the one with the private key can decrypt. Not the other way around.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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