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