What is a safe maximum message size limit when encrypting files to disk with AES-GCM before the need to re-generate the key or NONCE

Question

The general limits from the NIST recommendation are as follows:

Maximum Encrypted Plaintext Size ≤ 2³⁹ - 256 bits;
Maximum Processed Additional Authenticated Data ≤ 2⁶⁴ - 1 bits;

This stack overflow answer (https://crypto.stackexchange.com/a/20340/44337) hints that the maximum invocation of 2³⁹ - 256 bits of encrypted plaintext is too big and “you should be advised to stay well away from those limits.” In this case what kind of limit makes sense where I can optimize the use of a generated key, but also not decrease the security of the cipher text? Is reaching the maximum invocations of the encryption operation of 2³² operations considered too dangerous? Should I go ahead and limit the amount of invocations to 2³¹? Or may be half that to 2¹⁶? I have the ability to generate new keys at any time for any file. So the question is what is a good trade-off between maximum key use and security. Obviously I can’t process more than 2³⁹ - 256 bits with the same key.

Some of the comments on stack exchange mention the maximum number of 96 bit NONCEs to use with the same key is 2^28.9 which will keep the security above 2⁶⁴ (Is the length limit of AES-GCM per key or per (key, nonce) pair?). I am strictly trying to figure out what the maximum safe size of the processed message with the same key/NONCE is before the need to re-generate the key or change the NONCE.

Another stack exchange question deals directly with the size of the encrypted message but does not give a recommendation of the safe maximum size (Plain text size limits for AES-GCM mode just 64GB?). Instead it shows that the security depends on the tag and the number of encrypted message blocks. The relationship is n - k, where n is the tag length and k is the number of encrypted blocks. So for a 96 bit tag processing a message of size 2³² blocks, this gives us 96 - 32 = 64 or 2⁶⁴ security. Which is pretty low. Other commenters say to chunk the encryption at around 10GB per chunk. But what kind of security are we achieving then?

It seems that AES-GCM is not well suited to encrypt large files unless more complexity is added in chunking the files appropriately at some safe limits such as 1 GB or 10 GB etc. May be a better solution would be to use ChaCha20/Poly1305, but that is out of the scope of this question. I want to see what the current limits of AES-GCM are before I decide to change the cipher.

Answer 1

Security analysis of AES-GCM for maximum key use

Note: I am not a cryptographer. As such there are probably mistakes in my analysis. Please help me fix my mistakes and built on top of this answer so we can collectively arrive at the correct conclusion.

AES-GCM Setup

• Key: 256 bit
• IV 96 bit (deterministic construction)
• Tag: 128 bit

Analysis

The internal implementation of GCM is using CTR mode of operation with a 32 bit integer for a counter which sets a hard limit on the number of invocations of the encryption operation to 2³² blocks. The first two counter values are reserved so this gives us 2³² - 2 number of invocations. This corresponds to the first limit set by the NIST standard to 2³⁹ - 256 maximum bits that can be processed with a single key/IV pair.

The IV is recommended to be 96 bits and as such I’ll use this in my analysis. In the general deterministic construction the IV is made of a 64 bit (invocation field) counter and a fixed 32 bit field. The 32 bit field is not important in our discussion. Wrapping 64 bit counter will take 2⁶⁴ operations which far exceeds the actual maximum of the underlying CTR mode of operation: 2³² - 2. Therefore the minimum of the two is the allowed usage of the GCM mode: 2³² - 2.

The final security parameter for the GCM mode is the authentication tag length. I assume a 128 bit tag length as it is the recommended by most. Theoretically, all secure hash functions have at least one weakness defined from the Birthday Paradox. It states that in order to get 50% chance of collision you need to do half the hash output length number of operations. For our 128 bit hash this gives us a security of 2⁶⁴ for a 50% chance of collision. This is in contradiction to our desired security of 2¹²⁸, but it is what we have to deal with. Since the number of hash operations is still limited by the actual internal CTR mode of operation to 2³² - 2, the authentication security is 2⁹⁶ - 2 which is quite high for the 128 bit tag. This is outside of the reach of any attacker at the moment.

Niels Ferguson's message-forgery attack on GCM provides further limits on the authentication tag. It is primarily targeted to the truncated version of the tag, but we’ll look at the full 128 bit tag. The attack uses about 2^t (n-bit) blocks to succeed where t is the tag length. Here is the explanation of the attack from Rogaway

The adversary asks for the MAC of a single message having 2^{(t / 2 + 1)} blocks and then forges after about 2^{(t / 2)} expected tries, on messages again of 2^{(t / 2 + 1)} blocks. Focusing on the case of 32-bit tags, for example, the attack begins by asking for the MAC of a single message of 2¹⁷ blocks. After that, it needs about 2¹⁶ verification messages, again of 2¹⁷ blocks each, until the first forgery is expected.

This is not a concern for 128 bit authentication tag, because in order to succeed you need the tag of a message of size 2^{(128 / 2)} 128 bit blocks to begin with. This is impossible to craft as the internal CTR limit is 2³² - 2, 128 bit blocks.

However, the theoretical investigation of hashes deviates from the practical realization of the underlying GHASH algorithm. It has problems that have been identified which generally reduce its security somewhat. As such we are well advised to stay away of the theoretical birthday bound of 2⁶⁴ operations for the same key H. But since we have an upper limit of only 2³² operations from the underlying CTR construct, this raises our security parameter from 2⁶⁴ to 128 - 32 = 96 or 2⁹⁶ for the same key H.

Conclusion

After considering all of the above, it appears that the limiting security factor is the internal CTR mode of operation for AES-CTR which is processing at most 2³² - 2 blocks. If we process that number of blocks we should still achieve high security margins and no further data chunking should be necessary. Therefore it is safe to utilize the full range of AES-GCM encryption and process 2³⁹ - 256 bits of plaintext data with the same key when using a 128 bit tag and a 96 bit IV.

Update

I have summarized my research on how to use AES-GCM correctly in a blog post.