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