Breaking and Repairing GCM Security Proofs

Tetsu Iwata, Keisuke Ohashi, and Kazuhiko Minematsu

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.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. A preliminary version appears in the proceedings of CRYPTO 2012. This is the full version.
Keywords
GCMcounter-exampledistinguishing attackproof of security
Contact author(s)
iwata @ cse nagoya-u ac jp
History
Short URL
https://ia.cr/2012/438

CC BY

BibTeX

@misc{cryptoeprint:2012/438,
author = {Tetsu Iwata and Keisuke Ohashi and Kazuhiko Minematsu},
title = {Breaking and Repairing GCM Security Proofs},
howpublished = {Cryptology ePrint Archive, Paper 2012/438},
year = {2012},
note = {\url{https://eprint.iacr.org/2012/438}},
url = {https://eprint.iacr.org/2012/438}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.