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