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