source: project/release/4/modular-crypt/trunk/implementations/SHA-2/sha256crypt.c @ 22216

Last change on this file since 22216 was 22216, checked in by sjamaan, 9 years ago

Add initial code for crypt egg

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