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