gcm.c 11.4 KB
Newer Older
1
/* gcm.c
2 3 4 5 6 7 8 9

   Galois counter mode, specified by NIST,
   http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf

   See also the gcm paper at
   http://www.cryptobarn.com/papers/gcm-spec.pdf.

   Copyright (C) 2011 Katholieke Universiteit Leuven
10 11
   Copyright (C) 2011, 2013, 2018 Niels Möller
   Copyright (C) 2018 Red Hat, Inc.
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
   
   Contributed by Nikos Mavrogiannopoulos

   This file is part of GNU Nettle.

   GNU Nettle is free software: you can redistribute it and/or
   modify it under the terms of either:

     * the GNU Lesser General Public License as published by the Free
       Software Foundation; either version 3 of the License, or (at your
       option) any later version.

   or

     * the GNU General Public License as published by the Free
       Software Foundation; either version 2 of the License, or (at your
       option) any later version.

   or both in parallel, as here.

   GNU Nettle is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received copies of the GNU General Public License and
   the GNU Lesser General Public License along with this program.  If
   not, see http://www.gnu.org/licenses/.
*/
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
41 42 43 44 45 46 47 48 49 50 51 52 53 54

#if HAVE_CONFIG_H
# include "config.h"
#endif

#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "gcm.h"

#include "memxor.h"
#include "nettle-internal.h"
#include "macros.h"
55
#include "ctr-internal.h"
56
#include "block-internal.h"
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
57

58 59
#if GCM_TABLE_BITS == 0
/* Sets x <- x * y mod r, using the plain bitwise algorithm from the
60 61
   specification. y may be shorter than a full block, missing bytes
   are assumed zero. */
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
62
static void
Niels Möller's avatar
Niels Möller committed
63
gcm_gf_mul (union nettle_block16 *x, const union nettle_block16 *y)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
64
{
Niels Möller's avatar
Niels Möller committed
65 66
  union nettle_block16 V;
  union nettle_block16 Z;
67
  unsigned i;
68

69 70
  memcpy(V.b, x, sizeof(V));
  memset(Z.b, 0, sizeof(Z));
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
71

72
  for (i = 0; i < GCM_BLOCK_SIZE; i++)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
73
    {
74
      uint8_t b = y->b[i];
75 76 77 78
      unsigned j;
      for (j = 0; j < 8; j++, b <<= 1)
	{
	  if (b & 0x80)
79
	    block16_xor(&Z, &V);
80
	  
81
	  block16_mulx_ghash(&V, &V);
82
	}
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
83
    }
84
  memcpy (x->b, Z.b, sizeof(Z));
85
}
86
#else /* GCM_TABLE_BITS != 0 */
87 88 89 90 91 92 93

# if WORDS_BIGENDIAN
#  define W(left,right) (0x##left##right)
# else
#  define W(left,right) (0x##right##left)
# endif

94
# if GCM_TABLE_BITS == 4
95 96 97 98 99 100 101
static const uint16_t
shift_table[0x10] = {
  W(00,00),W(1c,20),W(38,40),W(24,60),W(70,80),W(6c,a0),W(48,c0),W(54,e0),
  W(e1,00),W(fd,20),W(d9,40),W(c5,60),W(91,80),W(8d,a0),W(a9,c0),W(b5,e0),
};

static void
Niels Möller's avatar
Niels Möller committed
102
gcm_gf_shift_4(union nettle_block16 *x)
103
{
104 105
  uint64_t *u64 = x->u64;
  uint64_t reduce;
106 107 108

  /* Shift uses big-endian representation. */
#if WORDS_BIGENDIAN
109 110 111
  reduce = shift_table[u64[1] & 0xf];
  u64[1] = (u64[1] >> 4) | ((u64[0] & 0xf) << 60);
  u64[0] = (u64[0] >> 4) ^ (reduce << 48);
112
#else /* ! WORDS_BIGENDIAN */
113 114 115 116 117 118 119
#define RSHIFT_WORD_4(x) \
  ((((x) & UINT64_C(0xf0f0f0f0f0f0f0f0)) >> 4) \
   | (((x) & UINT64_C(0x000f0f0f0f0f0f0f)) << 12))
  reduce = shift_table[(u64[1] >> 56) & 0xf];
  u64[1] = RSHIFT_WORD_4(u64[1]) | ((u64[0] >> 52) & 0xf0);
  u64[0] = RSHIFT_WORD_4(u64[0]) ^ reduce;
# undef RSHIFT_WORD_4
120 121 122 123
#endif /* ! WORDS_BIGENDIAN */
}

