How to stop an attacker from repeating the same ciphertext?

Question

I have this situation where a PC is connected, via RS-232, to a certain hardware module that controls industial machinery.

The hardware is supposed to receive commands to turn on or off these machines, and the same command may need to be sent multiple times in a span of a single minute. Now, I am very new to cryptography, so I will be programming this hardware with an already pre-existing library that supports AES-128, AES-192 and AES-256 in ECB and CBC modes.

The problem I'm facing is that a potential attacker can very easily gain access to the transmission line and just probe it for the message being sent, and then use this information to send commands that can compromise the industrial machinery.

Let's say that the PC encripts a message like "MACHINE1 ON" using AES-256 with a secret key that the hardware module knows. Since the command is always the same, using AES in ECB mode will result in the same ciphertext, meaning that the attacker can just repeat the same ciphertext in order to turn the machine on.

Now, CBC encryption makes use of an IV to randomize the ciphertext, but the problem is, how will both the PC and hardware module know the IV? If the PC generates a truly random IV and encrypts the command with it, there's no way the hardware module will be able to decrypt the message without it.

So it thought that maybe the PC should transmit the IV to the hardware, using ECB mode, and then transmit the command encrypted with that IV, but we're back to square one, because an attacker can just repeat both ciphertexts and the hardware will just accept it (is this considered a replay attack?).

I've read a little about MAC and how it allows to verify if the sender has not changed, but how does it apply to this scenario? Would it even help? If not, what techniques could one use in a situation such as this?

Keep in mind that there is very little variety in the messages that will be send to the hardware module. The hardware module is also capable of generating truly random numbers, and it replies to the commands with a simple "OK" or "Invalid command" messages. These should also be encrypted to ensure an attacker gets as little information as possible.

EDIT:

I also read that sometimes, the IV is sent at the beggining of the encrypted text, so that the receiving end knows that the first N bytes correspond to the IV and can decrypt the message. Isn't this also vulnerable to the same replay attack?

Wouldn't it be better to implement some kind of "handshaking", where the hardware is the one to generate the IV and send it to the PC, the PC modifies the IV in a deterministic way, and then sends the messages using that modified IV? The process would then repeat each time the PC needs to send a command, and as long as the hardware doesn't generate the same IV twice, everything would be safe, right?

I'm sorry if this question is all over the place, I'm very confused about criptography and I'm being asked to implement something that I have almost no clue as to how it works. Any help would be much appreciated.

Answer 1

Your question appears to be conflating the ideas of IV and antireplay protection; actually, they don't have anything to do with each other.

