Breaking and Repairing GCM Security Proofs
In this paper, the authors study the security proofs of GCM (Galois/Counter Mode of Operation). They first point out that a lemma, which is related to the upper bound on the probability of a counter collision, is invalid. Both the original privacy and authenticity proofs by the designers are based on the lemma. They further show that the observation can be translated into a distinguishing attack that invalidates the main part of the privacy proof. It turns out that the original security proofs of GCM contain a flaw, and hence the claimed security bounds are not justified. A very natural question is then whether the proofs can be repaired. They give an affirmative answer to the question by presenting new security bounds, both for privacy and authenticity.