ff0366d3181689cc5ebf28ff6652c39e0cd8cfa8
[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
51 struct CHACHA20_context_s;
52
53
54 typedef unsigned int (* chacha20_blocks_t)(u32 *state, const byte *src,
55                                            byte *dst, size_t bytes);
56
57 typedef struct CHACHA20_context_s
58 {
59   u32 input[CHACHA20_INPUT_LENGTH];
60   u32 pad[CHACHA20_INPUT_LENGTH];
61   chacha20_blocks_t blocks;
62   unsigned int unused; /* bytes in the pad.  */
63 } CHACHA20_context_t;
64
65
66 static void chacha20_setiv (void *context, const byte * iv, size_t ivlen);
67 static const char *selftest (void);
68 \f
69
70
71 #define QROUND(a,b,c,d)         \
72   do {                          \
73     a += b; d = rol(d ^ a, 16); \
74     c += d; b = rol(b ^ c, 12); \
75     a += b; d = rol(d ^ a, 8);  \
76     c += d; b = rol(b ^ c, 7);  \
77   } while (0)
78
79 #define QOUT(ai, bi, ci, di) \
80   DO_OUT(ai); DO_OUT(bi); DO_OUT(ci); DO_OUT(di)
81
82 static unsigned int
83 chacha20_blocks (u32 *state, const byte *src, byte *dst, size_t bytes)
84 {
85   u32 pad[CHACHA20_INPUT_LENGTH];
86   u32 inp[CHACHA20_INPUT_LENGTH];
87   unsigned int i;
88
89   /* Note: 'bytes' must be multiple of 64 and not zero. */
90
91   inp[0] = state[0];
92   inp[1] = state[1];
93   inp[2] = state[2];
94   inp[3] = state[3];
95   inp[4] = state[4];
96   inp[5] = state[5];
97   inp[6] = state[6];
98   inp[7] = state[7];
99   inp[8] = state[8];
100   inp[9] = state[9];
101   inp[10] = state[10];
102   inp[11] = state[11];
103   inp[12] = state[12];
104   inp[13] = state[13];
105   inp[14] = state[14];
106   inp[15] = state[15];
107
108   do
109     {
110       /* First round. */
111       pad[0] = inp[0];
112       pad[4] = inp[4];
113       pad[8] = inp[8];
114       pad[12] = inp[12];
115       QROUND (pad[0], pad[4], pad[8], pad[12]);
116       pad[1] = inp[1];
117       pad[5] = inp[5];
118       pad[9] = inp[9];
119       pad[13] = inp[13];
120       QROUND (pad[1], pad[5], pad[9], pad[13]);
121       pad[2] = inp[2];
122       pad[6] = inp[6];
123       pad[10] = inp[10];
124       pad[14] = inp[14];
125       QROUND (pad[2], pad[6], pad[10], pad[14]);
126       pad[3] = inp[3];
127       pad[7] = inp[7];
128       pad[11] = inp[11];
129       pad[15] = inp[15];
130       QROUND (pad[3], pad[7], pad[11], pad[15]);
131
132       QROUND (pad[0], pad[5], pad[10], pad[15]);
133       QROUND (pad[1], pad[6], pad[11], pad[12]);
134       QROUND (pad[2], pad[7], pad[8], pad[13]);
135       QROUND (pad[3], pad[4], pad[9], pad[14]);
136
137       for (i = 2; i < 20 - 2; i += 2)
138       {
139         QROUND (pad[0], pad[4], pad[8], pad[12]);
140         QROUND (pad[1], pad[5], pad[9], pad[13]);
141         QROUND (pad[2], pad[6], pad[10], pad[14]);
142         QROUND (pad[3], pad[7], pad[11], pad[15]);
143
144         QROUND (pad[0], pad[5], pad[10], pad[15]);
145         QROUND (pad[1], pad[6], pad[11], pad[12]);
146         QROUND (pad[2], pad[7], pad[8], pad[13]);
147         QROUND (pad[3], pad[4], pad[9], pad[14]);
148       }
149
150       QROUND (pad[0], pad[4], pad[8], pad[12]);
151       QROUND (pad[1], pad[5], pad[9], pad[13]);
152       QROUND (pad[2], pad[6], pad[10], pad[14]);
153       QROUND (pad[3], pad[7], pad[11], pad[15]);
154
155       if (src)
156         {
157 #define DO_OUT(idx) buf_put_le32(dst + (idx) * 4, \
158                                  (pad[idx] + inp[idx]) ^ \
159                                   buf_get_le32(src + (idx) * 4))
160           /* Last round. */
161           QROUND (pad[0], pad[5], pad[10], pad[15]);
162           QOUT(0, 5, 10, 15);
163           QROUND (pad[1], pad[6], pad[11], pad[12]);
164           QOUT(1, 6, 11, 12);
165           QROUND (pad[2], pad[7], pad[8], pad[13]);
166           QOUT(2, 7, 8, 13);
167           QROUND (pad[3], pad[4], pad[9], pad[14]);
168           QOUT(3, 4, 9, 14);
169 #undef DO_OUT
170         }
171       else
172         {
173 #define DO_OUT(idx) buf_put_le32(dst + (idx) * 4, pad[idx] + inp[idx])
174           /* Last round. */
175           QROUND (pad[0], pad[5], pad[10], pad[15]);
176           QOUT(0, 5, 10, 15);
177           QROUND (pad[1], pad[6], pad[11], pad[12]);
178           QOUT(1, 6, 11, 12);
179           QROUND (pad[2], pad[7], pad[8], pad[13]);
180           QOUT(2, 7, 8, 13);
181           QROUND (pad[3], pad[4], pad[9], pad[14]);
182           QOUT(3, 4, 9, 14);
183 #undef DO_OUT
184         }
185
186       /* Update counter. */
187       inp[13] += (!++inp[12]);
188
189       bytes -= CHACHA20_BLOCK_SIZE;
190       dst += CHACHA20_BLOCK_SIZE;
191       src += (src) ? CHACHA20_BLOCK_SIZE : 0;
192     }
193   while (bytes >= CHACHA20_BLOCK_SIZE);
194
195   state[12] = inp[12];
196   state[13] = inp[13];
197
198   /* burn_stack */
199   return (2 * CHACHA20_INPUT_LENGTH * sizeof(u32) + 6 * sizeof(void *));
200 }
201
202 #undef QROUND
203 #undef QOUT
204
205
206 static unsigned int
207 chacha20_core(u32 *dst, struct CHACHA20_context_s *ctx)
208 {
209   return ctx->blocks(ctx->input, NULL, (byte *)dst, CHACHA20_BLOCK_SIZE);
210 }
211
212
213 static void
214 chacha20_keysetup (CHACHA20_context_t * ctx, const byte * key,
215                    unsigned int keylen)
216 {
217   /* These constants are the little endian encoding of the string
218      "expand 32-byte k".  For the 128 bit variant, the "32" in that
219      string will be fixed up to "16".  */
220   ctx->input[0] = 0x61707865;        /* "apxe"  */
221   ctx->input[1] = 0x3320646e;        /* "3 dn"  */
222   ctx->input[2] = 0x79622d32;        /* "yb-2"  */
223   ctx->input[3] = 0x6b206574;        /* "k et"  */
224
225   ctx->input[4] = buf_get_le32 (key + 0);
226   ctx->input[5] = buf_get_le32 (key + 4);
227   ctx->input[6] = buf_get_le32 (key + 8);
228   ctx->input[7] = buf_get_le32 (key + 12);
229
230   if (keylen == CHACHA20_MAX_KEY_SIZE) /* 256 bits */
231     {
232       ctx->input[8] = buf_get_le32 (key + 16);
233       ctx->input[9] = buf_get_le32 (key + 20);
234       ctx->input[10] = buf_get_le32 (key + 24);
235       ctx->input[11] = buf_get_le32 (key + 28);
236     }
237   else /* 128 bits */
238     {
239       ctx->input[8] = ctx->input[4];
240       ctx->input[9] = ctx->input[5];
241       ctx->input[10] = ctx->input[6];
242       ctx->input[11] = ctx->input[7];
243
244       ctx->input[1] -= 0x02000000;        /* Change to "1 dn".  */
245       ctx->input[2] += 0x00000004;        /* Change to "yb-6".  */
246     }
247 }
248
249
250 static void
251 chacha20_ivsetup (CHACHA20_context_t * ctx, const byte * iv, size_t ivlen)
252 {
253   ctx->input[12] = 0;
254
255   if (ivlen == CHACHA20_MAX_IV_SIZE)
256     {
257       ctx->input[13] = buf_get_le32 (iv + 0);
258       ctx->input[14] = buf_get_le32 (iv + 4);
259       ctx->input[15] = buf_get_le32 (iv + 8);
260     }
261   else if (ivlen == CHACHA20_MIN_IV_SIZE)
262     {
263       ctx->input[13] = 0;
264       ctx->input[14] = buf_get_le32 (iv + 0);
265       ctx->input[15] = buf_get_le32 (iv + 4);
266     }
267   else
268     {
269       ctx->input[13] = 0;
270       ctx->input[14] = 0;
271       ctx->input[15] = 0;
272     }
273 }
274
275
276 static gcry_err_code_t
277 chacha20_do_setkey (CHACHA20_context_t * ctx,
278                     const byte * key, unsigned int keylen)
279 {
280   static int initialized;
281   static const char *selftest_failed;
282
283   if (!initialized)
284     {
285       initialized = 1;
286       selftest_failed = selftest ();
287       if (selftest_failed)
288         log_error ("CHACHA20 selftest failed (%s)\n", selftest_failed);
289     }
290   if (selftest_failed)
291     return GPG_ERR_SELFTEST_FAILED;
292
293   if (keylen != CHACHA20_MAX_KEY_SIZE && keylen != CHACHA20_MIN_KEY_SIZE)
294     return GPG_ERR_INV_KEYLEN;
295
296   ctx->blocks = chacha20_blocks;
297
298   chacha20_keysetup (ctx, key, keylen);
299
300   /* We default to a zero nonce.  */
301   chacha20_setiv (ctx, NULL, 0);
302
303   return 0;
304 }
305
306
307 static gcry_err_code_t
308 chacha20_setkey (void *context, const byte * key, unsigned int keylen)
309 {
310   CHACHA20_context_t *ctx = (CHACHA20_context_t *) context;
311   gcry_err_code_t rc = chacha20_do_setkey (ctx, key, keylen);
312   _gcry_burn_stack (4 + sizeof (void *) + 4 * sizeof (void *));
313   return rc;
314 }
315
316
317 static void
318 chacha20_setiv (void *context, const byte * iv, size_t ivlen)
319 {
320   CHACHA20_context_t *ctx = (CHACHA20_context_t *) context;
321
322   /* draft-nir-cfrg-chacha20-poly1305-02 defines 96-bit and 64-bit nonce. */
323   if (iv && ivlen != CHACHA20_MAX_IV_SIZE && ivlen != CHACHA20_MIN_IV_SIZE)
324     log_info ("WARNING: chacha20_setiv: bad ivlen=%u\n", (u32) ivlen);
325
326   if (iv && (ivlen == CHACHA20_MAX_IV_SIZE || ivlen == CHACHA20_MIN_IV_SIZE))
327     chacha20_ivsetup (ctx, iv, ivlen);
328   else
329     chacha20_ivsetup (ctx, NULL, 0);
330
331   /* Reset the unused pad bytes counter.  */
332   ctx->unused = 0;
333 }
334 \f
335
336
337 /* Note: This function requires LENGTH > 0.  */
338 static void
339 chacha20_do_encrypt_stream (CHACHA20_context_t * ctx,
340                             byte * outbuf, const byte * inbuf, size_t length)
341 {
342   unsigned int nburn, burn = 0;
343
344   if (ctx->unused)
345     {
346       unsigned char *p = (void *) ctx->pad;
347       size_t n;
348
349       gcry_assert (ctx->unused < CHACHA20_BLOCK_SIZE);
350
351       n = ctx->unused;
352       if (n > length)
353         n = length;
354       buf_xor (outbuf, inbuf, p + CHACHA20_BLOCK_SIZE - ctx->unused, n);
355       length -= n;
356       outbuf += n;
357       inbuf += n;
358       ctx->unused -= n;
359       if (!length)
360         return;
361       gcry_assert (!ctx->unused);
362     }
363
364   if (length >= CHACHA20_BLOCK_SIZE)
365     {
366       size_t nblocks = length / CHACHA20_BLOCK_SIZE;
367       size_t bytes = nblocks * CHACHA20_BLOCK_SIZE;
368       burn = ctx->blocks(ctx->input, inbuf, outbuf, bytes);
369       length -= bytes;
370       outbuf += bytes;
371       inbuf  += bytes;
372     }
373
374   if (length > 0)
375     {
376       nburn = chacha20_core (ctx->pad, ctx);
377       burn = nburn > burn ? nburn : burn;
378
379       buf_xor (outbuf, inbuf, ctx->pad, length);
380       ctx->unused = CHACHA20_BLOCK_SIZE - length;
381     }
382
383   _gcry_burn_stack (burn);
384 }
385
386
387 static void
388 chacha20_encrypt_stream (void *context, byte * outbuf, const byte * inbuf,
389                          size_t length)
390 {
391   CHACHA20_context_t *ctx = (CHACHA20_context_t *) context;
392
393   if (length)
394     chacha20_do_encrypt_stream (ctx, outbuf, inbuf, length);
395 }
396
397
398 static const char *
399 selftest (void)
400 {
401   CHACHA20_context_t ctx;
402   byte scratch[127 + 1];
403   byte buf[256 + 64 + 4];
404   int i;
405
406   /* From draft-strombergson-chacha-test-vectors */
407   static byte key_1[] = {
408     0xc4, 0x6e, 0xc1, 0xb1, 0x8c, 0xe8, 0xa8, 0x78,
409     0x72, 0x5a, 0x37, 0xe7, 0x80, 0xdf, 0xb7, 0x35,
410     0x1f, 0x68, 0xed, 0x2e, 0x19, 0x4c, 0x79, 0xfb,
411     0xc6, 0xae, 0xbe, 0xe1, 0xa6, 0x67, 0x97, 0x5d
412   };
413   static const byte nonce_1[] =
414     { 0x1a, 0xda, 0x31, 0xd5, 0xcf, 0x68, 0x82, 0x21 };
415   static const byte plaintext_1[127] = {
416     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
417     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
418     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
419     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
420     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
421     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
422     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
423     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
424     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
425     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
426     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
427     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
428     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
429     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
430     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
431     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
432   };
433   static const byte ciphertext_1[127] = {
434     0xf6, 0x3a, 0x89, 0xb7, 0x5c, 0x22, 0x71, 0xf9,
435     0x36, 0x88, 0x16, 0x54, 0x2b, 0xa5, 0x2f, 0x06,
436     0xed, 0x49, 0x24, 0x17, 0x92, 0x30, 0x2b, 0x00,
437     0xb5, 0xe8, 0xf8, 0x0a, 0xe9, 0xa4, 0x73, 0xaf,
438     0xc2, 0x5b, 0x21, 0x8f, 0x51, 0x9a, 0xf0, 0xfd,
439     0xd4, 0x06, 0x36, 0x2e, 0x8d, 0x69, 0xde, 0x7f,
440     0x54, 0xc6, 0x04, 0xa6, 0xe0, 0x0f, 0x35, 0x3f,
441     0x11, 0x0f, 0x77, 0x1b, 0xdc, 0xa8, 0xab, 0x92,
442     0xe5, 0xfb, 0xc3, 0x4e, 0x60, 0xa1, 0xd9, 0xa9,
443     0xdb, 0x17, 0x34, 0x5b, 0x0a, 0x40, 0x27, 0x36,
444     0x85, 0x3b, 0xf9, 0x10, 0xb0, 0x60, 0xbd, 0xf1,
445     0xf8, 0x97, 0xb6, 0x29, 0x0f, 0x01, 0xd1, 0x38,
446     0xae, 0x2c, 0x4c, 0x90, 0x22, 0x5b, 0xa9, 0xea,
447     0x14, 0xd5, 0x18, 0xf5, 0x59, 0x29, 0xde, 0xa0,
448     0x98, 0xca, 0x7a, 0x6c, 0xcf, 0xe6, 0x12, 0x27,
449     0x05, 0x3c, 0x84, 0xe4, 0x9a, 0x4a, 0x33
450   };
451
452   chacha20_setkey (&ctx, key_1, sizeof key_1);
453   chacha20_setiv (&ctx, nonce_1, sizeof nonce_1);
454   scratch[sizeof (scratch) - 1] = 0;
455   chacha20_encrypt_stream (&ctx, scratch, plaintext_1, sizeof plaintext_1);
456   if (memcmp (scratch, ciphertext_1, sizeof ciphertext_1))
457     return "ChaCha20 encryption test 1 failed.";
458   if (scratch[sizeof (scratch) - 1])
459     return "ChaCha20 wrote too much.";
460   chacha20_setkey (&ctx, key_1, sizeof (key_1));
461   chacha20_setiv (&ctx, nonce_1, sizeof nonce_1);
462   chacha20_encrypt_stream (&ctx, scratch, scratch, sizeof plaintext_1);
463   if (memcmp (scratch, plaintext_1, sizeof plaintext_1))
464     return "ChaCha20 decryption test 1 failed.";
465
466   for (i = 0; i < sizeof buf; i++)
467     buf[i] = i;
468   chacha20_setkey (&ctx, key_1, sizeof key_1);
469   chacha20_setiv (&ctx, nonce_1, sizeof nonce_1);
470   /*encrypt */
471   chacha20_encrypt_stream (&ctx, buf, buf, sizeof buf);
472   /*decrypt */
473   chacha20_setkey (&ctx, key_1, sizeof key_1);
474   chacha20_setiv (&ctx, nonce_1, sizeof nonce_1);
475   chacha20_encrypt_stream (&ctx, buf, buf, 1);
476   chacha20_encrypt_stream (&ctx, buf + 1, buf + 1, (sizeof buf) - 1 - 1);
477   chacha20_encrypt_stream (&ctx, buf + (sizeof buf) - 1,
478                            buf + (sizeof buf) - 1, 1);
479   for (i = 0; i < sizeof buf; i++)
480     if (buf[i] != (byte) i)
481       return "ChaCha20 encryption test 2 failed.";
482
483   return NULL;
484 }
485
486
487 gcry_cipher_spec_t _gcry_cipher_spec_chacha20 = {
488   GCRY_CIPHER_CHACHA20,
489   {0, 0},                       /* flags */
490   "CHACHA20",                   /* name */
491   NULL,                         /* aliases */
492   NULL,                         /* oids */
493   1,                            /* blocksize in bytes. */
494   CHACHA20_MAX_KEY_SIZE * 8,    /* standard key length in bits. */
495   sizeof (CHACHA20_context_t),
496   chacha20_setkey,
497   NULL,
498   NULL,
499   chacha20_encrypt_stream,
500   chacha20_encrypt_stream,
501   NULL,
502   NULL,
503   chacha20_setiv
504 };