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