Breaking and Repairing GCM
Security Proofs
Tetsu Iwata (
Keisuke
Ohashi (
Kazuhiko
Minematsu (NEC Corporation,
Abstract:
In this paper, we study the security proofs of GCM (Galois/Counter Mode of
Operation). We 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. We 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. We give an affirmative answer to the
question by presenting new security bounds, both for privacy and
authenticity. As a result, although the security bounds are larger than what
were previously claimed, GCM maintains its provable security. We also show
that, when the nonce length is restricted to 96 bits, GCM has better security
bounds than a general case of variable length nonces.