# 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" ?

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.
• I also just noticed you probably meant $\approx 2^{-32}$ instead of $\approx 2^{32}$ if I'm correct. – Zaphod Aug 13 at 20:06