# Why is counter mode encryption with a 16-byte cipher block not broken?

We determine a system IND-CPA secure when an adversary has a negligible advantage after any feasible amount of queries.

AES256-GCM uses a 128bit block cipher.

We know that the distinguishability from random of counter mode encryption follows the birthday bound.

If we encrypt a stream of static data, with counter mode encryption we will never see a repeated cipher text block.

A purely random oracle will have repeats. The probability of this happening follows the birthday bound, eg after $2^{64}$ blocks we expect a repeat with probability of about a half. This would give an attacker an advantage of one half with $2^{64}$ queries, which is completely insecure.

If we assume a negligible advantage of $10^{-9}$, we reach that after about $2^{54}$ blocks. This means we should limit the maximum amount of blocks encrypted under a single key to $2^{54}$ blocks right?

This is way less than the advertised $2^{32}$ invocations of $2^{32}$ block chunks in NIST SP 800-38D.

Why don’t we see any recommendations of limiting the use of AES256-GCM dependent on its security parameter due to this attack on the counter mode encryption?

• $2^{32}$ queries of $2^{32}$ blocks is not the same as $2^{64}$ block queries (since the IV isn't fixed). I think you are working in the abused IV IND-CPA setting? (as opposed to NIST SP 800-38D) – Aleph Mar 5 '18 at 21:56
• The IV (the whole 128 bits, no matter how you configure it) should never be reused in ctr encryption. NIST SP 800-38D advises to use a 32 bit counter for every new message, to allow for $2^{32}$ block messages. It also states that the invocations should be limited to $2^{32}$ which might result in $2^{64}$ block queries, each with a unique counter value. If an adversary uses all these $2^{64}$ block queries to encrypt static data eg, only 0's, he has advantage 0.5 in the IND-CPA game, which is certainly non negligible? – Sap Chicken Mar 6 '18 at 11:14
• Where do you see that limit advertised in NIST SP 800-38D? – Squeamish Ossifrage Mar 8 at 2:27
• The number of invocations in "8.3 Constraints on the Number of Invocations" on page 21, the limit on the message length is shown in chapter "5.2.1.1 Input Data" on page 8. – Sap Chicken Mar 22 at 12:08
• The limit on p. 21 is only for applications using nonces of lengths other than 96 bits. The limit on p. 8 is an artifact of the 32-bit block counter with a 96-bit IV: if you encrypted a longer message, the block counter would exceed 32 bits and you would need a way to handle that overflow. – Squeamish Ossifrage Apr 18 at 3:05

For a long time, the folklore understanding was that a non-collision in a CTR stream doesn't really leak all that much…until sweet32 demonstrated that it actually can be a real problem. Still, what is feasible for a 64-bit cipher with online cost $${\sim}2^{32}$$ may be considerably harder for a 128-bit cipher with online cost $${\sim}2^{64}$$.