Collision Attacks on Galois/Counter Mode (GCM)

[John Preuß Mattsson]

Hi,

As commented by (Kazuhiko Minematsu, if I remember correctly) during my presentation at the Accordion workshop, GCM with random IVs can provide more than 97 - log_2 n bits of security if longer than 96-bit IV are used. This is correct, I had the wrong mental picture of GCM IV hashing.
https://csrc.nist.gov/csrc/media/Presentations/2024/comments-on-nist-requirements-for-accordion-cm/images-media/sess-2-mattsson-acm-workshop-2024.pdf
https://www.nist.gov/video/nist-workshop-requirements-accordion-cipher-mode-day-1

After the workshop I spent some time calculating collision attack complexities for all IV constructions and IV lengths approved by NIST SP 800-38D when encrypting multiple plaintexts with the same key. Nonce hiding forces the attacker to change from ciphertext-only to known-plaintext but does otherwise not affect the complexity. Collision attacks are much serious than distinguishing attack using the lack of collisions. I hope NIST will take the findings into consideration when revising SP 800-38D and SP 800-38C. Comments on the pre-print is very welcome.

https://eprint.iacr.org/2024/1111.pdf

In an earlier comment to NIST, Ericsson wrote: "The update to 800-38D should allow for IV to be constructed as a 96-bit fixed random number XORed with the invocation field."
As an answer, NIST proposed to "clarify that the construction of initialization vectors (IVs) for GCM in the Transport Layer Security (TLS) 1.3 protocol is approved"
Reading 800-38D in detail, I agree that both the deterministic and RGB-based constructions seem compatible with TLS 1.3. A clarification would still be good, and maybe even a recommendation to put as much randomness as possible in the IV.
https://csrc.nist.gov/csrc/media/Projects/crypto-publication-review-project/documents/initial-comments/sp800-38d-initial-public-comments-2021.pdf
https://csrc.nist.gov/News/2024/nist-to-revise-sp-80038d-gcm-and-gmac-modes

Cheers,
John Preuß Mattsson
Expert Cryptographic Algorithms and Security Protocol, Ericsson Research