More optimized CRC implementations
[libgcrypt.git] / 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 int 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 scrypt_block_mix (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*)(void*)X, (u32*)(void*)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
177 static void
178 scrypt_ro_mix (u32 r, unsigned char *B, u64 N,
179               unsigned char *tmp1, unsigned char *tmp2)
180 {
181   unsigned char *X = B, *T = B;
182   u64 i;
183
184 #if 0
185   if (r == 1)
186     {
187       printf ("B = ");
188       for (i = 0; i < 128 * r; i++)
189         {
190           if (i && !(i % 16))
191             printf ("\n    ");
192           printf (" %02x", B[i]);
193         }
194       putchar ('\n');
195     }
196 #endif
197
198   /* for i = 0 to N - 1 do */
199   for (i = 0; i <= N - 1; i++)
200     {
201       /* V[i] = X */
202       memcpy (&tmp1[i * 128 * r], X, 128 * r);
203
204       /* X =  ScryptBlockMix (X) */
205       scrypt_block_mix (r, X, tmp2);
206     }
207
208   /* for i = 0 to N - 1 do */
209   for (i = 0; i <= N - 1; i++)
210     {
211       u64 j;
212
213       /* j = Integerify (X) mod N */
214       j = LE_READ_UINT64 (&X[128 * r - 64]) % N;
215
216       /* T = X xor V[j] */
217       buf_xor (T, T, &tmp1[j * 128 * r], 128 * r);
218
219       /* X = scryptBlockMix (T) */
220       scrypt_block_mix (r, T, tmp2);
221     }
222
223 #if 0
224   if (r == 1)
225     {
226       printf ("B' =");
227       for (i = 0; i < 128 * r; i++)
228         {
229           if (i && !(i % 16))
230             printf ("\n    ");
231           printf (" %02x", B[i]);
232         }
233       putchar ('\n');
234     }
235 #endif
236 }
237
238
239 /*
240  *
241  */
242 gcry_err_code_t
243 _gcry_kdf_scrypt (const unsigned char *passwd, size_t passwdlen,
244                   int algo, int subalgo,
245                   const unsigned char *salt, size_t saltlen,
246                   unsigned long iterations,
247                   size_t dkLen, unsigned char *DK)
248 {
249   u64 N = subalgo;    /* CPU/memory cost paramter.  */
250   u32 r;              /* Block size.  */
251   u32 p = iterations; /* Parallelization parameter.  */
252
253   gpg_err_code_t ec;
254   u32 i;
255   unsigned char *B = NULL;
256   unsigned char *tmp1 = NULL;
257   unsigned char *tmp2 = NULL;
258   size_t r128;
259   size_t nbytes;
260
261   if (subalgo < 1 || !iterations)
262     return GPG_ERR_INV_VALUE;
263
264   if (algo == GCRY_KDF_SCRYPT)
265     r = 8;
266   else if (algo == 41) /* Hack to allow the use of all test vectors.  */
267     r = 1;
268   else
269     return GPG_ERR_UNKNOWN_ALGORITHM;
270
271   r128 = r * 128;
272   if (r128 / 128 != r)
273     return GPG_ERR_ENOMEM;
274
275   nbytes = p * r128;
276   if (r128 && nbytes / r128 != p)
277     return GPG_ERR_ENOMEM;
278
279   nbytes = N * r128;
280   if (r128 && nbytes / r128 != N)
281     return GPG_ERR_ENOMEM;
282
283   nbytes = 64 + r128;
284   if (nbytes < r128)
285     return GPG_ERR_ENOMEM;
286
287   B = xtrymalloc (p * r128);
288   if (!B)
289     {
290       ec = gpg_err_code_from_syserror ();
291       goto leave;
292     }
293
294   tmp1 = xtrymalloc (N * r128);
295   if (!tmp1)
296     {
297       ec = gpg_err_code_from_syserror ();
298       goto leave;
299     }
300
301   tmp2 = xtrymalloc (64 + r128);
302   if (!tmp2)
303     {
304       ec = gpg_err_code_from_syserror ();
305       goto leave;
306     }
307
308   ec = _gcry_kdf_pkdf2 (passwd, passwdlen, GCRY_MD_SHA256, salt, saltlen,
309                         1 /* iterations */, p * r128, B);
310
311   for (i = 0; !ec && i < p; i++)
312     scrypt_ro_mix (r, &B[i * r128], N, tmp1, tmp2);
313
314   for (i = 0; !ec && i < p; i++)
315     ec = _gcry_kdf_pkdf2 (passwd, passwdlen, GCRY_MD_SHA256, B, p * r128,
316                           1 /* iterations */, dkLen, DK);
317
318  leave:
319   xfree (tmp2);
320   xfree (tmp1);
321   xfree (B);
322
323   return ec;
324 }
325
326
327 #endif /* HAVE_U64_TYPEDEF */