1 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 #include "shs.h"
3 #ifdef HAVE_SYS_TYPES_H
4 #include <sys/types.h>
5 #endif
6 #include <string.h>
7
8 #ifdef K5_BUILTIN_SHA1
9
10 /* The SHS f()-functions. The f1 and f3 functions can be optimized to
11 save one boolean operation each - thanks to Rich Schroeppel,
12 rcs@cs.arizona.edu for discovering this */
13
14 #define f1(x,y,z) ( z ^ ( x & ( y ^ z ) ) ) /* Rounds 0-19 */
15 #define f2(x,y,z) ( x ^ y ^ z ) /* Rounds 20-39 */
16 #define f3(x,y,z) ( ( x & y ) | ( z & ( x | y ) ) ) /* Rounds 40-59 */
17 #define f4(x,y,z) ( x ^ y ^ z ) /* Rounds 60-79 */
18
19 /* The SHS Mysterious Constants */
20
21 #define K1 0x5A827999L /* Rounds 0-19 */
22 #define K2 0x6ED9EBA1L /* Rounds 20-39 */
23 #define K3 0x8F1BBCDCL /* Rounds 40-59 */
24 #define K4 0xCA62C1D6L /* Rounds 60-79 */
25
26 /* SHS initial values */
27
28 #define h0init 0x67452301L
29 #define h1init 0xEFCDAB89L
30 #define h2init 0x98BADCFEL
31 #define h3init 0x10325476L
32 #define h4init 0xC3D2E1F0L
33
34 /* Note that it may be necessary to add parentheses to these macros if they
35 are to be called with expressions as arguments */
36
37 /* 32-bit rotate left - kludged with shifts */
38
39 #define ROTL(n,X) ((((X) << (n)) & 0xffffffff) | ((X) >> (32 - n)))
40
41 /* The initial expanding function. The hash function is defined over an
42 80-word expanded input array W, where the first 16 are copies of the input
43 data, and the remaining 64 are defined by
44
45 W[ i ] = W[ i - 16 ] ^ W[ i - 14 ] ^ W[ i - 8 ] ^ W[ i - 3 ]
46
47 This implementation generates these values on the fly in a circular
48 buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
49 optimization.
50
51 The updated SHS changes the expanding function by adding a rotate of 1
52 bit. Thanks to Jim Gillogly, jim@rand.org, and an anonymous contributor
53 for this information */
54
55 #ifdef NEW_SHS
56 #define expand(W,i) ( W[ i & 15 ] = ROTL( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
57 W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] )))
58 #else
59 #define expand(W,i) ( W[ i & 15 ] ^= W[ (i - 14) & 15 ] ^ \
60 W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] )
61 #endif /* NEW_SHS */
62
63 /* The prototype SHS sub-round. The fundamental sub-round is:
64
65 a' = e + ROTL( 5, a ) + f( b, c, d ) + k + data;
66 b' = a;
67 c' = ROTL( 30, b );
68 d' = c;
69 e' = d;
70
71 but this is implemented by unrolling the loop 5 times and renaming the
72 variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
73 This code is then replicated 20 times for each of the 4 functions, using
74 the next 20 values from the W[] array each time */
75
76 #define subRound(a, b, c, d, e, f, k, data) \
77 ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, \
78 e &= 0xffffffff, b = ROTL( 30, b ) )
79
80 /* Initialize the SHS values */
81
shsInit(SHS_INFO * shsInfo)82 void shsInit(SHS_INFO *shsInfo)
83 {
84 /* Set the h-vars to their initial values */
85 shsInfo->digest[ 0 ] = h0init;
86 shsInfo->digest[ 1 ] = h1init;
87 shsInfo->digest[ 2 ] = h2init;
88 shsInfo->digest[ 3 ] = h3init;
89 shsInfo->digest[ 4 ] = h4init;
90
91 /* Initialise bit count */
92 shsInfo->countLo = shsInfo->countHi = 0;
93 }
94
95 /* Perform the SHS transformation. Note that this code, like MD5, seems to
96 break some optimizing compilers due to the complexity of the expressions
97 and the size of the basic block. It may be necessary to split it into
98 sections, e.g. based on the four subrounds
99
100 Note that this corrupts the shsInfo->data area */
101
102 static void SHSTransform (SHS_LONG *digest, const SHS_LONG *data);
103
104 static
SHSTransform(SHS_LONG * digest,const SHS_LONG * data)105 void SHSTransform(SHS_LONG *digest, const SHS_LONG *data)
106 {
107 SHS_LONG A, B, C, D, E; /* Local vars */
108 SHS_LONG eData[ 16 ]; /* Expanded data */
109
110 /* Set up first buffer and local data buffer */
111 A = digest[ 0 ];
112 B = digest[ 1 ];
113 C = digest[ 2 ];
114 D = digest[ 3 ];
115 E = digest[ 4 ];
116 memcpy(eData, data, sizeof (eData));
117
118 #if defined(CONFIG_SMALL) && !defined(CONFIG_SMALL_NO_CRYPTO)
119
120 {
121 int i;
122 SHS_LONG temp;
123 for (i = 0; i < 20; i++) {
124 SHS_LONG x = (i < 16) ? eData[i] : expand(eData, i);
125 subRound(A, B, C, D, E, f1, K1, x);
126 temp = E, E = D, D = C, C = B, B = A, A = temp;
127 }
128 for (i = 20; i < 40; i++) {
129 subRound(A, B, C, D, E, f2, K2, expand(eData, i));
130 temp = E, E = D, D = C, C = B, B = A, A = temp;
131 }
132 for (i = 40; i < 60; i++) {
133 subRound(A, B, C, D, E, f3, K3, expand(eData, i));
134 temp = E, E = D, D = C, C = B, B = A, A = temp;
135 }
136 for (i = 60; i < 80; i++) {
137 subRound(A, B, C, D, E, f4, K4, expand(eData, i));
138 temp = E, E = D, D = C, C = B, B = A, A = temp;
139 }
140 }
141
142 #else
143
144 /* Heavy mangling, in 4 sub-rounds of 20 iterations each. */
145 subRound( A, B, C, D, E, f1, K1, eData[ 0 ] );
146 subRound( E, A, B, C, D, f1, K1, eData[ 1 ] );
147 subRound( D, E, A, B, C, f1, K1, eData[ 2 ] );
148 subRound( C, D, E, A, B, f1, K1, eData[ 3 ] );
149 subRound( B, C, D, E, A, f1, K1, eData[ 4 ] );
150 subRound( A, B, C, D, E, f1, K1, eData[ 5 ] );
151 subRound( E, A, B, C, D, f1, K1, eData[ 6 ] );
152 subRound( D, E, A, B, C, f1, K1, eData[ 7 ] );
153 subRound( C, D, E, A, B, f1, K1, eData[ 8 ] );
154 subRound( B, C, D, E, A, f1, K1, eData[ 9 ] );
155 subRound( A, B, C, D, E, f1, K1, eData[ 10 ] );
156 subRound( E, A, B, C, D, f1, K1, eData[ 11 ] );
157 subRound( D, E, A, B, C, f1, K1, eData[ 12 ] );
158 subRound( C, D, E, A, B, f1, K1, eData[ 13 ] );
159 subRound( B, C, D, E, A, f1, K1, eData[ 14 ] );
160 subRound( A, B, C, D, E, f1, K1, eData[ 15 ] );
161 subRound( E, A, B, C, D, f1, K1, expand( eData, 16 ) );
162 subRound( D, E, A, B, C, f1, K1, expand( eData, 17 ) );
163 subRound( C, D, E, A, B, f1, K1, expand( eData, 18 ) );
164 subRound( B, C, D, E, A, f1, K1, expand( eData, 19 ) );
165
166 subRound( A, B, C, D, E, f2, K2, expand( eData, 20 ) );
167 subRound( E, A, B, C, D, f2, K2, expand( eData, 21 ) );
168 subRound( D, E, A, B, C, f2, K2, expand( eData, 22 ) );
169 subRound( C, D, E, A, B, f2, K2, expand( eData, 23 ) );
170 subRound( B, C, D, E, A, f2, K2, expand( eData, 24 ) );
171 subRound( A, B, C, D, E, f2, K2, expand( eData, 25 ) );
172 subRound( E, A, B, C, D, f2, K2, expand( eData, 26 ) );
173 subRound( D, E, A, B, C, f2, K2, expand( eData, 27 ) );
174 subRound( C, D, E, A, B, f2, K2, expand( eData, 28 ) );
175 subRound( B, C, D, E, A, f2, K2, expand( eData, 29 ) );
176 subRound( A, B, C, D, E, f2, K2, expand( eData, 30 ) );
177 subRound( E, A, B, C, D, f2, K2, expand( eData, 31 ) );
178 subRound( D, E, A, B, C, f2, K2, expand( eData, 32 ) );
179 subRound( C, D, E, A, B, f2, K2, expand( eData, 33 ) );
180 subRound( B, C, D, E, A, f2, K2, expand( eData, 34 ) );
181 subRound( A, B, C, D, E, f2, K2, expand( eData, 35 ) );
182 subRound( E, A, B, C, D, f2, K2, expand( eData, 36 ) );
183 subRound( D, E, A, B, C, f2, K2, expand( eData, 37 ) );
184 subRound( C, D, E, A, B, f2, K2, expand( eData, 38 ) );
185 subRound( B, C, D, E, A, f2, K2, expand( eData, 39 ) );
186
187 subRound( A, B, C, D, E, f3, K3, expand( eData, 40 ) );
188 subRound( E, A, B, C, D, f3, K3, expand( eData, 41 ) );
189 subRound( D, E, A, B, C, f3, K3, expand( eData, 42 ) );
190 subRound( C, D, E, A, B, f3, K3, expand( eData, 43 ) );
191 subRound( B, C, D, E, A, f3, K3, expand( eData, 44 ) );
192 subRound( A, B, C, D, E, f3, K3, expand( eData, 45 ) );
193 subRound( E, A, B, C, D, f3, K3, expand( eData, 46 ) );
194 subRound( D, E, A, B, C, f3, K3, expand( eData, 47 ) );
195 subRound( C, D, E, A, B, f3, K3, expand( eData, 48 ) );
196 subRound( B, C, D, E, A, f3, K3, expand( eData, 49 ) );
197 subRound( A, B, C, D, E, f3, K3, expand( eData, 50 ) );
198 subRound( E, A, B, C, D, f3, K3, expand( eData, 51 ) );
199 subRound( D, E, A, B, C, f3, K3, expand( eData, 52 ) );
200 subRound( C, D, E, A, B, f3, K3, expand( eData, 53 ) );
201 subRound( B, C, D, E, A, f3, K3, expand( eData, 54 ) );
202 subRound( A, B, C, D, E, f3, K3, expand( eData, 55 ) );
203 subRound( E, A, B, C, D, f3, K3, expand( eData, 56 ) );
204 subRound( D, E, A, B, C, f3, K3, expand( eData, 57 ) );
205 subRound( C, D, E, A, B, f3, K3, expand( eData, 58 ) );
206 subRound( B, C, D, E, A, f3, K3, expand( eData, 59 ) );
207
208 subRound( A, B, C, D, E, f4, K4, expand( eData, 60 ) );
209 subRound( E, A, B, C, D, f4, K4, expand( eData, 61 ) );
210 subRound( D, E, A, B, C, f4, K4, expand( eData, 62 ) );
211 subRound( C, D, E, A, B, f4, K4, expand( eData, 63 ) );
212 subRound( B, C, D, E, A, f4, K4, expand( eData, 64 ) );
213 subRound( A, B, C, D, E, f4, K4, expand( eData, 65 ) );
214 subRound( E, A, B, C, D, f4, K4, expand( eData, 66 ) );
215 subRound( D, E, A, B, C, f4, K4, expand( eData, 67 ) );
216 subRound( C, D, E, A, B, f4, K4, expand( eData, 68 ) );
217 subRound( B, C, D, E, A, f4, K4, expand( eData, 69 ) );
218 subRound( A, B, C, D, E, f4, K4, expand( eData, 70 ) );
219 subRound( E, A, B, C, D, f4, K4, expand( eData, 71 ) );
220 subRound( D, E, A, B, C, f4, K4, expand( eData, 72 ) );
221 subRound( C, D, E, A, B, f4, K4, expand( eData, 73 ) );
222 subRound( B, C, D, E, A, f4, K4, expand( eData, 74 ) );
223 subRound( A, B, C, D, E, f4, K4, expand( eData, 75 ) );
224 subRound( E, A, B, C, D, f4, K4, expand( eData, 76 ) );
225 subRound( D, E, A, B, C, f4, K4, expand( eData, 77 ) );
226 subRound( C, D, E, A, B, f4, K4, expand( eData, 78 ) );
227 subRound( B, C, D, E, A, f4, K4, expand( eData, 79 ) );
228
229 #endif
230
231 /* Build message digest */
232 digest[ 0 ] += A;
233 digest[ 0 ] &= 0xffffffff;
234 digest[ 1 ] += B;
235 digest[ 1 ] &= 0xffffffff;
236 digest[ 2 ] += C;
237 digest[ 2 ] &= 0xffffffff;
238 digest[ 3 ] += D;
239 digest[ 3 ] &= 0xffffffff;
240 digest[ 4 ] += E;
241 digest[ 4 ] &= 0xffffffff;
242 }
243
244 /* Update SHS for a block of data */
245
shsUpdate(SHS_INFO * shsInfo,const SHS_BYTE * buffer,unsigned int count)246 void shsUpdate(SHS_INFO *shsInfo, const SHS_BYTE *buffer, unsigned int count)
247 {
248 SHS_LONG tmp;
249 unsigned int dataCount;
250 int canfill;
251 SHS_LONG *lp;
252
253 /* Update bitcount */
254 tmp = shsInfo->countLo;
255 shsInfo->countLo = tmp + (((SHS_LONG) count) << 3 );
256 if ((shsInfo->countLo &= 0xffffffff) < tmp)
257 shsInfo->countHi++; /* Carry from low to high */
258 shsInfo->countHi += count >> 29;
259
260 /* Get count of bytes already in data */
261 dataCount = (tmp >> 3) & 0x3F;
262
263 /* Handle any leading odd-sized chunks */
264 if (dataCount) {
265 lp = shsInfo->data + dataCount / 4;
266 dataCount = SHS_DATASIZE - dataCount;
267 canfill = (count >= dataCount);
268
269 if (dataCount % 4) {
270 /* Fill out a full 32 bit word first if needed -- this
271 is not very efficient (computed shift amount),
272 but it shouldn't happen often. */
273 while (dataCount % 4 && count > 0) {
274 *lp |= (SHS_LONG) *buffer++ << ((--dataCount % 4) * 8);
275 count--;
276 }
277 lp++;
278 }
279 while (lp < shsInfo->data + 16) {
280 if (count < 4) {
281 *lp = 0;
282 switch (count % 4) {
283 case 3:
284 *lp |= (SHS_LONG) buffer[2] << 8;
285 case 2:
286 *lp |= (SHS_LONG) buffer[1] << 16;
287 case 1:
288 *lp |= (SHS_LONG) buffer[0] << 24;
289 }
290 count = 0;
291 break; /* out of while loop */
292 }
293 *lp++ = load_32_be(buffer);
294 buffer += 4;
295 count -= 4;
296 }
297 if (canfill) {
298 SHSTransform(shsInfo->digest, shsInfo->data);
299 }
300 }
301
302 /* Process data in SHS_DATASIZE chunks */
303 while (count >= SHS_DATASIZE) {
304 lp = shsInfo->data;
305 while (lp < shsInfo->data + 16) {
306 *lp++ = load_32_be(buffer);
307 buffer += 4;
308 }
309 SHSTransform(shsInfo->digest, shsInfo->data);
310 count -= SHS_DATASIZE;
311 }
312
313 if (count > 0) {
314 lp = shsInfo->data;
315 while (count > 4) {
316 *lp++ = load_32_be(buffer);
317 buffer += 4;
318 count -= 4;
319 }
320 *lp = 0;
321 switch (count % 4) {
322 case 0:
323 *lp |= ((SHS_LONG) buffer[3]);
324 case 3:
325 *lp |= ((SHS_LONG) buffer[2]) << 8;
326 case 2:
327 *lp |= ((SHS_LONG) buffer[1]) << 16;
328 case 1:
329 *lp |= ((SHS_LONG) buffer[0]) << 24;
330 }
331 }
332 }
333
334 /* Final wrapup - pad to SHS_DATASIZE-byte boundary with the bit pattern
335 1 0* (64-bit count of bits processed, MSB-first) */
336
shsFinal(SHS_INFO * shsInfo)337 void shsFinal(SHS_INFO *shsInfo)
338 {
339 int count;
340 SHS_LONG *lp;
341
342 /* Compute number of bytes mod 64 */
343 count = (int) shsInfo->countLo;
344 count = (count >> 3) & 0x3F;
345
346 /* Set the first char of padding to 0x80. This is safe since there is
347 always at least one byte free */
348 lp = shsInfo->data + count / 4;
349 switch (count % 4) {
350 case 3:
351 *lp++ |= (SHS_LONG) 0x80;
352 break;
353 case 2:
354 *lp++ |= (SHS_LONG) 0x80 << 8;
355 break;
356 case 1:
357 *lp++ |= (SHS_LONG) 0x80 << 16;
358 break;
359 case 0:
360 *lp++ = (SHS_LONG) 0x80 << 24;
361 }
362
363 /* at this point, lp can point *past* shsInfo->data. If it points
364 there, just Transform and reset. If it points to the last
365 element, set that to zero. This pads out to 64 bytes if not
366 enough room for length words */
367
368 if (lp == shsInfo->data + 15)
369 *lp++ = 0;
370
371 if (lp == shsInfo->data + 16) {
372 SHSTransform(shsInfo->digest, shsInfo->data);
373 lp = shsInfo->data;
374 }
375
376 /* Pad out to 56 bytes */
377 while (lp < shsInfo->data + 14)
378 *lp++ = 0;
379
380 /* Append length in bits and transform */
381 *lp++ = shsInfo->countHi;
382 *lp++ = shsInfo->countLo;
383 SHSTransform(shsInfo->digest, shsInfo->data);
384 }
385
386 #endif /* K5_BUILTIN_SHA1 */
387