lib/sha256.c

   1 /*-
   2  * Copyright 2005,2007,2009 Colin Percival
   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
  27 #include <zebra.h>
  28 #include "sha256.h"
  29
  30 #if !HAVE_DECL_BE32DEC
  31 static inline uint32_t
  32 be32dec(const void *pp)
  33 {
  34         const uint8_t *p = (uint8_t const *)pp;
  35
  36         return ((uint32_t)(p[3]) + ((uint32_t)(p[2]) << 8) +
  37             ((uint32_t)(p[1]) << 16) + ((uint32_t)(p[0]) << 24));
  38 }
  39 #else
  40 #include <sys/endian.h>
  41 #endif
  42
  43 #if !HAVE_DECL_BE32ENC
  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 #else
  55 #include <sys/endian.h>
  56 #endif
  57
  58 /*
  59  * Encode a length len/4 vector of (uint32_t) into a length len vector of
  60  * (unsigned char) in big-endian form.  Assumes len is a multiple of 4.
  61  */
  62 static void
  63 be32enc_vect(unsigned char *dst, const uint32_t *src, size_t len)
  64 {
  65         size_t i;
  66
  67         for (i = 0; i < len / 4; i++)
  68                 be32enc(dst + i * 4, src[i]);
  69 }
  70
  71 /*
  72  * Decode a big-endian length len vector of (unsigned char) into a length
  73  * len/4 vector of (uint32_t).  Assumes len is a multiple of 4.
  74  */
  75 static void
  76 be32dec_vect(uint32_t *dst, const unsigned char *src, size_t len)
  77 {
  78         size_t i;
  79
  80         for (i = 0; i < len / 4; i++)
  81                 dst[i] = be32dec(src + i * 4);
  82 }
  83
  84 /* Elementary functions used by SHA256 */
  85 #define Ch(x, y, z)     ((x & (y ^ z)) ^ z)
  86 #define Maj(x, y, z)    ((x & (y | z)) | (y & z))
  87 #define SHR(x, n)       (x >> n)
  88 #define ROTR(x, n)      ((x >> n) | (x << (32 - n)))
  89 #define S0(x)           (ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22))
  90 #define S1(x)           (ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25))
  91 #define s0(x)           (ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3))
  92 #define s1(x)           (ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10))
  93
  94 /* SHA256 round function */
  95 #define RND(a, b, c, d, e, f, g, h, k)                  \
  96         t0 = h + S1(e) + Ch(e, f, g) + k;               \
  97         t1 = S0(a) + Maj(a, b, c);                      \
  98         d += t0;                                        \
  99         h  = t0 + t1;
 100
 101 /* Adjusted round function for rotating state */
 102 #define RNDr(S, W, i, k)                        \
 103         RND(S[(64 - i) % 8], S[(65 - i) % 8],   \
 104             S[(66 - i) % 8], S[(67 - i) % 8],   \
 105             S[(68 - i) % 8], S[(69 - i) % 8],   \
 106             S[(70 - i) % 8], S[(71 - i) % 8],   \
 107             W[i] + k)
 108
 109 /*
 110  * SHA256 block compression function.  The 256-bit state is transformed via
 111  * the 512-bit input block to produce a new state.
 112  */
 113 static void
 114 SHA256_Transform(uint32_t * state, const unsigned char block[64])
 115 {
 116         uint32_t W[64];
 117         uint32_t S[8];
 118         uint32_t t0, t1;
 119         int i;
 120
 121         /* 1. Prepare message schedule W. */
 122         be32dec_vect(W, block, 64);
 123         for (i = 16; i < 64; i++)
 124                 W[i] = s1(W[i - 2]) + W[i - 7] + s0(W[i - 15]) + W[i - 16];
 125
 126         /* 2. Initialize working variables. */
 127         memcpy(S, state, 32);
 128
 129         /* 3. Mix. */
 130         RNDr(S, W, 0, 0x428a2f98);
 131         RNDr(S, W, 1, 0x71374491);
 132         RNDr(S, W, 2, 0xb5c0fbcf);
 133         RNDr(S, W, 3, 0xe9b5dba5);
 134         RNDr(S, W, 4, 0x3956c25b);
 135         RNDr(S, W, 5, 0x59f111f1);
 136         RNDr(S, W, 6, 0x923f82a4);
 137         RNDr(S, W, 7, 0xab1c5ed5);
 138         RNDr(S, W, 8, 0xd807aa98);
 139         RNDr(S, W, 9, 0x12835b01);
 140         RNDr(S, W, 10, 0x243185be);
 141         RNDr(S, W, 11, 0x550c7dc3);
 142         RNDr(S, W, 12, 0x72be5d74);
 143         RNDr(S, W, 13, 0x80deb1fe);
 144         RNDr(S, W, 14, 0x9bdc06a7);
 145         RNDr(S, W, 15, 0xc19bf174);
 146         RNDr(S, W, 16, 0xe49b69c1);
 147         RNDr(S, W, 17, 0xefbe4786);
 148         RNDr(S, W, 18, 0x0fc19dc6);
 149         RNDr(S, W, 19, 0x240ca1cc);
 150         RNDr(S, W, 20, 0x2de92c6f);
 151         RNDr(S, W, 21, 0x4a7484aa);
 152         RNDr(S, W, 22, 0x5cb0a9dc);
 153         RNDr(S, W, 23, 0x76f988da);
 154         RNDr(S, W, 24, 0x983e5152);
 155         RNDr(S, W, 25, 0xa831c66d);
 156         RNDr(S, W, 26, 0xb00327c8);
 157         RNDr(S, W, 27, 0xbf597fc7);
 158         RNDr(S, W, 28, 0xc6e00bf3);
 159         RNDr(S, W, 29, 0xd5a79147);
 160         RNDr(S, W, 30, 0x06ca6351);
 161         RNDr(S, W, 31, 0x14292967);
 162         RNDr(S, W, 32, 0x27b70a85);
 163         RNDr(S, W, 33, 0x2e1b2138);
 164         RNDr(S, W, 34, 0x4d2c6dfc);
 165         RNDr(S, W, 35, 0x53380d13);
 166         RNDr(S, W, 36, 0x650a7354);
 167         RNDr(S, W, 37, 0x766a0abb);
 168         RNDr(S, W, 38, 0x81c2c92e);
 169         RNDr(S, W, 39, 0x92722c85);
 170         RNDr(S, W, 40, 0xa2bfe8a1);
 171         RNDr(S, W, 41, 0xa81a664b);
 172         RNDr(S, W, 42, 0xc24b8b70);
 173         RNDr(S, W, 43, 0xc76c51a3);
 174         RNDr(S, W, 44, 0xd192e819);
 175         RNDr(S, W, 45, 0xd6990624);
 176         RNDr(S, W, 46, 0xf40e3585);
 177         RNDr(S, W, 47, 0x106aa070);
 178         RNDr(S, W, 48, 0x19a4c116);
 179         RNDr(S, W, 49, 0x1e376c08);
 180         RNDr(S, W, 50, 0x2748774c);
 181         RNDr(S, W, 51, 0x34b0bcb5);
 182         RNDr(S, W, 52, 0x391c0cb3);
 183         RNDr(S, W, 53, 0x4ed8aa4a);
 184         RNDr(S, W, 54, 0x5b9cca4f);
 185         RNDr(S, W, 55, 0x682e6ff3);
 186         RNDr(S, W, 56, 0x748f82ee);
 187         RNDr(S, W, 57, 0x78a5636f);
 188         RNDr(S, W, 58, 0x84c87814);
 189         RNDr(S, W, 59, 0x8cc70208);
 190         RNDr(S, W, 60, 0x90befffa);
 191         RNDr(S, W, 61, 0xa4506ceb);
 192         RNDr(S, W, 62, 0xbef9a3f7);
 193         RNDr(S, W, 63, 0xc67178f2);
 194
 195         /* 4. Mix local working variables into global state */
 196         for (i = 0; i < 8; i++)
 197                 state[i] += S[i];
 198
 199         /* Clean the stack. */
 200         memset(W, 0, 256);
 201         memset(S, 0, 32);
 202         t0 = t1 = 0;
 203 }
 204
 205 static unsigned char PAD[64] = {
 206         0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 207         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 208         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 209         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 210 };
 211
 212 /* Add padding and terminating bit-count. */
 213 static void
 214 SHA256_Pad(SHA256_CTX * ctx)
 215 {
 216         unsigned char len[8];
 217         uint32_t r, plen;
 218
 219         /*
 220          * Convert length to a vector of bytes -- we do this now rather
 221          * than later because the length will change after we pad.
 222          */
 223         be32enc_vect(len, ctx->count, 8);
 224
 225         /* Add 1--64 bytes so that the resulting length is 56 mod 64 */
 226         r = (ctx->count[1] >> 3) & 0x3f;
 227         plen = (r < 56) ? (56 - r) : (120 - r);
 228         SHA256_Update(ctx, PAD, (size_t)plen);
 229
 230         /* Add the terminating bit-count */
 231         SHA256_Update(ctx, len, 8);
 232 }
 233
 234 /* SHA-256 initialization.  Begins a SHA-256 operation. */
 235 void
 236 SHA256_Init(SHA256_CTX * ctx)
 237 {
 238
 239         /* Zero bits processed so far */
 240         ctx->count[0] = ctx->count[1] = 0;
 241
 242         /* Magic initialization constants */
 243         ctx->state[0] = 0x6A09E667;
 244         ctx->state[1] = 0xBB67AE85;
 245         ctx->state[2] = 0x3C6EF372;
 246         ctx->state[3] = 0xA54FF53A;
 247         ctx->state[4] = 0x510E527F;
 248         ctx->state[5] = 0x9B05688C;
 249         ctx->state[6] = 0x1F83D9AB;
 250         ctx->state[7] = 0x5BE0CD19;
 251 }
 252
 253 /* Add bytes into the hash */
 254 void
 255 SHA256_Update(SHA256_CTX * ctx, const void *in, size_t len)
 256 {
 257         uint32_t bitlen[2];
 258         uint32_t r;
 259         const unsigned char *src = in;
 260
 261         /* Number of bytes left in the buffer from previous updates */
 262         r = (ctx->count[1] >> 3) & 0x3f;
 263
 264         /* Convert the length into a number of bits */
 265         bitlen[1] = ((uint32_t)len) << 3;
 266         bitlen[0] = (uint32_t)(len >> 29);
 267
 268         /* Update number of bits */
 269         if ((ctx->count[1] += bitlen[1]) < bitlen[1])
 270                 ctx->count[0]++;
 271         ctx->count[0] += bitlen[0];
 272
 273         /* Handle the case where we don't need to perform any transforms */
 274         if (len < 64 - r) {
 275                 memcpy(&ctx->buf[r], src, len);
 276                 return;
 277         }
 278
 279         /* Finish the current block */
 280         memcpy(&ctx->buf[r], src, 64 - r);
 281         SHA256_Transform(ctx->state, ctx->buf);
 282         src += 64 - r;
 283         len -= 64 - r;
 284
 285         /* Perform complete blocks */
 286         while (len >= 64) {
 287                 SHA256_Transform(ctx->state, src);
 288                 src += 64;
 289                 len -= 64;
 290         }
 291
 292         /* Copy left over data into buffer */
 293         memcpy(ctx->buf, src, len);
 294 }
 295
 296 /*
 297  * SHA-256 finalization.  Pads the input data, exports the hash value,
 298  * and clears the context state.
 299  */
 300 void
 301 SHA256_Final(unsigned char digest[32], SHA256_CTX * ctx)
 302 {
 303
 304         /* Add padding */
 305         SHA256_Pad(ctx);
 306
 307         /* Write the hash */
 308         be32enc_vect(digest, ctx->state, 32);
 309
 310         /* Clear the context state */
 311         memset((void *)ctx, 0, sizeof(*ctx));
 312 }
 313
 314 /* Initialize an HMAC-SHA256 operation with the given key. */
 315 void
 316 HMAC__SHA256_Init(HMAC_SHA256_CTX * ctx, const void * _K, size_t Klen)
 317 {
 318         unsigned char pad[64];
 319         unsigned char khash[32];
 320         const unsigned char * K = _K;
 321         size_t i;
 322
 323         /* If Klen > 64, the key is really SHA256(K). */
 324         if (Klen > 64) {
 325                 SHA256_Init(&ctx->ictx);
 326                 SHA256_Update(&ctx->ictx, K, Klen);
 327                 SHA256_Final(khash, &ctx->ictx);
 328                 K = khash;
 329                 Klen = 32;
 330         }
 331
 332         /* Inner SHA256 operation is SHA256(K xor [block of 0x36] || data). */
 333         SHA256_Init(&ctx->ictx);
 334         memset(pad, 0x36, 64);
 335         for (i = 0; i < Klen; i++)
 336                 pad[i] ^= K[i];
 337         SHA256_Update(&ctx->ictx, pad, 64);
 338
 339         /* Outer SHA256 operation is SHA256(K xor [block of 0x5c] || hash). */
 340         SHA256_Init(&ctx->octx);
 341         memset(pad, 0x5c, 64);
 342         for (i = 0; i < Klen; i++)
 343                 pad[i] ^= K[i];
 344         SHA256_Update(&ctx->octx, pad, 64);
 345
 346         /* Clean the stack. */
 347         memset(khash, 0, 32);
 348 }
 349
 350 /* Add bytes to the HMAC-SHA256 operation. */
 351 void
 352 HMAC__SHA256_Update(HMAC_SHA256_CTX * ctx, const void *in, size_t len)
 353 {
 354
 355         /* Feed data to the inner SHA256 operation. */
 356         SHA256_Update(&ctx->ictx, in, len);
 357 }
 358
 359 /* Finish an HMAC-SHA256 operation. */
 360 void
 361 HMAC__SHA256_Final(unsigned char digest[32], HMAC_SHA256_CTX * ctx)
 362 {
 363         unsigned char ihash[32];
 364
 365         /* Finish the inner SHA256 operation. */
 366         SHA256_Final(ihash, &ctx->ictx);
 367
 368         /* Feed the inner hash to the outer SHA256 operation. */
 369         SHA256_Update(&ctx->octx, ihash, 32);
 370
 371         /* Finish the outer SHA256 operation. */
 372         SHA256_Final(digest, &ctx->octx);
 373
 374         /* Clean the stack. */
 375         memset(ihash, 0, 32);
 376 }
 377
 378 /**
 379  * PBKDF2_SHA256(passwd, passwdlen, salt, saltlen, c, buf, dkLen):
 380  * Compute PBKDF2(passwd, salt, c, dkLen) using HMAC-SHA256 as the PRF, and
 381  * write the output to buf.  The value dkLen must be at most 32 * (2^32 - 1).
 382  */
 383 void
 384 PBKDF2_SHA256(const uint8_t * passwd, size_t passwdlen, const uint8_t * salt,
 385     size_t saltlen, uint64_t c, uint8_t * buf, size_t dkLen)
 386 {
 387         HMAC_SHA256_CTX PShctx, hctx;
 388         size_t i;
 389         uint8_t ivec[4];
 390         uint8_t U[32];
 391         uint8_t T[32];
 392         uint64_t j;
 393         int k;
 394         size_t clen;
 395
 396         /* Compute HMAC state after processing P and S. */
 397         HMAC__SHA256_Init(&PShctx, passwd, passwdlen);
 398         HMAC__SHA256_Update(&PShctx, salt, saltlen);
 399
 400         /* Iterate through the blocks. */
 401         for (i = 0; i * 32 < dkLen; i++) {
 402                 /* Generate INT(i + 1). */
 403                 be32enc(ivec, (uint32_t)(i + 1));
 404
 405                 /* Compute U_1 = PRF(P, S || INT(i)). */
 406                 memcpy(&hctx, &PShctx, sizeof(HMAC_SHA256_CTX));
 407                 HMAC__SHA256_Update(&hctx, ivec, 4);
 408                 HMAC__SHA256_Final(U, &hctx);
 409
 410                 /* T_i = U_1 ... */
 411                 memcpy(T, U, 32);
 412
 413                 for (j = 2; j <= c; j++) {
 414                         /* Compute U_j. */
 415                         HMAC__SHA256_Init(&hctx, passwd, passwdlen);
 416                         HMAC__SHA256_Update(&hctx, U, 32);
 417                         HMAC__SHA256_Final(U, &hctx);
 418
 419                         /* ... xor U_j ... */
 420                         for (k = 0; k < 32; k++)
 421                                 T[k] ^= U[k];
 422                 }
 423
 424                 /* Copy as many bytes as necessary into buf. */
 425                 clen = dkLen - i * 32;
 426                 if (clen > 32)
 427                         clen = 32;
 428                 memcpy(&buf[i * 32], T, clen);
 429         }
 430
 431         /* Clean PShctx, since we never called _Final on it. */
 432         memset(&PShctx, 0, sizeof(HMAC_SHA256_CTX));
 433 }