Debian Codegraph @

lib/alg-yescrypt-opt.c

raw
1 /*-
2 * Copyright 2009 Colin Percival
3 * Copyright 2012-2025 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 "crypt-port.h"
32
33 #if INCLUDE_yescrypt || INCLUDE_scrypt || INCLUDE_gost_yescrypt || \
34 INCLUDE_sm3_yescrypt
35
36 #pragma GCC diagnostic ignored "-Wcast-align"
37 #pragma GCC diagnostic ignored "-Wconversion"
38 #ifdef __clang__
39 #pragma GCC diagnostic ignored "-Wtautological-constant-out-of-range-compare"
40 #endif
41
42 /*
43 * AVX and especially XOP speed up Salsa20 a lot, but this mostly matters for
44 * classic scrypt and for YESCRYPT_WORM (which use 8 rounds of Salsa20 per
45 * sub-block), and much less so for YESCRYPT_RW (which uses 2 rounds of Salsa20
46 * per block except during pwxform S-box initialization).
47 */
48 #if 0
49 #ifdef __XOP__
50 #warning "Note: XOP is enabled. That's great."
51 #elif defined(__AVX512VL__)
52 #warning "Note: AVX512VL is enabled. That's great."
53 #elif defined(__AVX__)
54 #warning "Note: AVX is enabled, which is great for classic scrypt and YESCRYPT_WORM, but is sometimes slightly slower than plain SSE2 for YESCRYPT_RW"
55 #elif defined(__SSE2__)
56 #warning "Note: AVX and XOP are not enabled, which is great for YESCRYPT_RW, but they would substantially improve performance at classic scrypt and YESCRYPT_WORM"
57 #elif defined(__x86_64__) || defined(__i386__)
58 #warning "SSE2 not enabled. Expect poor performance."
59 #else
60 #warning "Note: building generic code for non-x86. That's OK."
61 #endif
62 #endif
63
64 /*
65 * The SSE4 code version has fewer instructions than the generic SSE2 version,
66 * but all of the instructions are SIMD, thereby wasting the scalar execution
67 * units. Thus, the generic SSE2 version below actually runs faster on some
68 * CPUs due to its balanced mix of SIMD and scalar instructions.
69 */
70 #undef USE_SSE4_FOR_32BIT
71
72 #ifdef __SSE2__
73 /*
74 * GCC before 4.9 would by default unnecessarily use store/load (without
75 * SSE4.1) or (V)PEXTR (with SSE4.1 or AVX) instead of simply (V)MOV.
76 * This was tracked as GCC bug 54349.
77 * "-mtune=corei7" works around this, but is only supported for GCC 4.6+.
78 * We use inline asm for pre-4.6 GCC, further down this file.
79 */
80 #if __GNUC__ == 4 && __GNUC_MINOR__ >= 6 && __GNUC_MINOR__ < 9 && \
81 !defined(__clang__) && !defined(__ICC)
82 #pragma GCC target ("tune=corei7")
83 #endif
84 #include <emmintrin.h>
85 #ifdef __XOP__
86 #include <x86intrin.h>
87 #elif defined(__AVX512VL__)
88 #include <immintrin.h>
89 #endif
90 #elif defined(__SSE__)
91 #include <xmmintrin.h>
92 #endif
93
94 #include <assert.h>
95 #include <errno.h>
96 #include <stdint.h>
97 #include <stdlib.h>
98 #include <string.h>
99
100 #include "alg-sha256.h"
101 #include "byteorder.h"
102
103 #define YESCRYPT_INTERNAL
104 #include "alg-yescrypt.h"
105
106 #include "alg-yescrypt-platform.c"
107
108 #if __STDC_VERSION__ >= 199901L
109 /* Have restrict */
110 #elif defined(__GNUC__)
111 #define restrict __restrict
112 #else
113 #define restrict
114 #endif
115
116 #ifdef __GNUC__
117 #define unlikely(exp) __builtin_expect(exp, 0)
118 #else
119 #define unlikely(exp) (exp)
120 #endif
121
122 #ifdef __SSE__
123 #define PREFETCH(x, hint) _mm_prefetch((x), (hint));
124 /* Older versions of clang have a bug in their xmmintrin.h that causes
125 spurious -Wcast-qual warnings on uses of _mm_prefetch. */
126 # if defined __clang_major__ && __clang_major__ < 11
127 # pragma clang diagnostic ignored "-Wcast-qual"
128 # endif
129 #else
130 #undef PREFETCH
131 #endif
132
133 typedef union {
134 uint32_t w[16];
135 uint64_t d[8];
136 #ifdef __SSE2__
137 __m128i q[4];
138 #endif
139 } salsa20_blk_t;
140
141 static inline void salsa20_simd_shuffle(const salsa20_blk_t *Bin,
142 salsa20_blk_t *Bout)
143 {
144 #define COMBINE(out, in1, in2) \
145 Bout->d[out] = Bin->w[in1 * 2] | ((uint64_t)Bin->w[in2 * 2 + 1] << 32);
146 COMBINE(0, 0, 2)
147 COMBINE(1, 5, 7)
148 COMBINE(2, 2, 4)
149 COMBINE(3, 7, 1)
150 COMBINE(4, 4, 6)
151 COMBINE(5, 1, 3)
152 COMBINE(6, 6, 0)
153 COMBINE(7, 3, 5)
154 #undef COMBINE
155 }
156
157 static inline void salsa20_simd_unshuffle(const salsa20_blk_t *Bin,
158 salsa20_blk_t *Bout)
159 {
160 #define UNCOMBINE(out, in1, in2) \
161 Bout->w[out * 2] = Bin->d[in1]; \
162 Bout->w[out * 2 + 1] = Bin->d[in2] >> 32;
163 UNCOMBINE(0, 0, 6)
164 UNCOMBINE(1, 5, 3)
165 UNCOMBINE(2, 2, 0)
166 UNCOMBINE(3, 7, 5)
167 UNCOMBINE(4, 4, 2)
168 UNCOMBINE(5, 1, 7)
169 UNCOMBINE(6, 6, 4)
170 UNCOMBINE(7, 3, 1)
171 #undef UNCOMBINE
172 }
173
174 #ifdef __SSE2__
175 #define DECL_X \
176 __m128i X0, X1, X2, X3;
177 #define DECL_Y \
178 __m128i Y0, Y1, Y2, Y3;
179 #define READ_X(in) \
180 X0 = (in).q[0]; X1 = (in).q[1]; X2 = (in).q[2]; X3 = (in).q[3];
181 #define WRITE_X(out) \
182 (out).q[0] = X0; (out).q[1] = X1; (out).q[2] = X2; (out).q[3] = X3;
183
184 #ifdef __XOP__
185 #define ARX(out, in1, in2, s) \
186 out = _mm_xor_si128(out, _mm_roti_epi32(_mm_add_epi32(in1, in2), s));
187 #elif defined(__AVX512VL__)
188 #define ARX(out, in1, in2, s) \
189 out = _mm_xor_si128(out, _mm_rol_epi32(_mm_add_epi32(in1, in2), s));
190 #else
191 #define ARX(out, in1, in2, s) { \
192 __m128i tmp = _mm_add_epi32(in1, in2); \
193 out = _mm_xor_si128(out, _mm_slli_epi32(tmp, s)); \
194 out = _mm_xor_si128(out, _mm_srli_epi32(tmp, 32 - s)); \
195 }
196 #endif
197
198 #define SALSA20_2ROUNDS \
199 /* Operate on "columns" */ \
200 ARX(X1, X0, X3, 7) \
201 ARX(X2, X1, X0, 9) \
202 ARX(X3, X2, X1, 13) \
203 ARX(X0, X3, X2, 18) \
204 /* Rearrange data */ \
205 X1 = _mm_shuffle_epi32(X1, 0x93); \
206 X2 = _mm_shuffle_epi32(X2, 0x4E); \
207 X3 = _mm_shuffle_epi32(X3, 0x39); \
208 /* Operate on "rows" */ \
209 ARX(X3, X0, X1, 7) \
210 ARX(X2, X3, X0, 9) \
211 ARX(X1, X2, X3, 13) \
212 ARX(X0, X1, X2, 18) \
213 /* Rearrange data */ \
214 X1 = _mm_shuffle_epi32(X1, 0x39); \
215 X2 = _mm_shuffle_epi32(X2, 0x4E); \
216 X3 = _mm_shuffle_epi32(X3, 0x93);
217
218 /**
219 * Apply the Salsa20 core to the block provided in (X0 ... X3).
220 */
221 #define SALSA20_wrapper(out, rounds) { \
222 __m128i Z0 = X0, Z1 = X1, Z2 = X2, Z3 = X3; \
223 rounds \
224 (out).q[0] = X0 = _mm_add_epi32(X0, Z0); \
225 (out).q[1] = X1 = _mm_add_epi32(X1, Z1); \
226 (out).q[2] = X2 = _mm_add_epi32(X2, Z2); \
227 (out).q[3] = X3 = _mm_add_epi32(X3, Z3); \
228 }
229
230 /**
231 * Apply the Salsa20/2 core to the block provided in X.
232 */
233 #define SALSA20_2(out) \
234 SALSA20_wrapper(out, SALSA20_2ROUNDS)
235
236 #define SALSA20_8ROUNDS \
237 SALSA20_2ROUNDS SALSA20_2ROUNDS SALSA20_2ROUNDS SALSA20_2ROUNDS
238
239 #define XOR_X(in) \
240 X0 = _mm_xor_si128(X0, (in).q[0]); \
241 X1 = _mm_xor_si128(X1, (in).q[1]); \
242 X2 = _mm_xor_si128(X2, (in).q[2]); \
243 X3 = _mm_xor_si128(X3, (in).q[3]);
244
245 #define XOR_X_2(in1, in2) \
246 X0 = _mm_xor_si128((in1).q[0], (in2).q[0]); \
247 X1 = _mm_xor_si128((in1).q[1], (in2).q[1]); \
248 X2 = _mm_xor_si128((in1).q[2], (in2).q[2]); \
249 X3 = _mm_xor_si128((in1).q[3], (in2).q[3]);
250
251 #define XOR_X_WRITE_XOR_Y_2(out, in) \
252 (out).q[0] = Y0 = _mm_xor_si128((out).q[0], (in).q[0]); \
253 (out).q[1] = Y1 = _mm_xor_si128((out).q[1], (in).q[1]); \
254 (out).q[2] = Y2 = _mm_xor_si128((out).q[2], (in).q[2]); \
255 (out).q[3] = Y3 = _mm_xor_si128((out).q[3], (in).q[3]); \
256 X0 = _mm_xor_si128(X0, Y0); \
257 X1 = _mm_xor_si128(X1, Y1); \
258 X2 = _mm_xor_si128(X2, Y2); \
259 X3 = _mm_xor_si128(X3, Y3);
260
261 /**
262 * Apply the Salsa20/8 core to the block provided in X ^ in.
263 */
264 #define SALSA20_8_XOR_MEM(in, out) \
265 XOR_X(in) \
266 SALSA20_wrapper(out, SALSA20_8ROUNDS)
267
268 #define INTEGERIFY (uint32_t)_mm_cvtsi128_si32(X0)
269
270 #else /* !defined(__SSE2__) */
271
272 #define DECL_X \
273 salsa20_blk_t X;
274 #define DECL_Y \
275 salsa20_blk_t Y;
276
277 #define COPY(out, in) \
278 (out).d[0] = (in).d[0]; \
279 (out).d[1] = (in).d[1]; \
280 (out).d[2] = (in).d[2]; \
281 (out).d[3] = (in).d[3]; \
282 (out).d[4] = (in).d[4]; \
283 (out).d[5] = (in).d[5]; \
284 (out).d[6] = (in).d[6]; \
285 (out).d[7] = (in).d[7];
286
287 #define READ_X(in) COPY(X, in)
288 #define WRITE_X(out) COPY(out, X)
289
290 /**
291 * salsa20(B):
292 * Apply the Salsa20 core to the provided block.
293 */
294 static inline void salsa20(salsa20_blk_t *restrict B,
295 salsa20_blk_t *restrict Bout, uint32_t doublerounds)
296 {
297 salsa20_blk_t X;
298 #define x X.w
299
300 salsa20_simd_unshuffle(B, &X);
301
302 do {
303 #define R(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
304 /* Operate on columns */
305 x[ 4] ^= R(x[ 0]+x[12], 7); x[ 8] ^= R(x[ 4]+x[ 0], 9);
306 x[12] ^= R(x[ 8]+x[ 4],13); x[ 0] ^= R(x[12]+x[ 8],18);
307
308 x[ 9] ^= R(x[ 5]+x[ 1], 7); x[13] ^= R(x[ 9]+x[ 5], 9);
309 x[ 1] ^= R(x[13]+x[ 9],13); x[ 5] ^= R(x[ 1]+x[13],18);
310
311 x[14] ^= R(x[10]+x[ 6], 7); x[ 2] ^= R(x[14]+x[10], 9);
312 x[ 6] ^= R(x[ 2]+x[14],13); x[10] ^= R(x[ 6]+x[ 2],18);
313
314 x[ 3] ^= R(x[15]+x[11], 7); x[ 7] ^= R(x[ 3]+x[15], 9);
315 x[11] ^= R(x[ 7]+x[ 3],13); x[15] ^= R(x[11]+x[ 7],18);
316
317 /* Operate on rows */
318 x[ 1] ^= R(x[ 0]+x[ 3], 7); x[ 2] ^= R(x[ 1]+x[ 0], 9);
319 x[ 3] ^= R(x[ 2]+x[ 1],13); x[ 0] ^= R(x[ 3]+x[ 2],18);
320
321 x[ 6] ^= R(x[ 5]+x[ 4], 7); x[ 7] ^= R(x[ 6]+x[ 5], 9);
322 x[ 4] ^= R(x[ 7]+x[ 6],13); x[ 5] ^= R(x[ 4]+x[ 7],18);
323
324 x[11] ^= R(x[10]+x[ 9], 7); x[ 8] ^= R(x[11]+x[10], 9);
325 x[ 9] ^= R(x[ 8]+x[11],13); x[10] ^= R(x[ 9]+x[ 8],18);
326
327 x[12] ^= R(x[15]+x[14], 7); x[13] ^= R(x[12]+x[15], 9);
328 x[14] ^= R(x[13]+x[12],13); x[15] ^= R(x[14]+x[13],18);
329 #undef R
330 } while (--doublerounds);
331 #undef x
332
333 {
334 uint32_t i;
335 salsa20_simd_shuffle(&X, Bout);
336 for (i = 0; i < 16; i += 4) {
337 B->w[i] = Bout->w[i] += B->w[i];
338 B->w[i + 1] = Bout->w[i + 1] += B->w[i + 1];
339 B->w[i + 2] = Bout->w[i + 2] += B->w[i + 2];
340 B->w[i + 3] = Bout->w[i + 3] += B->w[i + 3];
341 }
342 }
343
344 #if 0
345 /* Too expensive */
346 explicit_bzero(&X, sizeof(X));
347 #endif
348 }
349
350 /**
351 * Apply the Salsa20/2 core to the block provided in X.
352 */
353 #define SALSA20_2(out) \
354 salsa20(&X, &out, 1);
355
356 #define XOR(out, in1, in2) \
357 (out).d[0] = (in1).d[0] ^ (in2).d[0]; \
358 (out).d[1] = (in1).d[1] ^ (in2).d[1]; \
359 (out).d[2] = (in1).d[2] ^ (in2).d[2]; \
360 (out).d[3] = (in1).d[3] ^ (in2).d[3]; \
361 (out).d[4] = (in1).d[4] ^ (in2).d[4]; \
362 (out).d[5] = (in1).d[5] ^ (in2).d[5]; \
363 (out).d[6] = (in1).d[6] ^ (in2).d[6]; \
364 (out).d[7] = (in1).d[7] ^ (in2).d[7];
365
366 #define XOR_X(in) XOR(X, X, in)
367 #define XOR_X_2(in1, in2) XOR(X, in1, in2)
368 #define XOR_X_WRITE_XOR_Y_2(out, in) \
369 XOR(Y, out, in) \
370 COPY(out, Y) \
371 XOR(X, X, Y)
372
373 /**
374 * Apply the Salsa20/8 core to the block provided in X ^ in.
375 */
376 #define SALSA20_8_XOR_MEM(in, out) \
377 XOR_X(in); \
378 salsa20(&X, &out, 4);
379
380 #define INTEGERIFY (uint32_t)X.d[0]
381 #endif
382
383 /**
384 * blockmix_salsa8(Bin, Bout, r):
385 * Compute Bout = BlockMix_{salsa20/8, r}(Bin). The input Bin must be 128r
386 * bytes in length; the output Bout must also be the same size.
387 */
388 static void blockmix_salsa8(const salsa20_blk_t *restrict Bin,
389 salsa20_blk_t *restrict Bout, size_t r)
390 {
391 size_t i;
392 DECL_X
393
394 READ_X(Bin[r * 2 - 1])
395 for (i = 0; i < r; i++) {
396 SALSA20_8_XOR_MEM(Bin[i * 2], Bout[i])
397 SALSA20_8_XOR_MEM(Bin[i * 2 + 1], Bout[r + i])
398 }
399 }
400
401 static uint32_t blockmix_salsa8_xor(const salsa20_blk_t *restrict Bin1,
402 const salsa20_blk_t *restrict Bin2, salsa20_blk_t *restrict Bout,
403 size_t r)
404 {
405 size_t i;
406 DECL_X
407
408 #ifdef PREFETCH
409 PREFETCH(&Bin2[r * 2 - 1], _MM_HINT_T0)
410 for (i = 0; i < r - 1; i++) {
411 PREFETCH(&Bin2[i * 2], _MM_HINT_T0)
412 PREFETCH(&Bin2[i * 2 + 1], _MM_HINT_T0)
413 }
414 PREFETCH(&Bin2[i * 2], _MM_HINT_T0)
415 #endif
416
417 XOR_X_2(Bin1[r * 2 - 1], Bin2[r * 2 - 1])
418 for (i = 0; i < r; i++) {
419 XOR_X(Bin1[i * 2])
420 SALSA20_8_XOR_MEM(Bin2[i * 2], Bout[i])
421 XOR_X(Bin1[i * 2 + 1])
422 SALSA20_8_XOR_MEM(Bin2[i * 2 + 1], Bout[r + i])
423 }
424
425 return INTEGERIFY;
426 }
427
428 /* This is tunable */
429 #define Swidth 8
430
431 /* Not tunable in this implementation, hard-coded in a few places */
432 #define PWXsimple 2
433 #define PWXgather 4
434
435 /* Derived values. Not tunable except via Swidth above. */
436 #define PWXbytes (PWXgather * PWXsimple * 8)
437 #define Sbytes (3 * (1 << Swidth) * PWXsimple * 8)
438 #define Smask (((1 << Swidth) - 1) * PWXsimple * 8)
439 #define Smask2 (((uint64_t)Smask << 32) | Smask)
440
441 #define DECL_SMASK2REG /* empty */
442 #define FORCE_REGALLOC_3 /* empty */
443 #define MAYBE_MEMORY_BARRIER /* empty */
444
445 #ifdef __SSE2__
446 /*
447 * (V)PSRLDQ and (V)PSHUFD have higher throughput than (V)PSRLQ on some CPUs
448 * starting with Sandy Bridge. Additionally, PSHUFD uses separate source and
449 * destination registers, whereas the shifts would require an extra move
450 * instruction for our code when building without AVX. Unfortunately, PSHUFD
451 * is much slower on Conroe (4 cycles latency vs. 1 cycle latency for PSRLQ)
452 * and somewhat slower on some non-Intel CPUs (luckily not including AMD
453 * Bulldozer and Piledriver).
454 */
455 #ifdef __AVX__
456 #define HI32(X) \
457 _mm_srli_si128((X), 4)
458 #elif 1 /* As an option, check for __SSE4_1__ here not to hurt Conroe */
459 #define HI32(X) \
460 _mm_shuffle_epi32((X), _MM_SHUFFLE(2,3,0,1))
461 #else
462 #define HI32(X) \
463 _mm_srli_epi64((X), 32)
464 #endif
465
466 #if defined(__x86_64__) && \
467 __GNUC__ == 4 && __GNUC_MINOR__ < 6 && !defined(__ICC)
468 #ifdef __AVX__
469 #define MOVQ "vmovq"
470 #else
471 /* "movq" would be more correct, but "movd" is supported by older binutils
472 * due to an error in AMD's spec for x86-64. */
473 #define MOVQ "movd"
474 #endif
475 #define EXTRACT64(X) ({ \
476 uint64_t result; \
477 __asm__(MOVQ " %1, %0" : "=r" (result) : "x" (X)); \
478 result; \
479 })
480 #elif defined(__x86_64__) && !defined(_MSC_VER) && !defined(__OPEN64__)
481 /* MSVC and Open64 had bugs */
482 #define EXTRACT64(X) _mm_cvtsi128_si64(X)
483 #elif defined(__x86_64__) && defined(__SSE4_1__)
484 /* No known bugs for this intrinsic */
485 #include <smmintrin.h>
486 #define EXTRACT64(X) _mm_extract_epi64((X), 0)
487 #elif defined(USE_SSE4_FOR_32BIT) && defined(__SSE4_1__)
488 /* 32-bit */
489 #include <smmintrin.h>
490 #if 0
491 /* This is currently unused by the code below, which instead uses these two
492 * intrinsics explicitly when (!defined(__x86_64__) && defined(__SSE4_1__)) */
493 #define EXTRACT64(X) \
494 ((uint64_t)(uint32_t)_mm_cvtsi128_si32(X) | \
495 ((uint64_t)(uint32_t)_mm_extract_epi32((X), 1) << 32))
496 #endif
497 #else
498 /* 32-bit or compilers with known past bugs in _mm_cvtsi128_si64() */
499 #define EXTRACT64(X) \
500 ((uint64_t)(uint32_t)_mm_cvtsi128_si32(X) | \
501 ((uint64_t)(uint32_t)_mm_cvtsi128_si32(HI32(X)) << 32))
502 #endif
503
504 #if defined(__x86_64__) && (defined(__AVX__) || !defined(__GNUC__))
505 /* 64-bit with AVX */
506 /* Force use of 64-bit AND instead of two 32-bit ANDs */
507 #undef DECL_SMASK2REG
508 #if defined(__GNUC__) && !defined(__ICC)
509 #define DECL_SMASK2REG uint64_t Smask2reg = Smask2;
510 /* Force use of lower-numbered registers to reduce number of prefixes, relying
511 * on out-of-order execution and register renaming. */
512 #define FORCE_REGALLOC_1 \
513 __asm__("" : "=a" (x), "+d" (Smask2reg), "+S" (S0), "+D" (S1));
514 #define FORCE_REGALLOC_2 \
515 __asm__("" : : "c" (lo));
516 #else
517 static volatile uint64_t Smask2var = Smask2;
518 #define DECL_SMASK2REG uint64_t Smask2reg = Smask2var;
519 #define FORCE_REGALLOC_1 /* empty */
520 #define FORCE_REGALLOC_2 /* empty */
521 #endif
522 #define PWXFORM_SIMD(X) { \
523 uint64_t x; \
524 FORCE_REGALLOC_1 \
525 uint32_t lo = (uint32_t)(x = ((uint64_t)EXTRACT64(X)) & Smask2reg); \
526 FORCE_REGALLOC_2 \
527 uint32_t hi = x >> 32; \
528 X = _mm_mul_epu32(HI32(X), X); \
529 X = _mm_add_epi64(X, *(__m128i *)(S0 + lo)); \
530 X = _mm_xor_si128(X, *(__m128i *)(S1 + hi)); \
531 }
532 #elif defined(__x86_64__)
533 /* 64-bit without AVX. This relies on out-of-order execution and register
534 * renaming. It may actually be fastest on CPUs with AVX(2) as well - e.g.,
535 * it runs great on Haswell. */
536 #if 0
537 #warning "Note: using x86-64 inline assembly for YESCRYPT_RW. That's great."
538 #endif
539 /* We need a compiler memory barrier between sub-blocks to ensure that none of
540 * the writes into what was S2 during processing of the previous sub-block are
541 * postponed until after a read from S0 or S1 in the inline asm code below. */
542 #undef MAYBE_MEMORY_BARRIER
543 #define MAYBE_MEMORY_BARRIER \
544 __asm__("" : : : "memory");
545 #ifdef __ILP32__ /* x32 */
546 #define REGISTER_PREFIX "e"
547 #else
548 #define REGISTER_PREFIX "r"
549 #endif
550 #define PWXFORM_SIMD(X) { \
551 __m128i H; \
552 __asm__( \
553 "movd %0, %%rax\n\t" \
554 "pshufd $0xb1, %0, %1\n\t" \
555 "andq %2, %%rax\n\t" \
556 "pmuludq %1, %0\n\t" \
557 "movl %%eax, %%ecx\n\t" \
558 "shrq $0x20, %%rax\n\t" \
559 "paddq (%3,%%" REGISTER_PREFIX "cx), %0\n\t" \
560 "pxor (%4,%%" REGISTER_PREFIX "ax), %0\n\t" \
561 : "+x" (X), "=x" (H) \
562 : "d" (Smask2), "S" (S0), "D" (S1) \
563 : "cc", "ax", "cx"); \
564 }
565 #elif defined(USE_SSE4_FOR_32BIT) && defined(__SSE4_1__)
566 /* 32-bit with SSE4.1 */
567 #define PWXFORM_SIMD(X) { \
568 __m128i x = _mm_and_si128(X, _mm_set1_epi64x(Smask2)); \
569 __m128i s0 = *(__m128i *)(S0 + (uint32_t)_mm_cvtsi128_si32(x)); \
570 __m128i s1 = *(__m128i *)(S1 + (uint32_t)_mm_extract_epi32(x, 1)); \
571 X = _mm_mul_epu32(HI32(X), X); \
572 X = _mm_add_epi64(X, s0); \
573 X = _mm_xor_si128(X, s1); \
574 }
575 #else
576 /* 32-bit without SSE4.1 */
577 #define PWXFORM_SIMD(X) { \
578 uint64_t x = EXTRACT64(X) & Smask2; \
579 __m128i s0 = *(__m128i *)(S0 + (uint32_t)x); \
580 __m128i s1 = *(__m128i *)(S1 + (x >> 32)); \
581 X = _mm_mul_epu32(HI32(X), X); \
582 X = _mm_add_epi64(X, s0); \
583 X = _mm_xor_si128(X, s1); \
584 }
585 #endif
586
587 #define PWXFORM_ROUND \
588 PWXFORM_SIMD(X0) \
589 PWXFORM_SIMD(X1) \
590 PWXFORM_SIMD(X2) \
591 PWXFORM_SIMD(X3)
592
593 #if defined(__x86_64__) && defined(__GNUC__) && !defined(__ICC)
594 #undef FORCE_REGALLOC_3
595 #define FORCE_REGALLOC_3 __asm__("" : : "b" (Sw));
596 #endif
597
598 #else /* !defined(__SSE2__) */
599
600 #define PWXFORM_SIMD(x0, x1) { \
601 uint64_t x = x0 & Smask2; \
602 uint64_t *p0 = (uint64_t *)(S0 + (uint32_t)x); \
603 uint64_t *p1 = (uint64_t *)(S1 + (x >> 32)); \
604 x0 = ((x0 >> 32) * (uint32_t)x0 + p0[0]) ^ p1[0]; \
605 x1 = ((x1 >> 32) * (uint32_t)x1 + p0[1]) ^ p1[1]; \
606 }
607
608 #define PWXFORM_ROUND \
609 PWXFORM_SIMD(X.d[0], X.d[1]) \
610 PWXFORM_SIMD(X.d[2], X.d[3]) \
611 PWXFORM_SIMD(X.d[4], X.d[5]) \
612 PWXFORM_SIMD(X.d[6], X.d[7])
613 #endif
614
615 /*
616 * This offset helps address the 256-byte write block via the single-byte
617 * displacements encodable in x86(-64) instructions. It is needed because the
618 * displacements are signed. Without it, we'd get 4-byte displacements for
619 * half of the writes. Setting it to 0x80 instead of 0x7c would avoid needing
620 * a displacement for one of the writes, but then the LEA instruction would
621 * need a 4-byte displacement.
622 */
623 #define PWXFORM_WRITE_OFFSET 0x7c
624
625 #define PWXFORM_WRITE \
626 WRITE_X(*(salsa20_blk_t *)(Sw - PWXFORM_WRITE_OFFSET)) \
627 Sw += 64;
628
629 #define PWXFORM { \
630 uint8_t *Sw = S2 + w + PWXFORM_WRITE_OFFSET; \
631 FORCE_REGALLOC_3 \
632 MAYBE_MEMORY_BARRIER \
633 PWXFORM_ROUND \
634 PWXFORM_ROUND PWXFORM_WRITE \
635 PWXFORM_ROUND PWXFORM_WRITE \
636 PWXFORM_ROUND PWXFORM_WRITE \
637 PWXFORM_ROUND PWXFORM_WRITE \
638 PWXFORM_ROUND \
639 w = (w + 64 * 4) & Smask2; \
640 { \
641 uint8_t *Stmp = S2; \
642 S2 = S1; \
643 S1 = S0; \
644 S0 = Stmp; \
645 } \
646 }
647
648 typedef struct {
649 uint8_t *S0, *S1, *S2;
650 size_t w;
651 } pwxform_ctx_t;
652
653 #define Salloc (Sbytes + ((sizeof(pwxform_ctx_t) + 63) & ~63U))
654
655 /**
656 * blockmix_pwxform(Bin, Bout, r, S):
657 * Compute Bout = BlockMix_pwxform{salsa20/2, r, S}(Bin). The input Bin must
658 * be 128r bytes in length; the output Bout must also be the same size.
659 */
660 static void blockmix(const salsa20_blk_t *restrict Bin,
661 salsa20_blk_t *restrict Bout, size_t r, pwxform_ctx_t *restrict ctx)
662 {
663 /* ctx MUST NOT be NULL */
664 assert(ctx != NULL);
665
666 uint8_t *S0 = ctx->S0, *S1 = ctx->S1, *S2 = ctx->S2;
667 size_t w = ctx->w;
668 size_t i;
669 DECL_X
670
671 /* Convert count of 128-byte blocks to max index of 64-byte block */
672 r = r * 2 - 1;
673
674 READ_X(Bin[r])
675
676 DECL_SMASK2REG
677
678 i = 0;
679 do {
680 XOR_X(Bin[i])
681 PWXFORM
682 if (unlikely(i >= r))
683 break;
684 WRITE_X(Bout[i])
685 i++;
686 } while (1);
687
688 ctx->S0 = S0; ctx->S1 = S1; ctx->S2 = S2;
689 ctx->w = w;
690
691 SALSA20_2(Bout[i])
692 }
693
694 static uint32_t blockmix_xor(const salsa20_blk_t *Bin1,
695 const salsa20_blk_t *restrict Bin2, salsa20_blk_t *Bout,
696 size_t r, int Bin2_in_ROM, pwxform_ctx_t *restrict ctx)
697 {
698 /* ctx MUST NOT be NULL */
699 assert(ctx != NULL);
700
701 uint8_t *S0 = ctx->S0, *S1 = ctx->S1, *S2 = ctx->S2;
702 size_t w = ctx->w;
703 size_t i;
704 DECL_X
705
706 /* Convert count of 128-byte blocks to max index of 64-byte block */
707 r = r * 2 - 1;
708
709 #ifdef PREFETCH
710 if (Bin2_in_ROM) {
711 PREFETCH(&Bin2[r], _MM_HINT_NTA)
712 for (i = 0; i < r; i++) {
713 PREFETCH(&Bin2[i], _MM_HINT_NTA)
714 }
715 } else {
716 PREFETCH(&Bin2[r], _MM_HINT_T0)
717 for (i = 0; i < r; i++) {
718 PREFETCH(&Bin2[i], _MM_HINT_T0)
719 }
720 }
721 #else
722 (void)Bin2_in_ROM; /* unused */
723 #endif
724
725 XOR_X_2(Bin1[r], Bin2[r])
726
727 DECL_SMASK2REG
728
729 i = 0;
730 r--;
731 do {
732 XOR_X(Bin1[i])
733 XOR_X(Bin2[i])
734 PWXFORM
735 WRITE_X(Bout[i])
736
737 XOR_X(Bin1[i + 1])
738 XOR_X(Bin2[i + 1])
739 PWXFORM
740
741 if (unlikely(i >= r))
742 break;
743
744 WRITE_X(Bout[i + 1])
745
746 i += 2;
747 } while (1);
748 i++;
749
750 ctx->S0 = S0; ctx->S1 = S1; ctx->S2 = S2;
751 ctx->w = w;
752
753 SALSA20_2(Bout[i])
754
755 return INTEGERIFY;
756 }
757
758 static uint32_t blockmix_xor_save(salsa20_blk_t *restrict Bin1out,
759 salsa20_blk_t *restrict Bin2,
760 size_t r, pwxform_ctx_t *restrict ctx)
761 {
762 /* ctx MUST NOT be NULL */
763 assert(ctx != NULL);
764
765 uint8_t *S0 = ctx->S0, *S1 = ctx->S1, *S2 = ctx->S2;
766 size_t w = ctx->w;
767 size_t i;
768 DECL_X
769 DECL_Y
770
771 /* Convert count of 128-byte blocks to max index of 64-byte block */
772 r = r * 2 - 1;
773
774 #ifdef PREFETCH
775 PREFETCH(&Bin2[r], _MM_HINT_T0)
776 for (i = 0; i < r; i++) {
777 PREFETCH(&Bin2[i], _MM_HINT_T0)
778 }
779 #endif
780
781 XOR_X_2(Bin1out[r], Bin2[r])
782
783 DECL_SMASK2REG
784
785 i = 0;
786 r--;
787 do {
788 XOR_X_WRITE_XOR_Y_2(Bin2[i], Bin1out[i])
789 PWXFORM
790 WRITE_X(Bin1out[i])
791
792 XOR_X_WRITE_XOR_Y_2(Bin2[i + 1], Bin1out[i + 1])
793 PWXFORM
794
795 if (unlikely(i >= r))
796 break;
797
798 WRITE_X(Bin1out[i + 1])
799
800 i += 2;
801 } while (1);
802 i++;
803
804 ctx->S0 = S0; ctx->S1 = S1; ctx->S2 = S2;
805 ctx->w = w;
806
807 SALSA20_2(Bin1out[i])
808
809 return INTEGERIFY;
810 }
811
812 /**
813 * integerify(B, r):
814 * Return the result of parsing B_{2r-1} as a little-endian integer.
815 */
816 static inline uint32_t integerify(const salsa20_blk_t *B, size_t r)
817 {
818 /*
819 * Our 64-bit words are in host byte order, which is why we don't just read
820 * w[0] here (would be wrong on big-endian). Also, our 32-bit words are
821 * SIMD-shuffled (so the next 32 bits would be part of d[6]), but currently
822 * this does not matter as we only care about the least significant 32 bits.
823 */
824 return (uint32_t)B[2 * r - 1].d[0];
825 }
826
827 /**
828 * smix1(B, r, N, flags, V, NROM, VROM, XY, ctx):
829 * Compute first loop of B = SMix_r(B, N). The input B must be 128r bytes in
830 * length; the temporary storage V must be 128rN bytes in length; the temporary
831 * storage XY must be 128r+64 bytes in length. N must be even and at least 4.
832 * The array V must be aligned to a multiple of 64 bytes, and arrays B and XY
833 * to a multiple of at least 16 bytes.
834 */
835 static void smix1(uint8_t *B, size_t r, uint32_t N, yescrypt_flags_t flags,
836 salsa20_blk_t *V, uint32_t NROM, const salsa20_blk_t *VROM,
837 salsa20_blk_t *XY, pwxform_ctx_t *ctx)
838 {
839 size_t s = 2 * r;
840 salsa20_blk_t *X = V, *Y = &V[s];
841 uint32_t i, j;
842
843 for (i = 0; i < 2 * r; i++) {
844 const salsa20_blk_t *src = (salsa20_blk_t *)&B[i * 64];
845 salsa20_blk_t *tmp = Y;
846 salsa20_blk_t *dst = &X[i];
847 size_t k;
848 for (k = 0; k < 16; k++)
849 tmp->w[k] = le32dec((const uint8_t *) &src->w[k]);
850 salsa20_simd_shuffle(tmp, dst);
851 }
852
853 if (VROM) {
854 uint32_t n;
855 const salsa20_blk_t *V_j;
856
857 V_j = &VROM[(NROM - 1) * s];
858 j = blockmix_xor(X, V_j, Y, r, 1, ctx) & (NROM - 1);
859 V_j = &VROM[j * s];
860 X = Y + s;
861 j = blockmix_xor(Y, V_j, X, r, 1, ctx);
862
863 for (n = 2; n < N; n <<= 1) {
864 uint32_t m = (n < N / 2) ? n : (N - 1 - n);
865 for (i = 1; i < m; i += 2) {
866 j &= n - 1;
867 j += i - 1;
868 V_j = &V[j * s];
869 Y = X + s;
870 j = blockmix_xor(X, V_j, Y, r, 0, ctx) & (NROM - 1);
871 V_j = &VROM[j * s];
872 X = Y + s;
873 j = blockmix_xor(Y, V_j, X, r, 1, ctx);
874 }
875 }
876 n >>= 1;
877
878 j &= n - 1;
879 j += N - 2 - n;
880 V_j = &V[j * s];
881 Y = X + s;
882 j = blockmix_xor(X, V_j, Y, r, 0, ctx) & (NROM - 1);
883 V_j = &VROM[j * s];
884 blockmix_xor(Y, V_j, XY, r, 1, ctx);
885 } else if (flags & YESCRYPT_RW) {
886 uint32_t n;
887 salsa20_blk_t *V_j;
888
889 blockmix(X, Y, r, ctx);
890 X = Y + s;
891 blockmix(Y, X, r, ctx);
892 j = integerify(X, r);
893
894 for (n = 2; n < N; n <<= 1) {
895 uint32_t m = (n < N / 2) ? n : (N - 1 - n);
896 for (i = 1; i < m; i += 2) {
897 Y = X + s;
898 j &= n - 1;
899 j += i - 1;
900 V_j = &V[j * s];
901 j = blockmix_xor(X, V_j, Y, r, 0, ctx);
902 j &= n - 1;
903 j += i;
904 V_j = &V[j * s];
905 X = Y + s;
906 j = blockmix_xor(Y, V_j, X, r, 0, ctx);
907 }
908 }
909 n >>= 1;
910
911 j &= n - 1;
912 j += N - 2 - n;
913 V_j = &V[j * s];
914 Y = X + s;
915 j = blockmix_xor(X, V_j, Y, r, 0, ctx);
916 j &= n - 1;
917 j += N - 1 - n;
918 V_j = &V[j * s];
919 blockmix_xor(Y, V_j, XY, r, 0, ctx);
920 } else {
921 N -= 2;
922 do {
923 blockmix_salsa8(X, Y, r);
924 X = Y + s;
925 blockmix_salsa8(Y, X, r);
926 Y = X + s;
927 } while ((N -= 2));
928
929 blockmix_salsa8(X, Y, r);
930 blockmix_salsa8(Y, XY, r);
931 }
932
933 for (i = 0; i < 2 * r; i++) {
934 const salsa20_blk_t *src = &XY[i];
935 salsa20_blk_t *tmp = &XY[s];
936 salsa20_blk_t *dst = (salsa20_blk_t *)&B[i * 64];
937 size_t k;
938 for (k = 0; k < 16; k++)
939 le32enc((uint8_t *)&tmp->w[k], src->w[k]);
940 salsa20_simd_unshuffle(tmp, dst);
941 }
942 }
943
944 /**
945 * smix2(B, r, N, Nloop, flags, V, NROM, VROM, XY, ctx):
946 * Compute second loop of B = SMix_r(B, N). The input B must be 128r bytes in
947 * length; the temporary storage V must be 128rN bytes in length; the temporary
948 * storage XY must be 256r bytes in length. N must be a power of 2 and at
949 * least 2. Nloop must be even. The array V must be aligned to a multiple of
950 * 64 bytes, and arrays B and XY to a multiple of at least 16 bytes.
951 */
952 static void smix2(uint8_t *B, size_t r, uint32_t N, uint64_t Nloop,
953 yescrypt_flags_t flags, salsa20_blk_t *V, uint32_t NROM,
954 const salsa20_blk_t *VROM, salsa20_blk_t *XY, pwxform_ctx_t *ctx)
955 {
956 size_t s = 2 * r;
957 salsa20_blk_t *X = XY, *Y = &XY[s];
958 uint32_t i, j;
959
960 if (Nloop == 0)
961 return;
962
963 for (i = 0; i < 2 * r; i++) {
964 const salsa20_blk_t *src = (salsa20_blk_t *)&B[i * 64];
965 salsa20_blk_t *tmp = Y;
966 salsa20_blk_t *dst = &X[i];
967 size_t k;
968 for (k = 0; k < 16; k++)
969 tmp->w[k] = le32dec((const uint8_t *)&src->w[k]);
970 salsa20_simd_shuffle(tmp, dst);
971 }
972
973 j = integerify(X, r) & (N - 1);
974
975 /*
976 * Normally, VROM implies YESCRYPT_RW, but we check for these separately
977 * because our SMix resets YESCRYPT_RW for the smix2() calls operating on the
978 * entire V when p > 1.
979 */
980 if (VROM && (flags & YESCRYPT_RW)) {
981 do {
982 salsa20_blk_t *V_j = &V[j * s];
983 const salsa20_blk_t *VROM_j;
984 j = blockmix_xor_save(X, V_j, r, ctx) & (NROM - 1);
985 VROM_j = &VROM[j * s];
986 j = blockmix_xor(X, VROM_j, X, r, 1, ctx) & (N - 1);
987 } while (Nloop -= 2);
988 } else if (VROM) {
989 do {
990 const salsa20_blk_t *V_j = &V[j * s];
991 j = blockmix_xor(X, V_j, X, r, 0, ctx) & (NROM - 1);
992 V_j = &VROM[j * s];
993 j = blockmix_xor(X, V_j, X, r, 1, ctx) & (N - 1);
994 } while (Nloop -= 2);
995 } else if (flags & YESCRYPT_RW) {
996 do {
997 salsa20_blk_t *V_j = &V[j * s];
998 j = blockmix_xor_save(X, V_j, r, ctx) & (N - 1);
999 V_j = &V[j * s];
1000 j = blockmix_xor_save(X, V_j, r, ctx) & (N - 1);
1001 } while (Nloop -= 2);
1002 } else if (ctx) {
1003 do {
1004 const salsa20_blk_t *V_j = &V[j * s];
1005 j = blockmix_xor(X, V_j, X, r, 0, ctx) & (N - 1);
1006 V_j = &V[j * s];
1007 j = blockmix_xor(X, V_j, X, r, 0, ctx) & (N - 1);
1008 } while (Nloop -= 2);
1009 } else {
1010 do {
1011 const salsa20_blk_t *V_j = &V[j * s];
1012 j = blockmix_salsa8_xor(X, V_j, Y, r) & (N - 1);
1013 V_j = &V[j * s];
1014 j = blockmix_salsa8_xor(Y, V_j, X, r) & (N - 1);
1015 } while (Nloop -= 2);
1016 }
1017
1018 for (i = 0; i < 2 * r; i++) {
1019 const salsa20_blk_t *src = &X[i];
1020 salsa20_blk_t *tmp = Y;
1021 salsa20_blk_t *dst = (salsa20_blk_t *)&B[i * 64];
1022 size_t k;
1023 for (k = 0; k < 16; k++)
1024 le32enc((uint8_t *)&tmp->w[k], src->w[k]);
1025 salsa20_simd_unshuffle(tmp, dst);
1026 }
1027 }
1028
1029 /**
1030 * p2floor(x):
1031 * Largest power of 2 not greater than argument.
1032 */
1033 static uint64_t p2floor(uint64_t x)
1034 {
1035 uint64_t y;
1036 while ((y = x & (x - 1)))
1037 x = y;
1038 return x;
1039 }
1040
1041 /**
1042 * smix(B, r, N, p, t, flags, V, NROM, VROM, XY, S, passwd):
1043 * Compute B = SMix_r(B, N). The input B must be 128rp bytes in length; the
1044 * temporary storage V must be 128rN bytes in length; the temporary storage
1045 * XY must be 256r or 256rp bytes in length (the larger size is required with
1046 * OpenMP-enabled builds). N must be a power of 2 and at least 4. The array V
1047 * must be aligned to a multiple of 64 bytes, and arrays B and XY to a multiple
1048 * of at least 16 bytes (aligning them to 64 bytes as well saves cache lines
1049 * and helps avoid false sharing in OpenMP-enabled builds when p > 1, but it
1050 * might also result in cache bank conflicts).
1051 */
1052 static void smix(uint8_t *B, size_t r, uint32_t N, uint32_t p, uint32_t t,
1053 yescrypt_flags_t flags,
1054 salsa20_blk_t *V, uint32_t NROM, const salsa20_blk_t *VROM,
1055 salsa20_blk_t *XY, uint8_t *S, uint8_t *passwd)
1056 {
1057 size_t s = 2 * r;
1058 uint32_t Nchunk;
1059 uint64_t Nloop_all, Nloop_rw;
1060 uint32_t i;
1061
1062 Nchunk = N / p;
1063 Nloop_all = Nchunk;
1064 if (flags & YESCRYPT_RW) {
1065 if (t <= 1) {
1066 if (t)
1067 Nloop_all *= 2; /* 2/3 */
1068 Nloop_all = (Nloop_all + 2) / 3; /* 1/3, round up */
1069 } else {
1070 Nloop_all *= t - 1;
1071 }
1072 } else if (t) {
1073 if (t == 1)
1074 Nloop_all += (Nloop_all + 1) / 2; /* 1.5, round up */
1075 Nloop_all *= t;
1076 }
1077
1078 Nloop_rw = 0;
1079 if (flags & YESCRYPT_INIT_SHARED)
1080 Nloop_rw = Nloop_all;
1081 else if (flags & YESCRYPT_RW)
1082 Nloop_rw = Nloop_all / p;
1083
1084 Nchunk &= ~(uint32_t)1; /* round down to even */
1085 Nloop_all++; Nloop_all &= ~(uint64_t)1; /* round up to even */
1086 Nloop_rw++; Nloop_rw &= ~(uint64_t)1; /* round up to even */
1087
1088 #ifdef _OPENMP
1089 #pragma omp parallel if (p > 1) default(none) private(i) shared(B, r, N, p, flags, V, NROM, VROM, XY, S, passwd, s, Nchunk, Nloop_all, Nloop_rw)
1090 {
1091 #pragma omp for
1092 #endif
1093 for (i = 0; i < p; i++) {
1094 uint32_t Vchunk = i * Nchunk;
1095 uint32_t Np = (i < p - 1) ? Nchunk : (N - Vchunk);
1096 uint8_t *Bp = &B[128 * r * i];
1097 salsa20_blk_t *Vp = &V[Vchunk * s];
1098 #ifdef _OPENMP
1099 salsa20_blk_t *XYp = &XY[i * (2 * s)];
1100 #else
1101 salsa20_blk_t *XYp = XY;
1102 #endif
1103 pwxform_ctx_t *ctx_i = NULL;
1104 if (flags & YESCRYPT_RW) {
1105 uint8_t *Si = S + i * Salloc;
1106 smix1(Bp, 1, Sbytes / 128, 0 /* no flags */,
1107 (salsa20_blk_t *)Si, 0, NULL, XYp, NULL);
1108 ctx_i = (pwxform_ctx_t *)(Si + Sbytes);
1109 ctx_i->S2 = Si;
1110 ctx_i->S1 = Si + Sbytes / 3;
1111 ctx_i->S0 = Si + Sbytes / 3 * 2;
1112 ctx_i->w = 0;
1113 if (i == 0)
1114 HMAC_SHA256_Buf(Bp + (128 * r - 64), 64,
1115 passwd, 32, passwd);
1116 }
1117 smix1(Bp, r, Np, flags, Vp, NROM, VROM, XYp, ctx_i);
1118 smix2(Bp, r, p2floor(Np), Nloop_rw, flags, Vp,
1119 NROM, VROM, XYp, ctx_i);
1120 }
1121
1122 if (Nloop_all > Nloop_rw) {
1123 #ifdef _OPENMP
1124 #pragma omp for
1125 #endif
1126 for (i = 0; i < p; i++) {
1127 uint8_t *Bp = &B[128 * r * i];
1128 #ifdef _OPENMP
1129 salsa20_blk_t *XYp = &XY[i * (2 * s)];
1130 #else
1131 salsa20_blk_t *XYp = XY;
1132 #endif
1133 pwxform_ctx_t *ctx_i = NULL;
1134 if (flags & YESCRYPT_RW) {
1135 uint8_t *Si = S + i * Salloc;
1136 ctx_i = (pwxform_ctx_t *)(Si + Sbytes);
1137 }
1138 smix2(Bp, r, N, Nloop_all - Nloop_rw,
1139 flags & (yescrypt_flags_t)~YESCRYPT_RW,
1140 V, NROM, VROM, XYp, ctx_i);
1141 }
1142 }
1143 #ifdef _OPENMP
1144 }
1145 #endif
1146 }
1147
1148 /**
1149 * yescrypt_kdf_body(shared, local, passwd, passwdlen, salt, saltlen,
1150 * flags, N, r, p, t, NROM, buf, buflen):
1151 * Compute scrypt(passwd[0 .. passwdlen - 1], salt[0 .. saltlen - 1], N, r,
1152 * p, buflen), or a revision of scrypt as requested by flags and shared, and
1153 * write the result into buf.
1154 *
1155 * shared and flags may request special modes as described in yescrypt.h.
1156 *
1157 * local is the thread-local data structure, allowing to preserve and reuse a
1158 * memory allocation across calls, thereby reducing its overhead.
1159 *
1160 * t controls computation time while not affecting peak memory usage.
1161 *
1162 * Return 0 on success; or -1 on error.
1163 *
1164 * This optimized implementation currently limits N to the range from 4 to
1165 * 2^31, but other implementations might not.
1166 */
1167 static int yescrypt_kdf_body(const yescrypt_shared_t *shared,
1168 yescrypt_local_t *local,
1169 const uint8_t *passwd, size_t passwdlen,
1170 const uint8_t *salt, size_t saltlen,
1171 yescrypt_flags_t flags, uint64_t N, uint32_t r, uint32_t p, uint32_t t,
1172 uint64_t NROM,
1173 uint8_t *buf, size_t buflen)
1174 {
1175 yescrypt_region_t tmp;
1176 const salsa20_blk_t *VROM;
1177 size_t B_size, V_size, XY_size, need;
1178 uint8_t *B, *S;
1179 salsa20_blk_t *V, *XY;
1180 uint8_t sha256[32];
1181 uint8_t dk[sizeof(sha256)], *dkp = buf;
1182
1183 /* Sanity-check parameters */
1184 switch (flags & YESCRYPT_MODE_MASK) {
1185 case 0: /* classic scrypt - can't have anything non-standard */
1186 if (flags || t || NROM)
1187 goto out_EINVAL;
1188 break;
1189 case YESCRYPT_WORM:
1190 if (flags != YESCRYPT_WORM || NROM)
1191 goto out_EINVAL;
1192 break;
1193 case YESCRYPT_RW:
1194 if (flags != (flags & YESCRYPT_KNOWN_FLAGS))
1195 goto out_EINVAL;
1196 #if PWXsimple == 2 && PWXgather == 4 && Sbytes == 12288
1197 if ((flags & YESCRYPT_RW_FLAVOR_MASK) ==
1198 (YESCRYPT_ROUNDS_6 | YESCRYPT_GATHER_4 |
1199 YESCRYPT_SIMPLE_2 | YESCRYPT_SBOX_12K))
1200 break;
1201 #else
1202 #error "Unsupported pwxform settings"
1203 #endif
1204 /* FALLTHRU */
1205 default:
1206 goto out_EINVAL;
1207 }
1208 #if SIZE_MAX > UINT32_MAX
1209 if (buflen > (((uint64_t)1 << 32) - 1) * 32)
1210 goto out_EINVAL;
1211 #endif
1212 if ((uint64_t)r * (uint64_t)p >= 1 << 30)
1213 goto out_EINVAL;
1214 if (N > UINT32_MAX)
1215 goto out_EINVAL;
1216 if ((N & (N - 1)) != 0 || N <= 3 || r < 1 || p < 1)
1217 goto out_EINVAL;
1218 if (r > SIZE_MAX / 256 / p ||
1219 N > SIZE_MAX / 128 / r)
1220 goto out_EINVAL;
1221 if (flags & YESCRYPT_RW) {
1222 /* p cannot be greater than SIZE_MAX/Salloc on 64-bit systems,
1223 but it can on 32-bit systems. */
1224 #pragma GCC diagnostic push
1225 #pragma GCC diagnostic ignored "-Wtype-limits"
1226 if (N / p <= 3 || p > SIZE_MAX / Salloc)
1227 goto out_EINVAL;
1228 #pragma GCC diagnostic pop
1229 }
1230 #ifdef _OPENMP
1231 else if (N > SIZE_MAX / 128 / (r * p)) {
1232 goto out_EINVAL;
1233 }
1234 #endif
1235
1236 VROM = NULL;
1237 if (shared) {
1238 uint64_t expected_size = (size_t)128 * r * NROM;
1239 // coverity[overflow_const]
1240 if ((NROM & (NROM - 1)) != 0 ||
1241 NROM <= 1 || NROM > UINT32_MAX ||
1242 shared->aligned_size < expected_size)
1243 goto out_EINVAL;
1244 if (!(flags & YESCRYPT_INIT_SHARED)) {
1245 uint64_t *tag = (uint64_t *)
1246 ((uint8_t *)shared->aligned + expected_size - 48);
1247 if (tag[0] != YESCRYPT_ROM_TAG1 || tag[1] != YESCRYPT_ROM_TAG2)
1248 goto out_EINVAL;
1249 }
1250 VROM = shared->aligned;
1251 } else {
1252 if (NROM)
1253 goto out_EINVAL;
1254 }
1255
1256 /* Allocate memory */
1257 V = NULL;
1258 V_size = (size_t)128 * r * N;
1259 #ifdef _OPENMP
1260 if (!(flags & YESCRYPT_RW))
1261 V_size *= p;
1262 #endif
1263 need = V_size;
1264 if (flags & YESCRYPT_INIT_SHARED) {
1265 if (local->aligned_size < need) {
1266 if (local->base || local->aligned ||
1267 local->base_size || local->aligned_size)
1268 goto out_EINVAL;
1269 if (!alloc_region(local, need))
1270 return -1;
1271 }
1272 if (flags & YESCRYPT_ALLOC_ONLY)
1273 return -2; /* expected "failure" */
1274 V = (salsa20_blk_t *)local->aligned;
1275 need = 0;
1276 }
1277 B_size = (size_t)128 * r * p;
1278 need += B_size;
1279 if (need < B_size)
1280 goto out_EINVAL;
1281 XY_size = (size_t)256 * r;
1282 #ifdef _OPENMP
1283 XY_size *= p;
1284 #endif
1285 need += XY_size;
1286 if (need < XY_size)
1287 goto out_EINVAL;
1288 if (flags & YESCRYPT_RW) {
1289 size_t S_size = (size_t)Salloc * p;
1290 need += S_size;
1291 if (need < S_size)
1292 goto out_EINVAL;
1293 }
1294 if (flags & YESCRYPT_INIT_SHARED) {
1295 if (!alloc_region(&tmp, need))
1296 return -1;
1297 B = (uint8_t *)tmp.aligned;
1298 XY = (salsa20_blk_t *)((uint8_t *)B + B_size);
1299 } else {
1300 init_region(&tmp);
1301 if (local->aligned_size < need) {
1302 if (free_region(local))
1303 return -1;
1304 if (!alloc_region(local, need))
1305 return -1;
1306 }
1307 if (flags & YESCRYPT_ALLOC_ONLY)
1308 return -3; /* expected "failure" */
1309 B = (uint8_t *)local->aligned;
1310 V = (salsa20_blk_t *)((uint8_t *)B + B_size);
1311 XY = (salsa20_blk_t *)((uint8_t *)V + V_size);
1312 }
1313 S = NULL;
1314 if (flags & YESCRYPT_RW)
1315 S = (uint8_t *)XY + XY_size;
1316
1317 if (flags) {
1318 HMAC_SHA256_Buf("yescrypt-prehash",
1319 (flags & YESCRYPT_PREHASH) ? 16 : 8,
1320 passwd, passwdlen, sha256);
1321 passwd = sha256;
1322 passwdlen = sizeof(sha256);
1323 }
1324
1325 PBKDF2_SHA256(passwd, passwdlen, salt, saltlen, 1, B, B_size);
1326
1327 if (flags)
1328 memcpy(sha256, B, sizeof(sha256));
1329
1330 if (p == 1 || (flags & YESCRYPT_RW)) {
1331 smix(B, r, N, p, t, flags, V, NROM, VROM, XY, S, sha256);
1332 } else {
1333 uint32_t i;
1334 #ifdef _OPENMP
1335 #pragma omp parallel for default(none) private(i) shared(B, r, N, p, t, flags, V, NROM, VROM, XY, S)
1336 #endif
1337 for (i = 0; i < p; i++) {
1338 #ifdef _OPENMP
1339 smix(&B[(size_t)128 * r * i], r, N, 1, t, flags,
1340 &V[(size_t)2 * r * i * N],
1341 NROM, VROM,
1342 &XY[(size_t)4 * r * i], NULL, NULL);
1343 #else
1344 smix(&B[(size_t)128 * r * i], r, N, 1, t, flags, V,
1345 NROM, VROM, XY, NULL, NULL);
1346 #endif
1347 }
1348 }
1349
1350 dkp = buf;
1351 if (flags && buflen < sizeof(dk)) {
1352 PBKDF2_SHA256(passwd, passwdlen, B, B_size, 1, dk, sizeof(dk));
1353 dkp = dk;
1354 }
1355
1356 PBKDF2_SHA256(passwd, passwdlen, B, B_size, 1, buf, buflen);
1357
1358 /*
1359 * Except when computing classic scrypt, allow all computation so far
1360 * to be performed on the client. The final steps below match those of
1361 * SCRAM (RFC 5802), so that an extension of SCRAM (with the steps so
1362 * far in place of SCRAM's use of PBKDF2 and with SHA-256 in place of
1363 * SCRAM's use of SHA-1) would be usable with yescrypt hashes.
1364 */
1365 if (flags && !(flags & YESCRYPT_PREHASH)) {
1366 /* Compute ClientKey */
1367 HMAC_SHA256_Buf(dkp, sizeof(dk), "Client Key", 10, sha256);
1368 /* Compute StoredKey */
1369 {
1370 size_t clen = buflen;
1371 if (clen > sizeof(dk))
1372 clen = sizeof(dk);
1373 SHA256_Buf(sha256, sizeof(sha256), dk);
1374 memcpy(buf, dk, clen);
1375 }
1376 }
1377
1378 if (flags) {
1379 explicit_bzero(sha256, sizeof(sha256));
1380 explicit_bzero(dk, sizeof(dk));
1381 }
1382
1383 if (free_region(&tmp)) {
1384 explicit_bzero(buf, buflen); /* must preserve errno */
1385 return -1;
1386 }
1387
1388 /* Success! */
1389 return 0;
1390
1391 out_EINVAL:
1392 errno = EINVAL;
1393 return -1;
1394 }
1395
1396 /**
1397 * yescrypt_kdf(shared, local, passwd, passwdlen, salt, saltlen, params,
1398 * buf, buflen):
1399 * Compute scrypt or its revision as requested by the parameters. The inputs
1400 * to this function are the same as those for yescrypt_kdf_body() above, with
1401 * the addition of g, which controls hash upgrades (0 for no upgrades so far).
1402 */
1403 int yescrypt_kdf(const yescrypt_shared_t *shared, yescrypt_local_t *local,
1404 const uint8_t *passwd, size_t passwdlen,
1405 const uint8_t *salt, size_t saltlen,
1406 const yescrypt_params_t *params,
1407 uint8_t *buf, size_t buflen)
1408 {
1409 yescrypt_flags_t flags = params->flags;
1410 uint64_t N = params->N;
1411 uint32_t r = params->r;
1412 uint32_t p = params->p;
1413 uint32_t t = params->t;
1414 uint32_t g = params->g;
1415 uint64_t NROM = params->NROM;
1416 uint8_t dk[32];
1417 int retval;
1418
1419 /* Support for hash upgrades has been temporarily removed */
1420 if (g) {
1421 errno = EINVAL;
1422 return -1;
1423 }
1424
1425 if ((flags & (YESCRYPT_RW | YESCRYPT_INIT_SHARED)) == YESCRYPT_RW &&
1426 p >= 1 && N / p >= 0x100 && N / p * r >= 0x20000) {
1427 if (yescrypt_kdf_body(shared, local,
1428 passwd, passwdlen, salt, saltlen,
1429 flags | YESCRYPT_ALLOC_ONLY, N, r, p, t, NROM,
1430 buf, buflen) != -3) {
1431 errno = EINVAL;
1432 return -1;
1433 }
1434 if ((retval = yescrypt_kdf_body(shared, local,
1435 passwd, passwdlen, salt, saltlen,
1436 flags | YESCRYPT_PREHASH, N >> 6, r, p, 0, NROM,
1437 dk, sizeof(dk))))
1438 return retval;
1439 passwd = dk;
1440 passwdlen = sizeof(dk);
1441 }
1442
1443 retval = yescrypt_kdf_body(shared, local,
1444 passwd, passwdlen, salt, saltlen,
1445 flags, N, r, p, t, NROM, buf, buflen);
1446 #ifndef SKIP_MEMZERO
1447 if (passwd == dk)
1448 explicit_bzero(dk, sizeof(dk));
1449 #endif
1450 return retval;
1451 }
1452
1453 int yescrypt_init_shared(yescrypt_shared_t *shared,
1454 const uint8_t *seed, size_t seedlen,
1455 const yescrypt_params_t *params)
1456 {
1457 yescrypt_params_t subparams;
1458 yescrypt_shared_t half1, half2;
1459 uint8_t salt[32];
1460 uint64_t *tag;
1461
1462 subparams = *params;
1463 subparams.flags |= YESCRYPT_INIT_SHARED;
1464 subparams.N = params->NROM;
1465 subparams.NROM = 0;
1466
1467 if (!(params->flags & YESCRYPT_RW) || params->N || params->g)
1468 return -1;
1469
1470 if (params->flags & YESCRYPT_SHARED_PREALLOCATED) {
1471 if (!shared->aligned || !shared->aligned_size)
1472 return -1;
1473
1474 /* Overwrite a possible old ROM tag before we overwrite the rest */
1475 tag = (uint64_t *)
1476 ((uint8_t *)shared->aligned + shared->aligned_size - 48);
1477 memset(tag, 0, 48);
1478 } else {
1479 init_region(shared);
1480
1481 subparams.flags |= YESCRYPT_ALLOC_ONLY;
1482 if (yescrypt_kdf(NULL, shared, NULL, 0, NULL, 0, &subparams,
1483 NULL, 0) != -2 || !shared->aligned)
1484 return -1;
1485 subparams.flags -= YESCRYPT_ALLOC_ONLY;
1486 }
1487
1488 subparams.N /= 2;
1489
1490 half1 = *shared;
1491 half1.aligned_size /= 2;
1492 half2 = half1;
1493 half2.aligned = (uint8_t *)half2.aligned + half1.aligned_size;
1494
1495 if (yescrypt_kdf(NULL, &half1,
1496 seed, seedlen, (const uint8_t *)"yescrypt-ROMhash", 16, &subparams,
1497 salt, sizeof(salt)))
1498 goto fail;
1499
1500 subparams.NROM = subparams.N;
1501
1502 if (yescrypt_kdf(&half1, &half2,
1503 seed, seedlen, salt, sizeof(salt), &subparams, salt, sizeof(salt)))
1504 goto fail;
1505
1506 if (yescrypt_kdf(&half2, &half1,
1507 seed, seedlen, salt, sizeof(salt), &subparams, salt, sizeof(salt)))
1508 goto fail;
1509
1510 tag = (uint64_t *)
1511 ((uint8_t *)shared->aligned + shared->aligned_size - 48);
1512 tag[0] = YESCRYPT_ROM_TAG1;
1513 tag[1] = YESCRYPT_ROM_TAG2;
1514 tag[2] = le64dec(salt);
1515 tag[3] = le64dec(salt + 8);
1516 tag[4] = le64dec(salt + 16);
1517 tag[5] = le64dec(salt + 24);
1518
1519 explicit_bzero(salt, sizeof(salt));
1520 return 0;
1521
1522 fail:
1523 explicit_bzero(salt, sizeof(salt));
1524 if (!(params->flags & YESCRYPT_SHARED_PREALLOCATED))
1525 free_region(shared);
1526 return -1;
1527 }
1528
1529 yescrypt_binary_t *yescrypt_digest_shared(yescrypt_shared_t *shared)
1530 {
1531 static yescrypt_binary_t digest;
1532 uint64_t *tag;
1533
1534 if (shared->aligned_size < 48)
1535 return NULL;
1536
1537 tag = (uint64_t *)
1538 ((uint8_t *)shared->aligned + shared->aligned_size - 48);
1539
1540 if (tag[0] != YESCRYPT_ROM_TAG1 || tag[1] != YESCRYPT_ROM_TAG2)
1541 return NULL;
1542
1543 le64enc(digest.uc, tag[2]);
1544 le64enc(digest.uc + 8, tag[3]);
1545 le64enc(digest.uc + 16, tag[4]);
1546 le64enc(digest.uc + 24, tag[5]);
1547
1548 return &digest;
1549 }
1550
1551 int yescrypt_free_shared(yescrypt_shared_t *shared)
1552 {
1553 return free_region(shared);
1554 }
1555
1556 int yescrypt_init_local(yescrypt_local_t *local)
1557 {
1558 init_region(local);
1559 return 0;
1560 }
1561
1562 int yescrypt_free_local(yescrypt_local_t *local)
1563 {
1564 return free_region(local);
1565 }
1566
1567 #endif /* INCLUDE_yescrypt || INCLUDE_scrypt || INCLUDE_gost_yescrypt ||
1568 INCLUDE_sm3_yescrypt */