Nonce reuse resistance

Question

I read this article and I think the approach outlined there is very interesting for one of our use case.

We use ChaCha20 Poly1305 (via Sodium crypto_aead_chacha20poly1305_encrypt_detached) to encrypt the data, which is typically 8 kb in size. We use this because this way the mac + nonce can fit in the available space we have in the page header, using XChaCha20 (and random nonce) is not possible because of the amount of space they would take.

The data is pages in database, and each page may be modified multiple times over the lifetime of the database.

I'm trying to figure out what the best way to handle nonce / key management in this case.

Currently we generate a random nonce per page and then increment the nonce every time the page is modified. To avoid the case where a random nonce / increment is reused, we also derive a new key for each page (via crypto_kdf_derive_from_key, where the subkeyid is actually the page number).

This seems fine, but it require us to do quite a bit of work every single time.

Note that we use

The article above seems to indicate that using the hash of the data that we encrypt as the nonce will help avoid the problem with nonce reuse, since if that happens, it will be identical data & nonce, so you can't XOR them together to find anything meaningful (but can find if they are repeating).

If this is a valid option, that would give us the option of having a single key for all the pages, and a nonce based on the hash of the data and avoid the need to carefully manage the nonces.

Assuming this is the case, can we use any hashing algorithm (we already do checksum with XXHash64, or do we need a cryptographic hash to use)?

Answer 1

The scheme you propose certainly leaks plaintext repetitions to an attacker since the same plaintext is always encrypted to the same ciphertext. You typically don't want this and it can be disastrous if the attacker knows some of the messages.

If you are absolutely sure that leaking repetitions is no problem in your case, you can use an authenticated encryption scheme with nonce-misuse resistance. Note that not all authenticated encryption schemes have this property. If you use a scheme with nonce-misuse resistance, you can even use the same nonce (say $0...0$) for all messages, so you don't need the hashing trick. If it is not, a hash function that is not collision resistant does not make it secure because an attacker can find different messages that hash to the same value, so you will end up using the same nonce for different messages. I don't know whether ChaCha20 Poly1305 together with a cryptographic hash function provides nonce-misuse resistance, but unless this is proven somewhere (or at least some other evidence is provided), you should not assume it.