...
Run Format

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

View as plain text