3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Wait, so the base can store received data but not session info? $\endgroup$ – Reid Rankin Nov 13 '15 at 13:18
  • 1
    $\begingroup$ Also, I don't see how this prevents replays of mote data. It authenticates the base, but not the mote. If the base doesn't store R, it has no way of knowing if the mote sent the right R+2 in step 3. $\endgroup$ – Reid Rankin Nov 13 '15 at 13:22
  • $\begingroup$ Title says no storage but the random nonce is stored? Could you clarify? $\endgroup$ – otus Nov 13 '15 at 13:24
  • $\begingroup$ "Mote A decrypts 'ack' and verifies received [R+1] matches stored [R+1]". How does mote get the stored [R+1]? Is it a determanistic function of [R]? $\endgroup$ – poncho Nov 13 '15 at 13:26
  • 1
    $\begingroup$ @kd5pev: Aside from the security problem noted by poncho (which is fixable, as he notes), a more general feasibility issue is that you assume a mote can decrypt something enciphered with its public key. That's highly antagonist with small (8-bit) microcontroller. Can you entrust Base enough to hold a secret that (if misused) would allows to impersonate every mote? $\endgroup$ – fgrieu Nov 13 '15 at 15:23
1
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ it is feasible (and used to be common in Point Of Sales Terminals when they were built using 8-bit CPUs) that an 8-bit CPU without crypto-accelerator do an RSA public-key operation. Therefore, using RSA Public-Key crypto to authenticate the server or/and encipher the data sent to the server is feasible. Using ECC for this purpose is less feasible, for performance reasons. $\endgroup$ – fgrieu Nov 16 '15 at 16:12
  • $\begingroup$ Okay, maybe 8 bit cpu's and crypto work together, but he also said low power sensor unit. And considering that he doesn't want to save session information because of limited memory, doing public key crypto in memory is unrealistic. For a simple square and multiply for RSA you need at least two elements in memory, so that's at least 300 bytes. Quite a lot if you can't afford 32 bytes for a session key. $\endgroup$ – tylo Nov 17 '15 at 13:14
  • $\begingroup$ Agreed, RSA needs >3 times the modulus size in RAM, that is about 800 bytes of RAM for 2048-bit RSA. If we're stuck much below that, no hope. However 1kB is available in some 8-bit CPUs with 8x8->16 multiplication and well under US$2 (PIC18..). My understanding (likely flawed) of the without storage requirement was that it applies to the base; or/and that no permanent often-modifiable memory (like battery-backed RAM, FRAM, high-endurance EEPROM, Hard Disk, SDD) is available. $\endgroup$ – fgrieu Nov 17 '15 at 15:26

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.