[Bug]: nonces are only randomized with 31 bits, this make it rare but possible to see duplicated nonces in the wild threatening confidentiality of messages

Jorropo commented 3 weeks ago

Hardware

Not Applicable

Firmware Version

current

Description

The IV initialization looks incorrect, it use 96 bits IV, but ~65* of them are fixed, so only ~31* bits are randomized. It used to be stored in flash but apparently this did not worked (see 5a4fab25066e77dec48bb8cac11799edce8be67f). It now picks a random 31 bits number together with the lower 32bits of the mac address: https://github.com/meshtastic/firmware/blob/b43c7c0f23690a966c899bb91463861db9b54365/src/mesh/Router.cpp#L105 https://github.com/meshtastic/firmware/blob/b43c7c0f23690a966c899bb91463861db9b54365/src/mesh/CryptoEngine.cpp#L30-L37

The crypto code use 64 bits packet ids, but the packet id type is defined as 32 bits: https://github.com/meshtastic/firmware/blob/b43c7c0f23690a966c899bb91463861db9b54365/src/mesh/MeshTypes.h#L10 There is then a zero-extension when calling encrypt: https://github.com/meshtastic/firmware/blob/b43c7c0f23690a966c899bb91463861db9b54365/src/mesh/Router.cpp#L424

If you use a 64bits number but 33 of them are fixed, you only gain 31 bits of security.

Due to the birth paradox assuming the randomness source is good you would need ~58k reboots to reach a 50% duplicate nonce chance on one node. This does not cause an issue across nodes because they each have a different nodeid. The number of reboots is lower because each messages then incrementally update the packet id, so a reboot might only consume a handful of nonces or many thousands depending on how many messages were sent. Given there are many thousand nodes each rolling for theses odds independently it is likely a some of duplicate nonces will be used some day if they weren't already.

The consequences of duplicated nonces with AES-CTR is that it becomes possible to perform known plaintext attack to decrypt one message knowing the other. This is way worst than it sounds because it is possible to bruteforce each bit independently. That means if we know a tiny bit about the structure of the message (which for meshtastic we do, they are often nodeinfo, or chat messages) we can extend our guess with new information gained. Independent information like exact GPS positions or Battery % are unlikely to be recoverable. But we know chat messages are likely UTF8 and likely to form meaningful sentences, so you could bruteforce character by character until it makes meaningful words and sentences, this should be easy to do on a modern CPU and trivial on a modern GPU. Combined with #4030 attack, you could replay a malicious with a custom content. Upside because there is no MAC or AEAD it's impossible to know if you are actually correct in your complete guess, so completely random pieces of information like arbitrary numbers or GPS position would be hard to impossible to confidently break if they align. If one message is shorter than the other, only the shared length can be decrypted.

Because nonces are incremented sequentially, you wouldn't get a random duplicates from time to time. You would see all overlapped messages back-to-back duplicates.

Checking for duplicated nonces is trivial, the nodeid and packetid are sent in plaintext (which is normal, there is hardly a way around that within meshtastic's tradeoffs context).

This could be improved by using a duplicate nonce resistant cipher like AES-GCM-SIV or deriving the nonce from the message hash or many other things. This looks like it would be a breaking change either way.

*I say ~65bits because it is possible to roll something in the high 31 bits then the message increment would roll into 32 bits. So 64 out of 96 bits are fixed, 31 bits are randomized and 1 is very likely to be 0.

Relevant log output

N/A

Jorropo commented 3 weeks ago

If someone knows where I could find a database of historical meshtastic messages (let's say captured from MQTT) I would like to see this, we could check for duplicate nodeid, packetid pairs.

I guess we would see one or two ranges overlap, but they would use AQ== anyway (making trying to crack them a bit pointless since we already know the key).

caveman99 commented 3 weeks ago

The packet ID in the lora header will be truncated to 32 bit anyway, so this can not be changed. Doesn't mean the rest of the concerns are not valid, but i am closing this as it's a protocol restraint. Only reason this is defined as 64 bit is to make the nonce algo happy.

Jorropo commented 3 weeks ago

After sleeping on it I think we can fix it without breaking the protocol. Here is pseudo code:

packetRam = 0
packetLimit = 0

def generatePacketId():
 if packetRam == 0:
  packetRam = readPacketIdFromFlash()
  if packetRam == 0:
   packetRam = randomUint32()
  limit = packetRam + 2**16
  if limit == 0: limit += 1 # limit wrapped around to zero, skip it
  storePacketIdIntoFlash(limit)
  return packetId
 packetRam++
 if packetRam == 0: packetRam++ # we just wrapped around 0, skip it
 if limit == packetRam: # we reached the value stored into the flash, bump it before proceeding
  limit = packetRam + 2**16
  if limit == 0: limit += 1 # limit wrapped around to zero, skip it
  storePacketIdIntoFlash(limit)
 return packetRam

In english this stores the current packet ID into ram with a granularity of 2**16 this means we can generate 2**16 packets before having to write again to flash. Assuming you send 1 packet every second it would take 136 years before we use duplicated nonces. Assuming you reboot the node once a day it would take 179 years before we use duplicated nonces.

An other idea could be for modules with RTC use the RTC to seed packetRam and increment from there. Assuming we use second precision (this would require us to wait at most a second at each boot, we can probably pipeline this with the existing boot process) we would have 136 years before we use duplicated nonces (altho nodes would be limited to not send packets faster than 1 per second overall).

meshtastic / firmware