Add test case for SCRYPT and rework the code.
[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)                          \
62 (  (((u64) (p)[0]) << 56)                  \
63  | (((u64) (p)[1]) << 48)                  \
64  | (((u64) (p)[2]) << 40)                  \
65  | (((u64) (p)[3]) << 32)                  \
66  | (((u64) (p)[4]) << 24)                  \
67  | (((u64) (p)[5]) << 16)                  \
68  | (((u64) (p)[6]) << 8)                   \
69  |  ((u64) (p)[7]))
70
71
72
73 /* And the other, little-endian, byteorder */
74 #define LE_READ_UINT64(p)                       \
75 (  (((u64) (p)[7]) << 56)                  \
76  | (((u64) (p)[6]) << 48)                  \
77  | (((u64) (p)[5]) << 40)                  \
78  | (((u64) (p)[4]) << 32)                  \
79  | (((u64) (p)[3]) << 24)                  \
80  | (((u64) (p)[2]) << 16)                  \
81  | (((u64) (p)[1]) << 8)                   \
82  |  ((u64) (p)[0]))
83
84
85
86 #ifdef WORDS_BIGENDIAN
87 #define LE_SWAP32(v)                            \
88   ((ROTL32(8,  v) & 0x00FF00FFUL) |             \
89    (ROTL32(24, v) & 0xFF00FF00UL))
90 #else
91 #define LE_SWAP32(v) (v)
92 #endif
93
94 #define QROUND(x0, x1, x2, x3) do { \
95   x1 ^= ROTL32(7, x0 + x3);         \
96   x2 ^= ROTL32(9, x1 + x0);         \
97   x3 ^= ROTL32(13, x2 + x1);        \
98   x0 ^= ROTL32(18, x3 + x2);        \
99   } while(0)
100
101
102 static void
103 _salsa20_core(u32 *dst, const u32 *src, unsigned rounds)
104 {
105   u32 x[SALSA20_INPUT_LENGTH];
106   unsigned i;
107
108   assert ( (rounds & 1) == 0);
109
110   memcpy (x, src, sizeof(x));
111   for (i = 0; i < rounds;i += 2)
112     {
113       QROUND(x[0], x[4], x[8], x[12]);
114       QROUND(x[5], x[9], x[13], x[1]);
115       QROUND(x[10], x[14], x[2], x[6]);
116       QROUND(x[15], x[3], x[7], x[11]);
117
118       QROUND(x[0], x[1], x[2], x[3]);
119       QROUND(x[5], x[6], x[7], x[4]);
120       QROUND(x[10], x[11], x[8], x[9]);
121       QROUND(x[15], x[12], x[13], x[14]);
122     }
123
124   for (i = 0; i < SALSA20_INPUT_LENGTH; i++)
125     {
126       u32 t = x[i] + src[i];
127       dst[i] = LE_SWAP32 (t);
128     }
129 }
130
131
132 static void
133 _scryptBlockMix (u32 r, unsigned char *B, unsigned char *tmp2)
134 {
135   u64 i;
136   unsigned char *X = tmp2;
137   unsigned char *Y = tmp2 + 64;
138
139 #if 0
140   if (r == 1)
141     {
142       for (i = 0; i < 2 * r; i++)
143         {
144           size_t j;
145           printf ("B[%d] = ", (int)i);
146           for (j = 0; j < 64; j++)
147             {
148               if (j && !(j % 16))
149                 printf ("\n       ");
150               printf (" %02x", B[i * 64 + j]);
151             }
152           putchar ('\n');
153         }
154     }
155 #endif
156
157   /* X = B[2 * r - 1] */
158   memcpy (X, &B[(2 * r - 1) * 64], 64);
159
160   /* for i = 0 to 2 * r - 1 do */
161   for (i = 0; i <= 2 * r - 1; i++)
162     {
163       /* T = X xor B[i] */
164       buf_xor(X, X, &B[i * 64], 64);
165
166       /* X = Salsa (T) */
167       _salsa20_core ((u32*)X, (u32*)X, 8);
168
169       /* Y[i] = X */
170       memcpy (&Y[i * 64], X, 64);
171     }
172
173   for (i = 0; i < r; i++)
174     {
175       memcpy (&B[i * 64], &Y[2 * i * 64], 64);
176       memcpy (&B[(r + i) * 64], &Y[(2 * i + 1) * 64], 64);
177     }
178
179 #if 0
180   if (r==1)
181     {
182       for (i = 0; i < 2 * r; i++)
183         {
184           size_t j;
185           printf ("B'[%d] =", (int)i);
186           for (j = 0; j < 64; j++)
187             {
188               if (j && !(j % 16))
189                 printf ("\n       ");
190               printf (" %02x", B[i * 64 + j]);
191             }
192           putchar ('\n');
193         }
194     }
195 #endif
196 }
197
198 static void
199 _scryptROMix (u32 r, unsigned char *B, u64 N,
200               unsigned char *tmp1, unsigned char *tmp2)
201 {
202   unsigned char *X = B, *T = B;
203   u64 i;
204
205 #if 0
206   if (r == 1)
207     {
208       printf ("B = ");
209       for (i = 0; i < 128 * r; i++)
210         {
211           if (i && !(i % 16))
212             printf ("\n    ");
213           printf (" %02x", B[i]);
214         }
215       putchar ('\n');
216     }
217 #endif
218
219   /* for i = 0 to N - 1 do */
220   for (i = 0; i <= N - 1; i++)
221     {
222       /* V[i] = X */
223       memcpy (&tmp1[i * 128 * r], X, 128 * r);
224
225       /* X =  ScryptBlockMix (X) */
226       _scryptBlockMix (r, X, tmp2);
227     }
228
229   /* for i = 0 to N - 1 do */
230   for (i = 0; i <= N - 1; i++)
231     {
232       u64 j;
233
234       /* j = Integerify (X) mod N */
235       j = LE_READ_UINT64 (&X[128 * r - 64]) % N;
236
237       /* T = X xor V[j] */
238       buf_xor (T, T, &tmp1[j * 128 * r], 128 * r);
239
240       /* X = scryptBlockMix (T) */
241       _scryptBlockMix (r, T, tmp2);
242     }
243
244 #if 0
245   if (r == 1)
246     {
247       printf ("B' =");
248       for (i = 0; i < 128 * r; i++)
249         {
250           if (i && !(i % 16))
251             printf ("\n    ");
252           printf (" %02x", B[i]);
253         }
254       putchar ('\n');
255     }
256 #endif
257 }
258
259 /**
260  */
261 gcry_err_code_t
262 _gcry_kdf_scrypt (const unsigned char *passwd, size_t passwdlen,
263                   int algo, int subalgo,
264                   const unsigned char *salt, size_t saltlen,
265                   unsigned long iterations,
266                   size_t dkLen, unsigned char *DK)
267 {
268   u64 N = subalgo;    /* CPU/memory cost paramter.  */
269   u32 r;              /* Block size.  */
270   u32 p = iterations; /* Parallelization parameter.  */
271
272   gpg_err_code_t ec;
273   u32 i;
274   unsigned char *B = NULL;
275   unsigned char *tmp1 = NULL;
276   unsigned char *tmp2 = NULL;
277   size_t r128;
278   size_t nbytes;
279
280   if (subalgo < 1 || !iterations)
281     return GPG_ERR_INV_VALUE;
282
283   if (algo == GCRY_KDF_SCRYPT)
284     r = 8;
285   else if (algo == 41) /* Hack to allow the use of all test vectors.  */
286     r = 1;
287   else
288     return GPG_ERR_UNKNOWN_ALGORITHM;
289
290   r128 = r * 128;
291   if (r128 / 128 != r)
292     return GPG_ERR_ENOMEM;
293
294   nbytes = p * r128;
295   if (r128 && nbytes / r128 != p)
296     return GPG_ERR_ENOMEM;
297
298   nbytes = N * r128;
299   if (r128 && nbytes / r128 != N)
300     return GPG_ERR_ENOMEM;
301
302   nbytes = 64 + r128;
303   if (nbytes < r128)
304     return GPG_ERR_ENOMEM;
305
306   B = gcry_malloc (p * r128);
307   if (!B)
308     {
309       ec = gpg_err_code_from_syserror ();
310       goto leave;
311     }
312
313   tmp1 = gcry_malloc (N * r128);
314   if (!tmp1)
315     {
316       ec = gpg_err_code_from_syserror ();
317       goto leave;
318     }
319
320   tmp2 = gcry_malloc (64 + r128);
321   if (!tmp2)
322     {
323       ec = gpg_err_code_from_syserror ();
324       goto leave;
325     }
326
327   ec = _gcry_kdf_pkdf2 (passwd, passwdlen, GCRY_MD_SHA256, salt, saltlen,
328                         1 /* iterations */, p * r128, B);
329
330   for (i = 0; !ec && i < p; i++)
331     _scryptROMix (r, &B[i * r128], N, tmp1, tmp2);
332
333   for (i = 0; !ec && i < p; i++)
334     ec = _gcry_kdf_pkdf2 (passwd, passwdlen, GCRY_MD_SHA256, B, p * r128,
335                           1 /* iterations */, dkLen, DK);
336
337  leave:
338   gcry_free (tmp2);
339   gcry_free (tmp1);
340   gcry_free (B);
341
342   return ec;
343 }
344
345
346 #endif /* HAVE_U64_TYPEDEF */