Define and use nettle_cipher_func, for block ciphers.
[gd/nettle] / gcm.c
1 /* gcm.h
2  *
3  * Galois counter mode, specified by NIST,
4  * http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf
5  *
6  * See also the gcm paper at
7  * http://www.cryptobarn.com/papers/gcm-spec.pdf.
8  */
9
10 /* nettle, low-level cryptographics library
11  *
12  * Copyright (C) 2011 Niels Möller
13  * Copyright (C) 2011 Katholieke Universiteit Leuven
14  * 
15  * Contributed by Nikos Mavrogiannopoulos
16  *
17  * The nettle library is free software; you can redistribute it and/or modify
18  * it under the terms of the GNU Lesser General Public License as published by
19  * the Free Software Foundation; either version 2.1 of the License, or (at your
20  * option) any later version.
21  * 
22  * The nettle library is distributed in the hope that it will be useful, but
23  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
24  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
25  * License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public License
28  * along with the nettle library; see the file COPYING.LIB.  If not, write to
29  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
30  * MA 02111-1301, USA.
31  */
32
33 #if HAVE_CONFIG_H
34 # include "config.h"
35 #endif
36
37 #include <assert.h>
38 #include <stdlib.h>
39 #include <string.h>
40
41 #include "gcm.h"
42
43 #include "memxor.h"
44 #include "nettle-internal.h"
45 #include "macros.h"
46
47 #define GHASH_POLYNOMIAL 0xE1UL
48
49 static void
50 gcm_gf_add (union nettle_block16 *r,
51             const union nettle_block16 *x, const union nettle_block16 *y)
52 {
53   r->w[0] = x->w[0] ^ y->w[0];
54   r->w[1] = x->w[1] ^ y->w[1];
55 #if SIZEOF_LONG == 4
56   r->w[2] = x->w[2] ^ y->w[2];
57   r->w[3] = x->w[3] ^ y->w[3];
58 #endif      
59 }
60 /* Multiplication by 010...0; a big-endian shift right. If the bit
61    shifted out is one, the defining polynomial is added to cancel it
62    out. r == x is allowed. */
63 static void
64 gcm_gf_shift (union nettle_block16 *r, const union nettle_block16 *x)
65 {
66   long mask;
67
68   /* Shift uses big-endian representation. */
69 #if WORDS_BIGENDIAN
70 # if SIZEOF_LONG == 4
71   mask = - (x->w[3] & 1);
72   r->w[3] = (x->w[3] >> 1) | ((x->w[2] & 1) << 31);
73   r->w[2] = (x->w[2] >> 1) | ((x->w[1] & 1) << 31);
74   r->w[1] = (x->w[1] >> 1) | ((x->w[0] & 1) << 31);
75   r->w[0] = (x->w[0] >> 1) ^ (mask & (GHASH_POLYNOMIAL << 24)); 
76 # elif SIZEOF_LONG == 8
77   mask = - (x->w[1] & 1);
78   r->w[1] = (x->w[1] >> 1) | ((x->w[0] & 1) << 63);
79   r->w[0] = (x->w[0] >> 1) ^ (mask & (GHASH_POLYNOMIAL << 56));
80 # else
81 #  error Unsupported word size. */
82 #endif
83 #else /* ! WORDS_BIGENDIAN */
84 # if SIZEOF_LONG == 4
85 #define RSHIFT_WORD(x) \
86   ((((x) & 0xfefefefeUL) >> 1) \
87    | (((x) & 0x00010101) << 15))
88   mask = - ((x->w[3] >> 24) & 1);
89   r->w[3] = RSHIFT_WORD(x->w[3]) | ((x->w[2] >> 17) & 0x80);
90   r->w[2] = RSHIFT_WORD(x->w[2]) | ((x->w[1] >> 17) & 0x80);
91   r->w[1] = RSHIFT_WORD(x->w[1]) | ((x->w[0] >> 17) & 0x80);
92   r->w[0] = RSHIFT_WORD(x->w[0]) ^ (mask & GHASH_POLYNOMIAL);
93 # elif SIZEOF_LONG == 8
94 #define RSHIFT_WORD(x) \
95   ((((x) & 0xfefefefefefefefeUL) >> 1) \
96    | (((x) & 0x0001010101010101UL) << 15))
97   mask = - ((x->w[1] >> 56) & 1);
98   r->w[1] = RSHIFT_WORD(x->w[1]) | ((x->w[0] >> 49) & 0x80);
99   r->w[0] = RSHIFT_WORD(x->w[0]) ^ (mask & GHASH_POLYNOMIAL);
100 # else
101 #  error Unsupported word size. */
102 # endif
103 # undef RSHIFT_WORD
104 #endif /* ! WORDS_BIGENDIAN */
105 }
106
107 #if GCM_TABLE_BITS == 0
108 /* Sets x <- x * y mod r, using the plain bitwise algorithm from the
109    specification. y may be shorter than a full block, missing bytes
110    are assumed zero. */
111 static void
112 gcm_gf_mul (union nettle_block16 *x, const union nettle_block16 *y)
113 {
114   union nettle_block16 V;
115   union nettle_block16 Z;
116   unsigned i;
117
118   memcpy(V.b, x, sizeof(V));
119   memset(Z.b, 0, sizeof(Z));
120
121   for (i = 0; i < GCM_BLOCK_SIZE; i++)
122     {
123       uint8_t b = y->b[i];
124       unsigned j;
125       for (j = 0; j < 8; j++, b <<= 1)
126         {
127           if (b & 0x80)
128             gcm_gf_add(&Z, &Z, &V);
129           
130           gcm_gf_shift(&V, &V);
131         }
132     }
133   memcpy (x->b, Z.b, sizeof(Z));
134 }
135 #else /* GCM_TABLE_BITS != 0 */
136
137 # if WORDS_BIGENDIAN
138 #  define W(left,right) (0x##left##right)
139 # else
140 #  define W(left,right) (0x##right##left)
141 # endif
142
143 # if GCM_TABLE_BITS == 4
144 static const uint16_t
145 shift_table[0x10] = {
146   W(00,00),W(1c,20),W(38,40),W(24,60),W(70,80),W(6c,a0),W(48,c0),W(54,e0),
147   W(e1,00),W(fd,20),W(d9,40),W(c5,60),W(91,80),W(8d,a0),W(a9,c0),W(b5,e0),
148 };
149
150 static void
151 gcm_gf_shift_4(union nettle_block16 *x)
152 {
153   unsigned long *w = x->w;
154   unsigned long reduce;
155
156   /* Shift uses big-endian representation. */
157 #if WORDS_BIGENDIAN
158 # if SIZEOF_LONG == 4
159   reduce = shift_table[w[3] & 0xf];
160   w[3] = (w[3] >> 4) | ((w[2] & 0xf) << 28);
161   w[2] = (w[2] >> 4) | ((w[1] & 0xf) << 28);
162   w[1] = (w[1] >> 4) | ((w[0] & 0xf) << 28);
163   w[0] = (w[0] >> 4) ^ (reduce << 16);
164 # elif SIZEOF_LONG == 8
165   reduce = shift_table[w[1] & 0xf];
166   w[1] = (w[1] >> 4) | ((w[0] & 0xf) << 60);
167   w[0] = (w[0] >> 4) ^ (reduce << 48);
168 # else
169 #  error Unsupported word size. */
170 #endif
171 #else /* ! WORDS_BIGENDIAN */
172 # if SIZEOF_LONG == 4
173 #define RSHIFT_WORD(x) \
174   ((((x) & 0xf0f0f0f0UL) >> 4)                  \
175    | (((x) & 0x000f0f0f) << 12))
176   reduce = shift_table[(w[3] >> 24) & 0xf];
177   w[3] = RSHIFT_WORD(w[3]) | ((w[2] >> 20) & 0xf0);
178   w[2] = RSHIFT_WORD(w[2]) | ((w[1] >> 20) & 0xf0);
179   w[1] = RSHIFT_WORD(w[1]) | ((w[0] >> 20) & 0xf0);
180   w[0] = RSHIFT_WORD(w[0]) ^ reduce;
181 # elif SIZEOF_LONG == 8
182 #define RSHIFT_WORD(x) \
183   ((((x) & 0xf0f0f0f0f0f0f0f0UL) >> 4) \
184    | (((x) & 0x000f0f0f0f0f0f0fUL) << 12))
185   reduce = shift_table[(w[1] >> 56) & 0xf];
186   w[1] = RSHIFT_WORD(w[1]) | ((w[0] >> 52) & 0xf0);
187   w[0] = RSHIFT_WORD(w[0]) ^ reduce;
188 # else
189 #  error Unsupported word size. */
190 # endif
191 # undef RSHIFT_WORD
192 #endif /* ! WORDS_BIGENDIAN */
193 }
194
195 static void
196 gcm_gf_mul (union nettle_block16 *x, const union nettle_block16 *table)
197 {
198   union nettle_block16 Z;
199   unsigned i;
200
201   memset(Z.b, 0, sizeof(Z));
202
203   for (i = GCM_BLOCK_SIZE; i-- > 0;)
204     {
205       uint8_t b = x->b[i];
206
207       gcm_gf_shift_4(&Z);
208       gcm_gf_add(&Z, &Z, &table[b & 0xf]);
209       gcm_gf_shift_4(&Z);
210       gcm_gf_add(&Z, &Z, &table[b >> 4]);
211     }
212   memcpy (x->b, Z.b, sizeof(Z));
213 }
214 # elif GCM_TABLE_BITS == 8
215 #  if HAVE_NATIVE_gcm_hash8
216
217 #define gcm_hash _nettle_gcm_hash8
218 void
219 _nettle_gcm_hash8 (const struct gcm_key *key, union nettle_block16 *x,
220                    size_t length, const uint8_t *data);
221 #  else /* !HAVE_NATIVE_gcm_hash8 */
222 static const uint16_t
223 shift_table[0x100] = {
224   W(00,00),W(01,c2),W(03,84),W(02,46),W(07,08),W(06,ca),W(04,8c),W(05,4e),
225   W(0e,10),W(0f,d2),W(0d,94),W(0c,56),W(09,18),W(08,da),W(0a,9c),W(0b,5e),
226   W(1c,20),W(1d,e2),W(1f,a4),W(1e,66),W(1b,28),W(1a,ea),W(18,ac),W(19,6e),
227   W(12,30),W(13,f2),W(11,b4),W(10,76),W(15,38),W(14,fa),W(16,bc),W(17,7e),
228   W(38,40),W(39,82),W(3b,c4),W(3a,06),W(3f,48),W(3e,8a),W(3c,cc),W(3d,0e),
229   W(36,50),W(37,92),W(35,d4),W(34,16),W(31,58),W(30,9a),W(32,dc),W(33,1e),
230   W(24,60),W(25,a2),W(27,e4),W(26,26),W(23,68),W(22,aa),W(20,ec),W(21,2e),
231   W(2a,70),W(2b,b2),W(29,f4),W(28,36),W(2d,78),W(2c,ba),W(2e,fc),W(2f,3e),
232   W(70,80),W(71,42),W(73,04),W(72,c6),W(77,88),W(76,4a),W(74,0c),W(75,ce),
233   W(7e,90),W(7f,52),W(7d,14),W(7c,d6),W(79,98),W(78,5a),W(7a,1c),W(7b,de),
234   W(6c,a0),W(6d,62),W(6f,24),W(6e,e6),W(6b,a8),W(6a,6a),W(68,2c),W(69,ee),
235   W(62,b0),W(63,72),W(61,34),W(60,f6),W(65,b8),W(64,7a),W(66,3c),W(67,fe),
236   W(48,c0),W(49,02),W(4b,44),W(4a,86),W(4f,c8),W(4e,0a),W(4c,4c),W(4d,8e),
237   W(46,d0),W(47,12),W(45,54),W(44,96),W(41,d8),W(40,1a),W(42,5c),W(43,9e),
238   W(54,e0),W(55,22),W(57,64),W(56,a6),W(53,e8),W(52,2a),W(50,6c),W(51,ae),
239   W(5a,f0),W(5b,32),W(59,74),W(58,b6),W(5d,f8),W(5c,3a),W(5e,7c),W(5f,be),
240   W(e1,00),W(e0,c2),W(e2,84),W(e3,46),W(e6,08),W(e7,ca),W(e5,8c),W(e4,4e),
241   W(ef,10),W(ee,d2),W(ec,94),W(ed,56),W(e8,18),W(e9,da),W(eb,9c),W(ea,5e),
242   W(fd,20),W(fc,e2),W(fe,a4),W(ff,66),W(fa,28),W(fb,ea),W(f9,ac),W(f8,6e),
243   W(f3,30),W(f2,f2),W(f0,b4),W(f1,76),W(f4,38),W(f5,fa),W(f7,bc),W(f6,7e),
244   W(d9,40),W(d8,82),W(da,c4),W(db,06),W(de,48),W(df,8a),W(dd,cc),W(dc,0e),
245   W(d7,50),W(d6,92),W(d4,d4),W(d5,16),W(d0,58),W(d1,9a),W(d3,dc),W(d2,1e),
246   W(c5,60),W(c4,a2),W(c6,e4),W(c7,26),W(c2,68),W(c3,aa),W(c1,ec),W(c0,2e),
247   W(cb,70),W(ca,b2),W(c8,f4),W(c9,36),W(cc,78),W(cd,ba),W(cf,fc),W(ce,3e),
248   W(91,80),W(90,42),W(92,04),W(93,c6),W(96,88),W(97,4a),W(95,0c),W(94,ce),
249   W(9f,90),W(9e,52),W(9c,14),W(9d,d6),W(98,98),W(99,5a),W(9b,1c),W(9a,de),
250   W(8d,a0),W(8c,62),W(8e,24),W(8f,e6),W(8a,a8),W(8b,6a),W(89,2c),W(88,ee),
251   W(83,b0),W(82,72),W(80,34),W(81,f6),W(84,b8),W(85,7a),W(87,3c),W(86,fe),
252   W(a9,c0),W(a8,02),W(aa,44),W(ab,86),W(ae,c8),W(af,0a),W(ad,4c),W(ac,8e),
253   W(a7,d0),W(a6,12),W(a4,54),W(a5,96),W(a0,d8),W(a1,1a),W(a3,5c),W(a2,9e),
254   W(b5,e0),W(b4,22),W(b6,64),W(b7,a6),W(b2,e8),W(b3,2a),W(b1,6c),W(b0,ae),
255   W(bb,f0),W(ba,32),W(b8,74),W(b9,b6),W(bc,f8),W(bd,3a),W(bf,7c),W(be,be),
256 };
257
258 static void
259 gcm_gf_shift_8(union nettle_block16 *x)
260 {
261   unsigned long *w = x->w;
262   unsigned long reduce;
263
264   /* Shift uses big-endian representation. */
265 #if WORDS_BIGENDIAN
266 # if SIZEOF_LONG == 4
267   reduce = shift_table[w[3] & 0xff];
268   w[3] = (w[3] >> 8) | ((w[2] & 0xff) << 24);
269   w[2] = (w[2] >> 8) | ((w[1] & 0xff) << 24);
270   w[1] = (w[1] >> 8) | ((w[0] & 0xff) << 24);
271   w[0] = (w[0] >> 8) ^ (reduce << 16);
272 # elif SIZEOF_LONG == 8
273   reduce = shift_table[w[1] & 0xff];
274   w[1] = (w[1] >> 8) | ((w[0] & 0xff) << 56);
275   w[0] = (w[0] >> 8) ^ (reduce << 48);
276 # else
277 #  error Unsupported word size. */
278 #endif
279 #else /* ! WORDS_BIGENDIAN */
280 # if SIZEOF_LONG == 4
281   reduce = shift_table[(w[3] >> 24) & 0xff];
282   w[3] = (w[3] << 8) | (w[2] >> 24);
283   w[2] = (w[2] << 8) | (w[1] >> 24);
284   w[1] = (w[1] << 8) | (w[0] >> 24);
285   w[0] = (w[0] << 8) ^ reduce;
286 # elif SIZEOF_LONG == 8
287   reduce = shift_table[(w[1] >> 56) & 0xff];
288   w[1] = (w[1] << 8) | (w[0] >> 56);
289   w[0] = (w[0] << 8) ^ reduce;
290 # else
291 #  error Unsupported word size. */
292 # endif
293 #endif /* ! WORDS_BIGENDIAN */
294 }
295
296 static void
297 gcm_gf_mul (union nettle_block16 *x, const union nettle_block16 *table)
298 {
299   union nettle_block16 Z;
300   unsigned i;
301
302   memcpy(Z.b, table[x->b[GCM_BLOCK_SIZE-1]].b, GCM_BLOCK_SIZE);
303
304   for (i = GCM_BLOCK_SIZE-2; i > 0; i--)
305     {
306       gcm_gf_shift_8(&Z);
307       gcm_gf_add(&Z, &Z, &table[x->b[i]]);
308     }
309   gcm_gf_shift_8(&Z);
310   gcm_gf_add(x, &Z, &table[x->b[0]]);
311 }
312 #  endif /* ! HAVE_NATIVE_gcm_hash8 */
313 # else /* GCM_TABLE_BITS != 8 */
314 #  error Unsupported table size. 
315 # endif /* GCM_TABLE_BITS != 8 */
316
317 #undef W
318
319 #endif /* GCM_TABLE_BITS */
320
321 /* Increment the rightmost 32 bits. */
322 #define INC32(block) INCREMENT(4, (block.b) + GCM_BLOCK_SIZE - 4)
323
324 /* Initialization of GCM.
325  * @ctx: The context of GCM
326  * @cipher: The context of the underlying block cipher
327  * @f: The underlying cipher encryption function
328  */
329 void
330 gcm_set_key(struct gcm_key *key,
331             const void *cipher, nettle_cipher_func *f)
332 {
333   /* Middle element if GCM_TABLE_BITS > 0, otherwise the first
334      element */
335   unsigned i = (1<<GCM_TABLE_BITS)/2;
336
337   /* H */  
338   memset(key->h[0].b, 0, GCM_BLOCK_SIZE);
339   f (cipher, GCM_BLOCK_SIZE, key->h[i].b, key->h[0].b);
340   
341 #if GCM_TABLE_BITS
342   /* Algorithm 3 from the gcm paper. First do powers of two, then do
343      the rest by adding. */
344   while (i /= 2)
345     gcm_gf_shift(&key->h[i], &key->h[2*i]);
346   for (i = 2; i < 1<<GCM_TABLE_BITS; i *= 2)
347     {
348       unsigned j;
349       for (j = 1; j < i; j++)
350         gcm_gf_add(&key->h[i+j], &key->h[i],&key->h[j]);
351     }
352 #endif
353 }
354
355 #ifndef gcm_hash
356 static void
357 gcm_hash(const struct gcm_key *key, union nettle_block16 *x,
358          size_t length, const uint8_t *data)
359 {
360   for (; length >= GCM_BLOCK_SIZE;
361        length -= GCM_BLOCK_SIZE, data += GCM_BLOCK_SIZE)
362     {
363       memxor (x->b, data, GCM_BLOCK_SIZE);
364       gcm_gf_mul (x, key->h);
365     }
366   if (length > 0)
367     {
368       memxor (x->b, data, length);
369       gcm_gf_mul (x, key->h);
370     }
371 }
372 #endif /* !gcm_hash */
373
374 static void
375 gcm_hash_sizes(const struct gcm_key *key, union nettle_block16 *x,
376                uint64_t auth_size, uint64_t data_size)
377 {
378   uint8_t buffer[GCM_BLOCK_SIZE];
379
380   data_size *= 8;
381   auth_size *= 8;
382
383   WRITE_UINT64 (buffer, auth_size);
384   WRITE_UINT64 (buffer + 8, data_size);
385
386   gcm_hash(key, x, GCM_BLOCK_SIZE, buffer);
387 }
388
389 /* NOTE: The key is needed only if length != GCM_IV_SIZE */
390 void
391 gcm_set_iv(struct gcm_ctx *ctx, const struct gcm_key *key,
392            size_t length, const uint8_t *iv)
393 {
394   if (length == GCM_IV_SIZE)
395     {
396       memcpy (ctx->iv.b, iv, GCM_BLOCK_SIZE - 4);
397       ctx->iv.b[GCM_BLOCK_SIZE - 4] = 0;
398       ctx->iv.b[GCM_BLOCK_SIZE - 3] = 0;
399       ctx->iv.b[GCM_BLOCK_SIZE - 2] = 0;
400       ctx->iv.b[GCM_BLOCK_SIZE - 1] = 1;
401     }
402   else
403     {
404       memset(ctx->iv.b, 0, GCM_BLOCK_SIZE);
405       gcm_hash(key, &ctx->iv, length, iv);
406       gcm_hash_sizes(key, &ctx->iv, 0, length);
407     }
408
409   memcpy (ctx->ctr.b, ctx->iv.b, GCM_BLOCK_SIZE);
410   INC32 (ctx->ctr);
411
412   /* Reset the rest of the message-dependent state. */
413   memset(ctx->x.b, 0, sizeof(ctx->x));
414   ctx->auth_size = ctx->data_size = 0;
415 }
416
417 void
418 gcm_update(struct gcm_ctx *ctx, const struct gcm_key *key,
419            size_t length, const uint8_t *data)
420 {
421   assert(ctx->auth_size % GCM_BLOCK_SIZE == 0);
422   assert(ctx->data_size == 0);
423
424   gcm_hash(key, &ctx->x, length, data);
425
426   ctx->auth_size += length;
427 }
428
429 static void
430 gcm_crypt(struct gcm_ctx *ctx, const void *cipher, nettle_cipher_func *f,
431           size_t length, uint8_t *dst, const uint8_t *src)
432 {
433   uint8_t buffer[GCM_BLOCK_SIZE];
434
435   if (src != dst)
436     {
437       for (; length >= GCM_BLOCK_SIZE;
438            (length -= GCM_BLOCK_SIZE,
439             src += GCM_BLOCK_SIZE, dst += GCM_BLOCK_SIZE))
440         {
441           f (cipher, GCM_BLOCK_SIZE, dst, ctx->ctr.b);
442           memxor (dst, src, GCM_BLOCK_SIZE);
443           INC32 (ctx->ctr);
444         }
445     }
446   else
447     {
448       for (; length >= GCM_BLOCK_SIZE;
449            (length -= GCM_BLOCK_SIZE,
450             src += GCM_BLOCK_SIZE, dst += GCM_BLOCK_SIZE))
451         {
452           f (cipher, GCM_BLOCK_SIZE, buffer, ctx->ctr.b);
453           memxor3 (dst, src, buffer, GCM_BLOCK_SIZE);
454           INC32 (ctx->ctr);
455         }
456     }
457   if (length > 0)
458     {
459       /* A final partial block */
460       f (cipher, GCM_BLOCK_SIZE, buffer, ctx->ctr.b);
461       memxor3 (dst, src, buffer, length);
462       INC32 (ctx->ctr);
463     }
464 }
465
466 void
467 gcm_encrypt (struct gcm_ctx *ctx, const struct gcm_key *key,
468              const void *cipher, nettle_cipher_func *f,
469              size_t length, uint8_t *dst, const uint8_t *src)
470 {
471   assert(ctx->data_size % GCM_BLOCK_SIZE == 0);
472
473   gcm_crypt(ctx, cipher, f, length, dst, src);
474   gcm_hash(key, &ctx->x, length, dst);
475
476   ctx->data_size += length;
477 }
478
479 void
480 gcm_decrypt(struct gcm_ctx *ctx, const struct gcm_key *key,
481             const void *cipher, nettle_cipher_func *f,
482             size_t length, uint8_t *dst, const uint8_t *src)
483 {
484   assert(ctx->data_size % GCM_BLOCK_SIZE == 0);
485
486   gcm_hash(key, &ctx->x, length, src);
487   gcm_crypt(ctx, cipher, f, length, dst, src);
488
489   ctx->data_size += length;
490 }
491
492 void
493 gcm_digest(struct gcm_ctx *ctx, const struct gcm_key *key,
494            const void *cipher, nettle_cipher_func *f,
495            size_t length, uint8_t *digest)
496 {
497   uint8_t buffer[GCM_BLOCK_SIZE];
498
499   assert (length <= GCM_BLOCK_SIZE);
500
501   gcm_hash_sizes(key, &ctx->x, ctx->auth_size, ctx->data_size);
502
503   f (cipher, GCM_BLOCK_SIZE, buffer, ctx->iv.b);
504   memxor3 (digest, ctx->x.b, buffer, length);
505
506   return;
507 }