static void
Niels Möller's avatar
Niels Möller committed
124
gcm_gf_mul (union nettle_block16 *x, const union nettle_block16 *table)
125
{
Niels Möller's avatar
Niels Möller committed
126
  union nettle_block16 Z;
127 128
  unsigned i;

129
  memset(Z.b, 0, sizeof(Z));
130 131 132

  for (i = GCM_BLOCK_SIZE; i-- > 0;)
    {
133
      uint8_t b = x->b[i];
134

135
      gcm_gf_shift_4(&Z);
136
      block16_xor(&Z, &table[b & 0xf]);
137
      gcm_gf_shift_4(&Z);
138
      block16_xor(&Z, &table[b >> 4]);
139
    }
140
  memcpy (x->b, Z.b, sizeof(Z));
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
141
}
142
# elif GCM_TABLE_BITS == 8
143
#  if HAVE_NATIVE_gcm_hash8
144

145
#define gcm_hash _nettle_gcm_hash8
146
void
Niels Möller's avatar
Niels Möller committed
147
_nettle_gcm_hash8 (const struct gcm_key *key, union nettle_block16 *x,
148 149
		   size_t length, const uint8_t *data);
#  else /* !HAVE_NATIVE_gcm_hash8 */
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
static const uint16_t
shift_table[0x100] = {
  W(00,00),W(01,c2),W(03,84),W(02,46),W(07,08),W(06,ca),W(04,8c),W(05,4e),
  W(0e,10),W(0f,d2),W(0d,94),W(0c,56),W(09,18),W(08,da),W(0a,9c),W(0b,5e),
  W(1c,20),W(1d,e2),W(1f,a4),W(1e,66),W(1b,28),W(1a,ea),W(18,ac),W(19,6e),
  W(12,30),W(13,f2),W(11,b4),W(10,76),W(15,38),W(14,fa),W(16,bc),W(17,7e),
  W(38,40),W(39,82),W(3b,c4),W(3a,06),W(3f,48),W(3e,8a),W(3c,cc),W(3d,0e),
  W(36,50),W(37,92),W(35,d4),W(34,16),W(31,58),W(30,9a),W(32,dc),W(33,1e),
  W(24,60),W(25,a2),W(27,e4),W(26,26),W(23,68),W(22,aa),W(20,ec),W(21,2e),
  W(2a,70),W(2b,b2),W(29,f4),W(28,36),W(2d,78),W(2c,ba),W(2e,fc),W(2f,3e),
  W(70,80),W(71,42),W(73,04),W(72,c6),W(77,88),W(76,4a),W(74,0c),W(75,ce),
  W(7e,90),W(7f,52),W(7d,14),W(7c,d6),W(79,98),W(78,5a),W(7a,1c),W(7b,de),
  W(6c,a0),W(6d,62),W(6f,24),W(6e,e6),W(6b,a8),W(6a,6a),W(68,2c),W(69,ee),
  W(62,b0),W(63,72),W(61,34),W(60,f6),W(65,b8),W(64,7a),W(66,3c),W(67,fe),
  W(48,c0),W(49,02),W(4b,44),W(4a,86),W(4f,c8),W(4e,0a),W(4c,4c),W(4d,8e),
  W(46,d0),W(47,12),W(45,54),W(44,96),W(41,d8),W(40,1a),W(42,5c),W(43,9e),
  W(54,e0),W(55,22),W(57,64),W(56,a6),W(53,e8),W(52,2a),W(50,6c),W(51,ae),
  W(5a,f0),W(5b,32),W(59,74),W(58,b6),W(5d,f8),W(5c,3a),W(5e,7c),W(5f,be),
  W(e1,00),W(e0,c2),W(e2,84),W(e3,46),W(e6,08),W(e7,ca),W(e5,8c),W(e4,4e),
  W(ef,10),W(ee,d2),W(ec,94),W(ed,56),W(e8,18),W(e9,da),W(eb,9c),W(ea,5e),
  W(fd,20),W(fc,e2),W(fe,a4),W(ff,66),W(fa,28),W(fb,ea),W(f9,ac),W(f8,6e),
  W(f3,30),W(f2,f2),W(f0,b4),W(f1,76),W(f4,38),W(f5,fa),W(f7,bc),W(f6,7e),
  W(d9,40),W(d8,82),W(da,c4),W(db,06),W(de,48),W(df,8a),W(dd,cc),W(dc,0e),
  W(d7,50),W(d6,92),W(d4,d4),W(d5,16),W(d0,58),W(d1,9a),W(d3,dc),W(d2,1e),
  W(c5,60),W(c4,a2),W(c6,e4),W(c7,26),W(c2,68),W(c3,aa),W(c1,ec),W(c0,2e),
  W(cb,70),W(ca,b2),W(c8,f4),W(c9,36),W(cc,78),W(cd,ba),W(cf,fc),W(ce,3e),
  W(91,80),W(90,42),W(92,04),W(93,c6),W(96,88),W(97,4a),W(95,0c),W(94,ce),
  W(9f,90),W(9e,52),W(9c,14),W(9d,d6),W(98,98),W(99,5a),W(9b,1c),W(9a,de),
  W(8d,a0),W(8c,62),W(8e,24),W(8f,e6),W(8a,a8),W(8b,6a),W(89,2c),W(88,ee),
  W(83,b0),W(82,72),W(80,34),W(81,f6),W(84,b8),W(85,7a),W(87,3c),W(86,fe),
  W(a9,c0),W(a8,02),W(aa,44),W(ab,86),W(ae,c8),W(af,0a),W(ad,4c),W(ac,8e),
  W(a7,d0),W(a6,12),W(a4,54),W(a5,96),W(a0,d8),W(a1,1a),W(a3,5c),W(a2,9e),
  W(b5,e0),W(b4,22),W(b6,64),W(b7,a6),W(b2,e8),W(b3,2a),W(b1,6c),W(b0,ae),
  W(bb,f0),W(ba,32),W(b8,74),W(b9,b6),W(bc,f8),W(bd,3a),W(bf,7c),W(be,be),
};

