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.
8 subtleoverlap
"crypto/internal/subtle"
13 // AEAD is a cipher mode providing authenticated encryption with associated
14 // data. For a description of the methodology, see
15 // https://en.wikipedia.org/wiki/Authenticated_encryption
17 // NonceSize returns the size of the nonce that must be passed to Seal
21 // Overhead returns the maximum difference between the lengths of a
22 // plaintext and its ciphertext.
25 // Seal encrypts and authenticates plaintext, authenticates the
26 // additional data and appends the result to dst, returning the updated
27 // slice. The nonce must be NonceSize() bytes long and unique for all
28 // time, for a given key.
30 // To reuse plaintext's storage for the encrypted output, use plaintext[:0]
31 // as dst. Otherwise, the remaining capacity of dst must not overlap plaintext.
32 Seal(dst
, nonce
, plaintext
, additionalData
[]byte) []byte
34 // Open decrypts and authenticates ciphertext, authenticates the
35 // additional data and, if successful, appends the resulting plaintext
36 // to dst, returning the updated slice. The nonce must be NonceSize()
37 // bytes long and both it and the additional data must match the
38 // value passed to Seal.
40 // To reuse ciphertext's storage for the decrypted output, use ciphertext[:0]
41 // as dst. Otherwise, the remaining capacity of dst must not overlap plaintext.
43 // Even if the function fails, the contents of dst, up to its capacity,
44 // may be overwritten.
45 Open(dst
, nonce
, ciphertext
, additionalData
[]byte) ([]byte, error
)
48 // gcmAble is an interface implemented by ciphers that have a specific optimized
49 // implementation of GCM, like crypto/aes. NewGCM will check for this interface
50 // and return the specific AEAD if found.
51 type gcmAble
interface {
52 NewGCM(nonceSize
, tagSize
int) (AEAD
, error
)
55 // gcmFieldElement represents a value in GF(2¹²⁸). In order to reflect the GCM
56 // standard and make getUint64 suitable for marshaling these values, the bits
57 // are stored backwards. For example:
58 // the coefficient of x⁰ can be obtained by v.low >> 63.
59 // the coefficient of x⁶³ can be obtained by v.low & 1.
60 // the coefficient of x⁶⁴ can be obtained by v.high >> 63.
61 // the coefficient of x¹²⁷ can be obtained by v.high & 1.
62 type gcmFieldElement
struct {
66 // gcm represents a Galois Counter Mode with a specific key. See
67 // https://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-revised-spec.pdf
72 // productTable contains the first sixteen powers of the key, H.
73 // However, they are in bit reversed order. See NewGCMWithNonceSize.
74 productTable
[16]gcmFieldElement
77 // NewGCM returns the given 128-bit, block cipher wrapped in Galois Counter Mode
78 // with the standard nonce length.
80 // In general, the GHASH operation performed by this implementation of GCM is not constant-time.
81 // An exception is when the underlying Block was created by aes.NewCipher
82 // on systems with hardware support for AES. See the crypto/aes package documentation for details.
83 func NewGCM(cipher Block
) (AEAD
, error
) {
84 return newGCMWithNonceAndTagSize(cipher
, gcmStandardNonceSize
, gcmTagSize
)
87 // NewGCMWithNonceSize returns the given 128-bit, block cipher wrapped in Galois
88 // Counter Mode, which accepts nonces of the given length.
90 // Only use this function if you require compatibility with an existing
91 // cryptosystem that uses non-standard nonce lengths. All other users should use
92 // NewGCM, which is faster and more resistant to misuse.
93 func NewGCMWithNonceSize(cipher Block
, size
int) (AEAD
, error
) {
94 return newGCMWithNonceAndTagSize(cipher
, size
, gcmTagSize
)
97 // NewGCMWithTagSize returns the given 128-bit, block cipher wrapped in Galois
98 // Counter Mode, which generates tags with the given length.
100 // Tag sizes between 12 and 16 bytes are allowed.
102 // Only use this function if you require compatibility with an existing
103 // cryptosystem that uses non-standard tag lengths. All other users should use
104 // NewGCM, which is more resistant to misuse.
105 func NewGCMWithTagSize(cipher Block
, tagSize
int) (AEAD
, error
) {
106 return newGCMWithNonceAndTagSize(cipher
, gcmStandardNonceSize
, tagSize
)
109 func newGCMWithNonceAndTagSize(cipher Block
, nonceSize
, tagSize
int) (AEAD
, error
) {
110 if tagSize
< gcmMinimumTagSize || tagSize
> gcmBlockSize
{
111 return nil, errors
.New("cipher: incorrect tag size given to GCM")
114 if cipher
, ok
:= cipher
.(gcmAble
); ok
{
115 return cipher
.NewGCM(nonceSize
, tagSize
)
118 if cipher
.BlockSize() != gcmBlockSize
{
119 return nil, errors
.New("cipher: NewGCM requires 128-bit block cipher")
122 var key
[gcmBlockSize
]byte
123 cipher
.Encrypt(key
[:], key
[:])
125 g
:= &gcm
{cipher
: cipher
, nonceSize
: nonceSize
, tagSize
: tagSize
}
127 // We precompute 16 multiples of |key|. However, when we do lookups
128 // into this table we'll be using bits from a field element and
129 // therefore the bits will be in the reverse order. So normally one
130 // would expect, say, 4*key to be in index 4 of the table but due to
131 // this bit ordering it will actually be in index 0010 (base 2) = 2.
132 x
:= gcmFieldElement
{
136 g
.productTable
[reverseBits(1)] = x
138 for i
:= 2; i
< 16; i
+= 2 {
139 g
.productTable
[reverseBits(i
)] = gcmDouble(&g
.productTable
[reverseBits(i
/2)])
140 g
.productTable
[reverseBits(i
+1)] = gcmAdd(&g
.productTable
[reverseBits(i
)], &x
)
149 gcmMinimumTagSize
= 12 // NIST SP 800-38D recommends tags with 12 or more bytes.
150 gcmStandardNonceSize
= 12
153 func (g
*gcm
) NonceSize() int {
157 func (g
*gcm
) Overhead() int {
161 func (g
*gcm
) Seal(dst
, nonce
, plaintext
, data
[]byte) []byte {
162 if len(nonce
) != g
.nonceSize
{
163 panic("crypto/cipher: incorrect nonce length given to GCM")
165 if uint64(len(plaintext
)) > ((1<<32)-2)*uint64(g
.cipher
.BlockSize()) {
166 panic("crypto/cipher: message too large for GCM")
169 ret
, out
:= sliceForAppend(dst
, len(plaintext
)+g
.tagSize
)
170 if subtleoverlap
.InexactOverlap(out
, plaintext
) {
171 panic("crypto/cipher: invalid buffer overlap")
174 var counter
, tagMask
[gcmBlockSize
]byte
175 g
.deriveCounter(&counter
, nonce
)
177 g
.cipher
.Encrypt(tagMask
[:], counter
[:])
180 g
.counterCrypt(out
, plaintext
, &counter
)
182 var tag
[gcmTagSize
]byte
183 g
.auth(tag
[:], out
[:len(plaintext
)], data
, &tagMask
)
184 copy(out
[len(plaintext
):], tag
[:])
189 var errOpen
= errors
.New("cipher: message authentication failed")
191 func (g
*gcm
) Open(dst
, nonce
, ciphertext
, data
[]byte) ([]byte, error
) {
192 if len(nonce
) != g
.nonceSize
{
193 panic("crypto/cipher: incorrect nonce length given to GCM")
195 // Sanity check to prevent the authentication from always succeeding if an implementation
196 // leaves tagSize uninitialized, for example.
197 if g
.tagSize
< gcmMinimumTagSize
{
198 panic("crypto/cipher: incorrect GCM tag size")
201 if len(ciphertext
) < g
.tagSize
{
204 if uint64(len(ciphertext
)) > ((1<<32)-2)*uint64(g
.cipher
.BlockSize())+uint64(g
.tagSize
) {
208 tag
:= ciphertext
[len(ciphertext
)-g
.tagSize
:]
209 ciphertext
= ciphertext
[:len(ciphertext
)-g
.tagSize
]
211 var counter
, tagMask
[gcmBlockSize
]byte
212 g
.deriveCounter(&counter
, nonce
)
214 g
.cipher
.Encrypt(tagMask
[:], counter
[:])
217 var expectedTag
[gcmTagSize
]byte
218 g
.auth(expectedTag
[:], ciphertext
, data
, &tagMask
)
220 ret
, out
:= sliceForAppend(dst
, len(ciphertext
))
221 if subtleoverlap
.InexactOverlap(out
, ciphertext
) {
222 panic("crypto/cipher: invalid buffer overlap")
225 if subtle
.ConstantTimeCompare(expectedTag
[:g
.tagSize
], tag
) != 1 {
226 // The AESNI code decrypts and authenticates concurrently, and
227 // so overwrites dst in the event of a tag mismatch. That
228 // behavior is mimicked here in order to be consistent across
236 g
.counterCrypt(out
, ciphertext
, &counter
)
241 // reverseBits reverses the order of the bits of 4-bit number in i.
242 func reverseBits(i
int) int {
243 i
= ((i
<< 2) & 0xc) |
((i
>> 2) & 0x3)
244 i
= ((i
<< 1) & 0xa) |
((i
>> 1) & 0x5)
248 // gcmAdd adds two elements of GF(2¹²⁸) and returns the sum.
249 func gcmAdd(x
, y
*gcmFieldElement
) gcmFieldElement
{
250 // Addition in a characteristic 2 field is just XOR.
251 return gcmFieldElement
{x
.low
^ y
.low
, x
.high
^ y
.high
}
254 // gcmDouble returns the result of doubling an element of GF(2¹²⁸).
255 func gcmDouble(x
*gcmFieldElement
) (double gcmFieldElement
) {
256 msbSet
:= x
.high
&1 == 1
258 // Because of the bit-ordering, doubling is actually a right shift.
259 double
.high
= x
.high
>> 1
260 double
.high |
= x
.low
<< 63
261 double
.low
= x
.low
>> 1
263 // If the most-significant bit was set before shifting then it,
264 // conceptually, becomes a term of x^128. This is greater than the
265 // irreducible polynomial so the result has to be reduced. The
266 // irreducible polynomial is 1+x+x^2+x^7+x^128. We can subtract that to
267 // eliminate the term at x^128 which also means subtracting the other
268 // four terms. In characteristic 2 fields, subtraction == addition ==
271 double
.low
^= 0xe100000000000000
277 var gcmReductionTable
= []uint16{
278 0x0000, 0x1c20, 0x3840, 0x2460, 0x7080, 0x6ca0, 0x48c0, 0x54e0,
279 0xe100, 0xfd20, 0xd940, 0xc560, 0x9180, 0x8da0, 0xa9c0, 0xb5e0,
282 // mul sets y to y*H, where H is the GCM key, fixed during NewGCMWithNonceSize.
283 func (g
*gcm
) mul(y
*gcmFieldElement
) {
284 var z gcmFieldElement
286 for i
:= 0; i
< 2; i
++ {
292 // Multiplication works by multiplying z by 16 and adding in
293 // one of the precomputed multiples of H.
294 for j
:= 0; j
< 64; j
+= 4 {
297 z
.high |
= z
.low
<< 60
299 z
.low
^= uint64(gcmReductionTable
[msw
]) << 48
301 // the values in |table| are ordered for
302 // little-endian bit positions. See the comment
303 // in NewGCMWithNonceSize.
304 t
:= &g
.productTable
[word
&0xf]
315 // updateBlocks extends y with more polynomial terms from blocks, based on
316 // Horner's rule. There must be a multiple of gcmBlockSize bytes in blocks.
317 func (g
*gcm
) updateBlocks(y
*gcmFieldElement
, blocks
[]byte) {
318 for len(blocks
) > 0 {
319 y
.low
^= getUint64(blocks
)
320 y
.high
^= getUint64(blocks
[8:])
322 blocks
= blocks
[gcmBlockSize
:]
326 // update extends y with more polynomial terms from data. If data is not a
327 // multiple of gcmBlockSize bytes long then the remainder is zero padded.
328 func (g
*gcm
) update(y
*gcmFieldElement
, data
[]byte) {
329 fullBlocks
:= (len(data
) >> 4) << 4
330 g
.updateBlocks(y
, data
[:fullBlocks
])
332 if len(data
) != fullBlocks
{
333 var partialBlock
[gcmBlockSize
]byte
334 copy(partialBlock
[:], data
[fullBlocks
:])
335 g
.updateBlocks(y
, partialBlock
[:])
339 // gcmInc32 treats the final four bytes of counterBlock as a big-endian value
340 // and increments it.
341 func gcmInc32(counterBlock
*[16]byte) {
342 for i
:= gcmBlockSize
- 1; i
>= gcmBlockSize
-4; i
-- {
344 if counterBlock
[i
] != 0 {
350 // sliceForAppend takes a slice and a requested number of bytes. It returns a
351 // slice with the contents of the given slice followed by that many bytes and a
352 // second slice that aliases into it and contains only the extra bytes. If the
353 // original slice has sufficient capacity then no allocation is performed.
354 func sliceForAppend(in
[]byte, n
int) (head
, tail
[]byte) {
355 if total
:= len(in
) + n
; cap(in
) >= total
{
358 head
= make([]byte, total
)
361 tail
= head
[len(in
):]
365 // counterCrypt crypts in to out using g.cipher in counter mode.
366 func (g
*gcm
) counterCrypt(out
, in
[]byte, counter
*[gcmBlockSize
]byte) {
367 var mask
[gcmBlockSize
]byte
369 for len(in
) >= gcmBlockSize
{
370 g
.cipher
.Encrypt(mask
[:], counter
[:])
373 xorWords(out
, in
, mask
[:])
374 out
= out
[gcmBlockSize
:]
375 in
= in
[gcmBlockSize
:]
379 g
.cipher
.Encrypt(mask
[:], counter
[:])
381 xorBytes(out
, in
, mask
[:])
385 // deriveCounter computes the initial GCM counter state from the given nonce.
386 // See NIST SP 800-38D, section 7.1. This assumes that counter is filled with
388 func (g
*gcm
) deriveCounter(counter
*[gcmBlockSize
]byte, nonce
[]byte) {
389 // GCM has two modes of operation with respect to the initial counter
390 // state: a "fast path" for 96-bit (12-byte) nonces, and a "slow path"
391 // for nonces of other lengths. For a 96-bit nonce, the nonce, along
392 // with a four-byte big-endian counter starting at one, is used
393 // directly as the starting counter. For other nonce sizes, the counter
394 // is computed by passing it through the GHASH function.
395 if len(nonce
) == gcmStandardNonceSize
{
396 copy(counter
[:], nonce
)
397 counter
[gcmBlockSize
-1] = 1
399 var y gcmFieldElement
401 y
.high
^= uint64(len(nonce
)) * 8
403 putUint64(counter
[:8], y
.low
)
404 putUint64(counter
[8:], y
.high
)
408 // auth calculates GHASH(ciphertext, additionalData), masks the result with
409 // tagMask and writes the result to out.
410 func (g
*gcm
) auth(out
, ciphertext
, additionalData
[]byte, tagMask
*[gcmTagSize
]byte) {
411 var y gcmFieldElement
412 g
.update(&y
, additionalData
)
413 g
.update(&y
, ciphertext
)
415 y
.low
^= uint64(len(additionalData
)) * 8
416 y
.high
^= uint64(len(ciphertext
)) * 8
420 putUint64(out
, y
.low
)
421 putUint64(out
[8:], y
.high
)
423 xorWords(out
, out
, tagMask
[:])
426 func getUint64(data
[]byte) uint64 {
427 _
= data
[7] // bounds check hint to compiler; see golang.org/issue/14808
428 r
:= uint64(data
[0])<<56 |
429 uint64(data
[1])<<48 |
430 uint64(data
[2])<<40 |
431 uint64(data
[3])<<32 |
432 uint64(data
[4])<<24 |
433 uint64(data
[5])<<16 |
439 func putUint64(out
[]byte, v
uint64) {
440 _
= out
[7] // bounds check hint to compiler; see golang.org/issue/14808
441 out
[0] = byte(v
>> 56)
442 out
[1] = byte(v
>> 48)
443 out
[2] = byte(v
>> 40)
444 out
[3] = byte(v
>> 32)
445 out
[4] = byte(v
>> 24)
446 out
[5] = byte(v
>> 16)
447 out
[6] = byte(v
>> 8)