1 /*-
2 * Copyright 2009 Colin Percival
3 * Copyright 2013 Alexander Peslyak
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 *
27 * This file was originally written by Colin Percival as part of the Tarsnap
28 * online backup system.
29 */
30
31 #include <errno.h>
32 #include <limits.h>
33 #include <stdint.h>
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "../crypto_scrypt.h"
38 #include "../pbkdf2-sha256.h"
39 #include "private/common.h"
40
41 static inline void
blkcpy_64(escrypt_block_t * dest,const escrypt_block_t * src)42 blkcpy_64(escrypt_block_t *dest, const escrypt_block_t *src)
43 {
44 int i;
45
46 #if (ARCH_BITS == 32)
47 for (i = 0; i < 16; ++i) {
48 dest->w[i] = src->w[i];
49 }
50 #else
51 for (i = 0; i < 8; ++i) {
52 dest->d[i] = src->d[i];
53 }
54 #endif
55 }
56
57 static inline void
blkxor_64(escrypt_block_t * dest,const escrypt_block_t * src)58 blkxor_64(escrypt_block_t *dest, const escrypt_block_t *src)
59 {
60 int i;
61
62 #if (ARCH_BITS == 32)
63 for (i = 0; i < 16; ++i) {
64 dest->w[i] ^= src->w[i];
65 }
66 #else
67 for (i = 0; i < 8; ++i) {
68 dest->d[i] ^= src->d[i];
69 }
70 #endif
71 }
72
73 static inline void
blkcpy(escrypt_block_t * dest,const escrypt_block_t * src,size_t len)74 blkcpy(escrypt_block_t *dest, const escrypt_block_t *src, size_t len)
75 {
76 size_t i, L;
77
78 #if (ARCH_BITS == 32)
79 L = (len >> 2);
80 for (i = 0; i < L; ++i) {
81 dest->w[i] = src->w[i];
82 }
83 #else
84 L = (len >> 3);
85 for (i = 0; i < L; ++i) {
86 dest->d[i] = src->d[i];
87 }
88 #endif
89 }
90
91 static inline void
blkxor(escrypt_block_t * dest,const escrypt_block_t * src,size_t len)92 blkxor(escrypt_block_t *dest, const escrypt_block_t *src, size_t len)
93 {
94 size_t i, L;
95
96 #if (ARCH_BITS == 32)
97 L = (len >> 2);
98 for (i = 0; i < L; ++i) {
99 dest->w[i] ^= src->w[i];
100 }
101 #else
102 L = (len >> 3);
103 for (i = 0; i < L; ++i) {
104 dest->d[i] ^= src->d[i];
105 }
106 #endif
107 }
108
109 /**
110 * salsa20_8(B):
111 * Apply the salsa20/8 core to the provided block.
112 */
113 static void
salsa20_8(uint32_t B[16])114 salsa20_8(uint32_t B[16])
115 {
116 escrypt_block_t X;
117 uint32_t *x = X.w;
118 size_t i;
119
120 blkcpy_64(&X, (escrypt_block_t *) B);
121 for (i = 0; i < 8; i += 2) {
122 #define R(a, b) (((a) << (b)) | ((a) >> (32 - (b))))
123 /* Operate on columns. */
124 x[4] ^= R(x[0] + x[12], 7);
125 x[8] ^= R(x[4] + x[0], 9);
126 x[12] ^= R(x[8] + x[4], 13);
127 x[0] ^= R(x[12] + x[8], 18);
128
129 x[9] ^= R(x[5] + x[1], 7);
130 x[13] ^= R(x[9] + x[5], 9);
131 x[1] ^= R(x[13] + x[9], 13);
132 x[5] ^= R(x[1] + x[13], 18);
133
134 x[14] ^= R(x[10] + x[6], 7);
135 x[2] ^= R(x[14] + x[10], 9);
136 x[6] ^= R(x[2] + x[14], 13);
137 x[10] ^= R(x[6] + x[2], 18);
138
139 x[3] ^= R(x[15] + x[11], 7);
140 x[7] ^= R(x[3] + x[15], 9);
141 x[11] ^= R(x[7] + x[3], 13);
142 x[15] ^= R(x[11] + x[7], 18);
143
144 /* Operate on rows. */
145 x[1] ^= R(x[0] + x[3], 7);
146 x[2] ^= R(x[1] + x[0], 9);
147 x[3] ^= R(x[2] + x[1], 13);
148 x[0] ^= R(x[3] + x[2], 18);
149
150 x[6] ^= R(x[5] + x[4], 7);
151 x[7] ^= R(x[6] + x[5], 9);
152 x[4] ^= R(x[7] + x[6], 13);
153 x[5] ^= R(x[4] + x[7], 18);
154
155 x[11] ^= R(x[10] + x[9], 7);
156 x[8] ^= R(x[11] + x[10], 9);
157 x[9] ^= R(x[8] + x[11], 13);
158 x[10] ^= R(x[9] + x[8], 18);
159
160 x[12] ^= R(x[15] + x[14], 7);
161 x[13] ^= R(x[12] + x[15], 9);
162 x[14] ^= R(x[13] + x[12], 13);
163 x[15] ^= R(x[14] + x[13], 18);
164 #undef R
165 }
166 for (i = 0; i < 16; i++) {
167 B[i] += x[i];
168 }
169 }
170
171 /**
172 * blockmix_salsa8(Bin, Bout, X, r):
173 * Compute Bout = BlockMix_{salsa20/8, r}(Bin). The input Bin must be 128r
174 * bytes in length; the output Bout must also be the same size. The
175 * temporary space X must be 64 bytes.
176 */
177 static void
blockmix_salsa8(const uint32_t * Bin,uint32_t * Bout,uint32_t * X,size_t r)178 blockmix_salsa8(const uint32_t *Bin, uint32_t *Bout, uint32_t *X, size_t r)
179 {
180 size_t i;
181
182 /* 1: X <-- B_{2r - 1} */
183 blkcpy_64((escrypt_block_t *) X,
184 (escrypt_block_t *) &Bin[(2 * r - 1) * 16]);
185
186 /* 2: for i = 0 to 2r - 1 do */
187 for (i = 0; i < 2 * r; i += 2) {
188 /* 3: X <-- H(X \xor B_i) */
189 blkxor_64((escrypt_block_t *) X, (escrypt_block_t *) &Bin[i * 16]);
190 salsa20_8(X);
191
192 /* 4: Y_i <-- X */
193 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
194 blkcpy_64((escrypt_block_t *) &Bout[i * 8], (escrypt_block_t *) X);
195
196 /* 3: X <-- H(X \xor B_i) */
197 blkxor_64((escrypt_block_t *) X, (escrypt_block_t *) &Bin[i * 16 + 16]);
198 salsa20_8(X);
199
200 /* 4: Y_i <-- X */
201 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
202 blkcpy_64((escrypt_block_t *) &Bout[i * 8 + r * 16],
203 (escrypt_block_t *) X);
204 }
205 }
206
207 /**
208 * integerify(B, r):
209 * Return the result of parsing B_{2r-1} as a little-endian integer.
210 */
211 static inline uint64_t
integerify(const void * B,size_t r)212 integerify(const void *B, size_t r)
213 {
214 const uint32_t *X = (const uint32_t *) ((uintptr_t)(B) + (2 * r - 1) * 64);
215
216 return (((uint64_t)(X[1]) << 32) + X[0]);
217 }
218
219 /**
220 * smix(B, r, N, V, XY):
221 * Compute B = SMix_r(B, N). The input B must be 128r bytes in length;
222 * the temporary storage V must be 128rN bytes in length; the temporary
223 * storage XY must be 256r + 64 bytes in length. The value N must be a
224 * power of 2 greater than 1. The arrays B, V, and XY must be aligned to a
225 * multiple of 64 bytes.
226 */
227 static void
smix(uint8_t * B,size_t r,uint64_t N,uint32_t * V,uint32_t * XY)228 smix(uint8_t *B, size_t r, uint64_t N, uint32_t *V, uint32_t *XY)
229 {
230 uint32_t *X = XY;
231 uint32_t *Y = &XY[32 * r];
232 uint32_t *Z = &XY[64 * r];
233 uint64_t i;
234 uint64_t j;
235 size_t k;
236
237 /* 1: X <-- B */
238 for (k = 0; k < 32 * r; k++) {
239 X[k] = LOAD32_LE(&B[4 * k]);
240 }
241 /* 2: for i = 0 to N - 1 do */
242 for (i = 0; i < N; i += 2) {
243 /* 3: V_i <-- X */
244 blkcpy((escrypt_block_t *) &V[i * (32 * r)], (escrypt_block_t *) X,
245 128 * r);
246
247 /* 4: X <-- H(X) */
248 blockmix_salsa8(X, Y, Z, r);
249
250 /* 3: V_i <-- X */
251 blkcpy((escrypt_block_t *) &V[(i + 1) * (32 * r)],
252 (escrypt_block_t *) Y, 128 * r);
253
254 /* 4: X <-- H(X) */
255 blockmix_salsa8(Y, X, Z, r);
256 }
257
258 /* 6: for i = 0 to N - 1 do */
259 for (i = 0; i < N; i += 2) {
260 /* 7: j <-- Integerify(X) mod N */
261 j = integerify(X, r) & (N - 1);
262
263 /* 8: X <-- H(X \xor V_j) */
264 blkxor((escrypt_block_t *) X, (escrypt_block_t *) &V[j * (32 * r)],
265 128 * r);
266 blockmix_salsa8(X, Y, Z, r);
267
268 /* 7: j <-- Integerify(X) mod N */
269 j = integerify(Y, r) & (N - 1);
270
271 /* 8: X <-- H(X \xor V_j) */
272 blkxor((escrypt_block_t *) Y, (escrypt_block_t *) &V[j * (32 * r)],
273 128 * r);
274 blockmix_salsa8(Y, X, Z, r);
275 }
276 /* 10: B' <-- X */
277 for (k = 0; k < 32 * r; k++) {
278 STORE32_LE(&B[4 * k], X[k]);
279 }
280 }
281
282 /**
283 * escrypt_kdf(local, passwd, passwdlen, salt, saltlen,
284 * N, r, p, buf, buflen):
285 * Compute scrypt(passwd[0 .. passwdlen - 1], salt[0 .. saltlen - 1], N, r,
286 * p, buflen) and write the result into buf. The parameters r, p, and buflen
287 * must satisfy r * p < 2^30 and buflen <= (2^32 - 1) * 32. The parameter N
288 * must be a power of 2 greater than 1.
289 *
290 * Return 0 on success; or -1 on error.
291 */
292 int
escrypt_kdf_nosse(escrypt_local_t * local,const uint8_t * passwd,size_t passwdlen,const uint8_t * salt,size_t saltlen,uint64_t N,uint32_t _r,uint32_t _p,uint8_t * buf,size_t buflen)293 escrypt_kdf_nosse(escrypt_local_t *local, const uint8_t *passwd,
294 size_t passwdlen, const uint8_t *salt, size_t saltlen,
295 uint64_t N, uint32_t _r, uint32_t _p, uint8_t *buf,
296 size_t buflen)
297 {
298 size_t B_size, V_size, XY_size, need;
299 uint8_t * B;
300 uint32_t *V, *XY;
301 size_t r = _r, p = _p;
302 uint32_t i;
303
304 /* Sanity-check parameters. */
305 #if SIZE_MAX > UINT32_MAX
306 if (buflen > (((uint64_t)(1) << 32) - 1) * 32) {
307 errno = EFBIG;
308 return -1;
309 }
310 #endif
311 if ((uint64_t)(r) * (uint64_t)(p) >= ((uint64_t) 1 << 30)) {
312 errno = EFBIG;
313 return -1;
314 }
315 if (N > UINT32_MAX) {
316 errno = EFBIG;
317 return -1;
318 }
319 if (((N & (N - 1)) != 0) || (N < 2)) {
320 errno = EINVAL;
321 return -1;
322 }
323 if (r == 0 || p == 0) {
324 errno = EINVAL;
325 return -1;
326 }
327 if ((r > SIZE_MAX / 128 / p) ||
328 #if SIZE_MAX / 256 <= UINT32_MAX
329 (r > SIZE_MAX / 256) ||
330 #endif
331 (N > SIZE_MAX / 128 / r)) {
332 errno = ENOMEM;
333 return -1;
334 }
335
336 /* Allocate memory. */
337 B_size = (size_t) 128 * r * p;
338 V_size = (size_t) 128 * r * (size_t) N;
339 need = B_size + V_size;
340 if (need < V_size) {
341 errno = ENOMEM;
342 return -1;
343 }
344 XY_size = (size_t) 256 * r + 64;
345 need += XY_size;
346 if (need < XY_size) {
347 errno = ENOMEM;
348 return -1;
349 }
350 if (local->size < need) {
351 if (free_region(local)) {
352 return -1;
353 }
354 if (!alloc_region(local, need)) {
355 return -1;
356 }
357 }
358 B = (uint8_t *) local->aligned;
359 V = (uint32_t *) ((uint8_t *) B + B_size);
360 XY = (uint32_t *) ((uint8_t *) V + V_size);
361
362 /* 1: (B_0 ... B_{p-1}) <-- PBKDF2(P, S, 1, p * MFLen) */
363 PBKDF2_SHA256(passwd, passwdlen, salt, saltlen, 1, B, B_size);
364
365 /* 2: for i = 0 to p - 1 do */
366 for (i = 0; i < p; i++) {
367 /* 3: B_i <-- MF(B_i, N) */
368 smix(&B[(size_t) 128 * i * r], r, N, V, XY);
369 }
370
371 /* 5: DK <-- PBKDF2(P, B, 1, dkLen) */
372 PBKDF2_SHA256(passwd, passwdlen, B, B_size, 1, buf, buflen);
373
374 /* Success! */
375 return 0;
376 }
377