hphp/zend/crypt-sha256.cpp

   1 /* SHA256-based Unix crypt implementation.
   2    Released into the Public Domain by Ulrich Drepper <drepper@redhat.com>.  */
   3 /* Windows VC++ port by Pierre Joye <pierre@php.net> */
   4
   5 #include "php-crypt_r.h"
   6
   7 #include <errno.h>
   8 #include <limits.h>
   9 #include <memory.h>
  10 #include <stdio.h>
  11 #include <stdint.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14
  15 #include <folly/portability/Malloc.h>
  16 #include <folly/portability/Windows.h>
  17
  18 namespace HPHP {
  19
  20 char * __php_stpncpy(char *dst, const char *src, size_t len)
  21 {
  22   size_t n = strlen(src);
  23   if (n > len) {
  24     n = len;
  25   }
  26   return strncpy(dst, src, len) + n;
  27 }
  28
  29 void * __php_mempcpy(void * dst, const void * src, size_t len)
  30 {
  31   return (((char *)memcpy(dst, src, len)) + len);
  32 }
  33
  34 #ifndef MIN
  35 # define MIN(a, b) (((a) < (b)) ? (a) : (b))
  36 #endif
  37 #ifndef MAX
  38 # define MAX(a, b) (((a) > (b)) ? (a) : (b))
  39 #endif
  40
  41 /* Structure to save state of computation between the single steps.  */
  42 struct sha256_ctx {
  43   uint32_t H[8];
  44
  45   uint32_t total[2];
  46   uint32_t buflen;
  47   char buffer[128]; /* NB: always correctly aligned for uint32_t.  */
  48 };
  49
  50 #define SWAP(n) (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
  51
  52 /* This array contains the bytes used to pad the buffer to the next
  53    64-byte boundary.  (FIPS 180-2:5.1.1)  */
  54 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
  55
  56
  57 /* Constants for SHA256 from FIPS 180-2:4.2.2.  */
  58 static const uint32_t K[64] = {
  59   0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
  60   0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
  61   0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
  62   0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
  63   0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
  64   0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
  65   0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
  66   0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
  67   0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
  68   0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
  69   0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
  70   0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
  71   0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
  72   0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
  73   0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
  74   0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
  75 };
  76
  77
  78 /* Process LEN bytes of BUFFER, accumulating context into CTX.
  79    It is assumed that LEN % 64 == 0.  */
  80 static void sha256_process_block (const void *buffer, size_t len, struct sha256_ctx *ctx) {
  81   const uint32_t *words = (const uint32_t*)buffer;
  82   size_t nwords = len / sizeof (uint32_t);
  83   unsigned int t;
  84
  85   uint32_t a = ctx->H[0];
  86   uint32_t b = ctx->H[1];
  87   uint32_t c = ctx->H[2];
  88   uint32_t d = ctx->H[3];
  89   uint32_t e = ctx->H[4];
  90   uint32_t f = ctx->H[5];
  91   uint32_t g = ctx->H[6];
  92   uint32_t h = ctx->H[7];
  93
  94   /* First increment the byte count.  FIPS 180-2 specifies the possible
  95    length of the file up to 2^64 bits.  Here we only compute the
  96    number of bytes.  Do a double word increment.  */
  97   ctx->total[0] += (uint32_t)len;
  98   if (ctx->total[0] < len) {
  99     ++ctx->total[1];
 100   }
 101
 102   /* Process all bytes in the buffer with 64 bytes in each round of
 103    the loop.  */
 104   while (nwords > 0) {
 105     uint32_t W[64];
 106     uint32_t a_save = a;
 107     uint32_t b_save = b;
 108     uint32_t c_save = c;
 109     uint32_t d_save = d;
 110     uint32_t e_save = e;
 111     uint32_t f_save = f;
 112     uint32_t g_save = g;
 113     uint32_t h_save = h;
 114
 115   /* Operators defined in FIPS 180-2:4.1.2.  */
 116 #define Ch(x, y, z) ((x & y) ^ (~x & z))
 117 #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
 118 #define S0(x) (CYCLIC (x, 2) ^ CYCLIC (x, 13) ^ CYCLIC (x, 22))
 119 #define S1(x) (CYCLIC (x, 6) ^ CYCLIC (x, 11) ^ CYCLIC (x, 25))
 120 #define R0(x) (CYCLIC (x, 7) ^ CYCLIC (x, 18) ^ (x >> 3))
 121 #define R1(x) (CYCLIC (x, 17) ^ CYCLIC (x, 19) ^ (x >> 10))
 122
 123   /* It is unfortunate that C does not provide an operator for
 124   cyclic rotation.  Hope the C compiler is smart enough.  */
 125 #define CYCLIC(w, s) ((w >> s) | (w << (32 - s)))
 126
 127     /* Compute the message schedule according to FIPS 180-2:6.2.2 step 2.  */
 128     for (t = 0; t < 16; ++t) {
 129       W[t] = SWAP (*words);
 130       ++words;
 131     }
 132     for (t = 16; t < 64; ++t)
 133       W[t] = R1 (W[t - 2]) + W[t - 7] + R0 (W[t - 15]) + W[t - 16];
 134
 135     /* The actual computation according to FIPS 180-2:6.2.2 step 3.  */
 136     for (t = 0; t < 64; ++t) {
 137       uint32_t T1 = h + S1 (e) + Ch (e, f, g) + K[t] + W[t];
 138       uint32_t T2 = S0 (a) + Maj (a, b, c);
 139       h = g;
 140       g = f;
 141       f = e;
 142       e = d + T1;
 143       d = c;
 144       c = b;
 145       b = a;
 146       a = T1 + T2;
 147     }
 148
 149     /* Add the starting values of the context according to FIPS 180-2:6.2.2
 150     step 4.  */
 151     a += a_save;
 152     b += b_save;
 153     c += c_save;
 154     d += d_save;
 155     e += e_save;
 156     f += f_save;
 157     g += g_save;
 158     h += h_save;
 159
 160     /* Prepare for the next round.  */
 161     nwords -= 16;
 162   }
 163
 164   /* Put checksum in context given as argument.  */
 165   ctx->H[0] = a;
 166   ctx->H[1] = b;
 167   ctx->H[2] = c;
 168   ctx->H[3] = d;
 169   ctx->H[4] = e;
 170   ctx->H[5] = f;
 171   ctx->H[6] = g;
 172   ctx->H[7] = h;
 173 }
 174
 175
 176 /* Initialize structure containing state of computation.
 177    (FIPS 180-2:5.3.2)  */
 178 static void sha256_init_ctx(struct sha256_ctx *ctx) {
 179   ctx->H[0] = 0x6a09e667;
 180   ctx->H[1] = 0xbb67ae85;
 181   ctx->H[2] = 0x3c6ef372;
 182   ctx->H[3] = 0xa54ff53a;
 183   ctx->H[4] = 0x510e527f;
 184   ctx->H[5] = 0x9b05688c;
 185   ctx->H[6] = 0x1f83d9ab;
 186   ctx->H[7] = 0x5be0cd19;
 187
 188   ctx->total[0] = ctx->total[1] = 0;
 189   ctx->buflen = 0;
 190 }
 191
 192
 193 /* Process the remaining bytes in the internal buffer and the usual
 194    prolog according to the standard and write the result to RESBUF.
 195
 196    IMPORTANT: On some systems it is required that RESBUF is correctly
 197    aligned for a 32 bits value.  */
 198 static void * sha256_finish_ctx(struct sha256_ctx *ctx, void *resbuf) {
 199   /* Take yet unprocessed bytes into account.  */
 200   uint32_t bytes = ctx->buflen;
 201   size_t pad;
 202   unsigned int i;
 203
 204   /* Now count remaining bytes.  */
 205   ctx->total[0] += bytes;
 206   if (ctx->total[0] < bytes) {
 207     ++ctx->total[1];
 208   }
 209
 210   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
 211   memcpy(&ctx->buffer[bytes], fillbuf, pad);
 212
 213   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 214   *(uint32_t *) &ctx->buffer[bytes + pad + 4] = SWAP (ctx->total[0] << 3);
 215   *(uint32_t *) &ctx->buffer[bytes + pad] = SWAP ((ctx->total[1] << 3) |
 216               (ctx->total[0] >> 29));
 217
 218   /* Process last bytes.  */
 219   sha256_process_block(ctx->buffer, bytes + pad + 8, ctx);
 220
 221   /* Put result from CTX in first 32 bytes following RESBUF.  */
 222   for (i = 0; i < 8; ++i) {
 223     ((uint32_t *) resbuf)[i] = SWAP(ctx->H[i]);
 224   }
 225
 226   return resbuf;
 227 }
 228
 229
 230 static void sha256_process_bytes(const void *buffer, size_t len, struct sha256_ctx *ctx) {
 231   /* When we already have some bits in our internal buffer concatenate
 232    both inputs first.  */
 233   if (ctx->buflen != 0) {
 234     size_t left_over = ctx->buflen;
 235     size_t add = 128 - left_over > len ? len : 128 - left_over;
 236
 237       memcpy(&ctx->buffer[left_over], buffer, add);
 238       ctx->buflen += (uint32_t)add;
 239
 240     if (ctx->buflen > 64) {
 241       sha256_process_block(ctx->buffer, ctx->buflen & ~63, ctx);
 242       ctx->buflen &= 63;
 243       /* The regions in the following copy operation cannot overlap.  */
 244       memcpy(ctx->buffer, &ctx->buffer[(left_over + add) & ~63], ctx->buflen);
 245     }
 246
 247     buffer = (const char *) buffer + add;
 248     len -= add;
 249   }
 250
 251   /* Process available complete blocks.  */
 252   if (len >= 64) {
 253 # define UNALIGNED_P(p) (((uintptr_t) p) % alignof (uint32_t) != 0)
 254     if (UNALIGNED_P (buffer))
 255       while (len > 64) {
 256         sha256_process_block(memcpy(ctx->buffer, buffer, 64), 64, ctx);
 257         buffer = (const char *) buffer + 64;
 258         len -= 64;
 259       } else {
 260         sha256_process_block(buffer, len & ~63, ctx);
 261         buffer = (const char *) buffer + (len & ~63);
 262         len &= 63;
 263       }
 264   }
 265
 266   /* Move remaining bytes into internal buffer.  */
 267   if (len > 0) {
 268     size_t left_over = ctx->buflen;
 269
 270     memcpy(&ctx->buffer[left_over], buffer, len);
 271     left_over += len;
 272     if (left_over >= 64) {
 273       sha256_process_block(ctx->buffer, 64, ctx);
 274       left_over -= 64;
 275       memcpy(ctx->buffer, &ctx->buffer[64], left_over);
 276     }
 277     ctx->buflen = (uint32_t)left_over;
 278   }
 279 }
 280
 281
 282 /* Define our magic string to mark salt for SHA256 "encryption"
 283    replacement.  */
 284 static const char sha256_salt_prefix[] = "$5$";
 285
 286 /* Prefix for optional rounds specification.  */
 287 static const char sha256_rounds_prefix[] = "rounds=";
 288
 289 /* Maximum salt string length.  */
 290 #define SALT_LEN_MAX 16
 291 /* Default number of rounds if not explicitly specified.  */
 292 #define ROUNDS_DEFAULT 5000
 293 /* Minimum number of rounds.  */
 294 #define ROUNDS_MIN 1000
 295 /* Maximum number of rounds.  */
 296 #define ROUNDS_MAX 999999999
 297
 298 /* Table with characters for base64 transformation.  */
 299 static const char b64t[] =
 300 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
 301
 302 char * php_sha256_crypt_r(const char *key, const char *salt, char *buffer, int buflen)
 303 {
 304   alignas(32) unsigned char alt_result[32];
 305   alignas(32) unsigned char temp_result[32];
 306
 307   struct sha256_ctx ctx;
 308   struct sha256_ctx alt_ctx;
 309   size_t salt_len;
 310   size_t key_len;
 311   size_t cnt;
 312   char *cp;
 313   char *copied_key = NULL;
 314   char *copied_salt = NULL;
 315   char *p_bytes;
 316   char *s_bytes;
 317   /* Default number of rounds.  */
 318   size_t rounds = ROUNDS_DEFAULT;
 319   char rounds_custom = 0;
 320
 321   /* Find beginning of salt string.  The prefix should normally always
 322   be present.  Just in case it is not.  */
 323   if (strncmp(sha256_salt_prefix, salt, sizeof(sha256_salt_prefix) - 1) == 0) {
 324     /* Skip salt prefix.  */
 325     salt += sizeof(sha256_salt_prefix) - 1;
 326   }
 327
 328   if (strncmp(salt, sha256_rounds_prefix, sizeof(sha256_rounds_prefix) - 1) == 0) {
 329     const char *num = salt + sizeof(sha256_rounds_prefix) - 1;
 330     char *endp;
 331     unsigned long long srounds = STRTOUL(num, &endp, 10);
 332     if (*endp == '$') {
 333       salt = endp + 1;
 334       rounds = MAX(ROUNDS_MIN, MIN(srounds, ROUNDS_MAX));
 335       rounds_custom = 1;
 336     }
 337   }
 338
 339   salt_len = MIN(strcspn(salt, "$"), SALT_LEN_MAX);
 340   key_len = strlen(key);
 341
 342   if ((key - (char *) 0) % alignof (uint32_t) != 0) {
 343     char *tmp = (char *) alloca(key_len + alignof(uint32_t));
 344     key = copied_key = (char*)memcpy(tmp + alignof(uint32_t) - (tmp - (char *) 0) % alignof(uint32_t), key, key_len);
 345   }
 346
 347   if ((salt - (char *) 0) % alignof(uint32_t) != 0) {
 348     char *tmp = (char *) alloca(salt_len + 1 + alignof(uint32_t));
 349     salt = copied_salt =
 350     (char*)memcpy(tmp + alignof(uint32_t) - (tmp - (char *) 0) % alignof (uint32_t), salt, salt_len);
 351     copied_salt[salt_len] = 0;
 352   }
 353
 354   /* Prepare for the real work.  */
 355   sha256_init_ctx(&ctx);
 356
 357   /* Add the key string.  */
 358   sha256_process_bytes(key, key_len, &ctx);
 359
 360   /* The last part is the salt string.  This must be at most 16
 361    characters and it ends at the first `$' character (for
 362    compatibility with existing implementations).  */
 363   sha256_process_bytes(salt, salt_len, &ctx);
 364
 365
 366   /* Compute alternate SHA256 sum with input KEY, SALT, and KEY.  The
 367    final result will be added to the first context.  */
 368   sha256_init_ctx(&alt_ctx);
 369
 370   /* Add key.  */
 371   sha256_process_bytes(key, key_len, &alt_ctx);
 372
 373   /* Add salt.  */
 374   sha256_process_bytes(salt, salt_len, &alt_ctx);
 375
 376   /* Add key again.  */
 377   sha256_process_bytes(key, key_len, &alt_ctx);
 378
 379   /* Now get result of this (32 bytes) and add it to the other
 380    context.  */
 381   sha256_finish_ctx(&alt_ctx, alt_result);
 382
 383   /* Add for any character in the key one byte of the alternate sum.  */
 384   for (cnt = key_len; cnt > 32; cnt -= 32) {
 385     sha256_process_bytes(alt_result, 32, &ctx);
 386   }
 387   sha256_process_bytes(alt_result, cnt, &ctx);
 388
 389   /* Take the binary representation of the length of the key and for every
 390   1 add the alternate sum, for every 0 the key.  */
 391   for (cnt = key_len; cnt > 0; cnt >>= 1) {
 392     if ((cnt & 1) != 0) {
 393       sha256_process_bytes(alt_result, 32, &ctx);
 394     } else {
 395       sha256_process_bytes(key, key_len, &ctx);
 396     }
 397   }
 398
 399   /* Create intermediate result.  */
 400   sha256_finish_ctx(&ctx, alt_result);
 401
 402   /* Start computation of P byte sequence.  */
 403   sha256_init_ctx(&alt_ctx);
 404
 405   /* For every character in the password add the entire password.  */
 406   for (cnt = 0; cnt < key_len; ++cnt) {
 407     sha256_process_bytes(key, key_len, &alt_ctx);
 408   }
 409
 410   /* Finish the digest.  */
 411   sha256_finish_ctx(&alt_ctx, temp_result);
 412
 413   /* Create byte sequence P.  */
 414   cp = p_bytes = (char*)alloca(key_len);
 415   for (cnt = key_len; cnt >= 32; cnt -= 32) {
 416     cp = (char*)__php_mempcpy((void *)cp, (const void *)temp_result, 32);
 417   }
 418   memcpy(cp, temp_result, cnt);
 419
 420   /* Start computation of S byte sequence.  */
 421   sha256_init_ctx(&alt_ctx);
 422
 423   /* For every character in the password add the entire password.  */
 424   for (cnt = 0; cnt < (size_t) (16 + alt_result[0]); ++cnt) {
 425     sha256_process_bytes(salt, salt_len, &alt_ctx);
 426   }
 427
 428   /* Finish the digest.  */
 429   sha256_finish_ctx(&alt_ctx, temp_result);
 430
 431   /* Create byte sequence S.  */
 432   cp = s_bytes = (char*)alloca(salt_len);
 433   for (cnt = salt_len; cnt >= 32; cnt -= 32) {
 434     cp = (char*)__php_mempcpy(cp, temp_result, 32);
 435   }
 436   memcpy(cp, temp_result, cnt);
 437
 438   /* Repeatedly run the collected hash value through SHA256 to burn
 439   CPU cycles.  */
 440   for (cnt = 0; cnt < rounds; ++cnt) {
 441     /* New context.  */
 442     sha256_init_ctx(&ctx);
 443
 444     /* Add key or last result.  */
 445     if ((cnt & 1) != 0) {
 446       sha256_process_bytes(p_bytes, key_len, &ctx);
 447     } else {
 448       sha256_process_bytes(alt_result, 32, &ctx);
 449     }
 450
 451     /* Add salt for numbers not divisible by 3.  */
 452     if (cnt % 3 != 0) {
 453       sha256_process_bytes(s_bytes, salt_len, &ctx);
 454     }
 455
 456     /* Add key for numbers not divisible by 7.  */
 457     if (cnt % 7 != 0) {
 458       sha256_process_bytes(p_bytes, key_len, &ctx);
 459     }
 460
 461     /* Add key or last result.  */
 462     if ((cnt & 1) != 0) {
 463       sha256_process_bytes(alt_result, 32, &ctx);
 464     } else {
 465       sha256_process_bytes(p_bytes, key_len, &ctx);
 466     }
 467
 468     /* Create intermediate result.  */
 469     sha256_finish_ctx(&ctx, alt_result);
 470   }
 471
 472   /* Now we can construct the result string.  It consists of three
 473   parts.  */
 474   cp = __php_stpncpy(buffer, sha256_salt_prefix, MAX(0, buflen));
 475   buflen -= sizeof(sha256_salt_prefix) - 1;
 476
 477   if (rounds_custom) {
 478     int n = snprintf(cp, MAX(0, buflen), "%s%zu$", sha256_rounds_prefix, rounds);
 479     cp += n;
 480     buflen -= n;
 481   }
 482
 483   cp = __php_stpncpy(cp, salt, MIN ((size_t) MAX (0, buflen), salt_len));
 484   buflen -= MIN(MAX (0, buflen), (int)salt_len);
 485
 486   if (buflen > 0) {
 487     *cp++ = '$';
 488     --buflen;
 489   }
 490
 491 #define b64_from_24bit(B2, B1, B0, N)                \
 492   do {                        \
 493     unsigned int w = ((B2) << 16) | ((B1) << 8) | (B0);            \
 494     int n = (N);                    \
 495     while (n-- > 0 && buflen > 0)                \
 496       {                        \
 497   *cp++ = b64t[w & 0x3f];                  \
 498   --buflen;                    \
 499   w >>= 6;                    \
 500       }                        \
 501   } while (0)
 502
 503   b64_from_24bit(alt_result[0], alt_result[10], alt_result[20], 4);
 504   b64_from_24bit(alt_result[21], alt_result[1], alt_result[11], 4);
 505   b64_from_24bit(alt_result[12], alt_result[22], alt_result[2], 4);
 506   b64_from_24bit(alt_result[3], alt_result[13], alt_result[23], 4);
 507   b64_from_24bit(alt_result[24], alt_result[4], alt_result[14], 4);
 508   b64_from_24bit(alt_result[15], alt_result[25], alt_result[5], 4);
 509   b64_from_24bit(alt_result[6], alt_result[16], alt_result[26], 4);
 510   b64_from_24bit(alt_result[27], alt_result[7], alt_result[17], 4);
 511   b64_from_24bit(alt_result[18], alt_result[28], alt_result[8], 4);
 512   b64_from_24bit(alt_result[9], alt_result[19], alt_result[29], 4);
 513   b64_from_24bit(0, alt_result[31], alt_result[30], 3);
 514   if (buflen <= 0) {
 515     errno = ERANGE;
 516     buffer = NULL;
 517   } else
 518     *cp = '\0';    /* Terminate the string.  */
 519
 520   /* Clear the buffer for the intermediate result so that people
 521      attaching to processes or reading core dumps cannot get any
 522      information.  We do it in this way to clear correct_words[]
 523      inside the SHA256 implementation as well.  */
 524   sha256_init_ctx(&ctx);
 525   sha256_finish_ctx(&ctx, alt_result);
 526   SECURE_ZERO(temp_result, sizeof(temp_result));
 527   SECURE_ZERO(p_bytes, key_len);
 528   SECURE_ZERO(s_bytes, salt_len);
 529   SECURE_ZERO(&ctx, sizeof(ctx));
 530   SECURE_ZERO(&alt_ctx, sizeof(alt_ctx));
 531
 532   if (copied_key != NULL) {
 533     SECURE_ZERO(copied_key, key_len);
 534   }
 535   if (copied_salt != NULL) {
 536     SECURE_ZERO(copied_salt, salt_len);
 537   }
 538
 539   return buffer;
 540 }
 541
 542
 543 /* This entry point is equivalent to the `crypt' function in Unix
 544    libcs.  */
 545 char * php_sha256_crypt(const char *key, const char *salt)
 546 {
 547   /* We don't want to have an arbitrary limit in the size of the
 548   password.  We can compute an upper bound for the size of the
 549   result in advance and so we can prepare the buffer we pass to
 550   `sha256_crypt_r'.  */
 551   static char *buffer;
 552   static int buflen;
 553   int needed = (sizeof(sha256_salt_prefix) - 1
 554       + sizeof(sha256_rounds_prefix) + 9 + 1
 555       + (int)strlen(salt) + 1 + 43 + 1);
 556
 557   if (buflen < needed) {
 558     char *new_buffer = (char *) realloc(buffer, needed);
 559     if (new_buffer == NULL) {
 560       return NULL;
 561     }
 562
 563     buffer = new_buffer;
 564     buflen = needed;
 565   }
 566
 567   return php_sha256_crypt_r(key, salt, buffer, buflen);
 568 }
 569
 570 }