1
$\begingroup$

I'm writing an application, which can be used on multiple clients, and share data on a server. To make sure the data never leaves the clients unencrypted, the application should offer encryption with AES-GCM and ChaCha20-Poly1305. Both of them need a nonce of 96bits, and it is recommended to use a counter, to make sure the nonce never repeats for this key.

Since I cannot think of a reliable system to guarantee the uniqueness/state of this nonce (the server is passive and only offers storage), I thought about using a timestamp to build the nonce:

Nonce-96-bit = Timestamp-Milliseconds-64bit combined_with CsRandom-Number-32bit

Is this a correct way to solve the problem? I'm aware of XChaCha20-Poly1305 which solves the problem with a bigger nonce so a random number can be used, but at the moment I'm working with the BouncyCastle library which offers the necessary .Net cross-platform support.

$\endgroup$
  • $\begingroup$ If you can have a reliable timer, you should generally be able to arrange a counter, too. After all, a timer is just a hardware counter that automatically increments itself at a known rate. $\endgroup$ – Ilmari Karonen Aug 7 '18 at 19:13
  • $\begingroup$ @IlmariKaronen - The timer would not be shared by all clients, they would use the time of each device. They wouldn't be "reliable", but this way I could avoid the central controlling of the counter, which I can't implement. $\endgroup$ – martinstoeckli Aug 7 '18 at 19:22
  • $\begingroup$ You can always hash down a longer nonce and the master key to a new 256-bit key. XChaCha/XSalsa is a popular choice for that, but you can use any hash function/PRF you like. $\endgroup$ – CodesInChaos Aug 7 '18 at 19:38
  • 1
    $\begingroup$ Is there a reason why the clients can't each have a different key? Note that the server wouldn't necessarily need to store all the client keys, since it could derive them all from a single master key by combining it with the client ID using a suitable KDF. $\endgroup$ – Ilmari Karonen Aug 7 '18 at 19:52
  • $\begingroup$ @CodesInChaos - So that's the difference between ChaCha and XChaCha? Thanks for the input, that's interesting, but sadly I'm not experienced enough to do this. Already played around with your Chaos.NaCl library in search of a libsodium compatible library, thanks. $\endgroup$ – martinstoeckli Aug 7 '18 at 19:54
2
$\begingroup$

This isn't a very good idea - your chances of collision are not that low (depending on the number of clients you have). At best, your chances are $2^{-32}$ for 2 active clients. You would be better of just using a secure random 96 bit nonce as recommended by the NIST guidelines for AES-GCM (note though that you must not send more than $2^{32}$ messages with the same key when using this construction so that the chance of IV colliding doesn't exceed $2^{-32}$)

$\endgroup$
  • $\begingroup$ Just to make sure I understood it correctly: The 2^-32 is the chance of a collision, if the clients encrypt in the same millisecond, because the uniqueness is solely based on the random 32 bit number then? $\endgroup$ – martinstoeckli Aug 7 '18 at 19:02
  • 1
    $\begingroup$ @martinstoeckli: Right. If you ever send two messages within the same millisecond, your chance of getting a collision during that millisecond is $2^{-32}$ (i.e. about the same, or actually about twice as high, as your total chance of getting a collision if you send $2^{32}$ messages with random 96 bit nonces without re-keying). Of course, if the probability of two messages being sent within the same millisecond is low enough (and you can guarantee that, even under attack), then the time-based scheme could still be better. But I wouldn't generally count on it. $\endgroup$ – Ilmari Karonen Aug 7 '18 at 19:12
  • $\begingroup$ @IlmariKaronen - So that's a that's the scenario: an attacker tries to force the clients to use the same timestamp, so the chance of a collision grows, and he can take advantage? In this case a pure random nonce would indeed be the better choice. $\endgroup$ – martinstoeckli Aug 7 '18 at 19:33
  • 2
    $\begingroup$ @martinstoeckli: Yeah. In particular, note that if more than two messages get sent within the same millisecond, the chance of a collision grows quadratically. $\endgroup$ – Ilmari Karonen Aug 7 '18 at 19:53
1
$\begingroup$

The first point I'd make is: why can't you just use TLS? (Or if it's a non-interactive protocol, why can't you use ECIES?)

Nonce-96-bit = Timestamp-Milliseconds-64bit combined_with CsRandom-Number-32bit

My impression is that this might well be more prone to nonce reuse than just random 96-bit nonces. All that's required is that two messages be sent with the same key, at identical timestamp values, and with a 32-bit collision of the random value ($2^{-32}$ chance). It's impossible to calculate how often you'll see timestamp collisions without deep knowledge of how your app would be used in production, but in my experience such collisions do happen at rates that would be much more common than 96-bit nonce collisions as well.

One way to dodge the whole problem is to use ephemeral session keys (as TLS and ECIES already do for you, hint hint). That way you can use counter nonces because the sessions are scoped to the lifetime of your volatile memory, avoiding the need for persistent state. If you insist in building your own protocol, you could try using the shared master key only to encrypt random session keys; in this case the risks of random 96-bit nonce collisions is mitigated by the fact that the plaintexts are random.

$\endgroup$
  • $\begingroup$ @IlmariKaronen: Oh, duh. Fixed. $\endgroup$ – Luis Casillas Aug 7 '18 at 19:05
  • $\begingroup$ Will have to spend some time to investigate those suggestions, I'm not yet familiar how TLS or this integrated-encryption-scheme could play together with the symmetric encryption. Or do you mean to switch to asymetric encryption? Thanks anyway for the ideas, will need some time... $\endgroup$ – martinstoeckli Aug 7 '18 at 19:25
  • $\begingroup$ BTW, no I don't insist in building my own protocol, rather I want to learn what is best practise. From the answers so far, I conclude that using a pure random nonce is the way to go, and the maximum of 2^32 encryptions should be no problem in my situation. $\endgroup$ – martinstoeckli Aug 7 '18 at 19:40

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.