Restricting number of plaintext blocks encrypted in AES-GCM and other counter modes

[jurajsomorovsky]

Counter values in Counter modes must not repeat when using the same block cipher key. Otherwise, the attacker can get some information about the underlying plaintext.
One scenario where counters can be reused is when encrypting large messages. For example, if one uses AES-GCM with 12 bytes long nonce values, the counter is bytes long and repeats after 2^{32} plaintext blocks.

Botan does not explicitly check the number of input plaintex blocks, and thus it is possible to reset the counter when using large inputs.
Would it not be a security improvement to add such a check to the increment function?
https://github.com/randombit/botan/blob/master/src/lib/stream/ctr/ctr.cpp#L107
(something like if the max number of blocks has been reached, throw an exception?)

AES-GCM spec explicitly states that the max number of plaintext blocks must be 2^{32} (see Section 2.1 in http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf)

[randombit]

This seems like a reasonable precaution to me.

It would be useful if the exception type thrown in these situation was of some specific (new) type used only for this purpose, so an application could actually catch it and know to rekey

[jurajsomorovsky]

Yes, this is a good idea.
Please just note that the number of plaintext blocks depends on the size of the counter. In AES-GCM 2^{32} blocks should be allowed when using the default 12 byte long nonces. If using, for example, 14 byte long nonces, the exception should be thrown after only 2^{16} blocks, etc.

[randombit]

@jurajsomorovsky Re the 2^16 block limit for 14 byte nonces, can you point me to the appropriate spot in the GCM spec for that? I thought with GCM if the nonce was not exactly 96 bits it was processed with GHASH instead of having 0x00000001 appended to it to produce the 128 bit field, but then afterwards treated like any other nonce for CTR encryption with the 32-bit wide increment.

(What you're saying makes sense for plain CTR mode, I think)

[jurajsomorovsky]

Oh, I am sorry, you are right, I missed that. GCM always uses a 32-bit wide increment.
This applies only to a plain CTR mode.

[jurajsomorovsky]

Now also discussed in wycheproof: C2SP/wycheproof#9

[randombit]

Would be good to get this check in before 2.0.0, I will take a look tomorrow.

[randombit]

GCM relies on CTR_BE to implement counter mode. CTR_BE already tracks the width of the counter, and GCM sets it correctly. The problem is CTR_BE just overflows the counter, instead of erroring after too many plaintext bytes have been processed. The current behavior causes keystream bytes to be repeated after the counter wraps.

It would be easy to replicate this in a test with CTR since we can set a 1 or 2 byte counter field. A specific test for GCM would also be useful, in case GCM is ever refactored to not rely on CTR, but testing GCM's handling requires processing a rather large input.

If the counter width is >= 64 bits, I would say we should not bother tracking the plaintext processed in CTR since there is no real possibility of overflow (even AES-NI is not that fast), and tracking/comparing such large plaintext sizes would require a BigInt or multi valued integer.

[SideChannel]

I think the matter is more complicated. First, nowadays a nonce length of 96 bit in GCM is highly recommended (see SOGIS agreed crypto algorithms or BSI TR). This is after a result of Iwata et al. 2012 where they show that the original security bounds where off by a 'small' factor 2^22 for |IV| != 96. But even if you only consider GCM with 96 bit IV, we have two further cases according to the standard. 8.2.1 Deterministic construction and 8.2.2 RGB based construction. The deterministic construction is nowadays recommended by SOGIS and BSI.

The problem with the suggested 2^32 is that this is only necessary, not sufficient (or that this is an upper bound, see for example the discussion in 8.3 Constraints on the number of invocation in SP800-38D). Even more problematic is the case of truncated short tags, then you have to re-key even faster, see Appendix C.

So, either make the bound after which an error is raised depending on the tag length , too. Or let the user set the bound on the max. number of invocations with a reasonable default.