Say we want to use AES (or any other secure 128 bit block cipher) with GCM and a tag size of 96 or 128 bits. I'm assuming an AES key size of 128 bits and an IV size of 96 bits (the default).

NIST SP 800-SP 38D, Appendix C: "Requirements and Guidelines for Using Short Tags" specifies the amount of AAD and plaintext together with the number of invocations for 32 and 64 bit short tags, but not for the larger tag sizes. NIST specifies these properties using a table with the following columns set off to each other:

  • Maximum Combined Length of the Ciphertext and AAD In a Single Packet (bytes)
  • Maximum Invocations of the Authenticated Decryption Function

Here are the constraints for a 64 bit tag size:

64 bit constraints

Furthermore, the paper "The Galois/Counter Mode of Operation (GCM)" contains the following equation right at the end (chapter 7: "Security"):

The results of this analysis show that GCM is secure whenever the block cipher is indistinguishable from random and the condition $q^2l^22^{−142} + q^2l^32^{−147} \ll 1$ is met, where $q$ is the number of invocations of the authentication encryption operation and $l$ is the maximum number of bits in the fields $P$, $A$, and $IV$.

The Wikipedia page on GCM also has a lot of information and references (but not this information, obviously).

I'm not sure if any subsequent analysis has put a dent into the numbers of NIST or the paper though.

  • $\begingroup$ I've tried to fill in some values into the function of the GCM paper (using WolframAlpha) but the result did not make much sense to me. The algorithm did seem to be picked up fine, but the result for the maximum number of invocations was way too small. $\endgroup$ – Maarten Bodewes Aug 9 '15 at 21:47
  • $\begingroup$ I think the equation you cite is only applicable to 128-bit tag lengths and yields something like the above table assuming $P$ is the plaintext and $A$ is the associated data. I guess the tag length is somehow embedded into the "magic constants". $\endgroup$ – SEJPM Aug 31 '15 at 16:55
  • $\begingroup$ I've just tried to reproduce the above table. The right side is the solution to the exact stated equation for $2^{-38}$ as approximation for $\ll1$ $\endgroup$ – SEJPM Aug 31 '15 at 17:05
  • $\begingroup$ Sorry for the spam. But I just found something that may interest you: The (somewhat) original GCM paper including the security proof (although it may be the broken one) and they give a more generic equation there that may include the answer. $\endgroup$ – SEJPM Aug 31 '15 at 17:14
  • $\begingroup$ This is the kind of spam I'm looking for, although I haven't extracted the answer yet :) $\endgroup$ – Maarten Bodewes Sep 1 '15 at 7:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.