Add crypto hash SM3.
[libgcrypt.git] / cipher / salsa20.c
1 /* salsa20.c  -  Bernstein's Salsa20 cipher
2  * Copyright (C) 2012 Simon Josefsson, Niels Möller
3  * Copyright (C) 2013 g10 Code GmbH
4  *
5  * This file is part of Libgcrypt.
6  *
7  * Libgcrypt is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU Lesser general Public License as
9  * published by the Free Software Foundation; either version 2.1 of
10  * the License, or (at your option) any later version.
11  *
12  * Libgcrypt is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
19  *
20  * For a description of the algorithm, see:
21  *   http://cr.yp.to/snuffle/spec.pdf
22  *   http://cr.yp.to/snuffle/design.pdf
23  */
24
25 /* The code is based on the code in Nettle
26    (git commit id 9d2d8ddaee35b91a4e1a32ae77cba04bea3480e7)
27    which in turn is based on
28    salsa20-ref.c version 20051118
29    D. J. Bernstein
30    Public domain.
31 */
32
33
34 #include <config.h>
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include "types.h"
39 #include "g10lib.h"
40 #include "cipher.h"
41 #include "bufhelp.h"
42
43
44 /* USE_AMD64 indicates whether to compile with AMD64 code. */
45 #undef USE_AMD64
46 #if defined(__x86_64__) && (defined(HAVE_COMPATIBLE_GCC_AMD64_PLATFORM_AS) || \
47     defined(HAVE_COMPATIBLE_GCC_WIN64_PLATFORM_AS))
48 # define USE_AMD64 1
49 #endif
50
51 /* USE_ARM_NEON_ASM indicates whether to enable ARM NEON assembly code. */
52 #undef USE_ARM_NEON_ASM
53 #ifdef ENABLE_NEON_SUPPORT
54 # if defined(HAVE_ARM_ARCH_V6) && defined(__ARMEL__) \
55      && defined(HAVE_COMPATIBLE_GCC_ARM_PLATFORM_AS) \
56      && defined(HAVE_GCC_INLINE_ASM_NEON)
57 #  define USE_ARM_NEON_ASM 1
58 # endif
59 #endif /*ENABLE_NEON_SUPPORT*/
60
61
62 #define SALSA20_MIN_KEY_SIZE 16  /* Bytes.  */
63 #define SALSA20_MAX_KEY_SIZE 32  /* Bytes.  */
64 #define SALSA20_BLOCK_SIZE   64  /* Bytes.  */
65 #define SALSA20_IV_SIZE       8  /* Bytes.  */
66 #define SALSA20_INPUT_LENGTH 16  /* Bytes.  */
67
68 /* Number of rounds.  The standard uses 20 rounds.  In any case the
69    number of rounds must be even.  */
70 #define SALSA20_ROUNDS       20
71 #define SALSA20R12_ROUNDS    12
72
73
74 struct SALSA20_context_s;
75
76 typedef unsigned int (*salsa20_core_t) (u32 *dst, struct SALSA20_context_s *ctx,
77                                         unsigned int rounds);
78 typedef void (* salsa20_keysetup_t)(struct SALSA20_context_s *ctx,
79                                     const byte *key, int keylen);
80 typedef void (* salsa20_ivsetup_t)(struct SALSA20_context_s *ctx,
81                                    const byte *iv);
82
83 typedef struct SALSA20_context_s
84 {
85   /* Indices 1-4 and 11-14 holds the key (two identical copies for the
86      shorter key size), indices 0, 5, 10, 15 are constant, indices 6, 7
87      are the IV, and indices 8, 9 are the block counter:
88
89      C K K K
90      K C I I
91      B B C K
92      K K K C
93   */
94   u32 input[SALSA20_INPUT_LENGTH];
95   u32 pad[SALSA20_INPUT_LENGTH];
96   unsigned int unused; /* bytes in the pad.  */
97 #ifdef USE_ARM_NEON_ASM
98   int use_neon;
99 #endif
100   salsa20_keysetup_t keysetup;
101   salsa20_ivsetup_t ivsetup;
102   salsa20_core_t core;
103 } SALSA20_context_t;
104
105
106 /* The masking of the right shift is needed to allow n == 0 (using
107    just 32 - n and 64 - n results in undefined behaviour). Most uses
108    of these macros use a constant and non-zero rotation count. */
109 #define ROTL32(n,x) (((x)<<(n)) | ((x)>>((-(n)&31))))
110
111
112 #define LE_SWAP32(v) le_bswap32(v)
113
114 #define LE_READ_UINT32(p) buf_get_le32(p)
115
116
117 static void salsa20_setiv (void *context, const byte *iv, size_t ivlen);
118 static const char *selftest (void);
119
120
121 #ifdef USE_AMD64
122
123 /* Assembly implementations use SystemV ABI, ABI conversion and additional
124  * stack to store XMM6-XMM15 needed on Win64. */
125 #ifdef HAVE_COMPATIBLE_GCC_WIN64_PLATFORM_AS
126 # define ASM_FUNC_ABI __attribute__((sysv_abi))
127 # define ASM_EXTRA_STACK (10 * 16)
128 #else
129 # define ASM_FUNC_ABI
130 # define ASM_EXTRA_STACK 0
131 #endif
132
133 /* AMD64 assembly implementations of Salsa20. */
134 void _gcry_salsa20_amd64_keysetup(u32 *ctxinput, const void *key, int keybits)
135                                  ASM_FUNC_ABI;
136 void _gcry_salsa20_amd64_ivsetup(u32 *ctxinput, const void *iv)
137                                 ASM_FUNC_ABI;
138 unsigned int
139 _gcry_salsa20_amd64_encrypt_blocks(u32 *ctxinput, const void *src, void *dst,
140                                    size_t len, int rounds) ASM_FUNC_ABI;
141
142 static void
143 salsa20_keysetup(SALSA20_context_t *ctx, const byte *key, int keylen)
144 {
145   _gcry_salsa20_amd64_keysetup(ctx->input, key, keylen * 8);
146 }
147
148 static void
149 salsa20_ivsetup(SALSA20_context_t *ctx, const byte *iv)
150 {
151   _gcry_salsa20_amd64_ivsetup(ctx->input, iv);
152 }
153
154 static unsigned int
155 salsa20_core (u32 *dst, SALSA20_context_t *ctx, unsigned int rounds)
156 {
157   memset(dst, 0, SALSA20_BLOCK_SIZE);
158   return _gcry_salsa20_amd64_encrypt_blocks(ctx->input, dst, dst, 1, rounds)
159          + ASM_EXTRA_STACK;
160 }
161
162 #else /* USE_AMD64 */
163
164 \f
165
166 #if 0
167 # define SALSA20_CORE_DEBUG(i) do {             \
168     unsigned debug_j;                           \
169     for (debug_j = 0; debug_j < 16; debug_j++)  \
170       {                                         \
171         if (debug_j == 0)                       \
172           fprintf(stderr, "%2d:", (i));         \
173         else if (debug_j % 4 == 0)              \
174           fprintf(stderr, "\n   ");             \
175         fprintf(stderr, " %8x", pad[debug_j]);  \
176       }                                         \
177     fprintf(stderr, "\n");                      \
178   } while (0)
179 #else
180 # define SALSA20_CORE_DEBUG(i)
181 #endif
182
183 #define QROUND(x0, x1, x2, x3)      \
184   do {                              \
185     x1 ^= ROTL32 ( 7, x0 + x3);     \
186     x2 ^= ROTL32 ( 9, x1 + x0);     \
187     x3 ^= ROTL32 (13, x2 + x1);     \
188     x0 ^= ROTL32 (18, x3 + x2);     \
189   } while(0)
190
191 static unsigned int
192 salsa20_core (u32 *dst, SALSA20_context_t *ctx, unsigned rounds)
193 {
194   u32 pad[SALSA20_INPUT_LENGTH], *src = ctx->input;
195   unsigned int i;
196
197   memcpy (pad, src, sizeof(pad));
198   for (i = 0; i < rounds; i += 2)
199     {
200       SALSA20_CORE_DEBUG (i);
201       QROUND (pad[0],  pad[4],  pad[8],  pad[12]);
202       QROUND (pad[5],  pad[9],  pad[13], pad[1] );
203       QROUND (pad[10], pad[14], pad[2],  pad[6] );
204       QROUND (pad[15], pad[3],  pad[7],  pad[11]);
205
206       SALSA20_CORE_DEBUG (i+1);
207       QROUND (pad[0],  pad[1],  pad[2],  pad[3] );
208       QROUND (pad[5],  pad[6],  pad[7],  pad[4] );
209       QROUND (pad[10], pad[11], pad[8],  pad[9] );
210       QROUND (pad[15], pad[12], pad[13], pad[14]);
211     }
212   SALSA20_CORE_DEBUG (i);
213
214   for (i = 0; i < SALSA20_INPUT_LENGTH; i++)
215     {
216       u32 t = pad[i] + src[i];
217       dst[i] = LE_SWAP32 (t);
218     }
219
220   /* Update counter. */
221   if (!++src[8])
222     src[9]++;
223
224   /* burn_stack */
225   return ( 3*sizeof (void*) \
226          + 2*sizeof (void*) \
227          + 64 \
228          + sizeof (unsigned int) \
229          + sizeof (u32) );
230 }
231 #undef QROUND
232 #undef SALSA20_CORE_DEBUG
233
234 static void
235 salsa20_keysetup(SALSA20_context_t *ctx, const byte *key, int keylen)
236 {
237   /* These constants are the little endian encoding of the string
238      "expand 32-byte k".  For the 128 bit variant, the "32" in that
239      string will be fixed up to "16".  */
240   ctx->input[0]  = 0x61707865; /* "apxe"  */
241   ctx->input[5]  = 0x3320646e; /* "3 dn"  */
242   ctx->input[10] = 0x79622d32; /* "yb-2"  */
243   ctx->input[15] = 0x6b206574; /* "k et"  */
244
245   ctx->input[1] = LE_READ_UINT32(key + 0);
246   ctx->input[2] = LE_READ_UINT32(key + 4);
247   ctx->input[3] = LE_READ_UINT32(key + 8);
248   ctx->input[4] = LE_READ_UINT32(key + 12);
249   if (keylen == SALSA20_MAX_KEY_SIZE) /* 256 bits */
250     {
251       ctx->input[11] = LE_READ_UINT32(key + 16);
252       ctx->input[12] = LE_READ_UINT32(key + 20);
253       ctx->input[13] = LE_READ_UINT32(key + 24);
254       ctx->input[14] = LE_READ_UINT32(key + 28);
255     }
256   else  /* 128 bits */
257     {
258       ctx->input[11] = ctx->input[1];
259       ctx->input[12] = ctx->input[2];
260       ctx->input[13] = ctx->input[3];
261       ctx->input[14] = ctx->input[4];
262
263       ctx->input[5]  -= 0x02000000; /* Change to "1 dn".  */
264       ctx->input[10] += 0x00000004; /* Change to "yb-6".  */
265     }
266 }
267
268 static void salsa20_ivsetup(SALSA20_context_t *ctx, const byte *iv)
269 {
270   ctx->input[6] = LE_READ_UINT32(iv + 0);
271   ctx->input[7] = LE_READ_UINT32(iv + 4);
272   /* Reset the block counter.  */
273   ctx->input[8] = 0;
274   ctx->input[9] = 0;
275 }
276
277 #endif /*!USE_AMD64*/
278
279 #ifdef USE_ARM_NEON_ASM
280
281 /* ARM NEON implementation of Salsa20. */
282 unsigned int
283 _gcry_arm_neon_salsa20_encrypt(void *c, const void *m, unsigned int nblks,
284                                void *k, unsigned int rounds);
285
286 static unsigned int
287 salsa20_core_neon (u32 *dst, SALSA20_context_t *ctx, unsigned int rounds)
288 {
289   return _gcry_arm_neon_salsa20_encrypt(dst, NULL, 1, ctx->input, rounds);
290 }
291
292 static void salsa20_ivsetup_neon(SALSA20_context_t *ctx, const byte *iv)
293 {
294   memcpy(ctx->input + 8, iv, 8);
295   /* Reset the block counter.  */
296   memset(ctx->input + 10, 0, 8);
297 }
298
299 static void
300 salsa20_keysetup_neon(SALSA20_context_t *ctx, const byte *key, int klen)
301 {
302   static const unsigned char sigma32[16] = "expand 32-byte k";
303   static const unsigned char sigma16[16] = "expand 16-byte k";
304
305   if (klen == 16)
306     {
307       memcpy (ctx->input, key, 16);
308       memcpy (ctx->input + 4, key, 16); /* Duplicate 128-bit key. */
309       memcpy (ctx->input + 12, sigma16, 16);
310     }
311   else
312     {
313       /* 32-byte key */
314       memcpy (ctx->input, key, 32);
315       memcpy (ctx->input + 12, sigma32, 16);
316     }
317 }
318
319 #endif /*USE_ARM_NEON_ASM*/
320
321
322 static gcry_err_code_t
323 salsa20_do_setkey (SALSA20_context_t *ctx,
324                    const byte *key, unsigned int keylen)
325 {
326   static int initialized;
327   static const char *selftest_failed;
328
329   if (!initialized )
330     {
331       initialized = 1;
332       selftest_failed = selftest ();
333       if (selftest_failed)
334         log_error ("SALSA20 selftest failed (%s)\n", selftest_failed );
335     }
336   if (selftest_failed)
337     return GPG_ERR_SELFTEST_FAILED;
338
339   if (keylen != SALSA20_MIN_KEY_SIZE
340       && keylen != SALSA20_MAX_KEY_SIZE)
341     return GPG_ERR_INV_KEYLEN;
342
343   /* Default ops. */
344   ctx->keysetup = salsa20_keysetup;
345   ctx->ivsetup = salsa20_ivsetup;
346   ctx->core = salsa20_core;
347
348 #ifdef USE_ARM_NEON_ASM
349   ctx->use_neon = (_gcry_get_hw_features () & HWF_ARM_NEON) != 0;
350   if (ctx->use_neon)
351     {
352       /* Use ARM NEON ops instead. */
353       ctx->keysetup = salsa20_keysetup_neon;
354       ctx->ivsetup = salsa20_ivsetup_neon;
355       ctx->core = salsa20_core_neon;
356     }
357 #endif
358
359   ctx->keysetup (ctx, key, keylen);
360
361   /* We default to a zero nonce.  */
362   salsa20_setiv (ctx, NULL, 0);
363
364   return 0;
365 }
366
367
368 static gcry_err_code_t
369 salsa20_setkey (void *context, const byte *key, unsigned int keylen)
370 {
371   SALSA20_context_t *ctx = (SALSA20_context_t *)context;
372   gcry_err_code_t rc = salsa20_do_setkey (ctx, key, keylen);
373   _gcry_burn_stack (4 + sizeof (void *) + 4 * sizeof (void *));
374   return rc;
375 }
376
377
378 static void
379 salsa20_setiv (void *context, const byte *iv, size_t ivlen)
380 {
381   SALSA20_context_t *ctx = (SALSA20_context_t *)context;
382   byte tmp[SALSA20_IV_SIZE];
383
384   if (iv && ivlen != SALSA20_IV_SIZE)
385     log_info ("WARNING: salsa20_setiv: bad ivlen=%u\n", (u32)ivlen);
386
387   if (!iv || ivlen != SALSA20_IV_SIZE)
388     memset (tmp, 0, sizeof(tmp));
389   else
390     memcpy (tmp, iv, SALSA20_IV_SIZE);
391
392   ctx->ivsetup (ctx, tmp);
393
394   /* Reset the unused pad bytes counter.  */
395   ctx->unused = 0;
396
397   wipememory (tmp, sizeof(tmp));
398 }
399
400
401 \f
402 /* Note: This function requires LENGTH > 0.  */
403 static void
404 salsa20_do_encrypt_stream (SALSA20_context_t *ctx,
405                            byte *outbuf, const byte *inbuf,
406                            size_t length, unsigned rounds)
407 {
408   unsigned int nburn, burn = 0;
409
410   if (ctx->unused)
411     {
412       unsigned char *p = (void*)ctx->pad;
413       size_t n;
414
415       gcry_assert (ctx->unused < SALSA20_BLOCK_SIZE);
416
417       n = ctx->unused;
418       if (n > length)
419         n = length;
420       buf_xor (outbuf, inbuf, p + SALSA20_BLOCK_SIZE - ctx->unused, n);
421       length -= n;
422       outbuf += n;
423       inbuf  += n;
424       ctx->unused -= n;
425       if (!length)
426         return;
427       gcry_assert (!ctx->unused);
428     }
429
430 #ifdef USE_AMD64
431   if (length >= SALSA20_BLOCK_SIZE)
432     {
433       size_t nblocks = length / SALSA20_BLOCK_SIZE;
434       burn = _gcry_salsa20_amd64_encrypt_blocks(ctx->input, inbuf, outbuf,
435                                                 nblocks, rounds);
436       burn += ASM_EXTRA_STACK;
437       length -= SALSA20_BLOCK_SIZE * nblocks;
438       outbuf += SALSA20_BLOCK_SIZE * nblocks;
439       inbuf  += SALSA20_BLOCK_SIZE * nblocks;
440     }
441 #endif
442
443 #ifdef USE_ARM_NEON_ASM
444   if (ctx->use_neon && length >= SALSA20_BLOCK_SIZE)
445     {
446       unsigned int nblocks = length / SALSA20_BLOCK_SIZE;
447       _gcry_arm_neon_salsa20_encrypt (outbuf, inbuf, nblocks, ctx->input,
448                                       rounds);
449       length -= SALSA20_BLOCK_SIZE * nblocks;
450       outbuf += SALSA20_BLOCK_SIZE * nblocks;
451       inbuf  += SALSA20_BLOCK_SIZE * nblocks;
452     }
453 #endif
454
455   while (length > 0)
456     {
457       /* Create the next pad and bump the block counter.  Note that it
458          is the user's duty to change to another nonce not later than
459          after 2^70 processed bytes.  */
460       nburn = ctx->core (ctx->pad, ctx, rounds);
461       burn = nburn > burn ? nburn : burn;
462
463       if (length <= SALSA20_BLOCK_SIZE)
464         {
465           buf_xor (outbuf, inbuf, ctx->pad, length);
466           ctx->unused = SALSA20_BLOCK_SIZE - length;
467           break;
468         }
469       buf_xor (outbuf, inbuf, ctx->pad, SALSA20_BLOCK_SIZE);
470       length -= SALSA20_BLOCK_SIZE;
471       outbuf += SALSA20_BLOCK_SIZE;
472       inbuf  += SALSA20_BLOCK_SIZE;
473     }
474
475   _gcry_burn_stack (burn);
476 }
477
478
479 static void
480 salsa20_encrypt_stream (void *context,
481                         byte *outbuf, const byte *inbuf, size_t length)
482 {
483   SALSA20_context_t *ctx = (SALSA20_context_t *)context;
484
485   if (length)
486     salsa20_do_encrypt_stream (ctx, outbuf, inbuf, length, SALSA20_ROUNDS);
487 }
488
489
490 static void
491 salsa20r12_encrypt_stream (void *context,
492                            byte *outbuf, const byte *inbuf, size_t length)
493 {
494   SALSA20_context_t *ctx = (SALSA20_context_t *)context;
495
496   if (length)
497     salsa20_do_encrypt_stream (ctx, outbuf, inbuf, length, SALSA20R12_ROUNDS);
498 }
499
500
501 static const char*
502 selftest (void)
503 {
504   byte ctxbuf[sizeof(SALSA20_context_t) + 15];
505   SALSA20_context_t *ctx;
506   byte scratch[8+1];
507   byte buf[256+64+4];
508   int i;
509
510   static byte key_1[] =
511     { 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
512       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
513       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
514       0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
515   static const byte nonce_1[] =
516     { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
517   static const byte plaintext_1[] =
518     { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
519   static const byte ciphertext_1[] =
520     { 0xE3, 0xBE, 0x8F, 0xDD, 0x8B, 0xEC, 0xA2, 0xE3};
521
522   /* 16-byte alignment required for amd64 implementation. */
523   ctx = (SALSA20_context_t *)((uintptr_t)(ctxbuf + 15) & ~(uintptr_t)15);
524
525   salsa20_setkey (ctx, key_1, sizeof key_1);
526   salsa20_setiv  (ctx, nonce_1, sizeof nonce_1);
527   scratch[8] = 0;
528   salsa20_encrypt_stream (ctx, scratch, plaintext_1, sizeof plaintext_1);
529   if (memcmp (scratch, ciphertext_1, sizeof ciphertext_1))
530     return "Salsa20 encryption test 1 failed.";
531   if (scratch[8])
532     return "Salsa20 wrote too much.";
533   salsa20_setkey( ctx, key_1, sizeof(key_1));
534   salsa20_setiv  (ctx, nonce_1, sizeof nonce_1);
535   salsa20_encrypt_stream (ctx, scratch, scratch, sizeof plaintext_1);
536   if (memcmp (scratch, plaintext_1, sizeof plaintext_1))
537     return "Salsa20 decryption test 1 failed.";
538
539   for (i = 0; i < sizeof buf; i++)
540     buf[i] = i;
541   salsa20_setkey (ctx, key_1, sizeof key_1);
542   salsa20_setiv (ctx, nonce_1, sizeof nonce_1);
543   /*encrypt*/
544   salsa20_encrypt_stream (ctx, buf, buf, sizeof buf);
545   /*decrypt*/
546   salsa20_setkey (ctx, key_1, sizeof key_1);
547   salsa20_setiv (ctx, nonce_1, sizeof nonce_1);
548   salsa20_encrypt_stream (ctx, buf, buf, 1);
549   salsa20_encrypt_stream (ctx, buf+1, buf+1, (sizeof buf)-1-1);
550   salsa20_encrypt_stream (ctx, buf+(sizeof buf)-1, buf+(sizeof buf)-1, 1);
551   for (i = 0; i < sizeof buf; i++)
552     if (buf[i] != (byte)i)
553       return "Salsa20 encryption test 2 failed.";
554
555   return NULL;
556 }
557
558
559 gcry_cipher_spec_t _gcry_cipher_spec_salsa20 =
560   {
561     GCRY_CIPHER_SALSA20,
562     {0, 0},     /* flags */
563     "SALSA20",  /* name */
564     NULL,       /* aliases */
565     NULL,       /* oids */
566     1,          /* blocksize in bytes. */
567     SALSA20_MAX_KEY_SIZE*8,  /* standard key length in bits. */
568     sizeof (SALSA20_context_t),
569     salsa20_setkey,
570     NULL,
571     NULL,
572     salsa20_encrypt_stream,
573     salsa20_encrypt_stream,
574     NULL,
575     NULL,
576     salsa20_setiv
577   };
578
579 gcry_cipher_spec_t _gcry_cipher_spec_salsa20r12 =
580   {
581     GCRY_CIPHER_SALSA20R12,
582     {0, 0},     /* flags */
583     "SALSA20R12",  /* name */
584     NULL,       /* aliases */
585     NULL,       /* oids */
586     1,          /* blocksize in bytes. */
587     SALSA20_MAX_KEY_SIZE*8,  /* standard key length in bits. */
588     sizeof (SALSA20_context_t),
589     salsa20_setkey,
590     NULL,
591     NULL,
592     salsa20r12_encrypt_stream,
593     salsa20r12_encrypt_stream,
594     NULL,
595     NULL,
596     salsa20_setiv
597   };