New Security Evaluation Results of GCM, an International Standard Authenticated Encryption Algorithm- A Flaw Is Identified in the Original Security Proofs; the Proofs Are Then Successfully Repaired -

Abstract

• We have identified a flaw in security proofs of GCM, an international standard authenticated encryption algorithm.
• We have succeeded in showing that the flaw can be removed and the security proofs can be repaired without changing the specification of GCM.

Background

GCM (Galois/Counter Mode) is a cryptographic technique called an authenticated encryption algorithm that simultaneously protects privacy and authenticity of digital data. It was designed by David A. McGrew and John Viega in 2004. Since GCM is computationally efficient and its security has been considered to be guaranteed by mathematical proofs, it has been adopted by a number of standardization bodies including NIST (*3), IEEE (*4), and ISO/IEC (*5). It is used by NSA (*6) and is widely used in our daily life, for example, to protect data on the Internet.
The security of GCM is guaranteed by the mathematical proofs showing that, for attacks with practical complexities, their success probabilities are lower than a specific threshold. Development of attacks against GCM is an important research topic to understand and verify its security. Several attacks have been proposed and the success probabilities of these attacks are not higher than the threshold. Therefore, these attacks do not violate the mathematical security proofs of GCM, and it has been considered that the security of GCM is supported by these sound mathematical proofs.

Results

GCM uses a symmetric key cryptographic primitive called a block cipher as the underlying component, and we first consider the idealized version of GCM in which the block cipher has no weaknesses. Against this idealized version of GCM, we have succeeded in developing a concrete attack procedure that violates a part of the security proofs of GCM. If the proofs are correct, the success probability of the attack is supposed to be at most 80 × 2-128. However, the success probability is higher and is at least 94 × 2-128. Therefore, this attack shows that there is a flaw in the security proofs of GCM.
The success probability of the attack is insignificantly low (94 × 2-128 is approximately 2.76 × 10-37) and its practical implication is very limited, and hence our attack remains a theoretical one. Besides, the attack does not violate the security proofs if a real (non-idealized) block cipher is used, implying that it violates only a part of the security claims by the designers. Furthermore, the attack does not work if the length of input data called an initial vector is restricted to 96 bits, and this is actually required or recommended by many standards for efficiency reasons. On the other hand, the proposed attack does invalidate the theoretical basis of the proofs, indicating that improving the attack to become a practical threat may not be impossible. It also leaves an open question of whether the security of GCM can ever be mathematically proved.
For these issues, we have succeeded in showing that the flaw can be removed and the security proofs can be repaired without changing the specification of GCM. This indicates that, for GCM, success probabilities of attacks with practical complexities cannot be higher than a specific threshold if the underlying block cipher is secure. Furthermore, we have shown that if the length of the initial vector is restricted to 96 bits, then GCM has a lower threshold (and hence better security) than a general case.

Implication and Future Prospects

GCM is an authenticated encryption algorithm recommended by NIST and adopted by many other standardization bodies. Our theoretical attack is the first one against the widely standardized cryptographic technique GCM in the sense that it violates a part of the security claims by the designers.
On the other hand, we have succeeded in mathematically proving the security of GCM. In contrast to other cryptographic techniques that have no such proofs, this result shows that as long as GCM is appropriately implemented its use does not cause practical security concerns. However, since the threshold of success probabilities of attacks is higher than the previously believed value, we recommend reevaluating risks of this fact or restricting the length of the initial vector to 96 bits.
Our results indicate that there is room for improving the design of GCM. We anticipate development of new highly secure authenticated encryption algorithms based on the results and insights of this work.

Glossary

(*1) GCM: Galois/Counter Mode. A cryptographic technique called an authenticated encryption algorithm that simultaneously protects privacy and authenticity of digital data.

(*2) Block cipher: A cryptographic primitive that encrypts a block of data. AES (Advanced Encryption Standard) is an example of a block cipher used in GCM.

(*3) NIST: National Institute of Standards and Technology

(*4) IEEE: Institute of Electrical and Electronics Engineers

(*5) ISO/IEC: International Organization for Standardization/International
Electrotechnical Commission

(*6) NSA: National Security Agency

Publication

Conference: CRYPTO 2012 (http://www.iacr.org/conferences/crypto2012/)
Title: Breaking and Repairing GCM Security Proofs
Authors: Tetsu Iwata (Nagoya University), Keisuke Ohashi (Nagoya University), and Kazuhiko Minematsu (NEC Corporation)

The work by Tetsu Iwata was supported in part by MEXT KAKENHI, Grant-in-Aid for Young Scientists (A), 22680001.

Nagoya University Technical Contacts (Japan)

Nagoya University, Associate Professor
Tetsu Iwata
E-Mail: iwata@cse.nagoya-u.ac.jp

Nagoya University Press Contacts (Japan)

Nagoya University
Toshihiro Tange
Tel: +81-52-789-2016
E-Mail: tange.toshihiro@post.jimu.nagoya-u.ac.jp

NEC Press Contacts (Japan)

NEC Corporation
Seiichiro Toda
Tel: +81-3-3798-6511
E-Mail: s-toda@cj.jp.nec.com