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 * blockmix_salsa8(Bin, Bout, X, r):
172 * Compute Bout = BlockMix_{salsa20/8, r}(Bin). The input Bin must be 128r
173 * bytes in length; the output Bout must also be the same size. The
174 * temporary space X must be 64 bytes.
175 */
176 static void
blockmix_salsa8(const uint32_t * Bin,uint32_t * Bout,uint32_t * X,size_t r)177 blockmix_salsa8(const uint32_t *Bin, uint32_t *Bout, uint32_t *X, size_t r)
178 {
179 size_t i;
180
181 /* 1: X <-- B_{2r - 1} */
182 blkcpy_64((escrypt_block_t *) X,
183 (escrypt_block_t *) &Bin[(2 * r - 1) * 16]);
184
185 /* 2: for i = 0 to 2r - 1 do */
186 for (i = 0; i < 2 * r; i += 2) {
187 /* 3: X <-- H(X \xor B_i) */
188 blkxor_64((escrypt_block_t *) X, (escrypt_block_t *) &Bin[i * 16]);
189 salsa20_8(X);
190
191 /* 4: Y_i <-- X */
192 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
193 blkcpy_64((escrypt_block_t *) &Bout[i * 8], (escrypt_block_t *) X);
194
195 /* 3: X <-- H(X \xor B_i) */
196 blkxor_64((escrypt_block_t *) X, (escrypt_block_t *) &Bin[i * 16 + 16]);
197 salsa20_8(X);
198
199 /* 4: Y_i <-- X */
200 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
201 blkcpy_64((escrypt_block_t *) &Bout[i * 8 + r * 16],
202 (escrypt_block_t *) X);
203 }
204 }
205
206 /**
207 * integerify(B, r):
208 * Return the result of parsing B_{2r-1} as a little-endian integer.
209 */
210 static inline uint64_t
integerify(const void * B,size_t r)211 integerify(const void *B, size_t r)
212 {
213 const uint32_t *X = (const uint32_t *) ((uintptr_t)(B) + (2 * r - 1) * 64);
214
215 return (((uint64_t)(X[1]) << 32) + X[0]);
216 }
217
218 /**
219 * smix(B, r, N, V, XY):
220 * Compute B = SMix_r(B, N). The input B must be 128r bytes in length;
221 * the temporary storage V must be 128rN bytes in length; the temporary
222 * storage XY must be 256r + 64 bytes in length. The value N must be a
223 * power of 2 greater than 1. The arrays B, V, and XY must be aligned to a
224 * multiple of 64 bytes.
225 */
226 static void
smix(uint8_t * B,size_t r,uint64_t N,uint32_t * V,uint32_t * XY)227 smix(uint8_t *B, size_t r, uint64_t N, uint32_t *V, uint32_t *XY)
228 {
229 uint32_t *X = XY;
230 uint32_t *Y = &XY[32 * r];
231 uint32_t *Z = &XY[64 * r];
232 uint64_t i;
233 uint64_t j;
234 size_t k;
235
236 /* 1: X <-- B */
237 for (k = 0; k < 32 * r; k++) {
238 X[k] = LOAD32_LE(&B[4 * k]);
239 }
240 /* 2: for i = 0 to N - 1 do */
241 for (i = 0; i < N; i += 2) {
242 /* 3: V_i <-- X */
243 blkcpy((escrypt_block_t *) &V[i * (32 * r)], (escrypt_block_t *) X,
244 128 * r);
245
246 /* 4: X <-- H(X) */
247 blockmix_salsa8(X, Y, Z, r);
248
249 /* 3: V_i <-- X */
250 blkcpy((escrypt_block_t *) &V[(i + 1) * (32 * r)],
251 (escrypt_block_t *) Y, 128 * r);
252
253 /* 4: X <-- H(X) */
254 blockmix_salsa8(Y, X, Z, r);
255 }
256
257 /* 6: for i = 0 to N - 1 do */
258 for (i = 0; i < N; i += 2) {
259 /* 7: j <-- Integerify(X) mod N */
260 j = integerify(X, r) & (N - 1);
261
262 /* 8: X <-- H(X \xor V_j) */
263 blkxor((escrypt_block_t *) X, (escrypt_block_t *) &V[j * (32 * r)],
264 128 * r);
265 blockmix_salsa8(X, Y, Z, r);
266
267 /* 7: j <-- Integerify(X) mod N */
268 j = integerify(Y, r) & (N - 1);
269
270 /* 8: X <-- H(X \xor V_j) */
271 blkxor((escrypt_block_t *) Y, (escrypt_block_t *) &V[j * (32 * r)],
272 128 * r);
273 blockmix_salsa8(Y, X, Z, r);
274 }
275 /* 10: B' <-- X */
276 for (k = 0; k < 32 * r; k++) {
277 STORE32_LE(&B[4 * k], X[k]);
278 }
279 }
280
281 /**
282 * escrypt_kdf(local, passwd, passwdlen, salt, saltlen,
283 * N, r, p, buf, buflen):
284 * Compute scrypt(passwd[0 .. passwdlen - 1], salt[0 .. saltlen - 1], N, r,
285 * p, buflen) and write the result into buf. The parameters r, p, and buflen
286 * must satisfy r * p < 2^30 and buflen <= (2^32 - 1) * 32. The parameter N
287 * must be a power of 2 greater than 1.
288 *
289 * Return 0 on success; or -1 on error.
290 */
291 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)292 escrypt_kdf_nosse(escrypt_local_t *local, const uint8_t *passwd,
293 size_t passwdlen, const uint8_t *salt, size_t saltlen,
294 uint64_t N, uint32_t _r, uint32_t _p, uint8_t *buf,
295 size_t buflen)
296 {
297 size_t B_size, V_size, XY_size, need;
298 uint8_t * B;
299 uint32_t *V, *XY;
300 size_t r = _r, p = _p;
301 uint32_t i;
302
303 /* Sanity-check parameters. */
304 #if SIZE_MAX > UINT32_MAX
305 if (buflen > (((uint64_t)(1) << 32) - 1) * 32) {
306 errno = EFBIG;
307 return -1;
308 }
309 #endif
310 if ((uint64_t)(r) * (uint64_t)(p) >= ((uint64_t) 1 << 30)) {
311 errno = EFBIG;
312 return -1;
313 }
314 if (N > UINT32_MAX) {
315 errno = EFBIG;
316 return -1;
317 }
318 if (((N & (N - 1)) != 0) || (N < 2)) {
319 errno = EINVAL;
320 return -1;
321 }
322 if (r == 0 || p == 0) {
323 errno = EINVAL;
324 return -1;
325 }
326 if ((r > SIZE_MAX / 128 / p) ||
327 #if SIZE_MAX / 256 <= UINT32_MAX
328 (r > SIZE_MAX / 256) ||
329 #endif
330 (N > SIZE_MAX / 128 / r)) {
331 errno = ENOMEM;
332 return -1;
333 }
334
335 /* Allocate memory. */
336 B_size = (size_t) 128 * r * p;
337 V_size = (size_t) 128 * r * (size_t) N;
338 need = B_size + V_size;
339 if (need < V_size) {
340 errno = ENOMEM;
341 return -1;
342 }
343 XY_size = (size_t) 256 * r + 64;
344 need += XY_size;
345 if (need < XY_size) {
346 errno = ENOMEM;
347 return -1;
348 }
349 if (local->size < need) {
350 if (free_region(local)) {
351 return -1;
352 }
353 if (!alloc_region(local, need)) {
354 return -1;
355 }
356 }
357 B = (uint8_t *) local->aligned;
358 V = (uint32_t *) ((uint8_t *) B + B_size);
359 XY = (uint32_t *) ((uint8_t *) V + V_size);
360
361 /* 1: (B_0 ... B_{p-1}) <-- PBKDF2(P, S, 1, p * MFLen) */
362 PBKDF2_SHA256(passwd, passwdlen, salt, saltlen, 1, B, B_size);
363
364 /* 2: for i = 0 to p - 1 do */
365 for (i = 0; i < p; i++) {
366 /* 3: B_i <-- MF(B_i, N) */
367 smix(&B[(size_t) 128 * i * r], r, N, V, XY);
368 }
369
370 /* 5: DK <-- PBKDF2(P, B, 1, dkLen) */
371 PBKDF2_SHA256(passwd, passwdlen, B, B_size, 1, buf, buflen);
372
373 /* Success! */
374 return 0;
375 }
376