[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]

Category

Other

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 5a4fab2).
It now picks a random 31 bits number together with the lower 32bits of the mac address:

firmware/src/mesh/Router.cpp

Line 105 in b43c7c0

i = random(numPacketId & 0x7fffffff);

firmware/src/mesh/CryptoEngine.cpp

Lines 30 to 37 in b43c7c0

	void CryptoEngine::initNonce(uint32_t fromNode, uint64_t packetId)
	{
	memset(nonce, 0, sizeof(nonce));
	// use memcpy to avoid breaking strict-aliasing
	memcpy(nonce, &packetId, sizeof(uint64_t));
	memcpy(nonce + sizeof(uint64_t), &fromNode, sizeof(uint32_t));
	}

The crypto code use 64 bits packet ids, but the packet id type is defined as 32 bits:

firmware/src/mesh/MeshTypes.h

Line 10 in b43c7c0

typedef uint32_t PacketId; // A packet sequence number

There is then a zero-extension when calling encrypt:

firmware/src/mesh/Router.cpp

Line 424 in b43c7c0

crypto->encrypt(getFrom(p), p->id, numbytes, bytes);

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]

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).

[clwgh]

There's a utility which will dump packets as ascii and parse them. Is that format useful? I have around 10,500 packets saved from some recent testing if that's of any use to you, or do you need orders of magnitude more for the collision stats to play out?

Example:

{'from': 3806698956, 'to': 3664095572, 'decoded': {'portnum': 'NODEINFO_APP', 'payload': b'\n\t!e2e59dcc\x12\x12North Wales EmComm\x1a\x04NWEC"\x06H\'\xe2\xe5\x9d\xcc(\x0c8\x03', 'wantResponse': True, 'user': {'id': '!e2e59dcc', 'longName': 'North Wales EmComm', 'shortName': 'NWEC', 'macaddr': 'SCfi5Z3M', 'hwModel': 'LILYGO_TBEAM_S3_CORE', 'role': 'ROUTER_CLIENT', 'raw': id: "!e2e59dcc"
long_name: "North Wales EmComm"
short_name: "NWEC"
macaddr: "H'\342\345\235\314"
hw_model: LILYGO_TBEAM_S3_CORE
role: ROUTER_CLIENT
}}, 'id': 190517364, 'rxSnr': 4.25, 'hopLimit': 2, 'rxRssi': -84, 'raw': from: 3806698956
to: 3664095572
decoded {
  portnum: NODEINFO_APP
  payload: "\n\t!e2e59dcc\022\022North Wales EmComm\032\004NWEC"\006H'\342\345\235\314(\0148\003"
  want_response: true
}
id: 190517364
rx_snr: 4.25
hop_limit: 2
rx_rssi: -84
, 'fromId': None, 'toId': None} 


Received packet:
  From: 3806698956 / !e2e59dcc
  To: 3664095572 / !da65a954
  Hop Limit: 2
  SNR: 4.25
  RSSI: -84
  Port Number: NODEINFO_APP
  Node Information:
    ID: !e2e59dcc
    Long Name: North Wales EmComm
    Short Name: NWEC
    MAC Address: SCfi5Z3M
    Hardware Model: LILYGO_TBEAM_S3_CORE

[caveman99]

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]

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).

[caveman99]

I am not python savvy but i read that as a mechanism to prevent Nonce Re-Use... The problem with using RAM for this is that the nodes are already ramtight in larger networks and we have several stores competing for it. Also only a fraction of the nodes have an RTC.

After reading closer, you propose to start at a random point and then just increment the packet ID, no matter how you store it (and then the ram storage for a single int value is viable). What i am not sure of: Is incementing vs. actual random generation opening up other attack vectors, since the sequence is (very) predictable then ... ?

[mkgin]

Incrementing a nonce is computationally easier than getting random number from a good rng for each packet. At the same rate, I think the rng is more likely to have a duplicate nonce than incrementing, how much is hard to say.

A vetted pseudo random function is typically implemented in most ciphers anyway.

Incrementing and storing to flash has trade-offs too.

• If flash is written over when upgrading, a new nonce is chosen, so at the given rate a nonce is reused in 0-136 years.
• After an unclean shutdown where flash is not written, one is likely to reuse nonces. Incrementing on boot could be a way around this, one would end up skipping up to 2¹⁶-1 nonces per reboot.

[Jorropo]

After an unclean shutdown where flash is not written, one is likely to reuse nonces. Incrementing on boot could be a way around this, one would end up skipping up to 2¹⁶-1 nonces per reboot.

This is what I'm proposing.

[gmaxwell]

These nonce incrementing schemes aren't so great when you consider that many users are constantly reflashing devices-- better would be to use a cipher mode that isn't vulnerable to IV reuse. The messages sent in meshtastic are all very small, so the extra overhead of a iv misuse resistant scheme (e.g. AEC-GCM-SIV) shouldn't be substantial.