Making counter (CTR) mode robust against application state loss 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 &lt; 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:


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.
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.
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.
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.