gcm.go

Documentation: crypto/cipher

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