6
$\begingroup$

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>=0 && 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.

Improve this question
$\endgroup$
4
$\begingroup$

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>=0; i--) {
        int t = inout[i] + carry;
        inout[i] = t & 0xff;
        carry = t >> 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)

Improve this answer
$\endgroup$
8
  • $\begingroup$ ... wow, interesting, I'll remember and check some of the implementations (bouncy!), but note that 12 is the recommended size of the IV for GCM, and that TLS does use that size if I'm not mistaken... $\endgroup$
    – Maarten Bodewes ♦
    Nov 3 '15 at 1:28
  • $\begingroup$ Thanks Poncho. "the counter doesn't have to be updated in constant time (because it's not secret)" - but if a protocol declares it to be secret, then it is secret. Or am I missing something obvious? $\endgroup$
    – user10496
    Nov 3 '15 at 1:28
  • $\begingroup$ I'm trying to do some calculations in my head at this very late hour, but wouldn't the chances of gaining enough information about the lower bits to guess H be absolutely abysmal? $\endgroup$
    – Maarten Bodewes ♦
    Nov 3 '15 at 1:39
  • $\begingroup$ @Poncho - I'm going to hold off on accepting because I'm interested in a treatment when the counter or iv is considered secret. But I like your counter example. I was not aware it was a problem. $\endgroup$
    – user10496
    Nov 3 '15 at 1:40
  • 1
    $\begingroup$ @MaartenBodewes: actually, it wouldn't strike me as that difficult; the GHASH computation would appear to be simplifiable into something like $a H^2 + C$, for known $a$ (which would be derived from the $IV$ values); I believe that knowledge of some bits of that (for various $a$) would allow you to recover $H^2$, which immediately gives you $H$. $\endgroup$
    – poncho
    Nov 3 '15 at 5:35
1
$\begingroup$

No, the counter does not have to be near constant time as the counter does not have to be secret.

Block ciphers are generally resistant against known plain text attacks. Generating a key stream doesn't change that. As you already indicated yourself, the IV does not need to be secret. This means that the counter values won't be secret either. That some protocols do keep it secret doesn't change this fact.

The GCM example of poncho is of course the odd one out. If modulo operations are being employed for calculations of an authentication tag you might want to consider strong countermeasures against timing attacks.

A simple increase could be hard to catch, even if it is over a value of 16 bytes. If an attacker manages to put it on a page boundary there might however be a very large penalty if the page needs to retrieved from RAM. So it is certainly not impossible to time the increase if it is handled byte-by-byte.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hmm, "time the increase" is probably not the right expression, but you get the drift. "Detect the time delta between carry and no carry"? $\endgroup$
    – Maarten Bodewes ♦
    Nov 3 '15 at 1:03
  • $\begingroup$ Thanks Maarteen. "... does not have to be near constant time as the counter does not have to be secret." - that's actually the pivot point. Under protocols like TLS, the counter or iv is secret. If you or I said it should be treated as public, then that's just bike sheding because they have already defined it as secret. That is, we are telling them how to run their project. $\endgroup$
    – user10496
    Nov 3 '15 at 1:21
  • $\begingroup$ My open questions are closer to: (1) does the counter or iv survive long enough in a particular state for the attacker to learn something about it; and (2) if the attacker learns something, then what is the resulting risk? If the attacker learns something about the counter or iv, then a protocol like TLS has violated its security design. $\endgroup$
    – user10496
    Nov 3 '15 at 1:23
  • $\begingroup$ There is a bit of an issue if the protocol treats something that should be public knowledge as secret. You should not depend on the value to be protected against side channel attacks in that case. Fortunately I don't think the security of TLS depends on the counter to be secret (and it uses a 12 byte IV for GCM, if I'm not mistaken). If unsure, it doesn't hurt to create a near time constant increment of course, as poncho showed, that isn't that hard. $\endgroup$
    – Maarten Bodewes ♦
    Nov 3 '15 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy