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