scrypt/scrypt.c

   1 /*-
   2  * Copyright 2009 Colin Percival, 2011 ArtForz
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  * This file was originally written by Colin Percival as part of the Tarsnap
  27  * online backup system.
  28  */
  29
  30 #include "scrypt.h"
  31 #include <stdlib.h>
  32 #include <stdint.h>
  33 #include <string.h>
  34
  35 static __inline uint32_t
  36 be32dec(const void *pp)
  37 {
  38         const uint8_t *p = (uint8_t const *)pp;
  39
  40         return ((uint32_t)(p[3]) + ((uint32_t)(p[2]) << 8) +
  41             ((uint32_t)(p[1]) << 16) + ((uint32_t)(p[0]) << 24));
  42 }
  43
  44 static __inline void
  45 be32enc(void *pp, uint32_t x)
  46 {
  47         uint8_t * p = (uint8_t *)pp;
  48
  49         p[3] = x & 0xff;
  50         p[2] = (x >> 8) & 0xff;
  51         p[1] = (x >> 16) & 0xff;
  52         p[0] = (x >> 24) & 0xff;
  53 }
  54
  55 static __inline uint32_t
  56 le32dec(const void *pp)
  57 {
  58         const uint8_t *p = (uint8_t const *)pp;
  59
  60         return ((uint32_t)(p[0]) + ((uint32_t)(p[1]) << 8) +
  61             ((uint32_t)(p[2]) << 16) + ((uint32_t)(p[3]) << 24));
  62 }
  63
  64 static __inline void
  65 le32enc(void *pp, uint32_t x)
  66 {
  67         uint8_t * p = (uint8_t *)pp;
  68
  69         p[0] = x & 0xff;
  70         p[1] = (x >> 8) & 0xff;
  71         p[2] = (x >> 16) & 0xff;
  72         p[3] = (x >> 24) & 0xff;
  73 }
  74
  75
  76 typedef struct SHA256Context {
  77         uint32_t state[8];
  78         uint32_t count[2];
  79         unsigned char buf[64];
  80 } SHA256_CTX;
  81
  82 typedef struct HMAC_SHA256Context {
  83         SHA256_CTX ictx;
  84         SHA256_CTX octx;
  85 } HMAC_SHA256_CTX;
  86
  87 /*
  88  * Encode a length len/4 vector of (uint32_t) into a length len vector of
  89  * (unsigned char) in big-endian form.  Assumes len is a multiple of 4.
  90  */
  91 static void
  92 be32enc_vect(unsigned char *dst, const uint32_t *src, size_t len)
  93 {
  94         size_t i;
  95
  96         for (i = 0; i < len / 4; i++)
  97                 be32enc(dst + i * 4, src[i]);
  98 }
  99
 100 /*
 101  * Decode a big-endian length len vector of (unsigned char) into a length
 102  * len/4 vector of (uint32_t).  Assumes len is a multiple of 4.
 103  */
 104 static void
 105 be32dec_vect(uint32_t *dst, const unsigned char *src, size_t len)
 106 {
 107         size_t i;
 108
 109         for (i = 0; i < len / 4; i++)
 110                 dst[i] = be32dec(src + i * 4);
 111 }
 112
 113 /* Elementary functions used by SHA256 */
 114 #define Ch(x, y, z)     ((x & (y ^ z)) ^ z)
 115 #define Maj(x, y, z)    ((x & (y | z)) | (y & z))
 116 #define SHR(x, n)       (x >> n)
 117 #define ROTR(x, n)      ((x >> n) | (x << (32 - n)))
 118 #define S0(x)           (ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22))
 119 #define S1(x)           (ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25))
 120 #define s0(x)           (ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3))
 121 #define s1(x)           (ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10))
 122
 123 /* SHA256 round function */
 124 #define RND(a, b, c, d, e, f, g, h, k)                  \
 125         t0 = h + S1(e) + Ch(e, f, g) + k;               \
 126         t1 = S0(a) + Maj(a, b, c);                      \
 127         d += t0;                                        \
 128         h  = t0 + t1;
 129
 130 /* Adjusted round function for rotating state */
 131 #define RNDr(S, W, i, k)                        \
 132         RND(S[(64 - i) % 8], S[(65 - i) % 8],   \
 133             S[(66 - i) % 8], S[(67 - i) % 8],   \
 134             S[(68 - i) % 8], S[(69 - i) % 8],   \
 135             S[(70 - i) % 8], S[(71 - i) % 8],   \
 136             W[i] + k)
 137
 138 /*
 139  * SHA256 block compression function.  The 256-bit state is transformed via
 140  * the 512-bit input block to produce a new state.
 141  */
 142 static void
 143 SHA256_Transform(uint32_t * state, const unsigned char block[64])
 144 {
 145         uint32_t W[64];
 146         uint32_t S[8];
 147         uint32_t t0, t1;
 148         int i;
 149
 150         /* 1. Prepare message schedule W. */
 151         be32dec_vect(W, block, 64);
 152         for (i = 16; i < 64; i++)
 153                 W[i] = s1(W[i - 2]) + W[i - 7] + s0(W[i - 15]) + W[i - 16];
 154
 155         /* 2. Initialize working variables. */
 156         memcpy(S, state, 32);
 157
 158         /* 3. Mix. */
 159         RNDr(S, W, 0, 0x428a2f98);
 160         RNDr(S, W, 1, 0x71374491);
 161         RNDr(S, W, 2, 0xb5c0fbcf);
 162         RNDr(S, W, 3, 0xe9b5dba5);
 163         RNDr(S, W, 4, 0x3956c25b);
 164         RNDr(S, W, 5, 0x59f111f1);
 165         RNDr(S, W, 6, 0x923f82a4);
 166         RNDr(S, W, 7, 0xab1c5ed5);
 167         RNDr(S, W, 8, 0xd807aa98);
 168         RNDr(S, W, 9, 0x12835b01);
 169         RNDr(S, W, 10, 0x243185be);
 170         RNDr(S, W, 11, 0x550c7dc3);
 171         RNDr(S, W, 12, 0x72be5d74);
 172         RNDr(S, W, 13, 0x80deb1fe);
 173         RNDr(S, W, 14, 0x9bdc06a7);
 174         RNDr(S, W, 15, 0xc19bf174);
 175         RNDr(S, W, 16, 0xe49b69c1);
 176         RNDr(S, W, 17, 0xefbe4786);
 177         RNDr(S, W, 18, 0x0fc19dc6);
 178         RNDr(S, W, 19, 0x240ca1cc);
 179         RNDr(S, W, 20, 0x2de92c6f);
 180         RNDr(S, W, 21, 0x4a7484aa);
 181         RNDr(S, W, 22, 0x5cb0a9dc);
 182         RNDr(S, W, 23, 0x76f988da);
 183         RNDr(S, W, 24, 0x983e5152);
 184         RNDr(S, W, 25, 0xa831c66d);
 185         RNDr(S, W, 26, 0xb00327c8);
 186         RNDr(S, W, 27, 0xbf597fc7);
 187         RNDr(S, W, 28, 0xc6e00bf3);
 188         RNDr(S, W, 29, 0xd5a79147);
 189         RNDr(S, W, 30, 0x06ca6351);
 190         RNDr(S, W, 31, 0x14292967);
 191         RNDr(S, W, 32, 0x27b70a85);
 192         RNDr(S, W, 33, 0x2e1b2138);
 193         RNDr(S, W, 34, 0x4d2c6dfc);
 194         RNDr(S, W, 35, 0x53380d13);
 195         RNDr(S, W, 36, 0x650a7354);
 196         RNDr(S, W, 37, 0x766a0abb);
 197         RNDr(S, W, 38, 0x81c2c92e);
 198         RNDr(S, W, 39, 0x92722c85);
 199         RNDr(S, W, 40, 0xa2bfe8a1);
 200         RNDr(S, W, 41, 0xa81a664b);
 201         RNDr(S, W, 42, 0xc24b8b70);
 202         RNDr(S, W, 43, 0xc76c51a3);
 203         RNDr(S, W, 44, 0xd192e819);
 204         RNDr(S, W, 45, 0xd6990624);
 205         RNDr(S, W, 46, 0xf40e3585);
 206         RNDr(S, W, 47, 0x106aa070);
 207         RNDr(S, W, 48, 0x19a4c116);
 208         RNDr(S, W, 49, 0x1e376c08);
 209         RNDr(S, W, 50, 0x2748774c);
 210         RNDr(S, W, 51, 0x34b0bcb5);
 211         RNDr(S, W, 52, 0x391c0cb3);
 212         RNDr(S, W, 53, 0x4ed8aa4a);
 213         RNDr(S, W, 54, 0x5b9cca4f);
 214         RNDr(S, W, 55, 0x682e6ff3);
 215         RNDr(S, W, 56, 0x748f82ee);
 216         RNDr(S, W, 57, 0x78a5636f);
 217         RNDr(S, W, 58, 0x84c87814);
 218         RNDr(S, W, 59, 0x8cc70208);
 219         RNDr(S, W, 60, 0x90befffa);
 220         RNDr(S, W, 61, 0xa4506ceb);
 221         RNDr(S, W, 62, 0xbef9a3f7);
 222         RNDr(S, W, 63, 0xc67178f2);
 223
 224         /* 4. Mix local working variables into global state */
 225         for (i = 0; i < 8; i++)
 226                 state[i] += S[i];
 227
 228         /* Clean the stack. */
 229         memset(W, 0, 256);
 230         memset(S, 0, 32);
 231         t0 = t1 = 0;
 232 }
 233
 234 static unsigned char PAD[64] = {
 235         0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 236         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 237         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 238         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 239 };
 240
 241 /* SHA-256 initialization.  Begins a SHA-256 operation. */
 242 static void
 243 SHA256_Init(SHA256_CTX * ctx)
 244 {
 245
 246         /* Zero bits processed so far */
 247         ctx->count[0] = ctx->count[1] = 0;
 248
 249         /* Magic initialization constants */
 250         ctx->state[0] = 0x6A09E667;
 251         ctx->state[1] = 0xBB67AE85;
 252         ctx->state[2] = 0x3C6EF372;
 253         ctx->state[3] = 0xA54FF53A;
 254         ctx->state[4] = 0x510E527F;
 255         ctx->state[5] = 0x9B05688C;
 256         ctx->state[6] = 0x1F83D9AB;
 257         ctx->state[7] = 0x5BE0CD19;
 258 }
 259
 260 /* Add bytes into the hash */
 261 static void
 262 SHA256_Update(SHA256_CTX * ctx, const void *in, size_t len)
 263 {
 264         uint32_t bitlen[2];
 265         uint32_t r;
 266         const unsigned char *src = in;
 267
 268         /* Number of bytes left in the buffer from previous updates */
 269         r = (ctx->count[1] >> 3) & 0x3f;
 270
 271         /* Convert the length into a number of bits */
 272         bitlen[1] = ((uint32_t)len) << 3;
 273         bitlen[0] = (uint32_t)(len >> 29);
 274
 275         /* Update number of bits */
 276         if ((ctx->count[1] += bitlen[1]) < bitlen[1])
 277                 ctx->count[0]++;
 278         ctx->count[0] += bitlen[0];
 279
 280         /* Handle the case where we don't need to perform any transforms */
 281         if (len < 64 - r) {
 282                 memcpy(&ctx->buf[r], src, len);
 283                 return;
 284         }
 285
 286         /* Finish the current block */
 287         memcpy(&ctx->buf[r], src, 64 - r);
 288         SHA256_Transform(ctx->state, ctx->buf);
 289         src += 64 - r;
 290         len -= 64 - r;
 291
 292         /* Perform complete blocks */
 293         while (len >= 64) {
 294                 SHA256_Transform(ctx->state, src);
 295                 src += 64;
 296                 len -= 64;
 297         }
 298
 299         /* Copy left over data into buffer */
 300         memcpy(ctx->buf, src, len);
 301 }
 302
 303 /* Add padding and terminating bit-count. */
 304 static void
 305 SHA256_Pad(SHA256_CTX * ctx)
 306 {
 307         unsigned char len[8];
 308         uint32_t r, plen;
 309
 310         /*
 311          * Convert length to a vector of bytes -- we do this now rather
 312          * than later because the length will change after we pad.
 313          */
 314         be32enc_vect(len, ctx->count, 8);
 315
 316         /* Add 1--64 bytes so that the resulting length is 56 mod 64 */
 317         r = (ctx->count[1] >> 3) & 0x3f;
 318         plen = (r < 56) ? (56 - r) : (120 - r);
 319         SHA256_Update(ctx, PAD, (size_t)plen);
 320
 321         /* Add the terminating bit-count */
 322         SHA256_Update(ctx, len, 8);
 323 }
 324
 325 /*
 326  * SHA-256 finalization.  Pads the input data, exports the hash value,
 327  * and clears the context state.
 328  */
 329 static void
 330 SHA256_Final(unsigned char digest[32], SHA256_CTX * ctx)
 331 {
 332
 333         /* Add padding */
 334         SHA256_Pad(ctx);
 335
 336         /* Write the hash */
 337         be32enc_vect(digest, ctx->state, 32);
 338
 339         /* Clear the context state */
 340         memset((void *)ctx, 0, sizeof(*ctx));
 341 }
 342
 343 /* Initialize an HMAC-SHA256 operation with the given key. */
 344 static void
 345 HMAC_SHA256_Init(HMAC_SHA256_CTX * ctx, const void * _K, size_t Klen)
 346 {
 347         unsigned char pad[64];
 348         unsigned char khash[32];
 349         const unsigned char * K = _K;
 350         size_t i;
 351
 352         /* If Klen > 64, the key is really SHA256(K). */
 353         if (Klen > 64) {
 354                 SHA256_Init(&ctx->ictx);
 355                 SHA256_Update(&ctx->ictx, K, Klen);
 356                 SHA256_Final(khash, &ctx->ictx);
 357                 K = khash;
 358                 Klen = 32;
 359         }
 360
 361         /* Inner SHA256 operation is SHA256(K xor [block of 0x36] || data). */
 362         SHA256_Init(&ctx->ictx);
 363         memset(pad, 0x36, 64);
 364         for (i = 0; i < Klen; i++)
 365                 pad[i] ^= K[i];
 366         SHA256_Update(&ctx->ictx, pad, 64);
 367
 368         /* Outer SHA256 operation is SHA256(K xor [block of 0x5c] || hash). */
 369         SHA256_Init(&ctx->octx);
 370         memset(pad, 0x5c, 64);
 371         for (i = 0; i < Klen; i++)
 372                 pad[i] ^= K[i];
 373         SHA256_Update(&ctx->octx, pad, 64);
 374
 375         /* Clean the stack. */
 376         memset(khash, 0, 32);
 377 }
 378
 379 /* Add bytes to the HMAC-SHA256 operation. */
 380 static void
 381 HMAC_SHA256_Update(HMAC_SHA256_CTX * ctx, const void *in, size_t len)
 382 {
 383
 384         /* Feed data to the inner SHA256 operation. */
 385         SHA256_Update(&ctx->ictx, in, len);
 386 }
 387
 388 /* Finish an HMAC-SHA256 operation. */
 389 static void
 390 HMAC_SHA256_Final(unsigned char digest[32], HMAC_SHA256_CTX * ctx)
 391 {
 392         unsigned char ihash[32];
 393
 394         /* Finish the inner SHA256 operation. */
 395         SHA256_Final(ihash, &ctx->ictx);
 396
 397         /* Feed the inner hash to the outer SHA256 operation. */
 398         SHA256_Update(&ctx->octx, ihash, 32);
 399
 400         /* Finish the outer SHA256 operation. */
 401         SHA256_Final(digest, &ctx->octx);
 402
 403         /* Clean the stack. */
 404         memset(ihash, 0, 32);
 405 }
 406
 407 /**
 408  * PBKDF2_SHA256(passwd, passwdlen, salt, saltlen, c, buf, dkLen):
 409  * Compute PBKDF2(passwd, salt, c, dkLen) using HMAC-SHA256 as the PRF, and
 410  * write the output to buf.  The value dkLen must be at most 32 * (2^32 - 1).
 411  */
 412 static void
 413 PBKDF2_SHA256(const uint8_t * passwd, size_t passwdlen, const uint8_t * salt,
 414     size_t saltlen, uint64_t c, uint8_t * buf, size_t dkLen)
 415 {
 416         HMAC_SHA256_CTX PShctx, hctx;
 417         size_t i;
 418         uint8_t ivec[4];
 419         uint8_t U[32];
 420         uint8_t T[32];
 421         uint64_t j;
 422         int k;
 423         size_t clen;
 424
 425         /* Compute HMAC state after processing P and S. */
 426         HMAC_SHA256_Init(&PShctx, passwd, passwdlen);
 427         HMAC_SHA256_Update(&PShctx, salt, saltlen);
 428
 429         /* Iterate through the blocks. */
 430         for (i = 0; i * 32 < dkLen; i++) {
 431                 /* Generate INT(i + 1). */
 432                 be32enc(ivec, (uint32_t)(i + 1));
 433
 434                 /* Compute U_1 = PRF(P, S || INT(i)). */
 435                 memcpy(&hctx, &PShctx, sizeof(HMAC_SHA256_CTX));
 436                 HMAC_SHA256_Update(&hctx, ivec, 4);
 437                 HMAC_SHA256_Final(U, &hctx);
 438
 439                 /* T_i = U_1 ... */
 440                 memcpy(T, U, 32);
 441
 442                 for (j = 2; j <= c; j++) {
 443                         /* Compute U_j. */
 444                         HMAC_SHA256_Init(&hctx, passwd, passwdlen);
 445                         HMAC_SHA256_Update(&hctx, U, 32);
 446                         HMAC_SHA256_Final(U, &hctx);
 447
 448                         /* ... xor U_j ... */
 449                         for (k = 0; k < 32; k++)
 450                                 T[k] ^= U[k];
 451                 }
 452
 453                 /* Copy as many bytes as necessary into buf. */
 454                 clen = dkLen - i * 32;
 455                 if (clen > 32)
 456                         clen = 32;
 457                 memcpy(&buf[i * 32], T, clen);
 458         }
 459
 460         /* Clean PShctx, since we never called _Final on it. */
 461         memset(&PShctx, 0, sizeof(HMAC_SHA256_CTX));
 462 }
 463
 464
 465 static void blkcpy(void *, void *, size_t);
 466 static void blkxor(void *, void *, size_t);
 467 static void salsa20_8(uint32_t[16]);
 468 static void blockmix_salsa8(uint32_t *, uint32_t *, uint32_t *, size_t);
 469 static uint64_t integerify(void *, size_t);
 470 static void smix(uint8_t *, size_t, uint64_t, uint32_t *, uint32_t *);
 471
 472 static void
 473 blkcpy(void * dest, void * src, size_t len)
 474 {
 475         size_t * D = dest;
 476         size_t * S = src;
 477         size_t L = len / sizeof(size_t);
 478         size_t i;
 479
 480         for (i = 0; i < L; i++)
 481                 D[i] = S[i];
 482 }
 483
 484 static void
 485 blkxor(void * dest, void * src, size_t len)
 486 {
 487         size_t * D = dest;
 488         size_t * S = src;
 489         size_t L = len / sizeof(size_t);
 490         size_t i;
 491
 492         for (i = 0; i < L; i++)
 493                 D[i] ^= S[i];
 494 }
 495
 496 /**
 497  * salsa20_8(B):
 498  * Apply the salsa20/8 core to the provided block.
 499  */
 500 static void
 501 salsa20_8(uint32_t B[16])
 502 {
 503         uint32_t x[16];
 504         size_t i;
 505
 506         blkcpy(x, B, 64);
 507         for (i = 0; i < 8; i += 2) {
 508 #define R(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
 509                 /* Operate on columns. */
 510                 x[ 4] ^= R(x[ 0]+x[12], 7);  x[ 8] ^= R(x[ 4]+x[ 0], 9);
 511                 x[12] ^= R(x[ 8]+x[ 4],13);  x[ 0] ^= R(x[12]+x[ 8],18);
 512
 513                 x[ 9] ^= R(x[ 5]+x[ 1], 7);  x[13] ^= R(x[ 9]+x[ 5], 9);
 514                 x[ 1] ^= R(x[13]+x[ 9],13);  x[ 5] ^= R(x[ 1]+x[13],18);
 515
 516                 x[14] ^= R(x[10]+x[ 6], 7);  x[ 2] ^= R(x[14]+x[10], 9);
 517                 x[ 6] ^= R(x[ 2]+x[14],13);  x[10] ^= R(x[ 6]+x[ 2],18);
 518
 519                 x[ 3] ^= R(x[15]+x[11], 7);  x[ 7] ^= R(x[ 3]+x[15], 9);
 520                 x[11] ^= R(x[ 7]+x[ 3],13);  x[15] ^= R(x[11]+x[ 7],18);
 521
 522                 /* Operate on rows. */
 523                 x[ 1] ^= R(x[ 0]+x[ 3], 7);  x[ 2] ^= R(x[ 1]+x[ 0], 9);
 524                 x[ 3] ^= R(x[ 2]+x[ 1],13);  x[ 0] ^= R(x[ 3]+x[ 2],18);
 525
 526                 x[ 6] ^= R(x[ 5]+x[ 4], 7);  x[ 7] ^= R(x[ 6]+x[ 5], 9);
 527                 x[ 4] ^= R(x[ 7]+x[ 6],13);  x[ 5] ^= R(x[ 4]+x[ 7],18);
 528
 529                 x[11] ^= R(x[10]+x[ 9], 7);  x[ 8] ^= R(x[11]+x[10], 9);
 530                 x[ 9] ^= R(x[ 8]+x[11],13);  x[10] ^= R(x[ 9]+x[ 8],18);
 531
 532                 x[12] ^= R(x[15]+x[14], 7);  x[13] ^= R(x[12]+x[15], 9);
 533                 x[14] ^= R(x[13]+x[12],13);  x[15] ^= R(x[14]+x[13],18);
 534 #undef R
 535         }
 536         for (i = 0; i < 16; i++)
 537                 B[i] += x[i];
 538 }
 539
 540 /**
 541  * blockmix_salsa8(Bin, Bout, X, r):
 542  * Compute Bout = BlockMix_{salsa20/8, r}(Bin).  The input Bin must be 128r
 543  * bytes in length; the output Bout must also be the same size.  The
 544  * temporary space X must be 64 bytes.
 545  */
 546 static void
 547 blockmix_salsa8(uint32_t * Bin, uint32_t * Bout, uint32_t * X, size_t r)
 548 {
 549         size_t i;
 550
 551         /* 1: X <-- B_{2r - 1} */
 552         blkcpy(X, &Bin[(2 * r - 1) * 16], 64);
 553
 554         /* 2: for i = 0 to 2r - 1 do */
 555         for (i = 0; i < 2 * r; i += 2) {
 556                 /* 3: X <-- H(X \xor B_i) */
 557                 blkxor(X, &Bin[i * 16], 64);
 558                 salsa20_8(X);
 559
 560                 /* 4: Y_i <-- X */
 561                 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 562                 blkcpy(&Bout[i * 8], X, 64);
 563
 564                 /* 3: X <-- H(X \xor B_i) */
 565                 blkxor(X, &Bin[i * 16 + 16], 64);
 566                 salsa20_8(X);
 567
 568                 /* 4: Y_i <-- X */
 569                 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
 570                 blkcpy(&Bout[i * 8 + r * 16], X, 64);
 571         }
 572 }
 573
 574 /**
 575  * integerify(B, r):
 576  * Return the result of parsing B_{2r-1} as a little-endian integer.
 577  */
 578 static uint64_t
 579 integerify(void * B, size_t r)
 580 {
 581         uint32_t * X = (void *)((uintptr_t)(B) + (2 * r - 1) * 64);
 582
 583         return (((uint64_t)(X[1]) << 32) + X[0]);
 584 }
 585
 586 /**
 587  * smix(B, r, N, V, XY):
 588  * Compute B = SMix_r(B, N).  The input B must be 128r bytes in length;
 589  * the temporary storage V must be 128rN bytes in length; the temporary
 590  * storage XY must be 256r + 64 bytes in length.  The value N must be a
 591  * power of 2 greater than 1.  The arrays B, V, and XY must be aligned to a
 592  * multiple of 64 bytes.
 593  */
 594 static void
 595 smix(uint8_t * B, size_t r, uint64_t N, uint32_t * V, uint32_t * XY)
 596 {
 597         uint32_t * X = XY;
 598         uint32_t * Y = &XY[32 * r];
 599         uint32_t * Z = &XY[64 * r];
 600         uint64_t i;
 601         uint64_t j;
 602         size_t k;
 603
 604         /* 1: X <-- B */
 605         for (k = 0; k < 32 * r; k++)
 606                 X[k] = le32dec(&B[4 * k]);
 607
 608         /* 2: for i = 0 to N - 1 do */
 609         for (i = 0; i < N; i += 2) {
 610                 /* 3: V_i <-- X */
 611                 blkcpy(&V[i * (32 * r)], X, 128 * r);
 612
 613                 /* 4: X <-- H(X) */
 614                 blockmix_salsa8(X, Y, Z, r);
 615
 616                 /* 3: V_i <-- X */
 617                 blkcpy(&V[(i + 1) * (32 * r)], Y, 128 * r);
 618
 619                 /* 4: X <-- H(X) */
 620                 blockmix_salsa8(Y, X, Z, r);
 621         }
 622
 623         /* 6: for i = 0 to N - 1 do */
 624         for (i = 0; i < N; i += 2) {
 625                 /* 7: j <-- Integerify(X) mod N */
 626                 j = integerify(X, r) & (N - 1);
 627
 628                 /* 8: X <-- H(X \xor V_j) */
 629                 blkxor(X, &V[j * (32 * r)], 128 * r);
 630                 blockmix_salsa8(X, Y, Z, r);
 631
 632                 /* 7: j <-- Integerify(X) mod N */
 633                 j = integerify(Y, r) & (N - 1);
 634
 635                 /* 8: X <-- H(X \xor V_j) */
 636                 blkxor(Y, &V[j * (32 * r)], 128 * r);
 637                 blockmix_salsa8(Y, X, Z, r);
 638         }
 639
 640         /* 10: B' <-- X */
 641         for (k = 0; k < 32 * r; k++)
 642                 le32enc(&B[4 * k], X[k]);
 643 }
 644
 645 /* cpu and memory intensive function to transform a 80 byte buffer into a 32 byte output
 646    scratchpad size needs to be at least 63 + (128 * r * p) + (256 * r + 64) + (128 * r * N) bytes
 647  */
 648 void scrypt_1024_1_1_256_sp(const char* input, char* output, char* scratchpad)
 649 {
 650         uint8_t * B;
 651         uint32_t * V;
 652         uint32_t * XY;
 653         uint32_t i;
 654
 655         const uint32_t N = 1024;
 656         const uint32_t r = 1;
 657         const uint32_t p = 1;
 658
 659         B = (uint8_t *)(((uintptr_t)(scratchpad) + 63) & ~ (uintptr_t)(63));
 660         XY = (uint32_t *)(B + (128 * r * p));
 661         V = (uint32_t *)(B + (128 * r * p) + (256 * r + 64));
 662
 663         /* 1: (B_0 ... B_{p-1}) <-- PBKDF2(P, S, 1, p * MFLen) */
 664         PBKDF2_SHA256((const uint8_t*)input, 80, (const uint8_t*)input, 80, 1, B, p * 128 * r);
 665
 666         /* 2: for i = 0 to p - 1 do */
 667         for (i = 0; i < p; i++) {
 668                 /* 3: B_i <-- MF(B_i, N) */
 669                 smix(&B[i * 128 * r], r, N, V, XY);
 670         }
 671
 672         /* 5: DK <-- PBKDF2(P, B, 1, dkLen) */
 673         PBKDF2_SHA256((const uint8_t*)input, 80, B, p * 128 * r, 1, (uint8_t*)output, 32);
 674 }
 675
 676 void scrypt_1024_1_1_256(const char* input, char* output)
 677 {
 678         char scratchpad[131583];
 679         scrypt_1024_1_1_256_sp(input, output, scratchpad);
 680 }
 681