ghash.go

     1  // Copyright 2024 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 gcm
     6  
     7  import (
     8  	"crypto/internal/fips140"
     9  	"crypto/internal/fips140deps/byteorder"
    10  )
    11  
    12  // gcmFieldElement represents a value in GF(2¹²⁸). In order to reflect the GCM
    13  // standard and make binary.BigEndian suitable for marshaling these values, the
    14  // bits are stored in big endian order. For example:
    15  //
    16  //	the coefficient of x⁰ can be obtained by v.low >> 63.
    17  //	the coefficient of x⁶³ can be obtained by v.low & 1.
    18  //	the coefficient of x⁶⁴ can be obtained by v.high >> 63.
    19  //	the coefficient of x¹²⁷ can be obtained by v.high & 1.
    20  type gcmFieldElement struct {
    21  	low, high uint64
    22  }
    23  
    24  // GHASH is exposed to allow crypto/cipher to implement non-AES GCM modes.
    25  // It is not allowed as a stand-alone operation in FIPS mode because it
    26  // is not ACVP tested.
    27  func GHASH(key *[16]byte, inputs ...[]byte) []byte {
    28  	fips140.RecordNonApproved()
    29  	var out [gcmBlockSize]byte
    30  	ghash(&out, key, inputs...)
    31  	return out[:]
    32  }
    33  
    34  // ghash is a variable-time generic implementation of GHASH, which shouldn't
    35  // be used on any architecture with hardware support for AES-GCM.
    36  //
    37  // Each input is zero-padded to 128-bit before being absorbed.
    38  func ghash(out, H *[gcmBlockSize]byte, inputs ...[]byte) {
    39  	// productTable contains the first sixteen powers of the key, H.
    40  	// However, they are in bit reversed order.
    41  	var productTable [16]gcmFieldElement
    42  
    43  	// We precompute 16 multiples of H. However, when we do lookups
    44  	// into this table we'll be using bits from a field element and
    45  	// therefore the bits will be in the reverse order. So normally one
    46  	// would expect, say, 4*H to be in index 4 of the table but due to
    47  	// this bit ordering it will actually be in index 0010 (base 2) = 2.
    48  	x := gcmFieldElement{
    49  		byteorder.BEUint64(H[:8]),
    50  		byteorder.BEUint64(H[8:]),
    51  	}
    52  	productTable[reverseBits(1)] = x
    53  
    54  	for i := 2; i < 16; i += 2 {
    55  		productTable[reverseBits(i)] = ghashDouble(&productTable[reverseBits(i/2)])
    56  		productTable[reverseBits(i+1)] = ghashAdd(&productTable[reverseBits(i)], &x)
    57  	}
    58  
    59  	var y gcmFieldElement
    60  	for _, input := range inputs {
    61  		ghashUpdate(&productTable, &y, input)
    62  	}
    63  
    64  	byteorder.BEPutUint64(out[:], y.low)
    65  	byteorder.BEPutUint64(out[8:], y.high)
    66  }
    67  
    68  // reverseBits reverses the order of the bits of 4-bit number in i.
    69  func reverseBits(i int) int {
    70  	i = ((i << 2) & 0xc) | ((i >> 2) & 0x3)
    71  	i = ((i << 1) & 0xa) | ((i >> 1) & 0x5)
    72  	return i
    73  }
    74  
    75  // ghashAdd adds two elements of GF(2¹²⁸) and returns the sum.
    76  func ghashAdd(x, y *gcmFieldElement) gcmFieldElement {
    77  	// Addition in a characteristic 2 field is just XOR.
    78  	return gcmFieldElement{x.low ^ y.low, x.high ^ y.high}
    79  }
    80  
    81  // ghashDouble returns the result of doubling an element of GF(2¹²⁸).
    82  func ghashDouble(x *gcmFieldElement) (double gcmFieldElement) {
    83  	msbSet := x.high&1 == 1
    84  
    85  	// Because of the bit-ordering, doubling is actually a right shift.
    86  	double.high = x.high >> 1
    87  	double.high |= x.low << 63
    88  	double.low = x.low >> 1
    89  
    90  	// If the most-significant bit was set before shifting then it,
    91  	// conceptually, becomes a term of x^128. This is greater than the
    92  	// irreducible polynomial so the result has to be reduced. The
    93  	// irreducible polynomial is 1+x+x^2+x^7+x^128. We can subtract that to
    94  	// eliminate the term at x^128 which also means subtracting the other
    95  	// four terms. In characteristic 2 fields, subtraction == addition ==
    96  	// XOR.
    97  	if msbSet {
    98  		double.low ^= 0xe100000000000000
    99  	}
   100  
   101  	return
   102  }
   103  
   104  var ghashReductionTable = []uint16{
   105  	0x0000, 0x1c20, 0x3840, 0x2460, 0x7080, 0x6ca0, 0x48c0, 0x54e0,
   106  	0xe100, 0xfd20, 0xd940, 0xc560, 0x9180, 0x8da0, 0xa9c0, 0xb5e0,
   107  }
   108  
   109  // ghashMul sets y to y*H, where H is the GCM key, fixed during New.
   110  func ghashMul(productTable *[16]gcmFieldElement, y *gcmFieldElement) {
   111  	var z gcmFieldElement
   112  
   113  	for i := 0; i < 2; i++ {
   114  		word := y.high
   115  		if i == 1 {
   116  			word = y.low
   117  		}
   118  
   119  		// Multiplication works by multiplying z by 16 and adding in
   120  		// one of the precomputed multiples of H.
   121  		for j := 0; j < 64; j += 4 {
   122  			msw := z.high & 0xf
   123  			z.high >>= 4
   124  			z.high |= z.low << 60
   125  			z.low >>= 4
   126  			z.low ^= uint64(ghashReductionTable[msw]) << 48
   127  
   128  			// the values in |table| are ordered for little-endian bit
   129  			// positions. See the comment in New.
   130  			t := productTable[word&0xf]
   131  
   132  			z.low ^= t.low
   133  			z.high ^= t.high
   134  			word >>= 4
   135  		}
   136  	}
   137  
   138  	*y = z
   139  }
   140  
   141  // updateBlocks extends y with more polynomial terms from blocks, based on
   142  // Horner's rule. There must be a multiple of gcmBlockSize bytes in blocks.
   143  func updateBlocks(productTable *[16]gcmFieldElement, y *gcmFieldElement, blocks []byte) {
   144  	for len(blocks) > 0 {
   145  		y.low ^= byteorder.BEUint64(blocks)
   146  		y.high ^= byteorder.BEUint64(blocks[8:])
   147  		ghashMul(productTable, y)
   148  		blocks = blocks[gcmBlockSize:]
   149  	}
   150  }
   151  
   152  // ghashUpdate extends y with more polynomial terms from data. If data is not a
   153  // multiple of gcmBlockSize bytes long then the remainder is zero padded.
   154  func ghashUpdate(productTable *[16]gcmFieldElement, y *gcmFieldElement, data []byte) {
   155  	fullBlocks := (len(data) >> 4) << 4
   156  	updateBlocks(productTable, y, data[:fullBlocks])
   157  
   158  	if len(data) != fullBlocks {
   159  		var partialBlock [gcmBlockSize]byte
   160  		copy(partialBlock[:], data[fullBlocks:])
   161  		updateBlocks(productTable, y, partialBlock[:])
   162  	}
   163  }
   164
View as plain text