2
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ Can participants keep state? If so, given you know the number of participants, and each one broadcasts at the same frequency, is there something stopping you from partitioning the 48-bit nonce space into 20 equal chunks, with each participant getting their own and counting up? $\endgroup$
    – Morrolan
    Commented Sep 25, 2023 at 8:41
  • $\begingroup$ @kelalaka The problem is that I have 58 spare bits that I can use for the nonce. A 192-bit nonce would be too big. $\endgroup$
    – Florebol
    Commented Sep 25, 2023 at 8:47
  • $\begingroup$ What about the network protocols? there might be some part that can you integrate into IV etc. Not that; in the attackers advantage %50 is too high. One should stop way less than this even %1 may be high, $\endgroup$
    – kelalaka
    Commented Sep 25, 2023 at 8:48
  • $\begingroup$ @kelalaka I am sorry but I am afraid I dont know what you mean with integrating the network protocols into the IV. I chose 50% because that is when the reuse is more likely to happen. Based on this calculation it would tak 97 days with the same key for nonce reuse to be statically likely. When calculating the probability of nonce reuse for one day (I refresh the key every day) with a 48bit nonce and 20 nonces per second I get: P(collision) = 1 - (1 - 1/2^48)^20 nonces/second * 24 hours * 60 minutes * 60 seconds P(collision) ≈ 0.0000078% $\endgroup$
    – Florebol
    Commented Sep 25, 2023 at 9:20
  • $\begingroup$ Which network protocol the server/client communicates? How does the server know which client sent? Instead of once per second send once half second and gain ~100 bits per message ( you will need some header to combine the two). Depending on the attacker time and money and the value of the information 1/100 probability can be very profitable. $\endgroup$
    – kelalaka
    Commented Sep 25, 2023 at 9:25

1 Answer 1

1
$\begingroup$
  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.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.