]>
Commit | Line | Data |
---|---|---|
f038dae6 ILT |
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. | |
14 | type AEAD interface { | |
15 | // NonceSize returns the size of the nonce that must be passed to Seal | |
16 | // and Open. | |
17 | NonceSize() int | |
18 | ||
19 | // Overhead returns the maximum difference between the lengths of a | |
20 | // plaintext and ciphertext. | |
21 | Overhead() int | |
22 | ||
23 | // Seal encrypts and authenticates plaintext, authenticates the | |
24 | // additional data and appends the result to dst, returning the updated | |
25 | // slice. The nonce must be NonceSize() bytes long and unique for all | |
26 | // time, for a given key. | |
27 | // | |
28 | // The plaintext and dst may alias exactly or not at all. | |
29 | Seal(dst, nonce, plaintext, data []byte) []byte | |
30 | ||
31 | // Open decrypts and authenticates ciphertext, authenticates the | |
32 | // additional data and, if successful, appends the resulting plaintext | |
33 | // to dst, returning the updated slice and true. On error, nil and | |
34 | // false is returned. The nonce must be NonceSize() bytes long and both | |
35 | // it and the additional data must match the value passed to Seal. | |
36 | // | |
37 | // The ciphertext and dst may alias exactly or not at all. | |
38 | Open(dst, nonce, ciphertext, data []byte) ([]byte, error) | |
39 | } | |
40 | ||
41 | // gcmFieldElement represents a value in GF(2¹²⁸). In order to reflect the GCM | |
42 | // standard and make getUint64 suitable for marshaling these values, the bits | |
43 | // are stored backwards. For example: | |
44 | // the coefficient of x⁰ can be obtained by v.low >> 63. | |
45 | // the coefficient of x⁶³ can be obtained by v.low & 1. | |
46 | // the coefficient of x⁶⁴ can be obtained by v.high >> 63. | |
47 | // the coefficient of x¹²⁷ can be obtained by v.high & 1. | |
48 | type gcmFieldElement struct { | |
49 | low, high uint64 | |
50 | } | |
51 | ||
52 | // gcm represents a Galois Counter Mode with a specific key. See | |
53 | // http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-revised-spec.pdf | |
54 | type gcm struct { | |
55 | cipher Block | |
56 | // productTable contains the first sixteen powers of the key, H. | |
57 | // However, they are in bit reversed order. See NewGCM. | |
58 | productTable [16]gcmFieldElement | |
59 | } | |
60 | ||
61 | // NewGCM returns the given 128-bit, block cipher wrapped in Galois Counter Mode. | |
62 | func NewGCM(cipher Block) (AEAD, error) { | |
63 | if cipher.BlockSize() != gcmBlockSize { | |
64 | return nil, errors.New("cipher: NewGCM requires 128-bit block cipher") | |
65 | } | |
66 | ||
67 | var key [gcmBlockSize]byte | |
68 | cipher.Encrypt(key[:], key[:]) | |
69 | ||
70 | g := &gcm{cipher: cipher} | |
71 | ||
72 | // We precompute 16 multiples of |key|. However, when we do lookups | |
73 | // into this table we'll be using bits from a field element and | |
74 | // therefore the bits will be in the reverse order. So normally one | |
75 | // would expect, say, 4*key to be in index 4 of the table but due to | |
76 | // this bit ordering it will actually be in index 0010 (base 2) = 2. | |
77 | x := gcmFieldElement{ | |
78 | getUint64(key[:8]), | |
79 | getUint64(key[8:]), | |
80 | } | |
81 | g.productTable[reverseBits(1)] = x | |
82 | ||
83 | for i := 2; i < 16; i += 2 { | |
84 | g.productTable[reverseBits(i)] = gcmDouble(&g.productTable[reverseBits(i/2)]) | |
85 | g.productTable[reverseBits(i+1)] = gcmAdd(&g.productTable[reverseBits(i)], &x) | |
86 | } | |
87 | ||
88 | return g, nil | |
89 | } | |
90 | ||
91 | const ( | |
92 | gcmBlockSize = 16 | |
93 | gcmTagSize = 16 | |
94 | gcmNonceSize = 12 | |
95 | ) | |
96 | ||
97 | func (*gcm) NonceSize() int { | |
98 | return gcmNonceSize | |
99 | } | |
100 | ||
101 | func (*gcm) Overhead() int { | |
102 | return gcmTagSize | |
103 | } | |
104 | ||
105 | func (g *gcm) Seal(dst, nonce, plaintext, data []byte) []byte { | |
106 | if len(nonce) != gcmNonceSize { | |
107 | panic("cipher: incorrect nonce length given to GCM") | |
108 | } | |
109 | ||
110 | ret, out := sliceForAppend(dst, len(plaintext)+gcmTagSize) | |
111 | ||
112 | // See GCM spec, section 7.1. | |
113 | var counter, tagMask [gcmBlockSize]byte | |
114 | copy(counter[:], nonce) | |
115 | counter[gcmBlockSize-1] = 1 | |
116 | ||
117 | g.cipher.Encrypt(tagMask[:], counter[:]) | |
118 | gcmInc32(&counter) | |
119 | ||
120 | g.counterCrypt(out, plaintext, &counter) | |
121 | g.auth(out[len(plaintext):], out[:len(plaintext)], data, &tagMask) | |
122 | ||
123 | return ret | |
124 | } | |
125 | ||
126 | var errOpen = errors.New("cipher: message authentication failed") | |
127 | ||
128 | func (g *gcm) Open(dst, nonce, ciphertext, data []byte) ([]byte, error) { | |
129 | if len(nonce) != gcmNonceSize { | |
130 | panic("cipher: incorrect nonce length given to GCM") | |
131 | } | |
132 | ||
133 | if len(ciphertext) < gcmTagSize { | |
134 | return nil, errOpen | |
135 | } | |
136 | tag := ciphertext[len(ciphertext)-gcmTagSize:] | |
137 | ciphertext = ciphertext[:len(ciphertext)-gcmTagSize] | |
138 | ||
139 | // See GCM spec, section 7.1. | |
140 | var counter, tagMask [gcmBlockSize]byte | |
141 | copy(counter[:], nonce) | |
142 | counter[gcmBlockSize-1] = 1 | |
143 | ||
144 | g.cipher.Encrypt(tagMask[:], counter[:]) | |
145 | gcmInc32(&counter) | |
146 | ||
147 | var expectedTag [gcmTagSize]byte | |
148 | g.auth(expectedTag[:], ciphertext, data, &tagMask) | |
149 | ||
150 | if subtle.ConstantTimeCompare(expectedTag[:], tag) != 1 { | |
151 | return nil, errOpen | |
152 | } | |
153 | ||
154 | ret, out := sliceForAppend(dst, len(ciphertext)) | |
155 | g.counterCrypt(out, ciphertext, &counter) | |
156 | ||
157 | return ret, nil | |
158 | } | |
159 | ||
160 | // reverseBits reverses the order of the bits of 4-bit number in i. | |
161 | func reverseBits(i int) int { | |
162 | i = ((i << 2) & 0xc) | ((i >> 2) & 0x3) | |
163 | i = ((i << 1) & 0xa) | ((i >> 1) & 0x5) | |
164 | return i | |
165 | } | |
166 | ||
167 | // gcmAdd adds two elements of GF(2¹²⁸) and returns the sum. | |
168 | func gcmAdd(x, y *gcmFieldElement) gcmFieldElement { | |
169 | // Addition in a characteristic 2 field is just XOR. | |
170 | return gcmFieldElement{x.low ^ y.low, x.high ^ y.high} | |
171 | } | |
172 | ||
173 | // gcmDouble returns the result of doubling an element of GF(2¹²⁸). | |
174 | func gcmDouble(x *gcmFieldElement) (double gcmFieldElement) { | |
175 | msbSet := x.high&1 == 1 | |
176 | ||
177 | // Because of the bit-ordering, doubling is actually a right shift. | |
178 | double.high = x.high >> 1 | |
179 | double.high |= x.low << 63 | |
180 | double.low = x.low >> 1 | |
181 | ||
182 | // If the most-significant bit was set before shifting then it, | |
183 | // conceptually, becomes a term of x^128. This is greater than the | |
184 | // irreducible polynomial so the result has to be reduced. The | |
185 | // irreducible polynomial is 1+x+x^2+x^7+x^128. We can subtract that to | |
186 | // eliminate the term at x^128 which also means subtracting the other | |
187 | // four terms. In characteristic 2 fields, subtraction == addition == | |
188 | // XOR. | |
189 | if msbSet { | |
190 | double.low ^= 0xe100000000000000 | |
191 | } | |
192 | ||
193 | return | |
194 | } | |
195 | ||
196 | var gcmReductionTable = []uint16{ | |
197 | 0x0000, 0x1c20, 0x3840, 0x2460, 0x7080, 0x6ca0, 0x48c0, 0x54e0, | |
198 | 0xe100, 0xfd20, 0xd940, 0xc560, 0x9180, 0x8da0, 0xa9c0, 0xb5e0, | |
199 | } | |
200 | ||
201 | // mul sets y to y*H, where H is the GCM key, fixed during NewGCM. | |
202 | func (g *gcm) mul(y *gcmFieldElement) { | |
203 | var z gcmFieldElement | |
204 | ||
205 | for i := 0; i < 2; i++ { | |
206 | word := y.high | |
207 | if i == 1 { | |
208 | word = y.low | |
209 | } | |
210 | ||
211 | // Multiplication works by multiplying z by 16 and adding in | |
212 | // one of the precomputed multiples of H. | |
213 | for j := 0; j < 64; j += 4 { | |
214 | msw := z.high & 0xf | |
215 | z.high >>= 4 | |
216 | z.high |= z.low << 60 | |
217 | z.low >>= 4 | |
218 | z.low ^= uint64(gcmReductionTable[msw]) << 48 | |
219 | ||
220 | // the values in |table| are ordered for | |
221 | // little-endian bit positions. See the comment | |
222 | // in NewGCM. | |
223 | t := &g.productTable[word&0xf] | |
224 | ||
225 | z.low ^= t.low | |
226 | z.high ^= t.high | |
227 | word >>= 4 | |
228 | } | |
229 | } | |
230 | ||
231 | *y = z | |
232 | } | |
233 | ||
234 | // updateBlocks extends y with more polynomial terms from blocks, based on | |
235 | // Horner's rule. There must be a multiple of gcmBlockSize bytes in blocks. | |
236 | func (g *gcm) updateBlocks(y *gcmFieldElement, blocks []byte) { | |
237 | for len(blocks) > 0 { | |
238 | y.low ^= getUint64(blocks) | |
239 | y.high ^= getUint64(blocks[8:]) | |
240 | g.mul(y) | |
241 | blocks = blocks[gcmBlockSize:] | |
242 | } | |
243 | } | |
244 | ||
245 | // update extends y with more polynomial terms from data. If data is not a | |
246 | // multiple of gcmBlockSize bytes long then the remainder is zero padded. | |
247 | func (g *gcm) update(y *gcmFieldElement, data []byte) { | |
248 | fullBlocks := (len(data) >> 4) << 4 | |
249 | g.updateBlocks(y, data[:fullBlocks]) | |
250 | ||
251 | if len(data) != fullBlocks { | |
252 | var partialBlock [gcmBlockSize]byte | |
253 | copy(partialBlock[:], data[fullBlocks:]) | |
254 | g.updateBlocks(y, partialBlock[:]) | |
255 | } | |
256 | } | |
257 | ||
258 | // gcmInc32 treats the final four bytes of counterBlock as a big-endian value | |
259 | // and increments it. | |
260 | func gcmInc32(counterBlock *[16]byte) { | |
f038dae6 | 261 | for i := gcmBlockSize - 1; i >= gcmBlockSize-4; i-- { |
bae90c98 ILT |
262 | counterBlock[i]++ |
263 | if counterBlock[i] != 0 { | |
264 | break | |
265 | } | |
f038dae6 ILT |
266 | } |
267 | } | |
268 | ||
269 | // sliceForAppend takes a slice and a requested number of bytes. It returns a | |
270 | // slice with the contents of the given slice followed by that many bytes and a | |
271 | // second slice that aliases into it and contains only the extra bytes. If the | |
272 | // original slice has sufficient capacity then no allocation is performed. | |
273 | func sliceForAppend(in []byte, n int) (head, tail []byte) { | |
274 | if total := len(in) + n; cap(in) >= total { | |
275 | head = in[:total] | |
276 | } else { | |
277 | head = make([]byte, total) | |
278 | copy(head, in) | |
279 | } | |
280 | tail = head[len(in):] | |
281 | return | |
282 | } | |
283 | ||
284 | // counterCrypt crypts in to out using g.cipher in counter mode. | |
285 | func (g *gcm) counterCrypt(out, in []byte, counter *[gcmBlockSize]byte) { | |
286 | var mask [gcmBlockSize]byte | |
287 | ||
288 | for len(in) >= gcmBlockSize { | |
289 | g.cipher.Encrypt(mask[:], counter[:]) | |
290 | gcmInc32(counter) | |
291 | ||
bae90c98 | 292 | xorWords(out, in, mask[:]) |
f038dae6 ILT |
293 | out = out[gcmBlockSize:] |
294 | in = in[gcmBlockSize:] | |
295 | } | |
296 | ||
297 | if len(in) > 0 { | |
298 | g.cipher.Encrypt(mask[:], counter[:]) | |
299 | gcmInc32(counter) | |
bae90c98 | 300 | xorBytes(out, in, mask[:]) |
f038dae6 ILT |
301 | } |
302 | } | |
303 | ||
304 | // auth calculates GHASH(ciphertext, additionalData), masks the result with | |
305 | // tagMask and writes the result to out. | |
306 | func (g *gcm) auth(out, ciphertext, additionalData []byte, tagMask *[gcmTagSize]byte) { | |
307 | var y gcmFieldElement | |
308 | g.update(&y, additionalData) | |
309 | g.update(&y, ciphertext) | |
310 | ||
311 | y.low ^= uint64(len(additionalData)) * 8 | |
312 | y.high ^= uint64(len(ciphertext)) * 8 | |
313 | ||
314 | g.mul(&y) | |
315 | ||
316 | putUint64(out, y.low) | |
317 | putUint64(out[8:], y.high) | |
318 | ||
bae90c98 | 319 | xorWords(out, out, tagMask[:]) |
f038dae6 ILT |
320 | } |
321 | ||
322 | func getUint64(data []byte) uint64 { | |
323 | r := uint64(data[0])<<56 | | |
324 | uint64(data[1])<<48 | | |
325 | uint64(data[2])<<40 | | |
326 | uint64(data[3])<<32 | | |
327 | uint64(data[4])<<24 | | |
328 | uint64(data[5])<<16 | | |
329 | uint64(data[6])<<8 | | |
330 | uint64(data[7]) | |
331 | return r | |
332 | } | |
333 | ||
334 | func putUint64(out []byte, v uint64) { | |
335 | out[0] = byte(v >> 56) | |
336 | out[1] = byte(v >> 48) | |
337 | out[2] = byte(v >> 40) | |
338 | out[3] = byte(v >> 32) | |
339 | out[4] = byte(v >> 24) | |
340 | out[5] = byte(v >> 16) | |
341 | out[6] = byte(v >> 8) | |
342 | out[7] = byte(v) | |
343 | } |