The IV (in CBC mode) is a randomly selected value chosen by the encryptor; it can be sent along with the ciphertext (as we don't care if the attacker knows it). It's there so that if we decide to send the same message twice (or send two similar messages), the ciphertexts look completely unrelated (and hence the attacker doesn't gain any information). It doesn't help with antireplay; however, it was never designed to.

---

As for antireplay (rejecting identical messages), well, there are two standard ways for addressing it.

• The first way is to have the receiver remember which messages it has already received. That can be easier than you might think; if the sender includes a sequence number (which it increments each time it sends a message), the receiver can just check that with the last sequence number is saw; if it hasn't increased, it can reject the message. Now, this might have an issue that, for you, doesn't make it work; when either system restarts, how do both sides know which sequence number to use? When we use this strategy, we reset the sequence numbers to known values when we initially negotiate keys; it sounds like you're using configured keys, and so that doesn't work.

• The other strategy would be a challenge/response protocol; we have the receiver send a value (which can be random); and then the sender includes that value in the encrypted message, and then the receiver checks to see if the value in the message matches the value it sent out. In your case, it might look like this:

  PC: "I want to send you a command"

  Device: "OK, use the value 0x314159"

  PC: "Turn MACHINE1 on; value 0x314159; reply with value 0x271828"

  Device: "OK, command accepted; value 0x271828"

  Note that the first two messages don't really need to be encrypted; there's nothing useful that the attacker can learn from them.

  I included the reply value (chosen by the PC) so that the attacker can't simulate the device accepting the command when it really hasn't.

---

The third issue is "how do you make sure that the attacker can't gain anything from modifying the messages". Obviously, an attacker that can change arbitrary messages can forbid any communication (by simply jamming the RS-232 signal); cryptography can't solve that problem; the best it can do is to make sure that's all the attacker can accomplish.

You mention a MAC (Message Authentication Code); that's the correct solution for this problem. For each encrypted message, you would compute the MAC (which is the function of the message and a secret key); you send this value along with the encrypted message and the IV. When the device receives it, it also computes the MAC, and compares the value it computes with the value in the encrypted message. If the two values are the same, it knows that the message was not modified.

Without this, it's possible that an attacker might be able to modify encrypted messages; for example, he might be able to modify an encrypted "Turn Machine 1 on" message into an encrypted "Turn Machine 2 on" message. It strikes me that avoiding such a possibility is worth doing.

With the resources you have, the easiest MAC would be a CBC-MAC. To implement this, you would take your message (including the IV), prepend the message length if you support variable length messages, and then ask your CBC hardware to encrypt it, using a fixed IV (all 0's work), and a different AES key than you use to perform the actual message encryption. Then, you take the ciphertext, and discard everything except the last 16 bytes; that's your MAC.

The receive side would do the exact same thing; they'd take the received message (not including the MAC), possibly prepend the length, and ask their hardware to encrypt it (yes, encrypt, not decrypt) with the same fixed IV, and look at only the last 16 bytes of the resulting ciphertext, and compare that with the MAC included in the received message.

Answer 2

@poncho's answer is a good general answer. Here's a slightly conciser specific construction you might consider:

Are your messages always sent in order, and received mostly in order? Can the sender remember how many messages it has sent so far? Can the receiver remember how many messages it has received so far?

If so, you're in luck! You can use the message sequence number to derive an initialization vector, and you can use that to thwart replayed messages. Also, you should use an authenticated encryption scheme by default unless you have a reason not to. For this one, we'll pick AES256-CBC with HMAC-SHA256 in encrypt-then-MAC composition.^*

Let $k_0, k_1$ be two 256-bit secret keys shared by the sender and receiver.^†

Sender. To transmit the $i^\mathit{th}$ message $m$, the sender computes \begin{align*} \mathit{iv} &= \operatorname{AES256}_{k_0}(i), \\ c &= \operatorname{AES256-CBC}_{k_0}(\mathit{iv}, m), \\ t &= \operatorname{HMAC-SHA256}_{k_1}(i \mathop\Vert c), \end{align*} increments its message sequence number $i \leftarrow i + 1$, and transmits the concatenation $c \mathop\Vert t$.

Receiver. On receipt of the candidate $i^\mathit{th}$ packet $c' \mathop\Vert t'$, which may or may not be the same as $c \mathop\Vert t$, the receiver first checks whether $t' = \operatorname{HMAC-SHA256}_{k_1}(i \mathop\Vert c')$ with a constant-time string comparison.^‡ If the two are not equal, the receiver drops the packet on the floor. If the two are equal, the receiver computes \begin{align*} \mathit{iv} &= \operatorname{AES256}_{k_0}(i), \\ m' &= \operatorname{AES256-CBC}_{k_0}^{-1}(\mathit{iv}, c'), \end{align*} increments its sequence number $i \leftarrow i + 1$, and acts on the plaintext $m'$.

If messages are received mostly but not exactly in order, then you may want to transmit the packets as $i \mathop\Vert c \mathop\Vert t$. Then the receiver can

1. record what the last sequence number it acted on was and reject all messages with older sequence numbers, and
2. keep a small buffer of messages that are a little too new.

You may also want to include other public header information in the packet, and that should be included in what you hash with HMAC-SHA256 if the receiver might ever act on it.

---

_{* If the computational cost, and packet overhead, of HMAC-SHA256 doesn't fit in your budget, we can talk about cheaper alternatives. E.g., if you have only AES but no SHA-256 hardware, AES-CBC-MAC is an acceptable substitute. In the scheme above, you don't even need to prepend the length! That's because we always use a unique prefix, the message sequence number. But it's generally safer to have a length-prefixed AES-CBC-MAC lying around than to rely on the details of the scheme above.}

_{† You can derive them from a single master 256-bit key $k$ with, say, HKDF-SHA256, or simply let $k_0 = \operatorname{AES256}_k(0) \mathop\Vert \operatorname{AES256}_k(1)$ and $k_1 = \operatorname{AES256}_k(2) \mathop\Vert \operatorname{AES256}_k(3)$, as long as you never use $k$ for any other purpose.}

_{‡ In C, the fragment unsigned i, r = 0; for (i = 0; i < n; i++) r |= (unsigned char)a[i] ^ (unsigned char)b[i]; return 1 & ((r - 1) >> 8); returns 1 if the $n$-byte strings a and b are equal, and 0 if not. If you don't understand why to use this instead of memcmp, study the keywords I've given!}