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