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.
12 // AEAD is a cipher mode providing authenticated encryption with associated
15 // NonceSize returns the size of the nonce that must be passed to Seal
19 // Overhead returns the maximum difference between the lengths of a
20 // plaintext and ciphertext.
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.
28 // The plaintext and dst may alias exactly or not at all.
29 Seal(dst
, nonce
, plaintext
, data
[]byte) []byte
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. The nonce must be NonceSize()
34 // bytes long and both it and the additional data must match the
35 // value passed to Seal.
37 // The ciphertext and dst may alias exactly or not at all.
38 Open(dst
, nonce
, ciphertext
, data
[]byte) ([]byte, error
)
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 {
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
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
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")
67 var key
[gcmBlockSize
]byte
68 cipher
.Encrypt(key
[:], key
[:])
70 g
:= &gcm
{cipher
: cipher
}
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.
81 g
.productTable
[reverseBits(1)] = x
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
)
97 func (*gcm
) NonceSize() int {
101 func (*gcm
) Overhead() int {
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")
110 ret
, out
:= sliceForAppend(dst
, len(plaintext
)+gcmTagSize
)
112 // See GCM spec, section 7.1.
113 var counter
, tagMask
[gcmBlockSize
]byte
114 copy(counter
[:], nonce
)
115 counter
[gcmBlockSize
-1] = 1
117 g
.cipher
.Encrypt(tagMask
[:], counter
[:])
120 g
.counterCrypt(out
, plaintext
, &counter
)
121 g
.auth(out
[len(plaintext
):], out
[:len(plaintext
)], data
, &tagMask
)
126 var errOpen
= errors
.New("cipher: message authentication failed")
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")
133 if len(ciphertext
) < gcmTagSize
{
136 tag
:= ciphertext
[len(ciphertext
)-gcmTagSize
:]
137 ciphertext
= ciphertext
[:len(ciphertext
)-gcmTagSize
]
139 // See GCM spec, section 7.1.
140 var counter
, tagMask
[gcmBlockSize
]byte
141 copy(counter
[:], nonce
)
142 counter
[gcmBlockSize
-1] = 1
144 g
.cipher
.Encrypt(tagMask
[:], counter
[:])
147 var expectedTag
[gcmTagSize
]byte
148 g
.auth(expectedTag
[:], ciphertext
, data
, &tagMask
)
150 if subtle
.ConstantTimeCompare(expectedTag
[:], tag
) != 1 {
154 ret
, out
:= sliceForAppend(dst
, len(ciphertext
))
155 g
.counterCrypt(out
, ciphertext
, &counter
)
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)
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
}
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
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
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 ==
190 double
.low
^= 0xe100000000000000
196 var gcmReductionTable
= []uint16{
197 0x0000, 0x1c20, 0x3840, 0x2460, 0x7080, 0x6ca0, 0x48c0, 0x54e0,
198 0xe100, 0xfd20, 0xd940, 0xc560, 0x9180, 0x8da0, 0xa9c0, 0xb5e0,
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
205 for i
:= 0; i
< 2; i
++ {
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 {
216 z
.high |
= z
.low
<< 60
218 z
.low
^= uint64(gcmReductionTable
[msw
]) << 48
220 // the values in |table| are ordered for
221 // little-endian bit positions. See the comment
223 t
:= &g
.productTable
[word
&0xf]
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:])
241 blocks
= blocks
[gcmBlockSize
:]
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
])
251 if len(data
) != fullBlocks
{
252 var partialBlock
[gcmBlockSize
]byte
253 copy(partialBlock
[:], data
[fullBlocks
:])
254 g
.updateBlocks(y
, partialBlock
[:])
258 // gcmInc32 treats the final four bytes of counterBlock as a big-endian value
259 // and increments it.
260 func gcmInc32(counterBlock
*[16]byte) {
261 for i
:= gcmBlockSize
- 1; i
>= gcmBlockSize
-4; i
-- {
263 if counterBlock
[i
] != 0 {
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
{
277 head
= make([]byte, total
)
280 tail
= head
[len(in
):]
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
288 for len(in
) >= gcmBlockSize
{
289 g
.cipher
.Encrypt(mask
[:], counter
[:])
292 xorWords(out
, in
, mask
[:])
293 out
= out
[gcmBlockSize
:]
294 in
= in
[gcmBlockSize
:]
298 g
.cipher
.Encrypt(mask
[:], counter
[:])
300 xorBytes(out
, in
, mask
[:])
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
)
311 y
.low
^= uint64(len(additionalData
)) * 8
312 y
.high
^= uint64(len(ciphertext
)) * 8
316 putUint64(out
, y
.low
)
317 putUint64(out
[8:], y
.high
)
319 xorWords(out
, out
, tagMask
[:])
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 |
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)