scrypt-1.2.1/libcperciva/alg/sha256.c

   1 #include <assert.h>
   2 #include <stdint.h>
   3 #include <string.h>
   4
   5 #include "insecure_memzero.h"
   6 #include "sysendian.h"
   7
   8 #include "sha256.h"
   9
  10 /*
  11  * Encode a length len/4 vector of (uint32_t) into a length len vector of
  12  * (uint8_t) in big-endian form.  Assumes len is a multiple of 4.
  13  */
  14 static void
  15 be32enc_vect(uint8_t * dst, const uint32_t * src, size_t len)
  16 {
  17         size_t i;
  18
  19         /* Sanity-check. */
  20         assert(len % 4 == 0);
  21
  22         /* Encode vector, one word at a time. */
  23         for (i = 0; i < len / 4; i++)
  24                 be32enc(dst + i * 4, src[i]);
  25 }
  26
  27 /*
  28  * Decode a big-endian length len vector of (uint8_t) into a length
  29  * len/4 vector of (uint32_t).  Assumes len is a multiple of 4.
  30  */
  31 static void
  32 be32dec_vect(uint32_t * dst, const uint8_t * src, size_t len)
  33 {
  34         size_t i;
  35
  36         /* Sanity-check. */
  37         assert(len % 4 == 0);
  38
  39         /* Decode vector, one word at a time. */
  40         for (i = 0; i < len / 4; i++)
  41                 dst[i] = be32dec(src + i * 4);
  42 }
  43
  44 /* SHA256 round constants. */
  45 static const uint32_t Krnd[64] = {
  46         0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
  47         0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
  48         0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
  49         0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
  50         0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
  51         0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
  52         0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
  53         0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
  54         0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
  55         0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
  56         0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
  57         0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
  58         0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
  59         0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
  60         0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
  61         0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
  62 };
  63
  64 /* Elementary functions used by SHA256 */
  65 #define Ch(x, y, z)     ((x & (y ^ z)) ^ z)
  66 #define Maj(x, y, z)    ((x & (y | z)) | (y & z))
  67 #define SHR(x, n)       (x >> n)
  68 #define ROTR(x, n)      ((x >> n) | (x << (32 - n)))
  69 #define S0(x)           (ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22))
  70 #define S1(x)           (ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25))
  71 #define s0(x)           (ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3))
  72 #define s1(x)           (ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10))
  73
  74 /* SHA256 round function */
  75 #define RND(a, b, c, d, e, f, g, h, k)                  \
  76         h += S1(e) + Ch(e, f, g) + k;                   \
  77         d += h;                                         \
  78         h += S0(a) + Maj(a, b, c);
  79
  80 /* Adjusted round function for rotating state */
  81 #define RNDr(S, W, i, ii)                       \
  82         RND(S[(64 - i) % 8], S[(65 - i) % 8],   \
  83             S[(66 - i) % 8], S[(67 - i) % 8],   \
  84             S[(68 - i) % 8], S[(69 - i) % 8],   \
  85             S[(70 - i) % 8], S[(71 - i) % 8],   \
  86             W[i + ii] + Krnd[i + ii])
  87
  88 /* Message schedule computation */
  89 #define MSCH(W, ii, i)                          \
  90         W[i + ii + 16] = s1(W[i + ii + 14]) + W[i + ii + 9] + s0(W[i + ii + 1]) + W[i + ii]
  91
  92 /*
  93  * SHA256 block compression function.  The 256-bit state is transformed via
  94  * the 512-bit input block to produce a new state.
  95  */
  96 static void
  97 SHA256_Transform(uint32_t state[static restrict 8],
  98     const uint8_t block[static restrict 64],
  99     uint32_t W[static restrict 64], uint32_t S[static restrict 8])
 100 {
 101         int i;
 102
 103         /* 1. Prepare the first part of the message schedule W. */
 104         be32dec_vect(W, block, 64);
 105
 106         /* 2. Initialize working variables. */
 107         memcpy(S, state, 32);
 108
 109         /* 3. Mix. */
 110         for (i = 0; i < 64; i += 16) {
 111                 RNDr(S, W, 0, i);
 112                 RNDr(S, W, 1, i);
 113                 RNDr(S, W, 2, i);
 114                 RNDr(S, W, 3, i);
 115                 RNDr(S, W, 4, i);
 116                 RNDr(S, W, 5, i);
 117                 RNDr(S, W, 6, i);
 118                 RNDr(S, W, 7, i);
 119                 RNDr(S, W, 8, i);
 120                 RNDr(S, W, 9, i);
 121                 RNDr(S, W, 10, i);
 122                 RNDr(S, W, 11, i);
 123                 RNDr(S, W, 12, i);
 124                 RNDr(S, W, 13, i);
 125                 RNDr(S, W, 14, i);
 126                 RNDr(S, W, 15, i);
 127
 128                 if (i == 48)
 129                         break;
 130                 MSCH(W, 0, i);
 131                 MSCH(W, 1, i);
 132                 MSCH(W, 2, i);
 133                 MSCH(W, 3, i);
 134                 MSCH(W, 4, i);
 135                 MSCH(W, 5, i);
 136                 MSCH(W, 6, i);
 137                 MSCH(W, 7, i);
 138                 MSCH(W, 8, i);
 139                 MSCH(W, 9, i);
 140                 MSCH(W, 10, i);
 141                 MSCH(W, 11, i);
 142                 MSCH(W, 12, i);
 143                 MSCH(W, 13, i);
 144                 MSCH(W, 14, i);
 145                 MSCH(W, 15, i);
 146         }
 147
 148         /* 4. Mix local working variables into global state. */
 149         for (i = 0; i < 8; i++)
 150                 state[i] += S[i];
 151 }
 152
 153 static const uint8_t PAD[64] = {
 154         0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 155         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 156         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 157         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 158 };
 159
 160 /* Add padding and terminating bit-count. */
 161 static void
 162 SHA256_Pad(SHA256_CTX * ctx, uint32_t tmp32[static restrict 72])
 163 {
 164         size_t r;
 165
 166         /* Figure out how many bytes we have buffered. */
 167         r = (ctx->count >> 3) & 0x3f;
 168
 169         /* Pad to 56 mod 64, transforming if we finish a block en route. */
 170         if (r < 56) {
 171                 /* Pad to 56 mod 64. */
 172                 memcpy(&ctx->buf[r], PAD, 56 - r);
 173         } else {
 174                 /* Finish the current block and mix. */
 175                 memcpy(&ctx->buf[r], PAD, 64 - r);
 176                 SHA256_Transform(ctx->state, ctx->buf, &tmp32[0], &tmp32[64]);
 177
 178                 /* The start of the final block is all zeroes. */
 179                 memset(&ctx->buf[0], 0, 56);
 180         }
 181
 182         /* Add the terminating bit-count. */
 183         be64enc(&ctx->buf[56], ctx->count);
 184
 185         /* Mix in the final block. */
 186         SHA256_Transform(ctx->state, ctx->buf, &tmp32[0], &tmp32[64]);
 187 }
 188
 189 /* Magic initialization constants. */
 190 static const uint32_t initial_state[8] = {
 191         0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A,
 192         0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19
 193 };
 194
 195 /**
 196  * SHA256_Init(ctx):
 197  * Initialize the SHA256 context ${ctx}.
 198  */
 199 void
 200 SHA256_Init(SHA256_CTX * ctx)
 201 {
 202
 203         /* Zero bits processed so far. */
 204         ctx->count = 0;
 205
 206         /* Initialize state. */
 207         memcpy(ctx->state, initial_state, sizeof(initial_state));
 208 }
 209
 210 /**
 211  * SHA256_Update(ctx, in, len):
 212  * Input ${len} bytes from ${in} into the SHA256 context ${ctx}.
 213  */
 214 static void
 215 _SHA256_Update(SHA256_CTX * ctx, const void * in, size_t len,
 216     uint32_t tmp32[static restrict 72])
 217 {
 218         uint32_t r;
 219         const uint8_t * src = in;
 220
 221         /* Return immediately if we have nothing to do. */
 222         if (len == 0)
 223                 return;
 224
 225         /* Number of bytes left in the buffer from previous updates. */
 226         r = (ctx->count >> 3) & 0x3f;
 227
 228         /* Update number of bits. */
 229         ctx->count += (uint64_t)(len) << 3;
 230
 231         /* Handle the case where we don't need to perform any transforms. */
 232         if (len < 64 - r) {
 233                 memcpy(&ctx->buf[r], src, len);
 234                 return;
 235         }
 236
 237         /* Finish the current block. */
 238         memcpy(&ctx->buf[r], src, 64 - r);
 239         SHA256_Transform(ctx->state, ctx->buf, &tmp32[0], &tmp32[64]);
 240         src += 64 - r;
 241         len -= 64 - r;
 242
 243         /* Perform complete blocks. */
 244         while (len >= 64) {
 245                 SHA256_Transform(ctx->state, src, &tmp32[0], &tmp32[64]);
 246                 src += 64;
 247                 len -= 64;
 248         }
 249
 250         /* Copy left over data into buffer. */
 251         memcpy(ctx->buf, src, len);
 252 }
 253
 254 /* Wrapper function for intermediate-values sanitization. */
 255 void
 256 SHA256_Update(SHA256_CTX * ctx, const void * in, size_t len)
 257 {
 258         uint32_t tmp32[72];
 259
 260         /* Call the real function. */
 261         _SHA256_Update(ctx, in, len, tmp32);
 262
 263         /* Clean the stack. */
 264         insecure_memzero(tmp32, 288);
 265 }
 266
 267 /**
 268  * SHA256_Final(digest, ctx):
 269  * Output the SHA256 hash of the data input to the context ${ctx} into the
 270  * buffer ${digest}.
 271  */
 272 static void
 273 _SHA256_Final(uint8_t digest[32], SHA256_CTX * ctx,
 274     uint32_t tmp32[static restrict 72])
 275 {
 276
 277         /* Add padding. */
 278         SHA256_Pad(ctx, tmp32);
 279
 280         /* Write the hash. */
 281         be32enc_vect(digest, ctx->state, 32);
 282 }
 283
 284 /* Wrapper function for intermediate-values sanitization. */
 285 void
 286 SHA256_Final(uint8_t digest[32], SHA256_CTX * ctx)
 287 {
 288         uint32_t tmp32[72];
 289
 290         /* Call the real function. */
 291         _SHA256_Final(digest, ctx, tmp32);
 292
 293         /* Clear the context state. */
 294         insecure_memzero(ctx, sizeof(SHA256_CTX));
 295
 296         /* Clean the stack. */
 297         insecure_memzero(tmp32, 288);
 298 }
 299
 300 /**
 301  * SHA256_Buf(in, len, digest):
 302  * Compute the SHA256 hash of ${len} bytes from ${in} and write it to ${digest}.
 303  */
 304 void
 305 SHA256_Buf(const void * in, size_t len, uint8_t digest[32])
 306 {
 307         SHA256_CTX ctx;
 308         uint32_t tmp32[72];
 309
 310         SHA256_Init(&ctx);
 311         _SHA256_Update(&ctx, in, len, tmp32);
 312         _SHA256_Final(digest, &ctx, tmp32);
 313
 314         /* Clean the stack. */
 315         insecure_memzero(&ctx, sizeof(SHA256_CTX));
 316         insecure_memzero(tmp32, 288);
 317 }
 318
 319 /**
 320  * HMAC_SHA256_Init(ctx, K, Klen):
 321  * Initialize the HMAC-SHA256 context ${ctx} with ${Klen} bytes of key from
 322  * ${K}.
 323  */
 324 static void
 325 _HMAC_SHA256_Init(HMAC_SHA256_CTX * ctx, const void * _K, size_t Klen,
 326     uint32_t tmp32[static restrict 72], uint8_t pad[static restrict 64],
 327     uint8_t khash[static restrict 32])
 328 {
 329         const uint8_t * K = _K;
 330         size_t i;
 331
 332         /* If Klen > 64, the key is really SHA256(K). */
 333         if (Klen > 64) {
 334                 SHA256_Init(&ctx->ictx);
 335                 _SHA256_Update(&ctx->ictx, K, Klen, tmp32);
 336                 _SHA256_Final(khash, &ctx->ictx, tmp32);
 337                 K = khash;
 338                 Klen = 32;
 339         }
 340
 341         /* Inner SHA256 operation is SHA256(K xor [block of 0x36] || data). */
 342         SHA256_Init(&ctx->ictx);
 343         memset(pad, 0x36, 64);
 344         for (i = 0; i < Klen; i++)
 345                 pad[i] ^= K[i];
 346         _SHA256_Update(&ctx->ictx, pad, 64, tmp32);
 347
 348         /* Outer SHA256 operation is SHA256(K xor [block of 0x5c] || hash). */
 349         SHA256_Init(&ctx->octx);
 350         memset(pad, 0x5c, 64);
 351         for (i = 0; i < Klen; i++)
 352                 pad[i] ^= K[i];
 353         _SHA256_Update(&ctx->octx, pad, 64, tmp32);
 354 }
 355
 356 /* Wrapper function for intermediate-values sanitization. */
 357 void
 358 HMAC_SHA256_Init(HMAC_SHA256_CTX * ctx, const void * _K, size_t Klen)
 359 {
 360         uint32_t tmp32[72];
 361         uint8_t pad[64];
 362         uint8_t khash[32];
 363
 364         /* Call the real function. */
 365         _HMAC_SHA256_Init(ctx, _K, Klen, tmp32, pad, khash);
 366
 367         /* Clean the stack. */
 368         insecure_memzero(tmp32, 288);
 369         insecure_memzero(khash, 32);
 370         insecure_memzero(pad, 64);
 371 }
 372
 373 /**
 374  * HMAC_SHA256_Update(ctx, in, len):
 375  * Input ${len} bytes from ${in} into the HMAC-SHA256 context ${ctx}.
 376  */
 377 static void
 378 _HMAC_SHA256_Update(HMAC_SHA256_CTX * ctx, const void * in, size_t len,
 379     uint32_t tmp32[static restrict 72])
 380 {
 381
 382         /* Feed data to the inner SHA256 operation. */
 383         _SHA256_Update(&ctx->ictx, in, len, tmp32);
 384 }
 385
 386 /* Wrapper function for intermediate-values sanitization. */
 387 void
 388 HMAC_SHA256_Update(HMAC_SHA256_CTX * ctx, const void * in, size_t len)
 389 {
 390         uint32_t tmp32[72];
 391
 392         /* Call the real function. */
 393         _HMAC_SHA256_Update(ctx, in, len, tmp32);
 394
 395         /* Clean the stack. */
 396         insecure_memzero(tmp32, 288);
 397 }
 398
 399 /**
 400  * HMAC_SHA256_Final(digest, ctx):
 401  * Output the HMAC-SHA256 of the data input to the context ${ctx} into the
 402  * buffer ${digest}.
 403  */
 404 static void
 405 _HMAC_SHA256_Final(uint8_t digest[32], HMAC_SHA256_CTX * ctx,
 406     uint32_t tmp32[static restrict 72], uint8_t ihash[static restrict 32])
 407 {
 408
 409         /* Finish the inner SHA256 operation. */
 410         _SHA256_Final(ihash, &ctx->ictx, tmp32);
 411
 412         /* Feed the inner hash to the outer SHA256 operation. */
 413         _SHA256_Update(&ctx->octx, ihash, 32, tmp32);
 414
 415         /* Finish the outer SHA256 operation. */
 416         _SHA256_Final(digest, &ctx->octx, tmp32);
 417 }
 418
 419 /* Wrapper function for intermediate-values sanitization. */
 420 void
 421 HMAC_SHA256_Final(uint8_t digest[32], HMAC_SHA256_CTX * ctx)
 422 {
 423         uint32_t tmp32[72];
 424         uint8_t ihash[32];
 425
 426         /* Call the real function. */
 427         _HMAC_SHA256_Final(digest, ctx, tmp32, ihash);
 428
 429         /* Clean the stack. */
 430         insecure_memzero(tmp32, 288);
 431         insecure_memzero(ihash, 32);
 432 }
 433
 434 /**
 435  * HMAC_SHA256_Buf(K, Klen, in, len, digest):
 436  * Compute the HMAC-SHA256 of ${len} bytes from ${in} using the key ${K} of
 437  * length ${Klen}, and write the result to ${digest}.
 438  */
 439 void
 440 HMAC_SHA256_Buf(const void * K, size_t Klen, const void * in, size_t len,
 441     uint8_t digest[32])
 442 {
 443         HMAC_SHA256_CTX ctx;
 444         uint32_t tmp32[72];
 445         uint8_t tmp8[96];
 446
 447         _HMAC_SHA256_Init(&ctx, K, Klen, tmp32, &tmp8[0], &tmp8[64]);
 448         _HMAC_SHA256_Update(&ctx, in, len, tmp32);
 449         _HMAC_SHA256_Final(digest, &ctx, tmp32, &tmp8[0]);
 450
 451         /* Clean the stack. */
 452         insecure_memzero(&ctx, sizeof(HMAC_SHA256_CTX));
 453         insecure_memzero(tmp32, 288);
 454         insecure_memzero(tmp8, 96);
 455 }
 456
 457 /**
 458  * PBKDF2_SHA256(passwd, passwdlen, salt, saltlen, c, buf, dkLen):
 459  * Compute PBKDF2(passwd, salt, c, dkLen) using HMAC-SHA256 as the PRF, and
 460  * write the output to buf.  The value dkLen must be at most 32 * (2^32 - 1).
 461  */
 462 void
 463 PBKDF2_SHA256(const uint8_t * passwd, size_t passwdlen, const uint8_t * salt,
 464     size_t saltlen, uint64_t c, uint8_t * buf, size_t dkLen)
 465 {
 466         HMAC_SHA256_CTX Phctx, PShctx, hctx;
 467         uint32_t tmp32[72];
 468         uint8_t tmp8[96];
 469         size_t i;
 470         uint8_t ivec[4];
 471         uint8_t U[32];
 472         uint8_t T[32];
 473         uint64_t j;
 474         int k;
 475         size_t clen;
 476
 477         /* Sanity-check. */
 478         assert(dkLen <= 32 * (size_t)(UINT32_MAX));
 479
 480         /* Compute HMAC state after processing P. */
 481         _HMAC_SHA256_Init(&Phctx, passwd, passwdlen,
 482             tmp32, &tmp8[0], &tmp8[64]);
 483
 484         /* Compute HMAC state after processing P and S. */
 485         memcpy(&PShctx, &Phctx, sizeof(HMAC_SHA256_CTX));
 486         _HMAC_SHA256_Update(&PShctx, salt, saltlen, tmp32);
 487
 488         /* Iterate through the blocks. */
 489         for (i = 0; i * 32 < dkLen; i++) {
 490                 /* Generate INT(i + 1). */
 491                 be32enc(ivec, (uint32_t)(i + 1));
 492
 493                 /* Compute U_1 = PRF(P, S || INT(i)). */
 494                 memcpy(&hctx, &PShctx, sizeof(HMAC_SHA256_CTX));
 495                 _HMAC_SHA256_Update(&hctx, ivec, 4, tmp32);
 496                 _HMAC_SHA256_Final(U, &hctx, tmp32, tmp8);
 497
 498                 /* T_i = U_1 ... */
 499                 memcpy(T, U, 32);
 500
 501                 for (j = 2; j <= c; j++) {
 502                         /* Compute U_j. */
 503                         memcpy(&hctx, &Phctx, sizeof(HMAC_SHA256_CTX));
 504                         _HMAC_SHA256_Update(&hctx, U, 32, tmp32);
 505                         _HMAC_SHA256_Final(U, &hctx, tmp32, tmp8);
 506
 507                         /* ... xor U_j ... */
 508                         for (k = 0; k < 32; k++)
 509                                 T[k] ^= U[k];
 510                 }
 511
 512                 /* Copy as many bytes as necessary into buf. */
 513                 clen = dkLen - i * 32;
 514                 if (clen > 32)
 515                         clen = 32;
 516                 memcpy(&buf[i * 32], T, clen);
 517         }
 518
 519         /* Clean the stack. */
 520         insecure_memzero(&Phctx, sizeof(HMAC_SHA256_CTX));
 521         insecure_memzero(&PShctx, sizeof(HMAC_SHA256_CTX));
 522         insecure_memzero(&hctx, sizeof(HMAC_SHA256_CTX));
 523         insecure_memzero(tmp32, 288);
 524         insecure_memzero(tmp8, 96);
 525         insecure_memzero(U, 32);
 526         insecure_memzero(T, 32);
 527 }