...
Run Format

Source file src/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		"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 may alias 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 may alias 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