Prevent replay attack without storage 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 (&lt; 1 second) as the base has no memory for session storage.
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.