2 * Copyright 2009 Colin Percival, 2011 ArtForz
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
26 * This file was originally written by Colin Percival as part of the Tarsnap
27 * online backup system.
35 static __inline uint32_t
36 be32dec(const void *pp)
38 const uint8_t *p = (uint8_t const *)pp;
40 return ((uint32_t)(p[3]) + ((uint32_t)(p[2]) << 8) +
41 ((uint32_t)(p[1]) << 16) + ((uint32_t)(p[0]) << 24));
45 be32enc(void *pp, uint32_t x)
47 uint8_t * p = (uint8_t *)pp;
50 p[2] = (x >> 8) & 0xff;
51 p[1] = (x >> 16) & 0xff;
52 p[0] = (x >> 24) & 0xff;
55 static __inline uint32_t
56 le32dec(const void *pp)
58 const uint8_t *p = (uint8_t const *)pp;
60 return ((uint32_t)(p[0]) + ((uint32_t)(p[1]) << 8) +
61 ((uint32_t)(p[2]) << 16) + ((uint32_t)(p[3]) << 24));
65 le32enc(void *pp, uint32_t x)
67 uint8_t * p = (uint8_t *)pp;
70 p[1] = (x >> 8) & 0xff;
71 p[2] = (x >> 16) & 0xff;
72 p[3] = (x >> 24) & 0xff;
76 typedef struct SHA256Context {
79 unsigned char buf[64];
82 typedef struct HMAC_SHA256Context {
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.
92 be32enc_vect(unsigned char *dst, const uint32_t *src, size_t len)
96 for (i = 0; i < len / 4; i++)
97 be32enc(dst + i * 4, src[i]);
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.
105 be32dec_vect(uint32_t *dst, const unsigned char *src, size_t len)
109 for (i = 0; i < len / 4; i++)
110 dst[i] = be32dec(src + i * 4);
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))
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); \
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], \
139 * SHA256 block compression function. The 256-bit state is transformed via
140 * the 512-bit input block to produce a new state.
143 SHA256_Transform(uint32_t * state, const unsigned char block[64])
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];
155 /* 2. Initialize working variables. */
156 memcpy(S, state, 32);
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);
224 /* 4. Mix local working variables into global state */
225 for (i = 0; i < 8; i++)
228 /* Clean the stack. */
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
241 /* SHA-256 initialization. Begins a SHA-256 operation. */
243 SHA256_Init(SHA256_CTX * ctx)
246 /* Zero bits processed so far */
247 ctx->count[0] = ctx->count[1] = 0;
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;
260 /* Add bytes into the hash */
262 SHA256_Update(SHA256_CTX * ctx, const void *in, size_t len)
266 const unsigned char *src = in;
268 /* Number of bytes left in the buffer from previous updates */
269 r = (ctx->count[1] >> 3) & 0x3f;
271 /* Convert the length into a number of bits */
272 bitlen[1] = ((uint32_t)len) << 3;
273 bitlen[0] = (uint32_t)(len >> 29);
275 /* Update number of bits */
276 if ((ctx->count[1] += bitlen[1]) < bitlen[1])
278 ctx->count[0] += bitlen[0];
280 /* Handle the case where we don't need to perform any transforms */
282 memcpy(&ctx->buf[r], src, len);
286 /* Finish the current block */
287 memcpy(&ctx->buf[r], src, 64 - r);
288 SHA256_Transform(ctx->state, ctx->buf);
292 /* Perform complete blocks */
294 SHA256_Transform(ctx->state, src);
299 /* Copy left over data into buffer */
300 memcpy(ctx->buf, src, len);
303 /* Add padding and terminating bit-count. */
305 SHA256_Pad(SHA256_CTX * ctx)
307 unsigned char len[8];
311 * Convert length to a vector of bytes -- we do this now rather
312 * than later because the length will change after we pad.
314 be32enc_vect(len, ctx->count, 8);
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);
321 /* Add the terminating bit-count */
322 SHA256_Update(ctx, len, 8);
326 * SHA-256 finalization. Pads the input data, exports the hash value,
327 * and clears the context state.
330 SHA256_Final(unsigned char digest[32], SHA256_CTX * ctx)
337 be32enc_vect(digest, ctx->state, 32);
339 /* Clear the context state */
340 memset((void *)ctx, 0, sizeof(*ctx));
343 /* Initialize an HMAC-SHA256 operation with the given key. */
345 HMAC_SHA256_Init(HMAC_SHA256_CTX * ctx, const void * _K, size_t Klen)
347 unsigned char pad[64];
348 unsigned char khash[32];
349 const unsigned char * K = _K;
352 /* If Klen > 64, the key is really SHA256(K). */
354 SHA256_Init(&ctx->ictx);
355 SHA256_Update(&ctx->ictx, K, Klen);
356 SHA256_Final(khash, &ctx->ictx);
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++)
366 SHA256_Update(&ctx->ictx, pad, 64);
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++)
373 SHA256_Update(&ctx->octx, pad, 64);
375 /* Clean the stack. */
376 memset(khash, 0, 32);
379 /* Add bytes to the HMAC-SHA256 operation. */
381 HMAC_SHA256_Update(HMAC_SHA256_CTX * ctx, const void *in, size_t len)
384 /* Feed data to the inner SHA256 operation. */
385 SHA256_Update(&ctx->ictx, in, len);
388 /* Finish an HMAC-SHA256 operation. */
390 HMAC_SHA256_Final(unsigned char digest[32], HMAC_SHA256_CTX * ctx)
392 unsigned char ihash[32];
394 /* Finish the inner SHA256 operation. */
395 SHA256_Final(ihash, &ctx->ictx);
397 /* Feed the inner hash to the outer SHA256 operation. */
398 SHA256_Update(&ctx->octx, ihash, 32);
400 /* Finish the outer SHA256 operation. */
401 SHA256_Final(digest, &ctx->octx);
403 /* Clean the stack. */
404 memset(ihash, 0, 32);
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).
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)
416 HMAC_SHA256_CTX PShctx, hctx;
425 /* Compute HMAC state after processing P and S. */
426 HMAC_SHA256_Init(&PShctx, passwd, passwdlen);
427 HMAC_SHA256_Update(&PShctx, salt, saltlen);
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));
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);
442 for (j = 2; j <= c; j++) {
444 HMAC_SHA256_Init(&hctx, passwd, passwdlen);
445 HMAC_SHA256_Update(&hctx, U, 32);
446 HMAC_SHA256_Final(U, &hctx);
448 /* ... xor U_j ... */
449 for (k = 0; k < 32; k++)
453 /* Copy as many bytes as necessary into buf. */
454 clen = dkLen - i * 32;
457 memcpy(&buf[i * 32], T, clen);
460 /* Clean PShctx, since we never called _Final on it. */
461 memset(&PShctx, 0, sizeof(HMAC_SHA256_CTX));
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 *);
473 blkcpy(void * dest, void * src, size_t len)
477 size_t L = len / sizeof(size_t);
480 for (i = 0; i < L; i++)
485 blkxor(void * dest, void * src, size_t len)
489 size_t L = len / sizeof(size_t);
492 for (i = 0; i < L; i++)
498 * Apply the salsa20/8 core to the provided block.
501 salsa20_8(uint32_t B[16])
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);
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);
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);
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);
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);
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);
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);
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);
536 for (i = 0; i < 16; i++)
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.
547 blockmix_salsa8(uint32_t * Bin, uint32_t * Bout, uint32_t * X, size_t r)
551 /* 1: X <-- B_{2r - 1} */
552 blkcpy(X, &Bin[(2 * r - 1) * 16], 64);
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);
561 /* 6: B' <-- (Y_0, Y_2 ... Y_{2r-2}, Y_1, Y_3 ... Y_{2r-1}) */
562 blkcpy(&Bout[i * 8], X, 64);
564 /* 3: X <-- H(X \xor B_i) */
565 blkxor(X, &Bin[i * 16 + 16], 64);
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);
576 * Return the result of parsing B_{2r-1} as a little-endian integer.
579 integerify(void * B, size_t r)
581 uint32_t * X = (void *)((uintptr_t)(B) + (2 * r - 1) * 64);
583 return (((uint64_t)(X[1]) << 32) + X[0]);
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.
595 smix(uint8_t * B, size_t r, uint64_t N, uint32_t * V, uint32_t * XY)
598 uint32_t * Y = &XY[32 * r];
599 uint32_t * Z = &XY[64 * r];
605 for (k = 0; k < 32 * r; k++)
606 X[k] = le32dec(&B[4 * k]);
608 /* 2: for i = 0 to N - 1 do */
609 for (i = 0; i < N; i += 2) {
611 blkcpy(&V[i * (32 * r)], X, 128 * r);
614 blockmix_salsa8(X, Y, Z, r);
617 blkcpy(&V[(i + 1) * (32 * r)], Y, 128 * r);
620 blockmix_salsa8(Y, X, Z, r);
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);
628 /* 8: X <-- H(X \xor V_j) */
629 blkxor(X, &V[j * (32 * r)], 128 * r);
630 blockmix_salsa8(X, Y, Z, r);
632 /* 7: j <-- Integerify(X) mod N */
633 j = integerify(Y, r) & (N - 1);
635 /* 8: X <-- H(X \xor V_j) */
636 blkxor(Y, &V[j * (32 * r)], 128 * r);
637 blockmix_salsa8(Y, X, Z, r);
641 for (k = 0; k < 32 * r; k++)
642 le32enc(&B[4 * k], X[k]);
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
648 void scrypt_1024_1_1_256_sp(const char* input, char* output, char* scratchpad)
655 const uint32_t N = 1024;
656 const uint32_t r = 1;
657 const uint32_t p = 1;
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));
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);
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);
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);
676 void scrypt_1024_1_1_256(const char* input, char* output)
678 char scratchpad[131583];
679 scrypt_1024_1_1_256_sp(input, output, scratchpad);