Paper 2015/214

GCM Security Bounds Reconsidered

Yuichi Niwa, Keisuke Ohashi, Kazuhiko Minematsu, and Tetsu Iwata

Abstract

A constant of 222 appears in the security bounds of the Galois/Counter Mode of Operation, GCM. In this paper, we first develop an algorithm to generate nonces that have a high counter-collision probability. We show concrete examples of nonces with the counter-collision probability of about 220.75/2128. This shows that the constant in the security bounds, 222, cannot be made smaller than 219.74 if the proof relies on ``the sum bound.'' We next show that it is possible to avoid using the sum bound, leading to improved security bounds of GCM. One of our improvements shows that the constant of 222 can be reduced to 32.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2015
Keywords
GCMprovable securitycounter-collisionthe sum bound.
Contact author(s)
iwata @ cse nagoya-u ac jp
History
2015-03-08: received
Short URL
https://ia.cr/2015/214
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/214,
      author = {Yuichi Niwa and Keisuke Ohashi and Kazuhiko Minematsu and Tetsu Iwata},
      title = {{GCM} Security Bounds Reconsidered},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/214},
      year = {2015},
      url = {https://eprint.iacr.org/2015/214}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.