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