gerrit.fd Code Review - trex.git/blob

   1 /*-
   2  * Copyright 2009 Colin Percival
   3  * Copyright 2012,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 #if defined(HAVE_EMMINTRIN_H) || defined(_MSC_VER)
  32 #if __GNUC__
  33 # pragma GCC target("sse2")
  34 #endif
  35 #include <emmintrin.h>
  36 #if defined(__XOP__) && defined(DISABLED)
  37 # include <x86intrin.h>
  38 #endif
  39
  40 #include <errno.h>
  41 #include <limits.h>
  42 #include <stdint.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45
  46 #include "../pbkdf2-sha256.h"
  47 #include "../sysendian.h"
  48 #include "../crypto_scrypt.h"
  49
  50 #if defined(__XOP__) && defined(DISABLED)
  51 #define ARX(out, in1, in2, s) \
  52         out = _mm_xor_si128(out, _mm_roti_epi32(_mm_add_epi32(in1, in2), s));
  53 #else
  54 #define ARX(out, in1, in2, s) \
  55         { \
  56                 __m128i T = _mm_add_epi32(in1, in2); \
  57                 out = _mm_xor_si128(out, _mm_slli_epi32(T, s)); \
  58                 out = _mm_xor_si128(out, _mm_srli_epi32(T, 32-s)); \
  59         }
  60 #endif
  61
  62 #define SALSA20_2ROUNDS \
  63         /* Operate on "columns". */ \
  64         ARX(X1, X0, X3, 7) \
  65         ARX(X2, X1, X0, 9) \
  66         ARX(X3, X2, X1, 13) \
  67         ARX(X0, X3, X2, 18) \
  68 \
  69         /* Rearrange data. */ \
  70         X1 = _mm_shuffle_epi32(X1, 0x93); \
  71         X2 = _mm_shuffle_epi32(X2, 0x4E); \
  72         X3 = _mm_shuffle_epi32(X3, 0x39); \
  73 \
  74         /* Operate on "rows". */ \
  75         ARX(X3, X0, X1, 7) \
  76         ARX(X2, X3, X0, 9) \
  77         ARX(X1, X2, X3, 13) \
  78         ARX(X0, X1, X2, 18) \
  79 \
  80         /* Rearrange data. */ \
  81         X1 = _mm_shuffle_epi32(X1, 0x39); \
  82         X2 = _mm_shuffle_epi32(X2, 0x4E); \
  83         X3 = _mm_shuffle_epi32(X3, 0x93);
  84
  85 /**
  86  * Apply the salsa20/8 core to the block provided in (X0 ... X3) ^ (Z0 ... Z3).
  87  */
  88 #define SALSA20_8_XOR(in, out) \
  89         { \
  90                 __m128i Y0 = X0 = _mm_xor_si128(X0, (in)[0]); \
  91                 __m128i Y1 = X1 = _mm_xor_si128(X1, (in)[1]); \
  92                 __m128i Y2 = X2 = _mm_xor_si128(X2, (in)[2]); \
  93                 __m128i Y3 = X3 = _mm_xor_si128(X3, (in)[3]); \
  94                 SALSA20_2ROUNDS \
  95                 SALSA20_2ROUNDS \
  96                 SALSA20_2ROUNDS \
  97                 SALSA20_2ROUNDS \
  98                 (out)[0] = X0 = _mm_add_epi32(X0, Y0); \
  99                 (out)[1] = X1 = _mm_add_epi32(X1, Y1); \
 100                 (out)[2] = X2 = _mm_add_epi32(X2, Y2); \
 101                 (out)[3] = X3 = _mm_add_epi32(X3, Y3); \
 102         }
 103
 104 /**
 105  * blockmix_salsa8(Bin, Bout, r):
 106  * Compute Bout = BlockMix_{salsa20/8, r}(Bin).  The input Bin must be 128r
 107  * bytes in length; the output Bout must also be the same size.
 108  */
 109 static inline void
 110 blockmix_salsa8(const __m128i * Bin, __m128i * Bout, size_t r)
 111 {
 112         __m128i X0, X1, X2, X3;
 113         size_t i;
 114
 115         /* 1: X <-- B_{2r - 1} */
 116         X0 = Bin[8 * r - 4];
 117         X1 = Bin[8 * r - 3];
 118         X2 = Bin[8 * r - 2];
 119         X3 = Bin[8 * r - 1];
 120
 121         /* 3: X <-- H(X \xor B_i) */
 122         /* 4: Y_i <-- X */
 123         /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 124         SALSA20_8_XOR(Bin, Bout)
 125
 126         /* 2: for i = 0 to 2r - 1 do */
 127         r--;
 128         for (i = 0; i < r;) {
 129                 /* 3: X <-- H(X \xor B_i) */
 130                 /* 4: Y_i <-- X */
 131                 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 132                 SALSA20_8_XOR(&Bin[i * 8 + 4], &Bout[(r + i) * 4 + 4])
 133
 134                 i++;
 135
 136                 /* 3: X <-- H(X \xor B_i) */
 137                 /* 4: Y_i <-- X */
 138                 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 139                 SALSA20_8_XOR(&Bin[i * 8], &Bout[i * 4])
 140         }
 141
 142         /* 3: X <-- H(X \xor B_i) */
 143         /* 4: Y_i <-- X */
 144         /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 145         SALSA20_8_XOR(&Bin[i * 8 + 4], &Bout[(r + i) * 4 + 4])
 146 }
 147
 148 #define XOR4(in) \
 149         X0 = _mm_xor_si128(X0, (in)[0]); \
 150         X1 = _mm_xor_si128(X1, (in)[1]); \
 151         X2 = _mm_xor_si128(X2, (in)[2]); \
 152         X3 = _mm_xor_si128(X3, (in)[3]);
 153
 154 #define XOR4_2(in1, in2) \
 155         X0 = _mm_xor_si128((in1)[0], (in2)[0]); \
 156         X1 = _mm_xor_si128((in1)[1], (in2)[1]); \
 157         X2 = _mm_xor_si128((in1)[2], (in2)[2]); \
 158         X3 = _mm_xor_si128((in1)[3], (in2)[3]);
 159
 160 static inline uint32_t
 161 blockmix_salsa8_xor(const __m128i * Bin1, const __m128i * Bin2, __m128i * Bout,
 162     size_t r)
 163 {
 164         __m128i X0, X1, X2, X3;
 165         size_t i;
 166
 167         /* 1: X <-- B_{2r - 1} */
 168         XOR4_2(&Bin1[8 * r - 4], &Bin2[8 * r - 4])
 169
 170         /* 3: X <-- H(X \xor B_i) */
 171         /* 4: Y_i <-- X */
 172         /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 173         XOR4(Bin1)
 174         SALSA20_8_XOR(Bin2, Bout)
 175
 176         /* 2: for i = 0 to 2r - 1 do */
 177         r--;
 178         for (i = 0; i < r;) {
 179                 /* 3: X <-- H(X \xor B_i) */
 180                 /* 4: Y_i <-- X */
 181                 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 182                 XOR4(&Bin1[i * 8 + 4])
 183                 SALSA20_8_XOR(&Bin2[i * 8 + 4], &Bout[(r + i) * 4 + 4])
 184
 185                 i++;
 186
 187                 /* 3: X <-- H(X \xor B_i) */
 188                 /* 4: Y_i <-- X */
 189                 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 190                 XOR4(&Bin1[i * 8])
 191                 SALSA20_8_XOR(&Bin2[i * 8], &Bout[i * 4])
 192         }
 193
 194         /* 3: X <-- H(X \xor B_i) */
 195         /* 4: Y_i <-- X */
 196         /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 197         XOR4(&Bin1[i * 8 + 4])
 198         SALSA20_8_XOR(&Bin2[i * 8 + 4], &Bout[(r + i) * 4 + 4])
 199
 200         return _mm_cvtsi128_si32(X0);
 201 }
 202
 203 #undef ARX
 204 #undef SALSA20_2ROUNDS
 205 #undef SALSA20_8_XOR
 206 #undef XOR4
 207 #undef XOR4_2
 208
 209 /**
 210  * integerify(B, r):
 211  * Return the result of parsing B_{2r-1} as a little-endian integer.
 212  */
 213 static inline uint32_t
 214 integerify(const void * B, size_t r)
 215 {
 216         return *(const uint32_t *)((uintptr_t)(B) + (2 * r - 1) * 64);
 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
 228 smix(uint8_t * B, size_t r, uint32_t N, void * V, void * XY)
 229 {
 230         size_t s = 128 * r;
 231         __m128i * X = (__m128i *) V, * Y;
 232         uint32_t * X32 = (uint32_t *) V;
 233         uint32_t i, j;
 234         size_t k;
 235
 236         /* 1: X <-- B */
 237         /* 3: V_i <-- X */
 238         for (k = 0; k < 2 * r; k++) {
 239                 for (i = 0; i < 16; i++) {
 240                         X32[k * 16 + i] =
 241                             le32dec(&B[(k * 16 + (i * 5 % 16)) * 4]);
 242                 }
 243         }
 244
 245         /* 2: for i = 0 to N - 1 do */
 246         for (i = 1; i < N - 1; i += 2) {
 247                 /* 4: X <-- H(X) */
 248                 /* 3: V_i <-- X */
 249                 Y = (__m128i *)((uintptr_t)(V) + i * s);
 250                 blockmix_salsa8(X, Y, r);
 251
 252                 /* 4: X <-- H(X) */
 253                 /* 3: V_i <-- X */
 254                 X = (__m128i *)((uintptr_t)(V) + (i + 1) * s);
 255                 blockmix_salsa8(Y, X, r);
 256         }
 257
 258         /* 4: X <-- H(X) */
 259         /* 3: V_i <-- X */
 260         Y = (__m128i *)((uintptr_t)(V) + i * s);
 261         blockmix_salsa8(X, Y, r);
 262
 263         /* 4: X <-- H(X) */
 264         /* 3: V_i <-- X */
 265         X = (__m128i *) XY;
 266         blockmix_salsa8(Y, X, r);
 267
 268         X32 = (uint32_t *) XY;
 269         Y = (__m128i *)((uintptr_t)(XY) + s);
 270
 271         /* 7: j <-- Integerify(X) mod N */
 272         j = integerify(X, r) & (N - 1);
 273
 274         /* 6: for i = 0 to N - 1 do */
 275         for (i = 0; i < N; i += 2) {
 276                 __m128i * V_j = (__m128i *)((uintptr_t)(V) + j * s);
 277
 278                 /* 8: X <-- H(X \xor V_j) */
 279                 /* 7: j <-- Integerify(X) mod N */
 280                 j = blockmix_salsa8_xor(X, V_j, Y, r) & (N - 1);
 281                 V_j = (__m128i *)((uintptr_t)(V) + j * s);
 282
 283                 /* 8: X <-- H(X \xor V_j) */
 284                 /* 7: j <-- Integerify(X) mod N */
 285                 j = blockmix_salsa8_xor(Y, V_j, X, r) & (N - 1);
 286         }
 287
 288         /* 10: B' <-- X */
 289         for (k = 0; k < 2 * r; k++) {
 290                 for (i = 0; i < 16; i++) {
 291                         le32enc(&B[(k * 16 + (i * 5 % 16)) * 4],
 292                             X32[k * 16 + i]);
 293                 }
 294         }
 295 }
 296
 297 /**
 298  * escrypt_kdf(local, passwd, passwdlen, salt, saltlen,
 299  *     N, r, p, buf, buflen):
 300  * Compute scrypt(passwd[0 .. passwdlen - 1], salt[0 .. saltlen - 1], N, r,
 301  * p, buflen) and write the result into buf.  The parameters r, p, and buflen
 302  * must satisfy r * p < 2^30 and buflen <= (2^32 - 1) * 32.  The parameter N
 303  * must be a power of 2 greater than 1.
 304  *
 305  * Return 0 on success; or -1 on error.
 306  */
 307 int
 308 escrypt_kdf_sse(escrypt_local_t * local,
 309     const uint8_t * passwd, size_t passwdlen,
 310     const uint8_t * salt, size_t saltlen,
 311     uint64_t N, uint32_t _r, uint32_t _p,
 312     uint8_t * buf, size_t buflen)
 313 {
 314         size_t B_size, V_size, XY_size, need;
 315         uint8_t * B;
 316         uint32_t * V, * XY;
 317     size_t r = _r, p = _p;
 318         uint32_t i;
 319
 320         /* Sanity-check parameters. */
 321 #if SIZE_MAX > UINT32_MAX
 322         if (buflen > (((uint64_t)(1) << 32) - 1) * 32) {
 323                 errno = EFBIG;
 324                 return -1;
 325         }
 326 #endif
 327         if ((uint64_t)(r) * (uint64_t)(p) >= (1 << 30)) {
 328                 errno = EFBIG;
 329                 return -1;
 330         }
 331         if (N > UINT32_MAX) {
 332                 errno = EFBIG;
 333                 return -1;
 334         }
 335         if (((N & (N - 1)) != 0) || (N < 2)) {
 336                 errno = EINVAL;
 337                 return -1;
 338         }
 339         if (r == 0 || p == 0) {
 340                 errno = EINVAL;
 341                 return -1;
 342         }
 343         if ((r > SIZE_MAX / 128 / p) ||
 344 #if SIZE_MAX / 256 <= UINT32_MAX
 345             (r > SIZE_MAX / 256) ||
 346 #endif
 347             (N > SIZE_MAX / 128 / r)) {
 348                 errno = ENOMEM;
 349                 return -1;
 350         }
 351
 352         /* Allocate memory. */
 353         B_size = (size_t)128 * r * p;
 354         V_size = (size_t)128 * r * N;
 355         need = B_size + V_size;
 356         if (need < V_size) {
 357                 errno = ENOMEM;
 358                 return -1;
 359         }
 360         XY_size = (size_t)256 * r + 64;
 361         need += XY_size;
 362         if (need < XY_size) {
 363                 errno = ENOMEM;
 364                 return -1;
 365         }
 366         if (local->size < need) {
 367                 if (free_region(local))
 368                         return -1; /* LCOV_EXCL_LINE */
 369                 if (!alloc_region(local, need))
 370                         return -1; /* LCOV_EXCL_LINE */
 371         }
 372         B = (uint8_t *)local->aligned;
 373         V = (uint32_t *)((uint8_t *)B + B_size);
 374         XY = (uint32_t *)((uint8_t *)V + V_size);
 375
 376         /* 1: (B_0 ... B_{p-1}) <-- PBKDF2(P, S, 1, p * MFLen) */
 377         PBKDF2_SHA256(passwd, passwdlen, salt, saltlen, 1, B, B_size);
 378
 379         /* 2: for i = 0 to p - 1 do */
 380         for (i = 0; i < p; i++) {
 381                 /* 3: B_i <-- MF(B_i, N) */
 382                 smix(&B[(size_t)128 * i * r], r, (uint32_t) N, V, XY);
 383         }
 384
 385         /* 5: DK <-- PBKDF2(P, B, 1, dkLen) */
 386         PBKDF2_SHA256(passwd, passwdlen, B, B_size, 1, buf, buflen);
 387
 388         /* Success! */
 389         return 0;
 390 }
 391 #endif