Discussion
Ask a question about 'Galois/Counter Mode'
Start a new discussion about 'Galois/Counter Mode'
Answer questions from other users

Galois/Counter Mode is a
mode of operationIn cryptography, modes of operation is the procedure of enabling the repeated and secure use of a block cipher under a single key.A block cipher by itself allows encryption only of a single data block of the cipher's block length. When targeting a variablelength message, the data must first be...
for symmetric key cryptographic
block cipherIn cryptography, a block cipher is a symmetric key cipher operating on fixedlength groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128bit block of plaintext as input, and output a corresponding 128bit block of ciphertext...
s that has been widely adopted because of its efficiency and performance. GCM throughput rates for state of the art, high speed communication channels can be achieved with reasonable hardware resources .
It is an
authenticated encryptionAuthenticated Encryption is a block cipher mode of operation which simultaneously provides confidentiality, integrity and authenticity assurances on the data. It became readily apparent that securely compositing a confidentiality mode with an authentication mode could be error prone and difficult...
algorithm designed to provide both data authenticity (integrity) and confidentiality. GCM mode is defined for block ciphers with a block size of 128 bits.
GMAC is an authenticationonly variant of the GCM which can be used as an incremental message authentication code. Both GCM and GMAC can accept initialization vectors of arbitrary length.
Different block cipher modes of operation can have significantly different performance and efficiency characteristics, even when used with the same block cipher. GCM can take full advantage of parallel processing, and an implementation can make efficient use of an
instruction pipelineAn instruction pipeline is a technique used in the design of computers and other digital electronic devices to increase their instruction throughput ....
or a hadware pipeline. In contrast, the Cipher block chaining (CBC) mode of operation incurs significant pipeline stalls that hamper its efficiency and performance.
Encryption and authentication
As the name suggests, GCM mode combines the wellknown counter mode of encryption with the new Galois mode of authentication. The key feature is that the Galois field multiplication used for authentication can be easily computed in parallel thus permitting higher throughput than the authentication algorithms that use chaining modes, like CBC. The GF(2
^{128) field used is defined by the polynomial
The GHASH function is defined by
where H is a string of 128 zeros encrypted using the block cipherBlock cipherIn cryptography, a block cipher is a symmetric key cipher operating on fixedlength groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128bit block of plaintext as input, and output a corresponding 128bit block of ciphertext..., A is data which is only authenticated (not encrypted), C is the ciphertextCiphertextIn cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher..., m is the number of 128 bit blocks in A, n is the number of 128 bit blocks in C (the final blocks of A and C need not be exactly 128 bits), and the variable Xi for i = 0, ..., m + n + 1 is defined as
where v is the bit length of the final block of A, u is the bit length of the final block of C, and denotes concatenation of bit strings.
GCM mode was designed by John Viega and David A. McGrew as an improvement to Carter–Wegman Counter CWC modeCWC modeIn cryptography, CWC Mode is an AEAD block cipher mode of operation that provides both encryption and builtin message integrity, similar to CCM and OCB modes. Designed by Tadayoshi Kohno, John Viega and Doug Whiting, NIST is CWC mode for standardization....
On November 26, 2007 NIST announced the release of NIST Special Publication 80038D Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC making GCM and GMAC official standards.
Use
GCM mode is used in the IEEE 802.1AEIEEE 802.1AE802.1AE is the IEEE MAC Security standard which defines connectionless data confidentiality and integrity for media access independent protocols... (MACsec) Ethernet security, ANSI (INCITSINCITSThe InterNational Committee for Information Technology Standards, or INCITS , is an ANSIaccredited forum of IT developers. It was formerly known as the X3 and NCITS....) Fibre ChannelFibre ChannelFibre Channel, or FC, is a gigabitspeed network technology primarily used for storage networking. Fibre Channel is standardized in the T11 Technical Committee of the InterNational Committee for Information Technology Standards , an American National Standards Institute –accredited standards... Security Protocols (FCSP), IEEE P1619IEEE P1619IEEE P1619 is an Institute of Electrical and Electronics Engineers standardization project for encryption of stored data, but more generically refers to the work of the IEEE P1619 Security in Storage Working Group , which includes a family of standards for protection of stored data and for the....1 tape storage, IETFInternet Engineering Task ForceThe Internet Engineering Task Force develops and promotes Internet standards, cooperating closely with the W3C and ISO/IEC standards bodies and dealing in particular with standards of the TCP/IP and Internet protocol suite... IPsecIPsecInternet Protocol Security is a protocol suite for securing Internet Protocol communications by authenticating and encrypting each IP packet of a communication session... standards, SSHSSH In science and technology :* Saffir–Simpson Hurricane Scale* Sea surface height, the topography of the ocean surface* Secure Shell, a network protocol for remote administration of Unix computers* Social sciences and humanities, a broad field of research... and TLS/SSLTransport Layer SecurityTransport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet... . AESGCM is included into the NSA Suite B Cryptography.
Performance
GCM is ideal for protecting packetized data, because it has minimum latency and minimum operation overhead.
GCM requires one block cipher operation and one 128bit multiplication in the Galois field per each block (128 bit) of encrypted and authenticated data. The block cipher operations are easily pipelined or parallelized; the multiplication operations are easily pipelined, and can be parallelized with some modest effort (either by parallelizing the actual operation, or by adapting Horner's method as described in the original NIST submission, or both).
Intel has added the PCLMULQDQ instruction, highlighting its use for GCM http://software.intel.com/enus/articles/intelcarrylessmultiplicationinstructionanditsusageforcomputingthegcmmode. This instruction enables fast multiplication over GF(2^n), and can be used with any field representation.
Impressive performance results have been published for GCM on a number of platforms. Käsper and Schwabe described a "Faster and TimingAttack Resistant AESGCM"
that achieves 10.68 cycles per byte AESGCM authenticated encryption on 64bit Intel processors. Dai et al report 3.5 cycles per byte for the same algorithm when using Intel's AESNI and PCLMULQDQ instructions .
When both authentication and encryption need to be performed on a message, a software implementation can achieve speed gains by overlapping the execution of those operations. Performance is increased by exploiting instruction level parallelism by interleaving operations. This process is called function stitching , and while in principle it can be applied to any combination of cryptographic algorithms, GCM is especially suitable. Manley and Gregg show the ease of optimizing when using functionstitching with GCM, and present a program generator that takes an annotated C version a cryptographic algorithm and generates code that runs well on the target processor.
Patents
According to the authors' statement, GCM is unencumbered by patents.
Security
GCM has been proven secure in the concrete security model . It is secure when it is used with a block cipher mode of operation that is indistinguishable from a random permutation; however security depends on choosing a unique initialization vectorInitialization vectorIn cryptography, an initialization vector is a fixedsize input to a cryptographic primitive that is typically required to be random or pseudorandom... for every encryption performed with the same key (see stream cipher attackStream cipher attackStream ciphers, where plaintext bits are combined with a cipher bit stream by an exclusiveor operation , can be very secure if used properly. However they are vulnerable to attack if certain precautions are not followed:*keys must never be used twice...). NIST Special Publication 80038D includes guidelines for initialization vector selection.
The authentication strength depends on the length of the authentication tag, as with all symmetric message authentication codes. However, the use of shorter authentication tags with GCM is discouraged. The bitlength of the tag, denoted t, is a security parameter. In general, t may be any one of the following five values: 128, 120, 112, 104, or 96. For certain applications, t may be 64 or 32, but the use of these two tag lengths constrains the length of the input data and the lifetime of the key. Appendix C in NIST SP 80038D provides guidance for these constraints (for example, if t = 32 and the maximal packet size is 210 bytes, then the authentication decryption function should be invoked no more than 211 times; if t = 64 and the maximal packet size is 215 bytes, then the authentication decryption function should be invoked no more than 232 times).
As with any message authentication code, if the adversary chooses a tbit tag at random, it is expected to be correct for given data with probability 2−t. With GCM, however, an adversary can choose tags that increase this probability, proportional to the total length of the ciphertext and additional authenticated data (AAD). Consequently, GCM is not wellsuited for use with very short tag lengths or very long messages.
Ferguson and Saarinen independently described how an attacker can perform optimal attacks against GCM authentication, which meet the lower bound on its security.
Ferguson showed that, if n denotes the total number of blocks in the encoding (the input to the GHASH function), then there is a method of constructing a targeted ciphertext forgery that is expected to succeed with a probability of approximately n2−t. If the tag length t is shorter than 128, then each successful forgery in this attack increases the probability that subsequent targeted forgeries will succeed, and leaks information about the hash subkey, H. Eventually, H may be compromised entirely and the authentication assurance is completely lost.
Independent of this attack, an adversary may attempt to systematically guess many different tags for a given input to authenticated decryption, and thereby increase the probability that one (or more) of them, eventually, will be accepted as valid. For this reason, the system or protocol that implements GCM should monitor and, if necessary, limit the number of unsuccessful verification attempts for each key.
Saarinen described GCM weak keyWeak keyIn cryptography, a weak key is a key, which, used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that, if one generates a random key to encrypt a message, weak keys are very...s This work gives some valuable insights into how polynomial hash based authentication works. More precisely, this work describes a particular way of forging a GCM message, given a valid GCM message, which works with probability of about n/2^128 for messages that are n*128 bits long. However, this work does not show a more effective attack than was previously known; the success probability in Observation 1 of this paper matches that of Lemma 2 from the INDOCRYPT 2004 analysis (setting w=128 and l=n*128). Saarinen also described a GCM variant Sophie Germain Counter ModeSophie Germain Counter ModeA new mode called Sophie Germain Counter Mode has been proposed as a variant of the Galois/Counter Mode Galois/Counter Mode of operation for block ciphers... (SGCM), continuing the GCM tradition of including a mathematician in the name of the mode.
External links
NIST Special Publication SP80038D defining GCM and GMAC
RFC 4106: The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)
RFC 4543: The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH
IEEE 802.1AE  Media Access Control (MAC) Security
IEEE Security in Storage Working Group developed the P1619.1 standard
INCITS T11 Technical Committee works on Fibre Channel  Security Protocols project.
AESGCM and AESCCM Authenticated Encryption in Secure RTP (SRTP)
ShowWikipediaFooter("Galois/Counter_Mode")
}