c_cpp/etc/md5_sha/shs1.c

   1 /*
   2  * shs1 - implements new NIST Secure Hash Standard-1 (SHS1)
   3  *
   4  * @(#) $Revision: 13.5 $
   5  * @(#) $Id: shs1.c,v 13.5 2010/10/12 21:10:17 chongo Exp $
   6  * @(#) $Source: /usr/local/src/cmd/hash/RCS/shs1.c,v $
   7  *
   8  * Written 2 September 1992, Peter C. Gutmann.
   9  *
  10  * This file was modified by Landon Curt Noll.
  11  *
  12  * This code has been placed in the public domain.  Please do not
  13  * copyright this code.
  14  *
  15  * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH  REGARD  TO
  16  * THIS  SOFTWARE,  INCLUDING  ALL IMPLIED WARRANTIES OF MER-
  17  * CHANTABILITY AND FITNESS.  IN NO EVENT SHALL  LANDON  CURT
  18  * NOLL  BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  19  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM  LOSS  OF
  20  * USE,  DATA  OR  PROFITS, WHETHER IN AN ACTION OF CONTRACT,
  21  * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR  IN
  22  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  23  *
  24  * chongo (was here) /\oo/\
  25  * http://www.isthe.com/chongo/index.html
  26  *
  27  * Share and enjoy! :-)
  28  *
  29  * See shs1drvr.c for version and modification history.
  30  */
  31
  32 #include <stdio.h>
  33 #include <string.h>
  34 #define SHS1_IO
  35 #include "shs1.h"
  36 #include "align.h"
  37 #include "endian.h"
  38
  39 /*
  40  * The SHS1 f()-functions.  The f1 and f3 functions can be optimized
  41  * to save one boolean operation each - thanks to Rich Schroeppel,
  42  * rcs@cs.arizona.edu for discovering this.
  43  *
  44  * f1: ((x&y) | (~x&z)) == (z ^ (x&(y^z)))
  45  * f3: ((x&y) | (x&z) | (y&z)) == ((x&y) | (z&(x|y)))
  46  */
  47 #define f1(x,y,z)       (z ^ (x&(y^z)))         /* Rounds  0-19 */
  48 #define f2(x,y,z)       (x^y^z)                 /* Rounds 20-39 */
  49 #define f3(x,y,z)       ((x&y) | (z&(x|y)))     /* Rounds 40-59 */
  50 #define f4(x,y,z)       (x^y^z)                 /* Rounds 60-79 */
  51
  52 /* The SHS1 Mysterious Constants */
  53 #define K1      0x5A827999L     /* Rounds  0-19 */
  54 #define K2      0x6ED9EBA1L     /* Rounds 20-39 */
  55 #define K3      0x8F1BBCDCL     /* Rounds 40-59 */
  56 #define K4      0xCA62C1D6L     /* Rounds 60-79 */
  57
  58 /* SHS1 initial values */
  59 #define h0init  0x67452301L
  60 #define h1init  0xEFCDAB89L
  61 #define h2init  0x98BADCFEL
  62 #define h3init  0x10325476L
  63 #define h4init  0xC3D2E1F0L
  64
  65 /* 32-bit rotate left - kludged with shifts */
  66 #define LEFT_ROT(X,n)  (((X)<<(n)) | ((X)>>(32-(n))))
  67
  68 /*
  69  *
  70  * The initial expanding function.  The hash function is defined over an
  71  * 80-word expanded input array W, where the first 16 are copies of the input
  72  * data, and the remaining 64 are defined by
  73  *
  74  *      W[i] = LEFT_ROT(W[i-16] ^ W[i-14] ^ W[i-8] ^ W[i-3], 1)
  75  *
  76  * NOTE: The expanding function used in rounds 16 to 79 was changed from the
  77  *       original SHA (in FIPS Pub 180) to one that also left circular shifted
  78  *       by one bit for Secure Hash Algorithm-1 (FIPS Pub 180-1).
  79  */
  80 #define exor(W,i,t) \
  81     (t = (W[i&15] ^ W[(i-14)&15] ^ W[(i-8)&15] ^ W[(i-3)&15]), \
  82      W[i&15] = LEFT_ROT(t, 1))
  83
  84 /*
  85  * The prototype SHS1 sub-round.  The fundamental sub-round is:
  86  *
  87  *      a' = e + LEFT_ROT(a,5) + f(b,c,d) + k + data;
  88  *      b' = a;
  89  *      c' = LEFT_ROT(b,30);
  90  *      d' = c;
  91  *      e' = d;
  92  *
  93  * but this is implemented by unrolling the loop 5 times and renaming the
  94  * variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
  95  * This code is then replicated 20 times for each of the 4 functions, using
  96  * the next 20 values from the W[] array each time.
  97  */
  98 #define subRound(a, b, c, d, e, f, k, data) \
  99     (e += LEFT_ROT(a,5) + f(b,c,d) + k + data, b = LEFT_ROT(b,30))
 100
 101
 102 /*
 103  * shs1Init - initialize the SHS1 state
 104  */
 105 void
 106 shs1Init(SHS1_INFO *dig)
 107 {
 108     /* Set the h-vars to their initial values */
 109     dig->digest[0] = h0init;
 110     dig->digest[1] = h1init;
 111     dig->digest[2] = h2init;
 112     dig->digest[3] = h3init;
 113     dig->digest[4] = h4init;
 114
 115     /* Initialise bit count */
 116     dig->octets = 0;
 117     dig->datalen = 0;
 118 }
 119
 120
 121 /*
 122  * shs1Transform - perform the SHS1 transformatio
 123  *
 124  * Note that this code, like MD5, seems to break some optimizing compilers.
 125  * It may be necessary to split it into sections, eg based on the four
 126  * subrounds.  One may also want to roll each subround into a loop.
 127  */
 128 void
 129 shs1Transform(ULONG *digest, ULONG *W)
 130 {
 131     ULONG A, B, C, D, E;        /* Local vars */
 132     ULONG t;                    /* temp storage for exor() */
 133 #if BYTE_ORDER == LITTLE_ENDIAN || defined(DETAILED_DEBUG)
 134     unsigned int i;
 135 #endif /* BYTE_ORDER == LITTLE_ENDIAN || DETAILED_DEBUG */
 136
 137 #if defined(DETAILED_DEBUG)
 138     if (debug) {
 139         ULONG dig;      /* digest in Big Endian order */
 140         unsigned char *p;
 141         unsigned int i;
 142         unsigned int j;
 143
 144         /* print the input digest */
 145         fprintf(stderr, "DEBUG: input digest: ");
 146         for (i=0; i < SHS1_DIGESTWORDS; ++i) {
 147 #if BYTE_ORDER == LITTLE_ENDIAN
 148             dig = ((digest[i]<<16) | (digest[i]>>16));
 149             dig = (((digest[i] & 0xff00ff00UL) >> 8) |
 150                    ((digest[i] & 0x00ff00ffUL) >> 8));
 151 #else /* BYTE_ORDER == LITTLE_ENDIAN */
 152             dig = digest[i];
 153 #endif /* BYTE_ORDER == LITTLE_ENDIAN */
 154             for (j=0, p=(unsigned char *)&dig; j < sizeof(ULONG); ++j, ++p) {
 155                 fprintf(stderr, "%02x  ", *p);
 156             }
 157         }
 158         fputc('\n', stderr);
 159
 160         /* print the input buffer */
 161         fprintf(stderr, "DEBUG: input buffer: ");
 162         for (p = (unsigned char *)W, i=0; i < SHS1_CHUNKSIZE; ++i, ++p) {
 163             fprintf(stderr, "%02x  ", *p);
 164         }
 165         fputc('\n', stderr);
 166     }
 167 #endif /* DETAILED_DEBUG */
 168
 169     /* Set up first buffer and local data buffer */
 170     A = digest[0];
 171     B = digest[1];
 172     C = digest[2];
 173     D = digest[3];
 174     E = digest[4];
 175
 176     /*
 177      * The heavy mangling below was encoded for a Big Endian machine.
 178      * We must byte swap the data on a Little Endian machine unfortunately.
 179      */
 180 #if BYTE_ORDER == LITTLE_ENDIAN
 181     for (i=0; i < SHS1_CHUNKWORDS; ++i) {
 182         W[i] = ((W[i]<<16) | (W[i]>>16));
 183         W[i] = (((W[i] & 0xff00ff00UL) >> 8) |
 184                 ((W[i] & 0x00ff00ffUL) << 8));
 185     }
 186 #endif /* BYTE_ORDER == LITTLE_ENDIAN */
 187
 188     /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
 189     subRound(A, B, C, D, E, f1, K1, W[ 0]);
 190     subRound(E, A, B, C, D, f1, K1, W[ 1]);
 191     subRound(D, E, A, B, C, f1, K1, W[ 2]);
 192     subRound(C, D, E, A, B, f1, K1, W[ 3]);
 193     subRound(B, C, D, E, A, f1, K1, W[ 4]);
 194     subRound(A, B, C, D, E, f1, K1, W[ 5]);
 195     subRound(E, A, B, C, D, f1, K1, W[ 6]);
 196     subRound(D, E, A, B, C, f1, K1, W[ 7]);
 197     subRound(C, D, E, A, B, f1, K1, W[ 8]);
 198     subRound(B, C, D, E, A, f1, K1, W[ 9]);
 199     subRound(A, B, C, D, E, f1, K1, W[10]);
 200     subRound(E, A, B, C, D, f1, K1, W[11]);
 201     subRound(D, E, A, B, C, f1, K1, W[12]);
 202     subRound(C, D, E, A, B, f1, K1, W[13]);
 203     subRound(B, C, D, E, A, f1, K1, W[14]);
 204     subRound(A, B, C, D, E, f1, K1, W[15]);
 205     subRound(E, A, B, C, D, f1, K1, exor(W,16,t));
 206     subRound(D, E, A, B, C, f1, K1, exor(W,17,t));
 207     subRound(C, D, E, A, B, f1, K1, exor(W,18,t));
 208     subRound(B, C, D, E, A, f1, K1, exor(W,19,t));
 209
 210     subRound(A, B, C, D, E, f2, K2, exor(W,20,t));
 211     subRound(E, A, B, C, D, f2, K2, exor(W,21,t));
 212     subRound(D, E, A, B, C, f2, K2, exor(W,22,t));
 213     subRound(C, D, E, A, B, f2, K2, exor(W,23,t));
 214     subRound(B, C, D, E, A, f2, K2, exor(W,24,t));
 215     subRound(A, B, C, D, E, f2, K2, exor(W,25,t));
 216     subRound(E, A, B, C, D, f2, K2, exor(W,26,t));
 217     subRound(D, E, A, B, C, f2, K2, exor(W,27,t));
 218     subRound(C, D, E, A, B, f2, K2, exor(W,28,t));
 219     subRound(B, C, D, E, A, f2, K2, exor(W,29,t));
 220     subRound(A, B, C, D, E, f2, K2, exor(W,30,t));
 221     subRound(E, A, B, C, D, f2, K2, exor(W,31,t));
 222     subRound(D, E, A, B, C, f2, K2, exor(W,32,t));
 223     subRound(C, D, E, A, B, f2, K2, exor(W,33,t));
 224     subRound(B, C, D, E, A, f2, K2, exor(W,34,t));
 225     subRound(A, B, C, D, E, f2, K2, exor(W,35,t));
 226     subRound(E, A, B, C, D, f2, K2, exor(W,36,t));
 227     subRound(D, E, A, B, C, f2, K2, exor(W,37,t));
 228     subRound(C, D, E, A, B, f2, K2, exor(W,38,t));
 229     subRound(B, C, D, E, A, f2, K2, exor(W,39,t));
 230
 231     subRound(A, B, C, D, E, f3, K3, exor(W,40,t));
 232     subRound(E, A, B, C, D, f3, K3, exor(W,41,t));
 233     subRound(D, E, A, B, C, f3, K3, exor(W,42,t));
 234     subRound(C, D, E, A, B, f3, K3, exor(W,43,t));
 235     subRound(B, C, D, E, A, f3, K3, exor(W,44,t));
 236     subRound(A, B, C, D, E, f3, K3, exor(W,45,t));
 237     subRound(E, A, B, C, D, f3, K3, exor(W,46,t));
 238     subRound(D, E, A, B, C, f3, K3, exor(W,47,t));
 239     subRound(C, D, E, A, B, f3, K3, exor(W,48,t));
 240     subRound(B, C, D, E, A, f3, K3, exor(W,49,t));
 241     subRound(A, B, C, D, E, f3, K3, exor(W,50,t));
 242     subRound(E, A, B, C, D, f3, K3, exor(W,51,t));
 243     subRound(D, E, A, B, C, f3, K3, exor(W,52,t));
 244     subRound(C, D, E, A, B, f3, K3, exor(W,53,t));
 245     subRound(B, C, D, E, A, f3, K3, exor(W,54,t));
 246     subRound(A, B, C, D, E, f3, K3, exor(W,55,t));
 247     subRound(E, A, B, C, D, f3, K3, exor(W,56,t));
 248     subRound(D, E, A, B, C, f3, K3, exor(W,57,t));
 249     subRound(C, D, E, A, B, f3, K3, exor(W,58,t));
 250     subRound(B, C, D, E, A, f3, K3, exor(W,59,t));
 251
 252     subRound(A, B, C, D, E, f4, K4, exor(W,60,t));
 253     subRound(E, A, B, C, D, f4, K4, exor(W,61,t));
 254     subRound(D, E, A, B, C, f4, K4, exor(W,62,t));
 255     subRound(C, D, E, A, B, f4, K4, exor(W,63,t));
 256     subRound(B, C, D, E, A, f4, K4, exor(W,64,t));
 257     subRound(A, B, C, D, E, f4, K4, exor(W,65,t));
 258     subRound(E, A, B, C, D, f4, K4, exor(W,66,t));
 259     subRound(D, E, A, B, C, f4, K4, exor(W,67,t));
 260     subRound(C, D, E, A, B, f4, K4, exor(W,68,t));
 261     subRound(B, C, D, E, A, f4, K4, exor(W,69,t));
 262     subRound(A, B, C, D, E, f4, K4, exor(W,70,t));
 263     subRound(E, A, B, C, D, f4, K4, exor(W,71,t));
 264     subRound(D, E, A, B, C, f4, K4, exor(W,72,t));
 265     subRound(C, D, E, A, B, f4, K4, exor(W,73,t));
 266     subRound(B, C, D, E, A, f4, K4, exor(W,74,t));
 267     subRound(A, B, C, D, E, f4, K4, exor(W,75,t));
 268     subRound(E, A, B, C, D, f4, K4, exor(W,76,t));
 269     subRound(D, E, A, B, C, f4, K4, exor(W,77,t));
 270     subRound(C, D, E, A, B, f4, K4, exor(W,78,t));
 271     subRound(B, C, D, E, A, f4, K4, exor(W,79,t));
 272
 273     /* Build message digest */
 274     digest[0] += A;
 275     digest[1] += B;
 276     digest[2] += C;
 277     digest[3] += D;
 278     digest[4] += E;
 279
 280 #if defined(DETAILED_DEBUG)
 281     if (debug) {
 282         int i;
 283         unsigned char *p;
 284
 285         /* print the final digest */
 286         fprintf(stderr, "DEBUG: final digest: ");
 287         for (p = (unsigned char *)digest, i=0; i < SHS1_DIGESTSIZE; ++i, ++p) {
 288             fprintf(stderr, "%02x  ", *p);
 289         }
 290         fputc('\n', stderr);
 291     }
 292 #endif /* DETAILED_DEBUG */
 293 }
 294
 295
 296 /*
 297  * shs1Update - update SHS1 with arbitrary length data
 298  *
 299  * This code does not assume that the buffer size is a multiple of
 300  * SHS1_CHUNKSIZE bytes long.  This code handles partial chunk between
 301  * calls to shs1Update().
 302  */
 303 void
 304 shs1Update(SHS1_INFO *dig, BYTE *buffer, ULONG count)
 305 {
 306     ULONG datalen = dig->datalen;
 307
 308     /*
 309      * Catch the case of a non-empty data buffer
 310      */
 311     if (datalen > 0) {
 312
 313         /* determine the size we need to copy to fill the buffer */
 314         ULONG len_to_fill = SHS1_CHUNKSIZE - datalen;
 315
 316         /* case: new data will not fill the buffer */
 317         if (len_to_fill > count) {
 318             memcpy(((BYTE *)dig->data)+datalen, buffer, count);
 319             dig->datalen = datalen+count;
 320             return;
 321
 322         /* case: buffer will be filled */
 323         } else {
 324             memcpy(((BYTE *)dig->data)+datalen, buffer, len_to_fill);
 325             shs1Transform(dig->digest, dig->data);
 326             buffer += len_to_fill;
 327             count -= len_to_fill;
 328             dig->octets += SHS1_CHUNKSIZE;
 329             dig->datalen = 0;
 330         }
 331     }
 332
 333     /*
 334      * Process data in SHS1_CHUNKSIZE chunks
 335      */
 336     if (count >= SHS1_CHUNKSIZE) {
 337         shs1fullUpdate(dig, buffer, (count & ~SHS1_CHUNKMASK));
 338         buffer += (count & ~SHS1_CHUNKMASK);
 339         count &= SHS1_CHUNKMASK;
 340     }
 341
 342     /*
 343      * Handle any remaining bytes of data.
 344      * This should only happen once on the final lot of data
 345      */
 346     if (count > 0) {
 347         memcpy((char *)dig->data, (char *)buffer, count);
 348     }
 349     dig->datalen = count;
 350 }
 351
 352
 353 /*
 354  * shs1fullUpdate - update SHS1 with chunk multiple length data
 355  *
 356  * This function assumes that count is a multiple of SHS1_CHUNKSIZE and that
 357  * no partial chunk is left over from a previous call.
 358  */
 359 void
 360 shs1fullUpdate(SHS1_INFO *dig, BYTE *buffer, ULONG count)
 361 {
 362 #if defined(MUST_ALIGN)
 363     ULONG in[SHS1_CHUNKWORDS];  /* aligned buffer */
 364 #endif /* MUST_ALIGN */
 365
 366     /*
 367      * Process data in SHS1_CHUNKSIZE chunks
 368      */
 369     while (count >= SHS1_CHUNKSIZE) {
 370 #if defined(MUST_ALIGN)
 371         if ((long)buffer & (sizeof(ULONG)-1)) {
 372             memcpy((char *)in, (char *)buffer, SHS1_CHUNKSIZE);
 373             shs1Transform(dig->digest, in);
 374         } else {
 375             shs1Transform(dig->digest, buffer);
 376         }
 377 #else /* MUST_ALIGN */
 378         shs1Transform(dig->digest, (ULONG *)buffer);
 379 #endif /* MUST_ALIGN */
 380         buffer += SHS1_CHUNKSIZE;
 381         count -= SHS1_CHUNKSIZE;
 382         dig->octets += SHS1_CHUNKSIZE;
 383     }
 384 }
 385
 386
 387 /*
 388  * shs1Final - perform final SHS1 transforms
 389  *
 390  * At this point we have less than a full chunk of data remaining
 391  * (and possibly no data) in the shs1 state data buffer.
 392  *
 393  * First we append a final 0x80 byte.
 394  *
 395  * Next if we have more than 56 bytes, we will zero fill the remainder
 396  * of the chunk, transform and then zero fill the first 56 bytes.
 397  * If we have 56 or fewer bytes, we will zero fill out to the 56th
 398  * chunk byte.  Regardless, we wind up with 56 bytes data.
 399  *
 400  * Finally we append the 64 bit length on to the 56 bytes of data
 401  * remaining.  This final chunk is transformed.
 402  */
 403 void
 404 shs1Final(SHS1_INFO *dig)
 405 {
 406     int count = dig->datalen;   /* count of actual data in buffer */
 407     ULLONG bits;                /* number of bits of data processed */
 408
 409     /*
 410      * Set the first char of padding to 0x80.
 411      * This is safe since there is always at least one byte free
 412      */
 413     dig->octets += count;       /* add in any remaining data in buffer */
 414     ((BYTE *)dig->data)[count++] = 0x80;        /* add in guard octet */
 415
 416     /* Pad out to 56 mod SHS1_CHUNKSIZE */
 417     if (count > 56) {
 418         /* Two lots of padding:  Pad the first chunk to SHS1_CHUNKSIZE bytes */
 419         memset((BYTE *)dig->data + count, 0, SHS1_CHUNKSIZE - count);
 420         shs1Transform(dig->digest, dig->data);
 421
 422         /* Now fill the next chunk with 56 bytes */
 423         memset(dig->data, 0, 56);
 424     } else {
 425         /* Pad chunk to 56 bytes */
 426         memset((BYTE *)dig->data + count, 0, 56 - count);
 427     }
 428
 429     /*
 430      * Append length in bits and transform
 431      *
 432      * We assume that bit count is a multiple of 8 because we have
 433      * only processed full bytes.
 434      */
 435     bits = (dig->octets << 3);
 436 #if BYTE_ORDER == LITTLE_ENDIAN
 437     bits = ((bits << 32) | (bits >> 32));
 438     bits = ((bits & 0xffff0000ffff0000ULL) >> 16) |
 439            ((bits & 0x0000ffff0000ffffULL) << 16);
 440     bits = ((bits & 0xff00ff00ff00ff00ULL) >> 8) |
 441            ((bits & 0x00ff00ff00ff00ffULL) << 8);
 442 #endif /* BYTE_ORDER == LITTLE_ENDIAN */
 443     memcpy(&(dig->data[SHS1_HIGH]), &bits, sizeof(ULLONG));
 444     shs1Transform(dig->digest, dig->data);
 445     dig->datalen = 0;
 446 }