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

View as plain text