usr/src/lib/gss_mechs/mech_krb5/crypto/crc32/crc.c

   1 /*
   2  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
   3  * Use is subject to license terms.
   4  */
   5
   6 #pragma ident   "%Z%%M% %I%     %E% SMI"
   7
   8 /*
   9  * lib/crypto/crc32/crc.c
  10  *
  11  * Copyright 1990, 2002 by the Massachusetts Institute of Technology.
  12  * All Rights Reserved.
  13  *
  14  * Export of this software from the United States of America may
  15  *   require a specific license from the United States Government.
  16  *   It is the responsibility of any person or organization contemplating
  17  *   export to obtain such a license before exporting.
  18  *
  19  * WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
  20  * distribute this software and its documentation for any purpose and
  21  * without fee is hereby granted, provided that the above copyright
  22  * notice appear in all copies and that both that copyright notice and
  23  * this permission notice appear in supporting documentation, and that
  24  * the name of M.I.T. not be used in advertising or publicity pertaining
  25  * to distribution of the software without specific, written prior
  26  * permission.  M.I.T. makes no representations about the suitability of
  27  * this software for any purpose.  It is provided "as is" without express
  28  * or implied warranty.
  29  *
  30  *
  31  * CRC-32/AUTODIN-II routines
  32  */
  33
  34 #include <k5-int.h>
  35 #include <crc-32.h>
  36
  37 /* This table and block of comments are taken from code labeled: */
  38 /*
  39  * Copyright (C) 1986 Gary S. Brown.  You may use this program, or
  40  * code or tables extracted from it, as desired without restriction.
  41  */
  42
  43 /* First, the polynomial itself and its table of feedback terms.  The  */
  44 /* polynomial is                                                       */
  45 /* X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0 */
  46 /* Note that we take it "backwards" and put the highest-order term in  */
  47 /* the lowest-order bit.  The X^32 term is "implied"; the LSB is the   */
  48 /* X^31 term, etc.  The X^0 term (usually shown as "+1") results in    */
  49 /* the MSB being 1.                                                    */
  50
  51 /* Note that the usual hardware shift register implementation, which   */
  52 /* is what we're using (we're merely optimizing it by doing eight-bit  */
  53 /* chunks at a time) shifts bits into the lowest-order term.  In our   */
  54 /* implementation, that means shifting towards the right.  Why do we   */
  55 /* do it this way?  Because the calculated CRC must be transmitted in  */
  56 /* order from highest-order term to lowest-order term.  UARTs transmit */
  57 /* characters in order from LSB to MSB.  By storing the CRC this way,  */
  58 /* we hand it to the UART in the order low-byte to high-byte; the UART */
  59 /* sends each low-bit to hight-bit; and the result is transmission bit */
  60 /* by bit from highest- to lowest-order term without requiring any bit */
  61 /* shuffling on our part.  Reception works similarly.                  */
  62
  63 /* The feedback terms table consists of 256, 32-bit entries.  Notes:   */
  64 /*                                                                     */
  65 /*  1. The table can be generated at runtime if desired; code to do so */
  66 /*     is shown later.  It might not be obvious, but the feedback      */
  67 /*     terms simply represent the results of eight shift/xor opera-    */
  68 /*     tions for all combinations of data and CRC register values.     */
  69 /*                                                                     */
  70 /*  2. The CRC accumulation logic is the same for all CRC polynomials, */
  71 /*     be they sixteen or thirty-two bits wide.  You simply choose the */
  72 /*     appropriate table.  Alternatively, because the table can be     */
  73 /*     generated at runtime, you can start by generating the table for */
  74 /*     the polynomial in question and use exactly the same "updcrc",   */
  75 /*     if your application needn't simultaneously handle two CRC       */
  76 /*     polynomials.  (Note, however, that XMODEM is strange.)          */
  77 /*                                                                     */
  78 /*  3. For 16-bit CRCs, the table entries need be only 16 bits wide;   */
  79 /*     of course, 32-bit entries work OK if the high 16 bits are zero. */
  80 /*                                                                     */
  81 /*  4. The values must be right-shifted by eight bits by the "updcrc"  */
  82 /*     logic; the shift must be unsigned (bring in zeroes).  On some   */
  83 /*     hardware you could probably optimize the shift in assembler by  */
  84 /*     using byte-swap instructions.                                   */
  85
  86 static uint32_t const crc_table[256] = {
  87     0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
  88     0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
  89     0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  90     0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
  91     0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
  92     0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  93     0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
  94     0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
  95     0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  96     0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
  97     0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
  98     0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
  99     0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
 100     0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
 101     0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 102     0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
 103     0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
 104     0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 105     0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
 106     0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
 107     0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 108     0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
 109     0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
 110     0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 111     0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
 112     0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
 113     0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 114     0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
 115     0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
 116     0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 117     0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
 118     0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
 119     0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 120     0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
 121     0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
 122     0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 123     0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
 124     0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
 125     0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 126     0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
 127     0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
 128     0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 129     0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
 130     0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
 131     0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 132     0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
 133     0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
 134     0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 135     0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
 136     0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
 137     0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 138     0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
 139     0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
 140     0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 141     0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
 142     0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
 143     0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 144     0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
 145     0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
 146     0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 147     0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
 148     0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
 149     0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 150     0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 151     };
 152
 153 /* Windows needs to these prototypes for crc32_cksumtable_entry below */
 154
 155 static krb5_error_code
 156 crc32_sum_func (
 157         krb5_const krb5_pointer in,
 158         krb5_const size_t in_length,
 159         krb5_const krb5_pointer seed,
 160         krb5_const size_t seed_length,
 161         krb5_checksum *outcksum);
 162
 163 static krb5_error_code
 164 crc32_verify_func (
 165         krb5_const krb5_checksum *cksum,
 166         krb5_const krb5_pointer in,
 167         krb5_const size_t in_length,
 168         krb5_const krb5_pointer seed,
 169         krb5_const size_t seed_length);
 170
 171 /*ARGSUSED*/
 172 static krb5_error_code
 173 crc32_sum_func(in, in_length, seed, seed_length, outcksum)
 174     krb5_const krb5_pointer in;
 175     krb5_const size_t in_length;
 176     krb5_const krb5_pointer seed;
 177     krb5_const size_t seed_length;
 178     krb5_checksum *outcksum;
 179 {
 180     register u_char *data;
 181     register u_long c = 0;
 182     register int idx;
 183     size_t i;
 184
 185     if (outcksum->length < CRC32_CKSUM_LENGTH)
 186         return KRB5_BAD_MSIZE;
 187
 188     data = (u_char *)in;
 189     for (i = 0; i < in_length; i++) {
 190         idx = (int) (data[i] ^ c);
 191         idx &= 0xff;
 192         c >>= 8;
 193         c ^= (u_long) crc_table[idx];
 194     }
 195     /* c now holds the result */
 196     outcksum->checksum_type = CKSUMTYPE_CRC32;
 197     outcksum->length = CRC32_CKSUM_LENGTH;
 198     outcksum->contents[0] = (krb5_octet) (c & 0xff);
 199     outcksum->contents[1] = (krb5_octet) ((c >> 8) & 0xff);
 200     outcksum->contents[2] = (krb5_octet) ((c >> 16) & 0xff);
 201     outcksum->contents[3] = (krb5_octet) ((c >> 24) & 0xff);
 202     return 0;
 203 }
 204
 205 /*ARGSUSED*/
 206 static krb5_error_code
 207 crc32_verify_func(cksum, in, in_length, seed, seed_length)
 208     krb5_const krb5_checksum *cksum;
 209     krb5_const krb5_pointer in;
 210     krb5_const size_t in_length;
 211     krb5_const krb5_pointer seed;
 212     krb5_const size_t seed_length;
 213 {
 214     register u_char *data;
 215     register u_long c = 0;
 216     register int idx;
 217     size_t i;
 218     krb5_error_code     retval;
 219
 220     retval = 0;
 221     if (cksum->checksum_type == CKSUMTYPE_CRC32) {
 222         if (cksum->length == CRC32_CKSUM_LENGTH) {
 223             data = (u_char *)in;
 224             for (i = 0; i < in_length; i++) {
 225                 idx = (int) (data[i] ^ c);
 226                 idx &= 0xff;
 227                 c >>= 8;
 228                 c ^= (u_long) crc_table[idx];
 229             }
 230             if ((cksum->contents[0] != (krb5_octet) (c & 0xff)) ||
 231                 (cksum->contents[1] != (krb5_octet) ((c >> 8) & 0xff)) ||
 232                 (cksum->contents[2] != (krb5_octet) ((c >> 16) & 0xff)) ||
 233                 (cksum->contents[3] != (krb5_octet) ((c >> 24) & 0xff)))
 234                 retval = KRB5KRB_AP_ERR_BAD_INTEGRITY;
 235         }
 236         else
 237             retval = KRB5KRB_AP_ERR_BAD_INTEGRITY;
 238     }
 239     else
 240         retval = KRB5KRB_AP_ERR_INAPP_CKSUM;
 241     return(retval);
 242 }
 243