Source file src/pkg/crypto/cipher/gcm.go

     1	// Copyright 2013 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package cipher
     6	
     7	import (
     8		subtleoverlap "crypto/internal/subtle"
     9		"crypto/subtle"
    10		"encoding/binary"
    11		"errors"
    12	)
    13	
    14	// AEAD is a cipher mode providing authenticated encryption with associated
    15	// data. For a description of the methodology, see
    16	//	https://en.wikipedia.org/wiki/Authenticated_encryption
    17	type AEAD interface {
    18		// NonceSize returns the size of the nonce that must be passed to Seal
    19		// and Open.
    20		NonceSize() int
    21	
    22		// Overhead returns the maximum difference between the lengths of a
    23		// plaintext and its ciphertext.
    24		Overhead() int
    25	
    26		// Seal encrypts and authenticates plaintext, authenticates the
    27		// additional data and appends the result to dst, returning the updated
    28		// slice. The nonce must be NonceSize() bytes long and unique for all
    29		// time, for a given key.
    30		//
    31		// To reuse plaintext's storage for the encrypted output, use plaintext[:0]
    32		// as dst. Otherwise, the remaining capacity of dst must not overlap plaintext.
    33		Seal(dst, nonce, plaintext, additionalData []byte) []byte
    34	
    35		// Open decrypts and authenticates ciphertext, authenticates the
    36		// additional data and, if successful, appends the resulting plaintext
    37		// to dst, returning the updated slice. The nonce must be NonceSize()
    38		// bytes long and both it and the additional data must match the
    39		// value passed to Seal.
    40		//
    41		// To reuse ciphertext's storage for the decrypted output, use ciphertext[:0]
    42		// as dst. Otherwise, the remaining capacity of dst must not overlap plaintext.
    43		//
    44		// Even if the function fails, the contents of dst, up to its capacity,
    45		// may be overwritten.
    46		Open(dst, nonce, ciphertext, additionalData []byte) ([]byte, error)
    47	}
    48	
    49	// gcmAble is an interface implemented by ciphers that have a specific optimized
    50	// implementation of GCM, like crypto/aes. NewGCM will check for this interface
    51	// and return the specific AEAD if found.
    52	type gcmAble interface {
    53		NewGCM(nonceSize, tagSize int) (AEAD, error)
    54	}
    55	
    56	// gcmFieldElement represents a value in GF(2¹²⁸). In order to reflect the GCM
    57	// standard and make binary.BigEndian suitable for marshaling these values, the
    58	// bits are stored in big endian order. For example:
    59	//   the coefficient of x⁰ can be obtained by v.low >> 63.
    60	//   the coefficient of x⁶³ can be obtained by v.low & 1.
    61	//   the coefficient of x⁶⁴ can be obtained by v.high >> 63.
    62	//   the coefficient of x¹²⁷ can be obtained by v.high & 1.
    63	type gcmFieldElement struct {
    64		low, high uint64
    65	}
    66	
    67	// gcm represents a Galois Counter Mode with a specific key. See
    68	// https://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-revised-spec.pdf
    69	type gcm struct {
    70		cipher    Block
    71		nonceSize int
    72		tagSize   int
    73		// productTable contains the first sixteen powers of the key, H.
    74		// However, they are in bit reversed order. See NewGCMWithNonceSize.
    75		productTable [16]gcmFieldElement
    76	}
    77	
    78	// NewGCM returns the given 128-bit, block cipher wrapped in Galois Counter Mode
    79	// with the standard nonce length.
    80	//
    81	// In general, the GHASH operation performed by this implementation of GCM is not constant-time.
    82	// An exception is when the underlying Block was created by aes.NewCipher
    83	// on systems with hardware support for AES. See the crypto/aes package documentation for details.
    84	func NewGCM(cipher Block) (AEAD, error) {
    85		return newGCMWithNonceAndTagSize(cipher, gcmStandardNonceSize, gcmTagSize)
    86	}
    87	
    88	// NewGCMWithNonceSize returns the given 128-bit, block cipher wrapped in Galois
    89	// Counter Mode, which accepts nonces of the given length.
    90	//
    91	// Only use this function if you require compatibility with an existing
    92	// cryptosystem that uses non-standard nonce lengths. All other users should use
    93	// NewGCM, which is faster and more resistant to misuse.
    94	func NewGCMWithNonceSize(cipher Block, size int) (AEAD, error) {
    95		return newGCMWithNonceAndTagSize(cipher, size, gcmTagSize)
    96	}
    97	
    98	// NewGCMWithTagSize returns the given 128-bit, block cipher wrapped in Galois
    99	// Counter Mode, which generates tags with the given length.
   100	//
   101	// Tag sizes between 12 and 16 bytes are allowed.
   102	//
   103	// Only use this function if you require compatibility with an existing
   104	// cryptosystem that uses non-standard tag lengths. All other users should use
   105	// NewGCM, which is more resistant to misuse.
   106	func NewGCMWithTagSize(cipher Block, tagSize int) (AEAD, error) {
   107		return newGCMWithNonceAndTagSize(cipher, gcmStandardNonceSize, tagSize)
   108	}
   109	
   110	func newGCMWithNonceAndTagSize(cipher Block, nonceSize, tagSize int) (AEAD, error) {
   111		if tagSize < gcmMinimumTagSize || tagSize > gcmBlockSize {
   112			return nil, errors.New("cipher: incorrect tag size given to GCM")
   113		}
   114	
   115		if cipher, ok := cipher.(gcmAble); ok {
   116			return cipher.NewGCM(nonceSize, tagSize)
   117		}
   118	
   119		if cipher.BlockSize() != gcmBlockSize {
   120			return nil, errors.New("cipher: NewGCM requires 128-bit block cipher")
   121		}
   122	
   123		var key [gcmBlockSize]byte
   124		cipher.Encrypt(key[:], key[:])
   125	
   126		g := &gcm{cipher: cipher, nonceSize: nonceSize, tagSize: tagSize}
   127	
   128		// We precompute 16 multiples of |key|. However, when we do lookups
   129		// into this table we'll be using bits from a field element and
   130		// therefore the bits will be in the reverse order. So normally one
   131		// would expect, say, 4*key to be in index 4 of the table but due to
   132		// this bit ordering it will actually be in index 0010 (base 2) = 2.
   133		x := gcmFieldElement{
   134			binary.BigEndian.Uint64(key[:8]),
   135			binary.BigEndian.Uint64(key[8:]),
   136		}
   137		g.productTable[reverseBits(1)] = x
   138	
   139		for i := 2; i < 16; i += 2 {
   140			g.productTable[reverseBits(i)] = gcmDouble(&g.productTable[reverseBits(i/2)])
   141			g.productTable[reverseBits(i+1)] = gcmAdd(&g.productTable[reverseBits(i)], &x)
   142		}
   143	
   144		return g, nil
   145	}
   146	
   147	const (
   148		gcmBlockSize         = 16
   149		gcmTagSize           = 16
   150		gcmMinimumTagSize    = 12 // NIST SP 800-38D recommends tags with 12 or more bytes.
   151		gcmStandardNonceSize = 12
   152	)
   153	
   154	func (g *gcm) NonceSize() int {
   155		return g.nonceSize
   156	}
   157	
   158	func (g *gcm) Overhead() int {
   159		return g.tagSize
   160	}
   161	
   162	func (g *gcm) Seal(dst, nonce, plaintext, data []byte) []byte {
   163		if len(nonce) != g.nonceSize {
   164			panic("crypto/cipher: incorrect nonce length given to GCM")
   165		}
   166		if uint64(len(plaintext)) > ((1<<32)-2)*uint64(g.cipher.BlockSize()) {
   167			panic("crypto/cipher: message too large for GCM")
   168		}
   169	
   170		ret, out := sliceForAppend(dst, len(plaintext)+g.tagSize)
   171		if subtleoverlap.InexactOverlap(out, plaintext) {
   172			panic("crypto/cipher: invalid buffer overlap")
   173		}
   174	
   175		var counter, tagMask [gcmBlockSize]byte
   176		g.deriveCounter(&counter, nonce)
   177	
   178		g.cipher.Encrypt(tagMask[:], counter[:])
   179		gcmInc32(&counter)
   180	
   181		g.counterCrypt(out, plaintext, &counter)
   182	
   183		var tag [gcmTagSize]byte
   184		g.auth(tag[:], out[:len(plaintext)], data, &tagMask)
   185		copy(out[len(plaintext):], tag[:])
   186	
   187		return ret
   188	}
   189	
   190	var errOpen = errors.New("cipher: message authentication failed")
   191	
   192	func (g *gcm) Open(dst, nonce, ciphertext, data []byte) ([]byte, error) {
   193		if len(nonce) != g.nonceSize {
   194			panic("crypto/cipher: incorrect nonce length given to GCM")
   195		}
   196		// Sanity check to prevent the authentication from always succeeding if an implementation
   197		// leaves tagSize uninitialized, for example.
   198		if g.tagSize < gcmMinimumTagSize {
   199			panic("crypto/cipher: incorrect GCM tag size")
   200		}
   201	
   202		if len(ciphertext) < g.tagSize {
   203			return nil, errOpen
   204		}
   205		if uint64(len(ciphertext)) > ((1<<32)-2)*uint64(g.cipher.BlockSize())+uint64(g.tagSize) {
   206			return nil, errOpen
   207		}
   208	
   209		tag := ciphertext[len(ciphertext)-g.tagSize:]
   210		ciphertext = ciphertext[:len(ciphertext)-g.tagSize]
   211	
   212		var counter, tagMask [gcmBlockSize]byte
   213		g.deriveCounter(&counter, nonce)
   214	
   215		g.cipher.Encrypt(tagMask[:], counter[:])
   216		gcmInc32(&counter)
   217	
   218		var expectedTag [gcmTagSize]byte
   219		g.auth(expectedTag[:], ciphertext, data, &tagMask)
   220	
   221		ret, out := sliceForAppend(dst, len(ciphertext))
   222		if subtleoverlap.InexactOverlap(out, ciphertext) {
   223			panic("crypto/cipher: invalid buffer overlap")
   224		}
   225	
   226		if subtle.ConstantTimeCompare(expectedTag[:g.tagSize], tag) != 1 {
   227			// The AESNI code decrypts and authenticates concurrently, and
   228			// so overwrites dst in the event of a tag mismatch. That
   229			// behavior is mimicked here in order to be consistent across
   230			// platforms.
   231			for i := range out {
   232				out[i] = 0
   233			}
   234			return nil, errOpen
   235		}
   236	
   237		g.counterCrypt(out, ciphertext, &counter)
   238	
   239		return ret, nil
   240	}
   241	
   242	// reverseBits reverses the order of the bits of 4-bit number in i.
   243	func reverseBits(i int) int {
   244		i = ((i << 2) & 0xc) | ((i >> 2) & 0x3)
   245		i = ((i << 1) & 0xa) | ((i >> 1) & 0x5)
   246		return i
   247	}
   248	
   249	// gcmAdd adds two elements of GF(2¹²⁸) and returns the sum.
   250	func gcmAdd(x, y *gcmFieldElement) gcmFieldElement {
   251		// Addition in a characteristic 2 field is just XOR.
   252		return gcmFieldElement{x.low ^ y.low, x.high ^ y.high}
   253	}
   254	
   255	// gcmDouble returns the result of doubling an element of GF(2¹²⁸).
   256	func gcmDouble(x *gcmFieldElement) (double gcmFieldElement) {
   257		msbSet := x.high&1 == 1
   258	
   259		// Because of the bit-ordering, doubling is actually a right shift.
   260		double.high = x.high >> 1
   261		double.high |= x.low << 63
   262		double.low = x.low >> 1
   263	
   264		// If the most-significant bit was set before shifting then it,
   265		// conceptually, becomes a term of x^128. This is greater than the
   266		// irreducible polynomial so the result has to be reduced. The
   267		// irreducible polynomial is 1+x+x^2+x^7+x^128. We can subtract that to
   268		// eliminate the term at x^128 which also means subtracting the other
   269		// four terms. In characteristic 2 fields, subtraction == addition ==
   270		// XOR.
   271		if msbSet {
   272			double.low ^= 0xe100000000000000
   273		}
   274	
   275		return
   276	}
   277	
   278	var gcmReductionTable = []uint16{
   279		0x0000, 0x1c20, 0x3840, 0x2460, 0x7080, 0x6ca0, 0x48c0, 0x54e0,
   280		0xe100, 0xfd20, 0xd940, 0xc560, 0x9180, 0x8da0, 0xa9c0, 0xb5e0,
   281	}
   282	
   283	// mul sets y to y*H, where H is the GCM key, fixed during NewGCMWithNonceSize.
   284	func (g *gcm) mul(y *gcmFieldElement) {
   285		var z gcmFieldElement
   286	
   287		for i := 0; i < 2; i++ {
   288			word := y.high
   289			if i == 1 {
   290				word = y.low
   291			}
   292	
   293			// Multiplication works by multiplying z by 16 and adding in
   294			// one of the precomputed multiples of H.
   295			for j := 0; j < 64; j += 4 {
   296				msw := z.high & 0xf
   297				z.high >>= 4
   298				z.high |= z.low << 60
   299				z.low >>= 4
   300				z.low ^= uint64(gcmReductionTable[msw]) << 48
   301	
   302				// the values in |table| are ordered for
   303				// little-endian bit positions. See the comment
   304				// in NewGCMWithNonceSize.
   305				t := &g.productTable[word&0xf]
   306	
   307				z.low ^= t.low
   308				z.high ^= t.high
   309				word >>= 4
   310			}
   311		}
   312	
   313		*y = z
   314	}
   315	
   316	// updateBlocks extends y with more polynomial terms from blocks, based on
   317	// Horner's rule. There must be a multiple of gcmBlockSize bytes in blocks.
   318	func (g *gcm) updateBlocks(y *gcmFieldElement, blocks []byte) {
   319		for len(blocks) > 0 {
   320			y.low ^= binary.BigEndian.Uint64(blocks)
   321			y.high ^= binary.BigEndian.Uint64(blocks[8:])
   322			g.mul(y)
   323			blocks = blocks[gcmBlockSize:]
   324		}
   325	}
   326	
   327	// update extends y with more polynomial terms from data. If data is not a
   328	// multiple of gcmBlockSize bytes long then the remainder is zero padded.
   329	func (g *gcm) update(y *gcmFieldElement, data []byte) {
   330		fullBlocks := (len(data) >> 4) << 4
   331		g.updateBlocks(y, data[:fullBlocks])
   332	
   333		if len(data) != fullBlocks {
   334			var partialBlock [gcmBlockSize]byte
   335			copy(partialBlock[:], data[fullBlocks:])
   336			g.updateBlocks(y, partialBlock[:])
   337		}
   338	}
   339	
   340	// gcmInc32 treats the final four bytes of counterBlock as a big-endian value
   341	// and increments it.
   342	func gcmInc32(counterBlock *[16]byte) {
   343		ctr := counterBlock[len(counterBlock)-4:]
   344		binary.BigEndian.PutUint32(ctr, binary.BigEndian.Uint32(ctr)+1)
   345	}
   346	
   347	// sliceForAppend takes a slice and a requested number of bytes. It returns a
   348	// slice with the contents of the given slice followed by that many bytes and a
   349	// second slice that aliases into it and contains only the extra bytes. If the
   350	// original slice has sufficient capacity then no allocation is performed.
   351	func sliceForAppend(in []byte, n int) (head, tail []byte) {
   352		if total := len(in) + n; cap(in) >= total {
   353			head = in[:total]
   354		} else {
   355			head = make([]byte, total)
   356			copy(head, in)
   357		}
   358		tail = head[len(in):]
   359		return
   360	}
   361	
   362	// counterCrypt crypts in to out using g.cipher in counter mode.
   363	func (g *gcm) counterCrypt(out, in []byte, counter *[gcmBlockSize]byte) {
   364		var mask [gcmBlockSize]byte
   365	
   366		for len(in) >= gcmBlockSize {
   367			g.cipher.Encrypt(mask[:], counter[:])
   368			gcmInc32(counter)
   369	
   370			xorWords(out, in, mask[:])
   371			out = out[gcmBlockSize:]
   372			in = in[gcmBlockSize:]
   373		}
   374	
   375		if len(in) > 0 {
   376			g.cipher.Encrypt(mask[:], counter[:])
   377			gcmInc32(counter)
   378			xorBytes(out, in, mask[:])
   379		}
   380	}
   381	
   382	// deriveCounter computes the initial GCM counter state from the given nonce.
   383	// See NIST SP 800-38D, section 7.1. This assumes that counter is filled with
   384	// zeros on entry.
   385	func (g *gcm) deriveCounter(counter *[gcmBlockSize]byte, nonce []byte) {
   386		// GCM has two modes of operation with respect to the initial counter
   387		// state: a "fast path" for 96-bit (12-byte) nonces, and a "slow path"
   388		// for nonces of other lengths. For a 96-bit nonce, the nonce, along
   389		// with a four-byte big-endian counter starting at one, is used
   390		// directly as the starting counter. For other nonce sizes, the counter
   391		// is computed by passing it through the GHASH function.
   392		if len(nonce) == gcmStandardNonceSize {
   393			copy(counter[:], nonce)
   394			counter[gcmBlockSize-1] = 1
   395		} else {
   396			var y gcmFieldElement
   397			g.update(&y, nonce)
   398			y.high ^= uint64(len(nonce)) * 8
   399			g.mul(&y)
   400			binary.BigEndian.PutUint64(counter[:8], y.low)
   401			binary.BigEndian.PutUint64(counter[8:], y.high)
   402		}
   403	}
   404	
   405	// auth calculates GHASH(ciphertext, additionalData), masks the result with
   406	// tagMask and writes the result to out.
   407	func (g *gcm) auth(out, ciphertext, additionalData []byte, tagMask *[gcmTagSize]byte) {
   408		var y gcmFieldElement
   409		g.update(&y, additionalData)
   410		g.update(&y, ciphertext)
   411	
   412		y.low ^= uint64(len(additionalData)) * 8
   413		y.high ^= uint64(len(ciphertext)) * 8
   414	
   415		g.mul(&y)
   416	
   417		binary.BigEndian.PutUint64(out, y.low)
   418		binary.BigEndian.PutUint64(out[8:], y.high)
   419	
   420		xorWords(out, out, tagMask[:])
   421	}
   422	

View as plain text