CTR mode nonce with aggressive key rotation policy

Question

I'm writing a small encryption library which will be required to use the shortest possible amount of overhead for describing ciphertexts. I want to use CTR mode with a 6-byte random nonce.

Normally I would never disregard best practices like this, but I think in this context it is acceptable because the encryption keys will be rotated frequently. As I understand it, the weakness in CTR mode occurs when the same nonce AND key are used to encrypt. If the key is rotated, say, every 2 months, it's unlikely that there would ever be a nonce collision.

This is a heterodox use of CTR mode - feel free to savage my idea if it is flawed. Thanks for your help.

Answer 1

A 6-byte nonce can expect to receive a collision 0.01% of the time after around 240,000 nonce generations (based on a birthday attack). After 100 such rotations (a little under 17 years, based on your 2-month rotation policy), that comes out to a likelihood of just under 1% of experiencing a collision. On the surface, to me that seems like a reasonable margin of security.

If practical, you may also want to consider simply using an autoincrementing counter for your IV. Allow the first byte to be a machine identifier, and then use a mutex to synchronize access to the remaining five bytes. Whenever you need an IV, lock the mutex, read the current value as the IV, increment it by one, save it, and release the mutex. This allows you to encrypt over one trillion messages with a single key before the nonce rolls over, and has zero possibility of collision as long as you detect IV wraparound.

Answer 2

The "shortest possible amount of overhead for describing ciphertexts" is achieved by

encrypt(key,nonce,plaintext) =
prefixfree(length(nonce)) ||
FPE ( length(nonce)+length(plaintext) , PRF(key,length(nonce)+length(plaintext)) , nonce || plaintext)

The basic idea is to use independently keyed block ciphers for each possible plaintext length, and include the nonce in what the block ciphers are evaluated on. Since one can't quite independently key the block ciphers, one keys them with the output of a pseudo-random function (such as HMAC) evaluated at their block size. The simple way to include the nonce in what the block ciphers are evaluated on is to concatenate the nonce with the plaintext, so that is done. Finally, to allow the keyholders to extract the plaintext, one puts a prefix-free encoding of the nonce's length at the beginning of the ciphertext.

If you would be using fixed-length nonces, or more generally, if keyholders can efficiently determine length(nonce) from length(nonce)+length(plaintext), then you can skip the prefixfree(length(nonce)) part, since length(nonce)+length(plaintext) would be the length of the ciphertext.

These ciphertexts will always reveal length(plaintext). Unless you skip the first part, these ciphertexts will reveal length(nonce). If a nonce is reused with the same plaintext (and key), then that will be obvious because the ciphertexts will be equal. However, other than the previous two sentences, someone who does not have the key won't know whether or not a nonce was reused.

There another important point. Neither yours nor Stephen's nor my suggestion provide authenticity. (Doing so would require longer ciphertexts.)