c_cpp/etc/md5_sha/shs.c

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