How to protect against Replay Attacks

Question

I am trying to figure out a way to implement decent crypto on a micro-controller project. I have an ARMv4 based MCU that will control my garage door and receive commands over a WiFi module.

The MCU will run a TCP/IP server, that will listen for commands from Android clients that can connect from anywhere on the Internet, which is why I need to implement crypto.

I understand how to use AES with shared secret key to properly encrypt traffic, but I am finding it difficult to deal with Replay Attacks. All solutions I see so far have serious drawbacks.

There are two fundamental problems which prevent me from using well established methods like session tokens, timestamps or nonces:

1. The MCU has no reliable source of entropy, so I can't generate quality random numbers.

2. The attacker can reset the MCU by cutting power to the garage, thus erasing any stored state at will, and resetting time counter to zero (or just wait 49 days until it loops).

With these restrictions in mind, I can see only one approach that seems ok to me (i.e. I don't see how to break it yet). Unfortunately, this requires non-volatile storage, which means writing to external flash, which introduces some serious complexity due to a variety of technical details.

I would love to get some feedback on the following solution. Even better, is there a solution I am missing that does not require non-volatile storage?

Please note that the primary purpose of this project is education. I realize that I could simplify this problem by setting up a secure relay inside my firewall, and let that handle Internet traffic, instead of exposing the MCU directly. But what would be the fun in that? ;)

= Proposed Solution =

A pair of shared AES keys will be used. One key to turn a Nonce into an IV for the CBC stage, and another for encrypting the messages themselves:

• Shared message Key
• Shared IV_Key

Here's a picture of what I am doing: https://www.youtube.com/watch?v=JNsUrOVQKpE#t=10m11s

1) Android takes current time in milliseconds (Ti) (64-bit long) and uses it as a nonce input into the CBC stage to encrypt the command:

a) IV(i) = AES_ECB(IV_Key, Ti)
b) Ci = AES_CBC(Key, IV(i), COMMAND)

2) Android utilizes /dev/random to generate the IV_Response that the MCU will use to answer current request.

3) Android sends [<Ti, IV_Response, Ci>, <== HMAC(K)]

4) MCU receives and verifies integrity using HMAC, so attacker can't modify plain text Ti.

5) MCU checks that Ti > T(i-1) stored in flash. This ensures that recorded messages can't be replayed.

6) MCU calculates IV(i) = AES_ECB(IV_Key, Ti) and decrypts Ci.

7) MCU responds using AES_CBC(Key, IV_Response, RESPONSE)

8) MCU stores Ti in external flash memory.

Does this work? Is there a simpler approach?

EDIT: It was already shown in comments that this approach is vulnerable to a Delayed Playback Attack. If the attacker records and blocks messages from reaching the MCU, then the messages can be played back at any later time and still be considered valid, so this algorithm is no good.

As suggested by @owlstead, a challenge/response system is likely required. Unless I can find a way around that, I think I need to do the following:

• Port or implement a decent PRGA. (Any recommendations?)
• Pre-compute a lot of random seed values for the PRGA. A new seed will be used for every MCU restart. Assuming 128-bit seeds, 16K of storage buys be a 1000 unique seeds, so the values won't loop until the MCU successfully uses at least one PRGA output value and restarts a 1000 times. That doesn't seem too bad.
• Use the output of PRGA to generate the challenges.

Does that sound about right?

Answer 1

Having an IV_KEY is unnecessary. IVs (and similar constructs, such as salts) do not need to be encrypted, and if you look at image you linked to in the youtube video you'll see their description of the payload includes the IV in plaintext. They are used so that the same plaintext does not encode to the same ciphertext under the same key every time, which presents information to an attacker. The protection against the IV being altered is the HMAC on the message, not the encryption. As such, you can remove that requirement. EDIT: This paragraph is incorrect, see discussion below. As noted though, your approach described above will work fine.

Your system does have a flaw though, namely the IV_Response. I assume, from that you include it in your system, that it serves some purpose. However, because it is not in any way encoded, it allows an attacker to respond affirmatively to a device's request without the MCU receiving it. Let's say that your device's were instructing an MCU that was running a small robot to throw a ball. Your commands might look like.

1) Move to loc (x,y).
2) Lower anchor to secure bot table.
3) Throw ball

Our attacker can allow messages 1 and 3 to pass as expected, and block 2 from getting to the MCU while still responding affirmatively, causing our bot to be damaged when it tosses the ball without being anchored. This does have an imperfect solution. Append the response (which should fit into a single block) to the command so that it is encrypted as well, and have the MCU respond with AES_ECB(Key, Response), which the device will verify. As such, the attacker will not be able to forge (feasibly) a valid response. Note that as you consider /dev/random untrustworthy this could provide an attacker with plaintext-ciphertext pairs, which can be used for linear cryptanalysis of the key provided an attacker has a large set of pairs to work with. As such, you'll need to change the key with some regularity.

Other than that, your approach looks good. Just remember it is crucial that you use the stored Ti to protect against the replay attack, and not the MCU's clock. Otherwise you run into synchronization problems.