Using AES-256-GCM, is your security only 128 bits when solely relying on the MAC?

Question

Since the maximum authentication tag (MAC) size of AES-256-GCM is 16 bytes,

And given that in one implementation, that breaking the MAC would break the security (ex. when a boolean 'decrypted' is used to either deny or allow access),

Would using an additional MAC within the cipherText be a good idea or is this over-engineering?

Answer 1

There's a difference of nature between the $k$-bit bit security a $k$-bit key gives, and the $t$-bit security a $t$-bit authentication tag gives.

In the case of a key, adversaries can try keys by brute force, and after trying $2^n$ keys the security is reduced from $k$ to $k-n$-bit, that is there is probability $1/2^{\approx\max(k-n,0)}$ that the key search was successful. $n$ is limited only by the computing power of the adversary. $n=96$ may be realistic (see this) if the stakes are high.

In the case of a tag, adversaries can try tags, and after try $2^n$ they have probability $1/2^{\approx\max(t-n,0)}$ the right tag was reached. But they can only verify it by interacting with an entity (device, service). This severely limits $n$. e.g. with a 1 Gbit/s link and 128 bits per try, we are at $n<48$ after a year.

There are a few other differences:

	key	tag
limit factor for brute force attack	computing power	verification oracle speed
realistic $n$ for $2^n$ values tested	72-96	16-48
hypothetical CRQC could further help	yes	no
attack possible in the future from captured transcripts	yes	no
attack recovers key (total break)	yes	no

For these reasons, save for an attack better than brute force (e.g. platform compromise, side channel, IV reuse, cryptanalysis, Partitioning Oracle Attack if applicable [see this]…), a 128-bit tag seems fine in every application, when a 128-bit symmetric key arguably is closer to problematic for high-stakes security when long-term confidentiality matters.

Would using an additional MAC within the cipherText be a good idea or is this over-engineering?

If the only concern is the size of the tag, that would be over engineering. If on the other hand it's used a different key for the MAC, or/and it it there to mitigate some real threat beyond guess of the tag, it may add a barrier to exploitation.