libgo/go/crypto/cipher/gcm.go

   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) {
 261         for i := gcmBlockSize - 1; i >= gcmBlockSize-4; i-- {
 262                 counterBlock[i]++
 263                 if counterBlock[i] != 0 {
 264                         break
 265                 }
 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
 292                 xorWords(out, in, mask[:])
 293                 out = out[gcmBlockSize:]
 294                 in = in[gcmBlockSize:]
 295         }
 296
 297         if len(in) > 0 {
 298                 g.cipher.Encrypt(mask[:], counter[:])
 299                 gcmInc32(counter)
 300                 xorBytes(out, in, mask[:])
 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
 319         xorWords(out, out, tagMask[:])
 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 }