Making counter (CTR) mode robust against application state loss

Question

Counter (CTR) mode, which is a block cipher mode of operation, has some desirable qualities (no padding, parallel encryption and decryption), but at the cost of failing badly when non-unique counter blocks (the nonce combined with the counter that acts as input to the block cipher) are used. I'd like to share my ideas about how the counter block can be made reasonably unique even when there is application state loss (reinstalls, etc.) that may otherwise cause non-unique nonces. If my ideas turn out to be reasonable maybe they'll be helpful to others.

According to appendix B of the NIST guidelines the counter block should either be a simple counter that is incremented without concern for message boundaries (the "first approach") or it should be a combination of a nonce that is changed with each message and a counter (the "second approach"). Either approach is sound, but what if the history of either the counter and or the nonce is lost due to an application reinstall or other reasons?

For a cipher with a 16 byte block size, such as AES, I'm proposing a counter block that has the following layout:

NNNNNN0CCCCCCCCC

The six "N"s are the nonce, followed by "0", a zero byte, and finally the nine "C"s for the counter bytes. Consider the following pseudo code for getting the nonce:

static last_nonce = 0
synchronized get_nonce()
    if (last_nonce == 0)
        last_nonce = get_last_nonce_from_db() // returns 0 on failure
    local nonce = last_nonce + 1
    local since_epoch = get_time_since_epoch_in_msecs()
    if (nonce < since_epoch)
        nonce = since_epoch
    last_nonce = nonce
    return nonce

For each new message the counter ("C") bytes are random. The increment function simply treats the entire 16 byte counter block as a 16 byte big endian integer where the right most bytes are incremented first. This is the way Java's CounterMode.increment() seems to do it. This approach should have the following properties:

1. In the normal case where the database is intact the nonce is always unique. In this case the "0" assures that it's possible for the message to be at least 256*10 - 256*9 blocks long before colliding with the next possible nonce.
2. If the database is reset (this could be restoring the database from a backup, reverting a snapshot on the database system, etc., combined with restarting the application) the system time should assure unique nonces.
3. If both the database is reset and the system time is reverted the nine random counter bytes should assure that the odds of two one block messages colliding (having a counter block in common) with the same nonce is only one in 256**9. As the messages get longer the odds get worse.

So it should work correctly in the normal case, but still behave reasonably in the degraded case.

I know this was long, but I wanted to explain it clearly. I also realize that some of this leverages existing concepts (I think getting a unique incrementing value the way I did with the system time is similar to what's often done for unique identifiers), but I'm interested in how these concepts can be applied to CTR.

Answer 1

Relying solely on randomization for the block counter is actually more likely to cause a nonce collision in case of a system time reset. This only gets worse as the message length increases. This is further exacerbated if the PRNG takes the system time as input, or does not have enough seed entropy. There is also no reason for the static 0 byte in the nonce.

How about a 48-bit time(in ms) counter, a 48-bit random value, and a 32-bit counter than increments from 0 for each block of the data?

This gives 9000 years of unique nonces each millisecond, a 280 trillion to 1 chance of a random collision in case of a system time reset, and a 64GB max data limit per nonce. This also makes the code for nonce incrementation more simple since it starts at 0 and is only a 32-bit unsigned integer.

Values above are approximations, but close and provide a reasonable example of the periods with those given bit sizes.

Answer 2

An even more robust approach could be to use something like SIV mode (RFC 5297) with a nonce composed of a timestamp and a random value (and possibly, if practical, a message number).

Basically, when encrypting a message, SIV mode first computes a MAC of the plaintext and the nonce (and any other associated data) using a modified form of CMAC, and then uses the output as the initial counter value for CTR mode encryption. After decryption, the MAC is recalculated and compared against the value included with the message to verify message integrity.

Thus, SIV mode, used in the manner suggested above, provides the following advantages:

• SIV is an authenticated encryption mode, and thus protects not just confidentiality, but also message integrity. This is generally a highly desirable feature.

• Because the nonce is fed through CMAC (along with the plaintext) to derive the IV, it can have any length you want. This frees you from having to worry about security tradeoffs between its component parts. Want to use a 64-bit timestamp, a 128-bit random number and a 32-bit message number? Go right ahead! You can also include things like sender and received IDs in the associated data to further reduce the chance of collision, and also to protect against "mirror" replay attacks.

• SIV is designed to be "maximally misuse-resistant", meaning that, even if the entire nonce value is accidentally reused, the IVs for two different messages will not be the same (except by chance, with negligible probability). Thus, the only additional information an adversary can learn due to nonce reuse is whether or not two messages using the same nonce are exactly identical. This is much safer than plain CTR mode, where nonce reuse is generally catastrophic.

All that said, SIV mode does have one major shortcoming: it is an intrinsically serial two-pass encryption mode, meaning that the plaintext must be processed twice, and the second (encryption) pass cannot begin before the first (MAC) pass is done. Thus, SIV is generally not as fast or parallelizable as plain CTR mode, or even some other AE modes like OCB, GCM or Poly1305. It is also not an "on-line" mode, i.e. it cannot be used to encrypt a long data stream at the same time as it is being transmitted, although this may, to some extent, be worked around by splitting the stream into reasonable-sized segments (which is a good idea for AE modes anyway, since it allows authentication of partial streams).