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