186
static void
Niels Möller's avatar
Niels Möller committed
187
gcm_gf_shift_8(union nettle_block16 *x)
188
{
189
  uint64_t reduce;
190 191 192

  /* Shift uses big-endian representation. */
#if WORDS_BIGENDIAN
193 194 195
  reduce = shift_table[x->u64[1] & 0xff];
  x->u64[1] = (x->u64[1] >> 8) | ((x->u64[0] & 0xff) << 56);
  x->u64[0] = (x->u64[0] >> 8) ^ (reduce << 48);
196
#else /* ! WORDS_BIGENDIAN */
197 198 199
  reduce = shift_table[(x->u64[1] >> 56) & 0xff];
  x->u64[1] = (x->u64[1] << 8) | (x->u64[0] >> 56);
  x->u64[0] = (x->u64[0] << 8) ^ reduce;
200 201 202 203
#endif /* ! WORDS_BIGENDIAN */
}

static void
Niels Möller's avatar
Niels Möller committed
204
gcm_gf_mul (union nettle_block16 *x, const union nettle_block16 *table)
205
{
Niels Möller's avatar
Niels Möller committed
206
  union nettle_block16 Z;
207 208
  unsigned i;

209
  memcpy(Z.b, table[x->b[GCM_BLOCK_SIZE-1]].b, GCM_BLOCK_SIZE);
210

211
  for (i = GCM_BLOCK_SIZE-2; i > 0; i--)
212
    {
213
      gcm_gf_shift_8(&Z);
214
      block16_xor(&Z, &table[x->b[i]]);
215
    }
216
  gcm_gf_shift_8(&Z);
217
  block16_xor3(x, &Z, &table[x->b[0]]);
218
}
219
#  endif /* ! HAVE_NATIVE_gcm_hash8 */
220 221 222 223 224 225
# else /* GCM_TABLE_BITS != 8 */
#  error Unsupported table size. 
# endif /* GCM_TABLE_BITS != 8 */

