Add Poly1305 MAC
[libgcrypt.git] / cipher / chacha20.c
1 /* chacha20.c  -  Bernstein's ChaCha20 cipher
2  * Copyright (C) 2014 Jussi Kivilinna <jussi.kivilinna@iki.fi>
3  *
4  * This file is part of Libgcrypt.
5  *
6  * Libgcrypt is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser general Public License as
8  * published by the Free Software Foundation; either version 2.1 of
9  * the License, or (at your option) any later version.
10  *
11  * Libgcrypt is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
18  *
19  * For a description of the algorithm, see:
20  *   http://cr.yp.to/chacha.html
21  */
22
23 /* The code is based on salsa20.c and public-domain ChaCha implementations:
24  *  chacha-ref.c version 20080118
25  *  D. J. Bernstein
26  *  Public domain.
27  * and
28  *  Andrew Moon
29  *  https://github.com/floodyberry/chacha-opt
30  */
31
32
33 #include <config.h>
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <string.h>
37 #include "types.h"
38 #include "g10lib.h"
39 #include "cipher.h"
40 #include "bufhelp.h"
41
42
43 #define CHACHA20_MIN_KEY_SIZE 16        /* Bytes.  */
44 #define CHACHA20_MAX_KEY_SIZE 32        /* Bytes.  */
45 #define CHACHA20_BLOCK_SIZE   64        /* Bytes.  */
46 #define CHACHA20_MIN_IV_SIZE   8        /* Bytes.  */
47 #define CHACHA20_MAX_IV_SIZE  12        /* Bytes.  */
48 #define CHACHA20_INPUT_LENGTH (CHACHA20_BLOCK_SIZE / 4)
49
50 /* USE_SSSE3 indicates whether to compile with Intel SSSE3 code. */
51 #undef USE_SSSE3
52 #if defined(__x86_64__) && defined(HAVE_COMPATIBLE_GCC_AMD64_PLATFORM_AS) && \
53     defined(HAVE_GCC_INLINE_ASM_SSSE3)
54 # define USE_SSSE3 1
55 #endif
56
57 /* USE_AVX2 indicates whether to compile with Intel AVX2 code. */
58 #undef USE_AVX2
59 #if defined(__x86_64__) && defined(HAVE_COMPATIBLE_GCC_AMD64_PLATFORM_AS) && \
60     defined(ENABLE_AVX2_SUPPORT)
61 # define USE_AVX2 1
62 #endif
63
64
65 struct CHACHA20_context_s;
66
67
68 typedef unsigned int (* chacha20_blocks_t)(u32 *state, const byte *src,
69                                            byte *dst, size_t bytes);
70
71 typedef struct CHACHA20_context_s
72 {
73   u32 input[CHACHA20_INPUT_LENGTH];
74   u32 pad[CHACHA20_INPUT_LENGTH];
75   chacha20_blocks_t blocks;
76   unsigned int unused; /* bytes in the pad.  */
77 } CHACHA20_context_t;
78
79
80 #ifdef USE_SSSE3
81
82 unsigned int _gcry_chacha20_amd64_ssse3_blocks(u32 *state, const byte *in,
83                                                byte *out, size_t bytes);
84
85 #endif /* USE_SSSE3 */
86
87 #ifdef USE_AVX2
88
89 unsigned int _gcry_chacha20_amd64_avx2_blocks(u32 *state, const byte *in,
90                                               byte *out, size_t bytes);
91
92 #endif /* USE_AVX2 */
93
94
95 static void chacha20_setiv (void *context, const byte * iv, size_t ivlen);
96 static const char *selftest (void);
97 \f
98
99
100 #define QROUND(a,b,c,d)         \
101   do {                          \
102     a += b; d = rol(d ^ a, 16); \
103     c += d; b = rol(b ^ c, 12); \
104     a += b; d = rol(d ^ a, 8);  \
105     c += d; b = rol(b ^ c, 7);  \
106   } while (0)
107
108 #define QOUT(ai, bi, ci, di) \
109   DO_OUT(ai); DO_OUT(bi); DO_OUT(ci); DO_OUT(di)
110
111 static unsigned int
112 chacha20_blocks (u32 *state, const byte *src, byte *dst, size_t bytes)
113 {
114   u32 pad[CHACHA20_INPUT_LENGTH];
115   u32 inp[CHACHA20_INPUT_LENGTH];
116   unsigned int i;
117
118   /* Note: 'bytes' must be multiple of 64 and not zero. */
119
120   inp[0] = state[0];
121   inp[1] = state[1];
122   inp[2] = state[2];
123   inp[3] = state[3];
124   inp[4] = state[4];
125   inp[5] = state[5];
126   inp[6] = state[6];
127   inp[7] = state[7];
128   inp[8] = state[8];
129   inp[9] = state[9];
130   inp[10] = state[10];
131   inp[11] = state[11];
132   inp[12] = state[12];
133   inp[13] = state[13];
134   inp[14] = state[14];
135   inp[15] = state[15];
136
137   do
138     {
139       /* First round. */
140       pad[0] = inp[0];
141       pad[4] = inp[4];
142       pad[8] = inp[8];
143       pad[12] = inp[12];
144       QROUND (pad[0], pad[4], pad[8], pad[12]);
145       pad[1] = inp[1];
146       pad[5] = inp[5];
147       pad[9] = inp[9];
148       pad[13] = inp[13];
149       QROUND (pad[1], pad[5], pad[9], pad[13]);
150       pad[2] = inp[2];
151       pad[6] = inp[6];
152       pad[10] = inp[10];
153       pad[14] = inp[14];
154       QROUND (pad[2], pad[6], pad[10], pad[14]);
155       pad[3] = inp[3];
156       pad[7] = inp[7];
157       pad[11] = inp[11];
158       pad[15] = inp[15];
159       QROUND (pad[3], pad[7], pad[11], pad[15]);
160
161       QROUND (pad[0], pad[5], pad[10], pad[15]);
162       QROUND (pad[1], pad[6], pad[11], pad[12]);
163       QROUND (pad[2], pad[7], pad[8], pad[13]);
164       QROUND (pad[3], pad[4], pad[9], pad[14]);
165
166       for (i = 2; i < 20 - 2; i += 2)
167       {
168         QROUND (pad[0], pad[4], pad[8], pad[12]);
169         QROUND (pad[1], pad[5], pad[9], pad[13]);
170         QROUND (pad[2], pad[6], pad[10], pad[14]);
171         QROUND (pad[3], pad[7], pad[11], pad[15]);
172
173         QROUND (pad[0], pad[5], pad[10], pad[15]);
174         QROUND (pad[1], pad[6], pad[11], pad[12]);
175         QROUND (pad[2], pad[7], pad[8], pad[13]);
176         QROUND (pad[3], pad[4], pad[9], pad[14]);
177       }
178
179       QROUND (pad[0], pad[4], pad[8], pad[12]);
180       QROUND (pad[1], pad[5], pad[9], pad[13]);
181       QROUND (pad[2], pad[6], pad[10], pad[14]);
182       QROUND (pad[3], pad[7], pad[11], pad[15]);
183
184       if (src)
185         {
186 #define DO_OUT(idx) buf_put_le32(dst + (idx) * 4, \
187                                  (pad[idx] + inp[idx]) ^ \
188                                   buf_get_le32(src + (idx) * 4))
189           /* Last round. */
190           QROUND (pad[0], pad[5], pad[10], pad[15]);
191           QOUT(0, 5, 10, 15);
192           QROUND (pad[1], pad[6], pad[11], pad[12]);
193           QOUT(1, 6, 11, 12);
194           QROUND (pad[2], pad[7], pad[8], pad[13]);
195           QOUT(2, 7, 8, 13);
196           QROUND (pad[3], pad[4], pad[9], pad[14]);
197           QOUT(3, 4, 9, 14);
198 #undef DO_OUT
199         }
200       else
201         {
202 #define DO_OUT(idx) buf_put_le32(dst + (idx) * 4, pad[idx] + inp[idx])
203           /* Last round. */
204           QROUND (pad[0], pad[5], pad[10], pad[15]);
205           QOUT(0, 5, 10, 15);
206           QROUND (pad[1], pad[6], pad[11], pad[12]);
207           QOUT(1, 6, 11, 12);
208           QROUND (pad[2], pad[7], pad[8], pad[13]);
209           QOUT(2, 7, 8, 13);
210           QROUND (pad[3], pad[4], pad[9], pad[14]);
211           QOUT(3, 4, 9, 14);
212 #undef DO_OUT
213         }
214
215       /* Update counter. */
216       inp[13] += (!++inp[12]);
217
218       bytes -= CHACHA20_BLOCK_SIZE;
219       dst += CHACHA20_BLOCK_SIZE;
220       src += (src) ? CHACHA20_BLOCK_SIZE : 0;
221     }
222   while (bytes >= CHACHA20_BLOCK_SIZE);
223
224   state[12] = inp[12];
225   state[13] = inp[13];
226
227   /* burn_stack */
228   return (2 * CHACHA20_INPUT_LENGTH * sizeof(u32) + 6 * sizeof(void *));
229 }
230
231 #undef QROUND
232 #undef QOUT
233
234
235 static unsigned int
236 chacha20_core(u32 *dst, struct CHACHA20_context_s *ctx)
237 {
238   return ctx->blocks(ctx->input, NULL, (byte *)dst, CHACHA20_BLOCK_SIZE);
239 }
240
241
242 static void
243 chacha20_keysetup (CHACHA20_context_t * ctx, const byte * key,
244                    unsigned int keylen)
245 {
246   /* These constants are the little endian encoding of the string
247      "expand 32-byte k".  For the 128 bit variant, the "32" in that
248      string will be fixed up to "16".  */
249   ctx->input[0] = 0x61707865;        /* "apxe"  */
250   ctx->input[1] = 0x3320646e;        /* "3 dn"  */
251   ctx->input[2] = 0x79622d32;        /* "yb-2"  */
252   ctx->input[3] = 0x6b206574;        /* "k et"  */
253
254   ctx->input[4] = buf_get_le32 (key + 0);
255   ctx->input[5] = buf_get_le32 (key + 4);
256   ctx->input[6] = buf_get_le32 (key + 8);
257   ctx->input[7] = buf_get_le32 (key + 12);
258
259   if (keylen == CHACHA20_MAX_KEY_SIZE) /* 256 bits */
260     {
261       ctx->input[8] = buf_get_le32 (key + 16);
262       ctx->input[9] = buf_get_le32 (key + 20);
263       ctx->input[10] = buf_get_le32 (key + 24);
264       ctx->input[11] = buf_get_le32 (key + 28);
265     }
266   else /* 128 bits */
267     {
268       ctx->input[8] = ctx->input[4];
269       ctx->input[9] = ctx->input[5];
270       ctx->input[10] = ctx->input[6];
271       ctx->input[11] = ctx->input[7];
272
273       ctx->input[1] -= 0x02000000;        /* Change to "1 dn".  */
274       ctx->input[2] += 0x00000004;        /* Change to "yb-6".  */
275     }
276 }
277
278
279 static void
280 chacha20_ivsetup (CHACHA20_context_t * ctx, const byte * iv, size_t ivlen)
281 {
282   ctx->input[12] = 0;
283
284   if (ivlen == CHACHA20_MAX_IV_SIZE)
285     {
286       ctx->input[13] = buf_get_le32 (iv + 0);
287       ctx->input[14] = buf_get_le32 (iv + 4);
288       ctx->input[15] = buf_get_le32 (iv + 8);
289     }
290   else if (ivlen == CHACHA20_MIN_IV_SIZE)
291     {
292       ctx->input[13] = 0;
293       ctx->input[14] = buf_get_le32 (iv + 0);
294       ctx->input[15] = buf_get_le32 (iv + 4);
295     }
296   else
297     {
298       ctx->input[13] = 0;
299       ctx->input[14] = 0;
300       ctx->input[15] = 0;
301     }
302 }
303
304
305 static gcry_err_code_t
306 chacha20_do_setkey (CHACHA20_context_t * ctx,
307                     const byte * key, unsigned int keylen)
308 {
309   static int initialized;
310   static const char *selftest_failed;
311   unsigned int features = _gcry_get_hw_features ();
312
313   if (!initialized)
314     {
315       initialized = 1;
316       selftest_failed = selftest ();
317       if (selftest_failed)
318         log_error ("CHACHA20 selftest failed (%s)\n", selftest_failed);
319     }
320   if (selftest_failed)
321     return GPG_ERR_SELFTEST_FAILED;
322
323   if (keylen != CHACHA20_MAX_KEY_SIZE && keylen != CHACHA20_MIN_KEY_SIZE)
324     return GPG_ERR_INV_KEYLEN;
325
326   ctx->blocks = chacha20_blocks;
327 #ifdef USE_SSSE3
328   if (features & HWF_INTEL_SSSE3)
329     ctx->blocks = _gcry_chacha20_amd64_ssse3_blocks;
330 #endif
331 #ifdef USE_AVX2
332   if (features & HWF_INTEL_AVX2)
333     ctx->blocks = _gcry_chacha20_amd64_avx2_blocks;
334 #endif
335
336   (void)features;
337
338   chacha20_keysetup (ctx, key, keylen);
339
340   /* We default to a zero nonce.  */
341   chacha20_setiv (ctx, NULL, 0);
342
343   return 0;
344 }
345
346
347 static gcry_err_code_t
348 chacha20_setkey (void *context, const byte * key, unsigned int keylen)
349 {
350   CHACHA20_context_t *ctx = (CHACHA20_context_t *) context;
351   gcry_err_code_t rc = chacha20_do_setkey (ctx, key, keylen);
352   _gcry_burn_stack (4 + sizeof (void *) + 4 * sizeof (void *));
353   return rc;
354 }
355
356
357 static void
358 chacha20_setiv (void *context, const byte * iv, size_t ivlen)
359 {
360   CHACHA20_context_t *ctx = (CHACHA20_context_t *) context;
361
362   /* draft-nir-cfrg-chacha20-poly1305-02 defines 96-bit and 64-bit nonce. */
363   if (iv && ivlen != CHACHA20_MAX_IV_SIZE && ivlen != CHACHA20_MIN_IV_SIZE)
364     log_info ("WARNING: chacha20_setiv: bad ivlen=%u\n", (u32) ivlen);
365
366   if (iv && (ivlen == CHACHA20_MAX_IV_SIZE || ivlen == CHACHA20_MIN_IV_SIZE))
367     chacha20_ivsetup (ctx, iv, ivlen);
368   else
369     chacha20_ivsetup (ctx, NULL, 0);
370
371   /* Reset the unused pad bytes counter.  */
372   ctx->unused = 0;
373 }
374 \f
375
376
377 /* Note: This function requires LENGTH > 0.  */
378 static void
379 chacha20_do_encrypt_stream (CHACHA20_context_t * ctx,
380                             byte * outbuf, const byte * inbuf, size_t length)
381 {
382   unsigned int nburn, burn = 0;
383
384   if (ctx->unused)
385     {
386       unsigned char *p = (void *) ctx->pad;
387       size_t n;
388
389       gcry_assert (ctx->unused < CHACHA20_BLOCK_SIZE);
390
391       n = ctx->unused;
392       if (n > length)
393         n = length;
394       buf_xor (outbuf, inbuf, p + CHACHA20_BLOCK_SIZE - ctx->unused, n);
395       length -= n;
396       outbuf += n;
397       inbuf += n;
398       ctx->unused -= n;
399       if (!length)
400         return;
401       gcry_assert (!ctx->unused);
402     }
403
404   if (length >= CHACHA20_BLOCK_SIZE)
405     {
406       size_t nblocks = length / CHACHA20_BLOCK_SIZE;
407       size_t bytes = nblocks * CHACHA20_BLOCK_SIZE;
408       burn = ctx->blocks(ctx->input, inbuf, outbuf, bytes);
409       length -= bytes;
410       outbuf += bytes;
411       inbuf  += bytes;
412     }
413
414   if (length > 0)
415     {
416       nburn = chacha20_core (ctx->pad, ctx);
417       burn = nburn > burn ? nburn : burn;
418
419       buf_xor (outbuf, inbuf, ctx->pad, length);
420       ctx->unused = CHACHA20_BLOCK_SIZE - length;
421     }
422
423   _gcry_burn_stack (burn);
424 }
425
426
427 static void
428 chacha20_encrypt_stream (void *context, byte * outbuf, const byte * inbuf,
429                          size_t length)
430 {
431   CHACHA20_context_t *ctx = (CHACHA20_context_t *) context;
432
433   if (length)
434     chacha20_do_encrypt_stream (ctx, outbuf, inbuf, length);
435 }
436
437
438 static const char *
439 selftest (void)
440 {
441   CHACHA20_context_t ctx;
442   byte scratch[127 + 1];
443   byte buf[512 + 64 + 4];
444   int i;
445
446   /* From draft-strombergson-chacha-test-vectors */
447   static byte key_1[] = {
448     0xc4, 0x6e, 0xc1, 0xb1, 0x8c, 0xe8, 0xa8, 0x78,
449     0x72, 0x5a, 0x37, 0xe7, 0x80, 0xdf, 0xb7, 0x35,
450     0x1f, 0x68, 0xed, 0x2e, 0x19, 0x4c, 0x79, 0xfb,
451     0xc6, 0xae, 0xbe, 0xe1, 0xa6, 0x67, 0x97, 0x5d
452   };
453   static const byte nonce_1[] =
454     { 0x1a, 0xda, 0x31, 0xd5, 0xcf, 0x68, 0x82, 0x21 };
455   static const byte plaintext_1[127] = {
456     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
457     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
458     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
459     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
460     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
461     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
462     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
463     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
464     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
465     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
466     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
467     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
468     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
469     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
470     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
471     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
472   };
473   static const byte ciphertext_1[127] = {
474     0xf6, 0x3a, 0x89, 0xb7, 0x5c, 0x22, 0x71, 0xf9,
475     0x36, 0x88, 0x16, 0x54, 0x2b, 0xa5, 0x2f, 0x06,
476     0xed, 0x49, 0x24, 0x17, 0x92, 0x30, 0x2b, 0x00,
477     0xb5, 0xe8, 0xf8, 0x0a, 0xe9, 0xa4, 0x73, 0xaf,
478     0xc2, 0x5b, 0x21, 0x8f, 0x51, 0x9a, 0xf0, 0xfd,
479     0xd4, 0x06, 0x36, 0x2e, 0x8d, 0x69, 0xde, 0x7f,
480     0x54, 0xc6, 0x04, 0xa6, 0xe0, 0x0f, 0x35, 0x3f,
481     0x11, 0x0f, 0x77, 0x1b, 0xdc, 0xa8, 0xab, 0x92,
482     0xe5, 0xfb, 0xc3, 0x4e, 0x60, 0xa1, 0xd9, 0xa9,
483     0xdb, 0x17, 0x34, 0x5b, 0x0a, 0x40, 0x27, 0x36,
484     0x85, 0x3b, 0xf9, 0x10, 0xb0, 0x60, 0xbd, 0xf1,
485     0xf8, 0x97, 0xb6, 0x29, 0x0f, 0x01, 0xd1, 0x38,
486     0xae, 0x2c, 0x4c, 0x90, 0x22, 0x5b, 0xa9, 0xea,
487     0x14, 0xd5, 0x18, 0xf5, 0x59, 0x29, 0xde, 0xa0,
488     0x98, 0xca, 0x7a, 0x6c, 0xcf, 0xe6, 0x12, 0x27,
489     0x05, 0x3c, 0x84, 0xe4, 0x9a, 0x4a, 0x33
490   };
491
492   chacha20_setkey (&ctx, key_1, sizeof key_1);
493   chacha20_setiv (&ctx, nonce_1, sizeof nonce_1);
494   scratch[sizeof (scratch) - 1] = 0;
495   chacha20_encrypt_stream (&ctx, scratch, plaintext_1, sizeof plaintext_1);
496   if (memcmp (scratch, ciphertext_1, sizeof ciphertext_1))
497     return "ChaCha20 encryption test 1 failed.";
498   if (scratch[sizeof (scratch) - 1])
499     return "ChaCha20 wrote too much.";
500   chacha20_setkey (&ctx, key_1, sizeof (key_1));
501   chacha20_setiv (&ctx, nonce_1, sizeof nonce_1);
502   chacha20_encrypt_stream (&ctx, scratch, scratch, sizeof plaintext_1);
503   if (memcmp (scratch, plaintext_1, sizeof plaintext_1))
504     return "ChaCha20 decryption test 1 failed.";
505
506   for (i = 0; i < sizeof buf; i++)
507     buf[i] = i;
508   chacha20_setkey (&ctx, key_1, sizeof key_1);
509   chacha20_setiv (&ctx, nonce_1, sizeof nonce_1);
510   /*encrypt */
511   chacha20_encrypt_stream (&ctx, buf, buf, sizeof buf);
512   /*decrypt */
513   chacha20_setkey (&ctx, key_1, sizeof key_1);
514   chacha20_setiv (&ctx, nonce_1, sizeof nonce_1);
515   chacha20_encrypt_stream (&ctx, buf, buf, 1);
516   chacha20_encrypt_stream (&ctx, buf + 1, buf + 1, (sizeof buf) - 1 - 1);
517   chacha20_encrypt_stream (&ctx, buf + (sizeof buf) - 1,
518                            buf + (sizeof buf) - 1, 1);
519   for (i = 0; i < sizeof buf; i++)
520     if (buf[i] != (byte) i)
521       return "ChaCha20 encryption test 2 failed.";
522
523   return NULL;
524 }
525
526
527 gcry_cipher_spec_t _gcry_cipher_spec_chacha20 = {
528   GCRY_CIPHER_CHACHA20,
529   {0, 0},                       /* flags */
530   "CHACHA20",                   /* name */
531   NULL,                         /* aliases */
532   NULL,                         /* oids */
533   1,                            /* blocksize in bytes. */
534   CHACHA20_MAX_KEY_SIZE * 8,    /* standard key length in bits. */
535   sizeof (CHACHA20_context_t),
536   chacha20_setkey,
537   NULL,
538   NULL,
539   chacha20_encrypt_stream,
540   chacha20_encrypt_stream,
541   NULL,
542   NULL,
543   chacha20_setiv
544 };