What is a randomly derived key?

It is a well-known fact that using the same key + nonce combination with a stream cipher twice breaks security. The NaCl library has different primitives for authenticated encryption (i.e., xsalsa20poly1305 and aes256gcm) and its website warns:

Beware that some of these primitives have 8-byte nonces. For those primitives it is no longer true that randomly generated nonces have negligible risk of collision. Callers who are unable to count 1,2,3,..., and who insist on using these primitives, are advised to use a randomly derived key for each message.

Now, I'm wondering: what is a randomly derived key ?

If I use Argon2i to derive a key K from an user-entered password and random 32-byte (256 bits) salt, is the key K a "randomly derived key" ?

“Randomly derived” is not standard phrasing and I suspect that it isn't what the author meant to write. From context, what is necessary here is to have a distinct key for each message. This can be achieved either by randomly generating a key (I think that's what the author meant to write) or by deriving a key using a key derivation function with a unique input. The second possibility could be called “pseudorandomly deriving a unique key”, because a KDF should be indistinguishable from random if you don't know its secret input, but usually we just say “deriving”.

Since the problem to solve here is the absence of a unique input that's distinct for each message, deriving a key is unlikely to be possible. However, it could be possible if there is a unique input for each message, but it isn't a simple counter, rather it's some long string. With a KDF to derive a key, a unique input of any length is fine. But to derive an 8-byte nonce, a KDF doesn't help, because no matter how it's done, a randomly or pseudorandomly generated 8-byte strings has a $$\approx 2^{-32}$$ chance of colliding if you generate two of them, increasing as the number of messages increases.

If you derive a key from a password and a salt, that's a pseudorandomly derived key. From the same password and the same salt, you always get the same key. Never use a key that's derived from a password to encrypt actual data: if you ever want to change the password, you'd need to decrypt and re-encrypt the data. Instead, use K only to encrypt a master secret S. Then, on a password change, you only need to decrypt S and re-encrypt it with the new K. Although S can be the key that you use to encrypt data, I recommend adding another level of indirection: it gives you more flexibility. For each message or each conversation, use S as the secret input to an ordinary key derivation function (e.g. KDF1 or KDF2 or HKDF) with two public inputs: a public nonce which is sent with the message (or the first message in the conversation), and a version number which is initially 0 and which you'll increment if you ever want to use S for different things in the future. Once you have that per-message or per-conversation key L, it doesn't matter how it was generated. For each distinct L, if you use L for multiple messages, each needs to have a distinct nonce. If you have different keys L₁ and L₂, you can use the same nonce twice, once for each key.

• What do you mean by "use it with a per message or per conversation as the secret input" ? I feel like there is a missing word. Also what's the problem with using K directly ? Is it that it is derived from Argon2i and not KDF1/2 or HKDF ? Finally, if for each message I generate a new random 32-byte salt and derive a new key K' using Argon2i from this new salt and the same user-entered password, do I still need to make sure the nonces of each messages are distinct ? – Zaphod Aug 13 '19 at 20:02
• I also just noticed you probably meant $\approx 2^{-32}$ instead of $\approx 2^{32}$ if I'm correct. – Zaphod Aug 13 '19 at 20:06
• @Zaphod I rewrote the sentence. Actually, I rewrote the whole paragraph, because it was missing an important step. Since K is a key and not a password, there's no point in using Argon2 on it: save the heavy computations for the things that need them. Don't derive multiple keys from the same password and different salts unless you have a very good reason to treat those operations as using different passwords where the user happened to have reused the password. It makes key management harder and uses a lot more CPU without any security benefit. – Gilles 'SO- stop being evil' Aug 13 '19 at 20:16
• Thanks for the edit, it's clearer now. I understand that deriving a new key from a unique password but different random salt for each message, with Argon2i for instance, may not be the best thing to do in practice. However, on a theoretical perspective, is it secure to do so ? Can the same nonce be used with two of these keys ? – Zaphod Aug 14 '19 at 11:00
• @Zaphod Yes, as long as the two keys are distinct, it's ok to use the same nonce with both. – Gilles 'SO- stop being evil' Aug 14 '19 at 11:44