Should Increment functions be near-constant time? When operating a block cipher in CTR or GCM mode, should the function used to increment the counter or initialization vector be near-constant time? Here, I'm wondering about the "addition with carry" that often occurs. For example:

void IncrementCounterByOne(byte *inout, unsigned int size)
{
    for (int i=int(size-1), carry=1; i&gt;=0 &amp;&amp; carry; i--)
        carry = !++inout[i];
}


In the function above, processing terminates when carry is 0.

While not readily apparent, some protocols treat the counter or initialization vector as secret or private data (like TLS). That appears to beg a near-constant time function to avoid leaking information.

I realize there will likely be CPU micro-code variations, and there's probably nothing that can be done about it. (Corrections, please).



A related question is, should the Increment function be near-constant time when it increments the seed to an ANSI X9.17 or X9.31 generator.



And a question I am not asking: should a counter or iv be considered public or secret information. Some projects, like TLS, have already made that decision.
Actually, Maarten isn't quite correct; in most cases, the counter doesn't have to be updated in constant time (because it's not secret); however in one case it does: GCM with an IV size that's not 12 bytes.

The reason the counter needs to be secret in this case is not because how it is used, but how it is generated.  It is initialized to $GHASH_H(IV||0^{s+64}||len(IV))$; if the attacker can learn the lower bits of this value (based on whether or not an internal carry has occurred), he can gain information on the internal value of $H$, and if we can fully recover that, then he can forge.

In this (admitedly obscure) case, it would be wise to fully disguise whether the carry occurred.  Here is some code that should be safe on most processors to do that:

void IncrementCounterByOne(byte *inout, unsigned int size)
{
    for (int i=int(size-1), carry=1; i&gt;=0; i--) {
        int t = inout[i] + carry;
        inout[i] = t &amp; 0xff;
        carry = t &gt;&gt; 8;
    }
}


It runs slower than your code (because it reads and writes every byte); however it avoids data dependent operations (on most CPUs and compilers)