48-bit nonce reuse with ChaCha20

Question

The situation:

I have a group with 20 members, each member broadcasting 1 message per second. Communicating one on one is possible, but 1 message per member per second is the absolute limit and every member needs every message.

The only means of communication for this group allows me to send 258 bits per message. The message the group members need to send is precisely 200 bits long. This means that I have 258 - 200 = 58 bits left. These messages consist of 20 bits that do not need to get encrypted and 180 bits that do need to get encrypted.

The solution I thought of:

Because of the limits on the amount of messages I need a symmetric cipher where every member has a shared key. Asymmetric cryptography won't work since I simply do not have the means to send every group member a message every second, asymmetric cryptography would mean that every group member will send 20 messages a second instead of 1.

I wanted to use ChaCha20 to encrypt the part of a message that needs to get encrypted since I would need a streamcipher anyway (because I don't have the room to encrypt 2 128-bit blocks).

ChaCha20, as you guys know uses a nonce. Since the group shares a key and every member broadcasts messages every second I cannot use a simple counter. The only solution would be a 48-bit (the largest possible given my constraint) random nonce (which is a very bad idea).

BUT: I did the following math:

Calculate the square root of the number of possible nonces (2^48) to find the point at which the probability of collision reaches approximately 50%. This is the point at which nonce reuse becomes statistically likely since $\sqrt{(2^{48}} = 2^{24}$

Divide the result by the number of messages per second (20) to find how many seconds it takes for nonce reuse to become statistically likely:

(2^24) / 20 = 838,860.8 seconds

So, in a worst-case scenario, with a 48-bit nonce field and 20 messages encrypted per second, nonce reuse may become statistically likely after approximately 8,388,608 seconds, which is roughly equivalent to 97 days.

It's important to note that this is a simplified calculation and assumes truly random nonce generation

My questions:

1. If I use the 48-bit random nonce and change the key every day, would this solution be secure?
2. Is there a better solution for my problem?

EDIT:

I managed to get 6 bits more for my nonce. this means that my nonce is now 64-bit long giving the following calculations:

Seconds before nonce reuse becomes statically likely

With a 64-bit nonce space, there are 2^64 possible nonces. To apply the birthday paradox, I calculated the approximate number of nonces (N) required for the probability: N ≈ 113,382,816,773

In seconds ≈ 5,669,140,838,650 seconds

which is 179 years before nonce reuse becomes statically likely, according to the birthday paradox.

Probability of nonce reuse in a single day (assuming keys get switches every day)

To calculate the probability of a collision in a set of n nonces, I calculated: P(collision) = 1 - (1 - 1/2^64)^1,728,000

1,728,000 is the amount of nonces generated in a day.

P(collision) ≈ 0.0000000000000000000000000000000000000000000000000000000000000024%

Second Edit:

As @kelalaka mentioned I do have a ID for each client that sends messages in the header of each message. The current idea I have for a nonce is as follows:

Use the clientID (32bit) + a 32bit counter + a 32bit random field.

Since each client now has a field in the nonce that is unique to them, they can have their personal counter. The 32bit random field makes sure that future nonces aren't predictable.

This solution is obviously better than generating random nonces in the hope that a nonce doesn't get reused since every client now has 2^32 unique nonces.

Do I have this right? If so, I will post it as an answer and close this topic.

Answer 1

1. If I use the 48-bit random nonce and change the key every day, would this solution be secure?

Well, every day, you will be (in aggregate) sending $20 \times 86,400 = 1,728,000$ encrypted messages each day. So, the expected number of pairs of transmissions that randomly pick the same 48 bit nonce is $\binom{1728000}{2} \times 2^{-48} \approx 0.005304$, that is, about one every 189 days or so.

So, the question is: are those odds too high for you? For me, that would be (unless the consequences of the adversary finding the xor of two random plaintexts is quite small), but that's really up to you.

2. Is there a better solution for my problem?

The obvious alternative is to use nonrandom nonces. If each sender can remember how many messages it has sent that day, then (as Morrolan has suggested); give each sender a (say) unique 1 byte identifier, and have the nonce be the sender concatinated by a 20 bit count of the number of messages sent (which gives you another 20 bits to play with; possibly including a 20 bit message authentication code (to detect forgeries), or maybe putting a random value in there as a 'belt-and-suspenders' option, or maybe even using those 20 bits for something else in the protocol).

Alternatively, if the senders cannot remember how many messages they have sent (e.g. because they might reboot and forget), what you can do is have them send their 1 byte identifier followed by the current time of day (and 40 bits gives you enough space to express it in microseconds); again, if they have a rough idea about what time it is, this can work too.