3
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ $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) $\endgroup$
    – Aleph
    Mar 5, 2018 at 21:56
  • $\begingroup$ 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? $\endgroup$
    – Sap Chicken
    Mar 6, 2018 at 11:14
  • $\begingroup$ Where do you see that limit advertised in NIST SP 800-38D? $\endgroup$
    – Squeamish Ossifrage
    Mar 8, 2019 at 2:27
  • $\begingroup$ 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. $\endgroup$
    – Sap Chicken
    Mar 22, 2019 at 12:08
  • $\begingroup$ 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. $\endgroup$
    – Squeamish Ossifrage
    Apr 18, 2019 at 3:05

1 Answer 1

Reset to default
2
$\begingroup$

You are right that it is generally foolish to try to use AES-GCM for zetabytes of data under a single key. The standard ought to have clearer data volume limits.

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}$.

An alternative is to use crypto_secretbox_xsalsa20poly1305, which is a pseudorandom function family rather than a pseudorandom permutation family like AES, so the generic birthday distinguisher for permutation-based CTR doesn't apply. One could also imagine using a wider-block cipher like Threefish-256, in which case the birthday bound is unimaginably larger; it is a pity that AES was standardized with a meager 128-bit block.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Perhaps you should note that Salsa20 is a PRF, so you can continue using it safely right up until the point where the counter wraps. When using a PRP like AES on the other hand, going through a significant fraction of the counter leads to revealing a fraction of the codebook, which is not an issue for a PRF like Salsa20. $\endgroup$
    – forest ♦
    Apr 19, 2019 at 1:06
  • $\begingroup$ @forest So noted! $\endgroup$
    – Squeamish Ossifrage
    Apr 19, 2019 at 3:49
  • $\begingroup$ So it's an obvious and well known 'problem?', but we don't base any recommendations on it because we do not expect it to cause big issues. And yes, there are many authenticated encryption methods where this has less impact. $\endgroup$
    – Sap Chicken
    Apr 24, 2019 at 12:39
  • $\begingroup$ @SapChicken Pretty much. Read any paper on the security in the literature, like the AES-GCM paper (or a corrected paper for the case of non-96-bit nonces), and you'll find a quantitative statement of bounds on the adversary's advantage which can easily be translated into safe data volumes. But, sometimes this gets lost in translation to API documentation and standards documents. That's justifiable when the limits are unimaginably huge, but less so for, e.g., AES-GCM. $\endgroup$
    – Squeamish Ossifrage
    Apr 24, 2019 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.