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