Prevent replay attack without storage

Question

I am designing a set of low-power sensing motes. Each mote will communicate to a central base over RF.

I want the mote to be able to authenticate itself with the base, and send its data without being vulnerable to replay attacks while not using a lot of processing power.

Are there major flaws in the following algorithm?

• Mote A sends a 'hello' message to Base. This message contains the ID# (public key of the mote) and a random nonce [R] (HW generated) encrypted by the base's public key.
• Base decrypts the 'hello' and verifies the ID# against a whitelist.
• Base sends an 'ack' message to Mote A. This message contains [R+1] and is encrypted by the ID# (mote's public key)
• Mote A decrypts 'ack' and verifies received [R+1] matches stored [R+1].
• Mote A sends ID#, data and [R+2] to base encrypted by Base public key.
• Base decrypts and sends an 'ack' and [R+3] and is encrypted by the ID# (mote's public key)
• Mote A verifies 'ack' and Communication is Complete.

The random nonce [R, R+1, R+2, R+3] will only be valid for a short period of time (< 1 second) as the base has no memory for session storage.

Answer 1

You don't really need to authenticate the base to the mote before transmission to ensure confidentiality, since the data will be encrypted to its key. The real reason you need it is to prevent an attacker from tricking the mote into thinking it's reported already and causing data loss.

To prevent replay, storage is fundamentally required. The problem is the base, which may have multiple sessions to deal with at a time. I suggest that if you have an SD card connected already, it's probably much easier to read from it than to reduce storage to what fits in RAM by somehow restricting sessions to one at a time. (What about timeouts? What about backoff? These are hard problems!)

If you can put up with identifying the data by a hash, or the nonce, and deriving your anti-replay protection for the base from simply checking the SD card to see if the data has been written already, you can use the following extremely lightweight protocol:

• Mote sends cleartext ID, encrypted data, encrypted nonce to base, under base pubkey
• Base sends ack, with nonce encrypted under mote pubkey
• Mote updates timestamp of last successful transmission after checking nonce

For bonus points, use the timestamp of the last successful transmission as the nonce, and switch from encrypting the nonce to the mote to signing the nonce with the base privkey, and you can save some RAM (and avoid transmitting the mote pubkey each time).

Also, look into ECDH. Having the same shared secret for each cipher operation on the mote would save some cycles and RAM.

Also note that you must used AEAD modes (surprisingly lightweight) or Encrypt-then-MAC (with separate keys) for all of this, or malicious bitflips will ruin your day, especially if you're using the timestamp trick above. And use a proper cipher. RC4 is lightweight, but don't touch it with a 10 foot pole.

Answer 2

This protocol doesn't authenticate the mote at all. Consider this attack:

• Mote B sends a 'hello' message to Base. This message contains the ID# of Mote A and a random nonce [R] (HW generated) encrypted by the base's public key.

• Base decrypts the 'hello' and verifies the ID# against a whitelist.

• Base sends an 'ack' message. This message contains some gibberish that Mote B cannot understand.

• Mote B sends ID#, data and [R+2] to base encrypted by Base public key.

• Base decrypts and sends more gibberish that Mote B cannot understand

• Mote B ignores the ack.

Here, the base has accepted data as coming from Mote A, even though it actually came from Mote B.

In addition, it does nothing to prevent a replay attack (as someone just replaying the two messages that the mote sends to the server would cause the server to accept the replay).

For this general idea to work, then either:

• The base needs to send some data to the mote encrypted by the mote's public key, and the mote must use that data as a necessary part to continue the exchange; or

• The mote needs to sign something with its private key (which the base validates)

In addition, then if the server cannot store state about the messages it has already received, then it is the one that needs to pick the random number (nonce), and inject that into the protocol.

Answer 3

The entire setting is highly unrealistic.

• You assume, your motes can do public key cryptography.
• The motes know the public key of the base. Reasonably sized public keys (non-ECC crypto, like RSA, ElGamal, etc.) are at least 150 byte (1200 bit), and anything below 100 byte is considered broken today.
• The base has a whitelist with the public keys of the motes

If you have a 8 bit microcontroller, surely you don't have public key cryptography. You need several hundreds of bytes in memory just to execute the decryption (depends on algorithm and implementation). More likely you have symmetric cryptography only, and that is not trivial already.

Considering your protocol:

• If you want to authenticate both parties, then you need a challenge-response in both directions, with different randomness. Calculating R+1, then R+2, then R+3, .... does not help at all for authentication.
• Using R+2, R+3, ... helps against replay attacks. But it is unnecessary. It's better to have a key exchange protocol at the start of the communication to prevent replays, and then use this session key as protection against replay attacks. You could either just use the session key to encrypt, or derive two keys for encryption and integrity (e.g. HMAC)

Finally, I suggest reading up on existing work in exactly this context. Keywords "low power mutual authentication" give you a lot of results on google scholar.