cipher/scrypt.c

   1 /* scrypt.c - Scrypt password-based key derivation function.
   2  * Copyright (C) 2012 Simon Josefsson
   3  * Copyright (C) 2013 Christian Grothoff
   4  * Copyright (C) 2013 g10 Code GmbH
   5  *
   6  * This file is part of Libgcrypt.
   7  *
   8  * Libgcrypt is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU Lesser general Public License as
  10  * published by the Free Software Foundation; either version 2.1 of
  11  * the License, or (at your option) any later version.
  12  *
  13  * Libgcrypt is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
  20  */
  21
  22 /* Adapted from the nettle, low-level cryptographics library for
  23  * libgcrypt by Christian Grothoff; original license:
  24  *
  25  * Copyright (C) 2012 Simon Josefsson
  26  *
  27  * The nettle library is free software; you can redistribute it and/or modify
  28  * it under the terms of the GNU Lesser General Public License as published by
  29  * the Free Software Foundation; either version 2.1 of the License, or (at your
  30  * option) any later version.
  31  *
  32  * The nettle library is distributed in the hope that it will be useful, but
  33  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  34  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  35  * License for more details.
  36  *
  37  * You should have received a copy of the GNU Lesser General Public License
  38  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  39  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  40  * MA 02111-1301, USA.
  41  */
  42
  43 #include <config.h>
  44 #include <assert.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47
  48 #include "g10lib.h"
  49 #include "kdf-internal.h"
  50 #include "bufhelp.h"
  51
  52 /* We really need a 64 bit type for this code.  */
  53 #ifdef HAVE_U64_TYPEDEF
  54
  55 #define SALSA20_INPUT_LENGTH 16
  56
  57 #define ROTL32(n,x) (((x)<<(n)) | ((x)>>(32-(n))))
  58
  59
  60 /* Reads a 64-bit integer, in network, big-endian, byte order */
  61 #define READ_UINT64(p) buf_get_be64(p)
  62
  63
  64 /* And the other, little-endian, byteorder */
  65 #define LE_READ_UINT64(p) buf_get_le64(p)
  66
  67 #define LE_SWAP32(v) le_bswap32(v)
  68
  69
  70 #define QROUND(x0, x1, x2, x3) do { \
  71   x1 ^= ROTL32(7, x0 + x3);         \
  72   x2 ^= ROTL32(9, x1 + x0);         \
  73   x3 ^= ROTL32(13, x2 + x1);        \
  74   x0 ^= ROTL32(18, x3 + x2);        \
  75   } while(0)
  76
  77
  78 static void
  79 _salsa20_core(u32 *dst, const u32 *src, unsigned rounds)
  80 {
  81   u32 x[SALSA20_INPUT_LENGTH];
  82   unsigned i;
  83
  84   assert ( (rounds & 1) == 0);
  85
  86   for (i = 0; i < SALSA20_INPUT_LENGTH; i++)
  87     x[i] = LE_SWAP32(src[i]);
  88
  89   for (i = 0; i < rounds;i += 2)
  90     {
  91       QROUND(x[0], x[4], x[8], x[12]);
  92       QROUND(x[5], x[9], x[13], x[1]);
  93       QROUND(x[10], x[14], x[2], x[6]);
  94       QROUND(x[15], x[3], x[7], x[11]);
  95
  96       QROUND(x[0], x[1], x[2], x[3]);
  97       QROUND(x[5], x[6], x[7], x[4]);
  98       QROUND(x[10], x[11], x[8], x[9]);
  99       QROUND(x[15], x[12], x[13], x[14]);
 100     }
 101
 102   for (i = 0; i < SALSA20_INPUT_LENGTH; i++)
 103     {
 104       u32 t = x[i] + LE_SWAP32(src[i]);
 105       dst[i] = LE_SWAP32(t);
 106     }
 107 }
 108
 109
 110 static void
 111 _scryptBlockMix (u32 r, unsigned char *B, unsigned char *tmp2)
 112 {
 113   u64 i;
 114   unsigned char *X = tmp2;
 115   unsigned char *Y = tmp2 + 64;
 116
 117 #if 0
 118   if (r == 1)
 119     {
 120       for (i = 0; i < 2 * r; i++)
 121         {
 122           size_t j;
 123           printf ("B[%d] = ", (int)i);
 124           for (j = 0; j < 64; j++)
 125             {
 126               if (j && !(j % 16))
 127                 printf ("\n       ");
 128               printf (" %02x", B[i * 64 + j]);
 129             }
 130           putchar ('\n');
 131         }
 132     }
 133 #endif
 134
 135   /* X = B[2 * r - 1] */
 136   memcpy (X, &B[(2 * r - 1) * 64], 64);
 137
 138   /* for i = 0 to 2 * r - 1 do */
 139   for (i = 0; i <= 2 * r - 1; i++)
 140     {
 141       /* T = X xor B[i] */
 142       buf_xor(X, X, &B[i * 64], 64);
 143
 144       /* X = Salsa (T) */
 145       _salsa20_core ((u32*)X, (u32*)X, 8);
 146
 147       /* Y[i] = X */
 148       memcpy (&Y[i * 64], X, 64);
 149     }
 150
 151   for (i = 0; i < r; i++)
 152     {
 153       memcpy (&B[i * 64], &Y[2 * i * 64], 64);
 154       memcpy (&B[(r + i) * 64], &Y[(2 * i + 1) * 64], 64);
 155     }
 156
 157 #if 0
 158   if (r==1)
 159     {
 160       for (i = 0; i < 2 * r; i++)
 161         {
 162           size_t j;
 163           printf ("B'[%d] =", (int)i);
 164           for (j = 0; j < 64; j++)
 165             {
 166               if (j && !(j % 16))
 167                 printf ("\n       ");
 168               printf (" %02x", B[i * 64 + j]);
 169             }
 170           putchar ('\n');
 171         }
 172     }
 173 #endif
 174 }
 175
 176 static void
 177 _scryptROMix (u32 r, unsigned char *B, u64 N,
 178               unsigned char *tmp1, unsigned char *tmp2)
 179 {
 180   unsigned char *X = B, *T = B;
 181   u64 i;
 182
 183 #if 0
 184   if (r == 1)
 185     {
 186       printf ("B = ");
 187       for (i = 0; i < 128 * r; i++)
 188         {
 189           if (i && !(i % 16))
 190             printf ("\n    ");
 191           printf (" %02x", B[i]);
 192         }
 193       putchar ('\n');
 194     }
 195 #endif
 196
 197   /* for i = 0 to N - 1 do */
 198   for (i = 0; i <= N - 1; i++)
 199     {
 200       /* V[i] = X */
 201       memcpy (&tmp1[i * 128 * r], X, 128 * r);
 202
 203       /* X =  ScryptBlockMix (X) */
 204       _scryptBlockMix (r, X, tmp2);
 205     }
 206
 207   /* for i = 0 to N - 1 do */
 208   for (i = 0; i <= N - 1; i++)
 209     {
 210       u64 j;
 211
 212       /* j = Integerify (X) mod N */
 213       j = LE_READ_UINT64 (&X[128 * r - 64]) % N;
 214
 215       /* T = X xor V[j] */
 216       buf_xor (T, T, &tmp1[j * 128 * r], 128 * r);
 217
 218       /* X = scryptBlockMix (T) */
 219       _scryptBlockMix (r, T, tmp2);
 220     }
 221
 222 #if 0
 223   if (r == 1)
 224     {
 225       printf ("B' =");
 226       for (i = 0; i < 128 * r; i++)
 227         {
 228           if (i && !(i % 16))
 229             printf ("\n    ");
 230           printf (" %02x", B[i]);
 231         }
 232       putchar ('\n');
 233     }
 234 #endif
 235 }
 236
 237 /**
 238  */
 239 gcry_err_code_t
 240 _gcry_kdf_scrypt (const unsigned char *passwd, size_t passwdlen,
 241                   int algo, int subalgo,
 242                   const unsigned char *salt, size_t saltlen,
 243                   unsigned long iterations,
 244                   size_t dkLen, unsigned char *DK)
 245 {
 246   u64 N = subalgo;    /* CPU/memory cost paramter.  */
 247   u32 r;              /* Block size.  */
 248   u32 p = iterations; /* Parallelization parameter.  */
 249
 250   gpg_err_code_t ec;
 251   u32 i;
 252   unsigned char *B = NULL;
 253   unsigned char *tmp1 = NULL;
 254   unsigned char *tmp2 = NULL;
 255   size_t r128;
 256   size_t nbytes;
 257
 258   if (subalgo < 1 || !iterations)
 259     return GPG_ERR_INV_VALUE;
 260
 261   if (algo == GCRY_KDF_SCRYPT)
 262     r = 8;
 263   else if (algo == 41) /* Hack to allow the use of all test vectors.  */
 264     r = 1;
 265   else
 266     return GPG_ERR_UNKNOWN_ALGORITHM;
 267
 268   r128 = r * 128;
 269   if (r128 / 128 != r)
 270     return GPG_ERR_ENOMEM;
 271
 272   nbytes = p * r128;
 273   if (r128 && nbytes / r128 != p)
 274     return GPG_ERR_ENOMEM;
 275
 276   nbytes = N * r128;
 277   if (r128 && nbytes / r128 != N)
 278     return GPG_ERR_ENOMEM;
 279
 280   nbytes = 64 + r128;
 281   if (nbytes < r128)
 282     return GPG_ERR_ENOMEM;
 283
 284   B = xtrymalloc (p * r128);
 285   if (!B)
 286     {
 287       ec = gpg_err_code_from_syserror ();
 288       goto leave;
 289     }
 290
 291   tmp1 = xtrymalloc (N * r128);
 292   if (!tmp1)
 293     {
 294       ec = gpg_err_code_from_syserror ();
 295       goto leave;
 296     }
 297
 298   tmp2 = xtrymalloc (64 + r128);
 299   if (!tmp2)
 300     {
 301       ec = gpg_err_code_from_syserror ();
 302       goto leave;
 303     }
 304
 305   ec = _gcry_kdf_pkdf2 (passwd, passwdlen, GCRY_MD_SHA256, salt, saltlen,
 306                         1 /* iterations */, p * r128, B);
 307
 308   for (i = 0; !ec && i < p; i++)
 309     _scryptROMix (r, &B[i * r128], N, tmp1, tmp2);
 310
 311   for (i = 0; !ec && i < p; i++)
 312     ec = _gcry_kdf_pkdf2 (passwd, passwdlen, GCRY_MD_SHA256, B, p * r128,
 313                           1 /* iterations */, dkLen, DK);
 314
 315  leave:
 316   xfree (tmp2);
 317   xfree (tmp1);
 318   xfree (B);
 319
 320   return ec;
 321 }
 322
 323
 324 #endif /* HAVE_U64_TYPEDEF */