#undef W

226
#endif /* GCM_TABLE_BITS */
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
227 228

/* Increment the rightmost 32 bits. */
229
#define INC32(block) INCREMENT(4, (block.b) + GCM_BLOCK_SIZE - 4)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
230 231 232 233 234 235 236

/* Initialization of GCM.
 * @ctx: The context of GCM
 * @cipher: The context of the underlying block cipher
 * @f: The underlying cipher encryption function
 */
void
237
gcm_set_key(struct gcm_key *key,
238
	    const void *cipher, nettle_cipher_func *f)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
239
{
240 241 242 243 244
  /* Middle element if GCM_TABLE_BITS > 0, otherwise the first
     element */
  unsigned i = (1<<GCM_TABLE_BITS)/2;

  /* H */  
245 246
  memset(key->h[0].b, 0, GCM_BLOCK_SIZE);
  f (cipher, GCM_BLOCK_SIZE, key->h[i].b, key->h[0].b);
247
  
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
248
#if GCM_TABLE_BITS
249 250 251
  /* Algorithm 3 from the gcm paper. First do powers of two, then do
     the rest by adding. */
  while (i /= 2)
252
    block16_mulx_ghash(&key->h[i], &key->h[2*i]);
253 254 255 256
  for (i = 2; i < 1<<GCM_TABLE_BITS; i *= 2)
    {
      unsigned j;
      for (j = 1; j < i; j++)
257
	block16_xor3(&key->h[i+j], &key->h[i],&key->h[j]);
258
    }
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
259 260 261
#endif
}

262
#ifndef gcm_hash
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
263
static void
Niels Möller's avatar
Niels Möller committed
264
gcm_hash(const struct gcm_key *key, union nettle_block16 *x,
265
	 size_t length, const uint8_t *data)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
266 267 268 269
{
  for (; length >= GCM_BLOCK_SIZE;
       length -= GCM_BLOCK_SIZE, data += GCM_BLOCK_SIZE)
    {
270 271
      memxor (x->b, data, GCM_BLOCK_SIZE);
      gcm_gf_mul (x, key->h);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
272 273 274
    }
  if (length > 0)
    {
275 276
      memxor (x->b, data, length);
      gcm_gf_mul (x, key->h);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
277 278
    }
}
279
#endif /* !gcm_hash */
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
280

281
static void
Niels Möller's avatar
Niels Möller committed
282
gcm_hash_sizes(const struct gcm_key *key, union nettle_block16 *x,
Niels Möller's avatar
Niels Möller committed
283
	       uint64_t auth_size, uint64_t data_size)
284 285 286 287 288 289 290 291 292 293 294 295
{
  uint8_t buffer[GCM_BLOCK_SIZE];

  data_size *= 8;
  auth_size *= 8;

  WRITE_UINT64 (buffer, auth_size);
  WRITE_UINT64 (buffer + 8, data_size);

  gcm_hash(key, x, GCM_BLOCK_SIZE, buffer);
}

Niels Möller's avatar
Niels Möller committed
296
/* NOTE: The key is needed only if length != GCM_IV_SIZE */
297 298
void
gcm_set_iv(struct gcm_ctx *ctx, const struct gcm_key *key,
299
	   size_t length, const uint8_t *iv)
