What if an AES GCM nonce overflows and collides with the GHASH nonce (0^128)?

Question

When using AES in GCM mode, the GHASH function uses E(0^128) as the initial value for H, the authentication key. The IV, for the underlaying CTR mode, is initialized with:

[prefix (application nonce)] [initial_counter (4 byte counter)]

This initial counter starts at ...02, like explained here. I'm guessing this is done to prevent a collision with the GHASH function.

It's known that letting a nonce overflow is very, very bad, because repeating a nonce completely breaks GCM mode. But what if the prefix is all zeroes, and the counter overflows only to 0xffffff+1 (0^128)? You'd have one block that's xor'ed with the same value as the authentication key. Would this break GCM?

Answer 1

This is not allowed. An AES-GCM implementation that accepts messages longer than $2^{39} - 256$ bits, i.e. $2^{32} - 2$ blocks, is broken. A protocol that is defined in terms of AES-GCM on messages longer than $2^{39} - 256$ bits is nonsensical.

Protocols shouldn't be defined in terms of messages that long anyway because an adversary can waste the receiver's resources by sending an obscenely long message. If you allow terabyte-long messages, an adversary can waste a terabyte of memory before you realize it's a forgery and drop it on the floor.

Instead, you should break messages up into units no longer than you want to have to buffer in memory before you can decide to drop forgeries on the floor, like 1500 bytes for an IP packet, or 64 KB for a TCP segment, or maybe a megabyte if appropriate for your application.

---

But let's suppose you did have a broken protocol that violated the rules of AES-GCM and a broken implementation that let it happen. What happens if you do this—encrypt a message of ${>}2^{32} - 2$ blocks, with the counter truncated at 32 bits and wrapping around? Then:

1. An adversary who knows the first block of plaintext can solve for the GHASH authentication key and forge arbitrarily many additional messages.

2. An adversary who knows the third block of plaintext can decrypt block number $2^{32}$ of the plaintext.

If the counter carries into the nonce, rather than being truncated at 32 bits, then it is a slightly different known-plaintext attack—e.g., enabling decryption of the first block of the next message, assuming sequential message numbers for the nonce, rather than block $2^{32}$ of the same message.

In brief, don't do it!