300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323
{
  if (length == GCM_IV_SIZE)
    {
      memcpy (ctx->iv.b, iv, GCM_BLOCK_SIZE - 4);
      ctx->iv.b[GCM_BLOCK_SIZE - 4] = 0;
      ctx->iv.b[GCM_BLOCK_SIZE - 3] = 0;
      ctx->iv.b[GCM_BLOCK_SIZE - 2] = 0;
      ctx->iv.b[GCM_BLOCK_SIZE - 1] = 1;
    }
  else
    {
      memset(ctx->iv.b, 0, GCM_BLOCK_SIZE);
      gcm_hash(key, &ctx->iv, length, iv);
      gcm_hash_sizes(key, &ctx->iv, 0, length);
    }

  memcpy (ctx->ctr.b, ctx->iv.b, GCM_BLOCK_SIZE);
  INC32 (ctx->ctr);

  /* Reset the rest of the message-dependent state. */
  memset(ctx->x.b, 0, sizeof(ctx->x));
  ctx->auth_size = ctx->data_size = 0;
}

Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
324
void
325
gcm_update(struct gcm_ctx *ctx, const struct gcm_key *key,
326
	   size_t length, const uint8_t *data)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
327 328
{
  assert(ctx->auth_size % GCM_BLOCK_SIZE == 0);
329
  assert(ctx->data_size == 0);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
330

331
  gcm_hash(key, &ctx->x, length, data);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
332 333 334 335

  ctx->auth_size += length;
}

336
static nettle_fill16_func gcm_fill;
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
337
static void
338
gcm_fill(uint8_t *ctr, size_t blocks, union nettle_block16 *buffer)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
339
{
340
  uint32_t c;
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
341

342 343 344
  c = READ_UINT32(ctr + GCM_BLOCK_SIZE - 4);

  for (; blocks-- > 0; buffer++, c++)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
345
    {
346 347
      memcpy(buffer->b, ctr, GCM_BLOCK_SIZE - 4);
      WRITE_UINT32(buffer->b + GCM_BLOCK_SIZE - 4, c);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
348
    }
349 350

  WRITE_UINT32(ctr + GCM_BLOCK_SIZE - 4, c);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
351 352 353
}

void
354
gcm_encrypt (struct gcm_ctx *ctx, const struct gcm_key *key,
355
	     const void *cipher, nettle_cipher_func *f,
356
	     size_t length, uint8_t *dst, const uint8_t *src)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
357 358 359
{
  assert(ctx->data_size % GCM_BLOCK_SIZE == 0);

360
  _ctr_crypt16(cipher, f, gcm_fill, ctx->ctr.b, length, dst, src);
361
  gcm_hash(key, &ctx->x, length, dst);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
362 363 364 365 366

  ctx->data_size += length;
}

void
367
gcm_decrypt(struct gcm_ctx *ctx, const struct gcm_key *key,
368
	    const void *cipher, nettle_cipher_func *f,
369
	    size_t length, uint8_t *dst, const uint8_t *src)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
370 371 372
{
  assert(ctx->data_size % GCM_BLOCK_SIZE == 0);

373
  gcm_hash(key, &ctx->x, length, src);
374
  _ctr_crypt16(cipher, f, gcm_fill, ctx->ctr.b, length, dst, src);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
375 376 377 378 379

  ctx->data_size += length;
}

void
380
gcm_digest(struct gcm_ctx *ctx, const struct gcm_key *key,
381
	   const void *cipher, nettle_cipher_func *f,
382
	   size_t length, uint8_t *digest)
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
383 384 385 386 387
{
  uint8_t buffer[GCM_BLOCK_SIZE];

  assert (length <= GCM_BLOCK_SIZE);

388
  gcm_hash_sizes(key, &ctx->x, ctx->auth_size, ctx->data_size);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
389

390 391
  f (cipher, GCM_BLOCK_SIZE, buffer, ctx->iv.b);
  memxor3 (digest, ctx->x.b, buffer, length);
Nikos Mavrogiannopoulos's avatar
Nikos Mavrogiannopoulos committed
392 393 394

  return;
}