1 /* sha1.c : Implementation of the Secure Hash Algorithm */
2 
3 /* SHA: NIST's Secure Hash Algorithm */
4 
5 /*	This version written November 2000 by David Ireland of
6 	DI Management Services Pty Limited <code@di-mgt.com.au>
7 
8 	Adapted from code in the Python Cryptography Toolkit,
9 	version 1.0.0 by A.M. Kuchling 1995.
10 */
11 
12 /* AM Kuchling's posting:-
13    Based on SHA code originally posted to sci.crypt by Peter Gutmann
14    in message <30ajo5$oe8@ccu2.auckland.ac.nz>.
15    Modified to test for endianness on creation of SHA objects by AMK.
16    Also, the original specification of SHA was found to have a weakness
17    by NSA/NIST.  This code implements the fixed version of SHA.
18 */
19 
20 /* Here's the first paragraph of Peter Gutmann's posting:
21 
22 The following is my SHA (FIPS 180) code updated to allow use of the "fixed"
23 SHA, thanks to Jim Gillogly and an anonymous contributor for the information on
24 what's changed in the new version.  The fix is a simple change which involves
25 adding a single rotate in the initial expansion function.  It is unknown
26 whether this is an optimal solution to the problem which was discovered in the
27 SHA or whether it's simply a bandaid which fixes the problem with a minimum of
28 effort (for example the reengineering of a great many Capstone chips).
29 */
30 
31 /* h files included here to make this just one file ... */
32 
33 /* global.h */
34 
35 
36 
37 /* sha.c */
38 #include "SHA1.h"
39 
40 #include <stdio.h>
41 #include <string.h>
42 
43 static void SHAtoByte(BYTE *output, UINT4 *input, unsigned int len);
44 
45 /* The SHS block size and message digest sizes, in bytes */
46 
47 #define SHS_DATASIZE    64
48 #define SHS_DIGESTSIZE  20
49 
50 
51 /* The SHS f()-functions.  The f1 and f3 functions can be optimized to
52    save one boolean operation each - thanks to Rich Schroeppel,
53    rcs@cs.arizona.edu for discovering this */
54 
55 /*#define f1(x,y,z) ( ( x & y ) | ( ~x & z ) )          // Rounds  0-19 */
56 #define f1(x,y,z)   ( z ^ ( x & ( y ^ z ) ) )           /* Rounds  0-19 */
57 #define f2(x,y,z)   ( x ^ y ^ z )                       /* Rounds 20-39 */
58 /*#define f3(x,y,z) ( ( x & y ) | ( x & z ) | ( y & z ) )   // Rounds 40-59 */
59 #define f3(x,y,z)   ( ( x & y ) | ( z & ( x | y ) ) )   /* Rounds 40-59 */
60 #define f4(x,y,z)   ( x ^ y ^ z )                       /* Rounds 60-79 */
61 
62 /* The SHS Mysterious Constants */
63 
64 #define K1  0x5A827999L                                 /* Rounds  0-19 */
65 #define K2  0x6ED9EBA1L                                 /* Rounds 20-39 */
66 #define K3  0x8F1BBCDCL                                 /* Rounds 40-59 */
67 #define K4  0xCA62C1D6L                                 /* Rounds 60-79 */
68 
69 /* SHS initial values */
70 
71 #define h0init  0x67452301L
72 #define h1init  0xEFCDAB89L
73 #define h2init  0x98BADCFEL
74 #define h3init  0x10325476L
75 #define h4init  0xC3D2E1F0L
76 
77 /* Note that it may be necessary to add parentheses to these macros if they
78    are to be called with expressions as arguments */
79 /* 32-bit rotate left - kludged with shifts */
80 
81 #define ROTL(n,X)  ( ( ( X ) << n ) | ( ( X ) >> ( 32 - n ) ) )
82 
83 /* The initial expanding function.  The hash function is defined over an
84    80-UINT2 expanded input array W, where the first 16 are copies of the input
85    data, and the remaining 64 are defined by
86 
87         W[ i ] = W[ i - 16 ] ^ W[ i - 14 ] ^ W[ i - 8 ] ^ W[ i - 3 ]
88 
89    This implementation generates these values on the fly in a circular
90    buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
91    optimization.
92 
93    The updated SHS changes the expanding function by adding a rotate of 1
94    bit.  Thanks to Jim Gillogly, jim@rand.org, and an anonymous contributor
95    for this information */
96 
97 #define expand(W,i) ( W[ i & 15 ] = ROTL( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
98                                                  W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] ) ) )
99 
100 
101 /* The prototype SHS sub-round.  The fundamental sub-round is:
102 
103         a' = e + ROTL( 5, a ) + f( b, c, d ) + k + data;
104         b' = a;
105         c' = ROTL( 30, b );
106         d' = c;
107         e' = d;
108 
109    but this is implemented by unrolling the loop 5 times and renaming the
110    variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
111    This code is then replicated 20 times for each of the 4 functions, using
112    the next 20 values from the W[] array each time */
113 
114 #define subRound(a, b, c, d, e, f, k, data) \
115     ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
116 
117 /* Initialize the SHS values */
118 
SHAInit(SHA_CTX * shsInfo)119 void SHAInit(SHA_CTX *shsInfo)
120 {
121     endianTest(&shsInfo->Endianness);
122     /* Set the h-vars to their initial values */
123     shsInfo->digest[ 0 ] = h0init;
124     shsInfo->digest[ 1 ] = h1init;
125     shsInfo->digest[ 2 ] = h2init;
126     shsInfo->digest[ 3 ] = h3init;
127     shsInfo->digest[ 4 ] = h4init;
128 
129     /* Initialise bit count */
130     shsInfo->countLo = shsInfo->countHi = 0;
131 }
132 
133 
134 /* Perform the SHS transformation.  Note that this code, like MD5, seems to
135    break some optimizing compilers due to the complexity of the expressions
136    and the size of the basic block.  It may be necessary to split it into
137    sections, e.g. based on the four subrounds
138 
139    Note that this corrupts the shsInfo->data area */
140 
SHSTransform(digest,data)141 static void SHSTransform( digest, data )
142      UINT4 *digest, *data ;
143     {
144     UINT4 A, B, C, D, E;     /* Local vars */
145     UINT4 eData[ 16 ];       /* Expanded data */
146 
147     /* Set up first buffer and local data buffer */
148     A = digest[ 0 ];
149     B = digest[ 1 ];
150     C = digest[ 2 ];
151     D = digest[ 3 ];
152     E = digest[ 4 ];
153     memcpy( (POINTER)eData, (POINTER)data, SHS_DATASIZE );
154 
155     /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
156     subRound( A, B, C, D, E, f1, K1, eData[  0 ] );
157     subRound( E, A, B, C, D, f1, K1, eData[  1 ] );
158     subRound( D, E, A, B, C, f1, K1, eData[  2 ] );
159     subRound( C, D, E, A, B, f1, K1, eData[  3 ] );
160     subRound( B, C, D, E, A, f1, K1, eData[  4 ] );
161     subRound( A, B, C, D, E, f1, K1, eData[  5 ] );
162     subRound( E, A, B, C, D, f1, K1, eData[  6 ] );
163     subRound( D, E, A, B, C, f1, K1, eData[  7 ] );
164     subRound( C, D, E, A, B, f1, K1, eData[  8 ] );
165     subRound( B, C, D, E, A, f1, K1, eData[  9 ] );
166     subRound( A, B, C, D, E, f1, K1, eData[ 10 ] );
167     subRound( E, A, B, C, D, f1, K1, eData[ 11 ] );
168     subRound( D, E, A, B, C, f1, K1, eData[ 12 ] );
169     subRound( C, D, E, A, B, f1, K1, eData[ 13 ] );
170     subRound( B, C, D, E, A, f1, K1, eData[ 14 ] );
171     subRound( A, B, C, D, E, f1, K1, eData[ 15 ] );
172     subRound( E, A, B, C, D, f1, K1, expand( eData, 16 ) );
173     subRound( D, E, A, B, C, f1, K1, expand( eData, 17 ) );
174     subRound( C, D, E, A, B, f1, K1, expand( eData, 18 ) );
175     subRound( B, C, D, E, A, f1, K1, expand( eData, 19 ) );
176 
177     subRound( A, B, C, D, E, f2, K2, expand( eData, 20 ) );
178     subRound( E, A, B, C, D, f2, K2, expand( eData, 21 ) );
179     subRound( D, E, A, B, C, f2, K2, expand( eData, 22 ) );
180     subRound( C, D, E, A, B, f2, K2, expand( eData, 23 ) );
181     subRound( B, C, D, E, A, f2, K2, expand( eData, 24 ) );
182     subRound( A, B, C, D, E, f2, K2, expand( eData, 25 ) );
183     subRound( E, A, B, C, D, f2, K2, expand( eData, 26 ) );
184     subRound( D, E, A, B, C, f2, K2, expand( eData, 27 ) );
185     subRound( C, D, E, A, B, f2, K2, expand( eData, 28 ) );
186     subRound( B, C, D, E, A, f2, K2, expand( eData, 29 ) );
187     subRound( A, B, C, D, E, f2, K2, expand( eData, 30 ) );
188     subRound( E, A, B, C, D, f2, K2, expand( eData, 31 ) );
189     subRound( D, E, A, B, C, f2, K2, expand( eData, 32 ) );
190     subRound( C, D, E, A, B, f2, K2, expand( eData, 33 ) );
191     subRound( B, C, D, E, A, f2, K2, expand( eData, 34 ) );
192     subRound( A, B, C, D, E, f2, K2, expand( eData, 35 ) );
193     subRound( E, A, B, C, D, f2, K2, expand( eData, 36 ) );
194     subRound( D, E, A, B, C, f2, K2, expand( eData, 37 ) );
195     subRound( C, D, E, A, B, f2, K2, expand( eData, 38 ) );
196     subRound( B, C, D, E, A, f2, K2, expand( eData, 39 ) );
197 
198     subRound( A, B, C, D, E, f3, K3, expand( eData, 40 ) );
199     subRound( E, A, B, C, D, f3, K3, expand( eData, 41 ) );
200     subRound( D, E, A, B, C, f3, K3, expand( eData, 42 ) );
201     subRound( C, D, E, A, B, f3, K3, expand( eData, 43 ) );
202     subRound( B, C, D, E, A, f3, K3, expand( eData, 44 ) );
203     subRound( A, B, C, D, E, f3, K3, expand( eData, 45 ) );
204     subRound( E, A, B, C, D, f3, K3, expand( eData, 46 ) );
205     subRound( D, E, A, B, C, f3, K3, expand( eData, 47 ) );
206     subRound( C, D, E, A, B, f3, K3, expand( eData, 48 ) );
207     subRound( B, C, D, E, A, f3, K3, expand( eData, 49 ) );
208     subRound( A, B, C, D, E, f3, K3, expand( eData, 50 ) );
209     subRound( E, A, B, C, D, f3, K3, expand( eData, 51 ) );
210     subRound( D, E, A, B, C, f3, K3, expand( eData, 52 ) );
211     subRound( C, D, E, A, B, f3, K3, expand( eData, 53 ) );
212     subRound( B, C, D, E, A, f3, K3, expand( eData, 54 ) );
213     subRound( A, B, C, D, E, f3, K3, expand( eData, 55 ) );
214     subRound( E, A, B, C, D, f3, K3, expand( eData, 56 ) );
215     subRound( D, E, A, B, C, f3, K3, expand( eData, 57 ) );
216     subRound( C, D, E, A, B, f3, K3, expand( eData, 58 ) );
217     subRound( B, C, D, E, A, f3, K3, expand( eData, 59 ) );
218 
219     subRound( A, B, C, D, E, f4, K4, expand( eData, 60 ) );
220     subRound( E, A, B, C, D, f4, K4, expand( eData, 61 ) );
221     subRound( D, E, A, B, C, f4, K4, expand( eData, 62 ) );
222     subRound( C, D, E, A, B, f4, K4, expand( eData, 63 ) );
223     subRound( B, C, D, E, A, f4, K4, expand( eData, 64 ) );
224     subRound( A, B, C, D, E, f4, K4, expand( eData, 65 ) );
225     subRound( E, A, B, C, D, f4, K4, expand( eData, 66 ) );
226     subRound( D, E, A, B, C, f4, K4, expand( eData, 67 ) );
227     subRound( C, D, E, A, B, f4, K4, expand( eData, 68 ) );
228     subRound( B, C, D, E, A, f4, K4, expand( eData, 69 ) );
229     subRound( A, B, C, D, E, f4, K4, expand( eData, 70 ) );
230     subRound( E, A, B, C, D, f4, K4, expand( eData, 71 ) );
231     subRound( D, E, A, B, C, f4, K4, expand( eData, 72 ) );
232     subRound( C, D, E, A, B, f4, K4, expand( eData, 73 ) );
233     subRound( B, C, D, E, A, f4, K4, expand( eData, 74 ) );
234     subRound( A, B, C, D, E, f4, K4, expand( eData, 75 ) );
235     subRound( E, A, B, C, D, f4, K4, expand( eData, 76 ) );
236     subRound( D, E, A, B, C, f4, K4, expand( eData, 77 ) );
237     subRound( C, D, E, A, B, f4, K4, expand( eData, 78 ) );
238     subRound( B, C, D, E, A, f4, K4, expand( eData, 79 ) );
239 
240     /* Build message digest */
241     digest[ 0 ] += A;
242     digest[ 1 ] += B;
243     digest[ 2 ] += C;
244     digest[ 3 ] += D;
245     digest[ 4 ] += E;
246     }
247 
248 /* When run on a little-endian CPU we need to perform byte reversal on an
249    array of long words. */
250 
longReverse(UINT4 * buffer,int byteCount,int Endianness)251 static void longReverse(UINT4 *buffer, int byteCount, int Endianness )
252 {
253     UINT4 value;
254 
255     if (Endianness==TRUE) return;
256     byteCount /= sizeof( UINT4 );
257     while( byteCount-- )
258         {
259         value = *buffer;
260         value = ( ( value & 0xFF00FF00L ) >> 8  ) | \
261                 ( ( value & 0x00FF00FFL ) << 8 );
262         *buffer++ = ( value << 16 ) | ( value >> 16 );
263         }
264 }
265 
266 /* Update SHS for a block of data */
267 
SHAUpdate(SHA_CTX * shsInfo,BYTE * buffer,int count)268 void SHAUpdate(SHA_CTX *shsInfo, BYTE *buffer, int count)
269 {
270     UINT4 tmp;
271     int dataCount;
272 
273     /* Update bitcount */
274     tmp = shsInfo->countLo;
275     if ( ( shsInfo->countLo = tmp + ( ( UINT4 ) count << 3 ) ) < tmp )
276         shsInfo->countHi++;             /* Carry from low to high */
277     shsInfo->countHi += count >> 29;
278 
279     /* Get count of bytes already in data */
280     dataCount = ( int ) ( tmp >> 3 ) & 0x3F;
281 
282     /* Handle any leading odd-sized chunks */
283     if( dataCount )
284         {
285         BYTE *p = ( BYTE * ) shsInfo->data + dataCount;
286 
287         dataCount = SHS_DATASIZE - dataCount;
288         if( count < dataCount )
289             {
290             memcpy( p, buffer, count );
291             return;
292             }
293         memcpy( p, buffer, dataCount );
294         longReverse( shsInfo->data, SHS_DATASIZE, shsInfo->Endianness);
295         SHSTransform( shsInfo->digest, shsInfo->data );
296         buffer += dataCount;
297         count -= dataCount;
298         }
299 
300     /* Process data in SHS_DATASIZE chunks */
301     while( count >= SHS_DATASIZE )
302         {
303         memcpy( (POINTER)shsInfo->data, (POINTER)buffer, SHS_DATASIZE );
304         longReverse( shsInfo->data, SHS_DATASIZE, shsInfo->Endianness );
305         SHSTransform( shsInfo->digest, shsInfo->data );
306         buffer += SHS_DATASIZE;
307         count -= SHS_DATASIZE;
308         }
309 
310     /* Handle any remaining bytes of data. */
311     memcpy( (POINTER)shsInfo->data, (POINTER)buffer, count );
312     }
313 
314 /* Final wrapup - pad to SHS_DATASIZE-byte boundary with the bit pattern
315    1 0* (64-bit count of bits processed, MSB-first) */
316 
SHAFinal(BYTE * output,SHA_CTX * shsInfo)317 void SHAFinal(BYTE *output, SHA_CTX *shsInfo)
318 {
319     int count;
320     BYTE *dataPtr;
321 
322     /* Compute number of bytes mod 64 */
323     count = ( int ) shsInfo->countLo;
324     count = ( count >> 3 ) & 0x3F;
325 
326     /* Set the first char of padding to 0x80.  This is safe since there is
327        always at least one byte free */
328     dataPtr = ( BYTE * ) shsInfo->data + count;
329     *dataPtr++ = 0x80;
330 
331     /* Bytes of padding needed to make 64 bytes */
332     count = SHS_DATASIZE - 1 - count;
333 
334     /* Pad out to 56 mod 64 */
335     if( count < 8 )
336         {
337         /* Two lots of padding:  Pad the first block to 64 bytes */
338         memset( dataPtr, 0, count );
339         longReverse( shsInfo->data, SHS_DATASIZE, shsInfo->Endianness );
340         SHSTransform( shsInfo->digest, shsInfo->data );
341 
342         /* Now fill the next block with 56 bytes */
343         memset( (POINTER)shsInfo->data, 0, SHS_DATASIZE - 8 );
344         }
345     else
346         /* Pad block to 56 bytes */
347         memset( dataPtr, 0, count - 8 );
348 
349     /* Append length in bits and transform */
350     shsInfo->data[ 14 ] = shsInfo->countHi;
351     shsInfo->data[ 15 ] = shsInfo->countLo;
352 
353     longReverse( shsInfo->data, SHS_DATASIZE - 8, shsInfo->Endianness );
354     SHSTransform( shsInfo->digest, shsInfo->data );
355 
356 	/* Output to an array of bytes */
357 	SHAtoByte(output, shsInfo->digest, SHS_DIGESTSIZE);
358 
359 	/* Zeroise sensitive stuff */
360 	memset((POINTER)shsInfo, 0, sizeof(shsInfo));
361 }
362 
SHAtoByte(BYTE * output,UINT4 * input,unsigned int len)363 static void SHAtoByte(BYTE *output, UINT4 *input, unsigned int len)
364 {	/* Output SHA digest in byte array */
365 	unsigned int i, j;
366 
367 	for(i = 0, j = 0; j < len; i++, j += 4)
368 	{
369         output[j+3] = (BYTE)( input[i]        & 0xff);
370         output[j+2] = (BYTE)((input[i] >> 8 ) & 0xff);
371         output[j+1] = (BYTE)((input[i] >> 16) & 0xff);
372         output[j  ] = (BYTE)((input[i] >> 24) & 0xff);
373 	}
374 }
375 
376 
377 
378 
379 /* endian.c */
380 
endianTest(int * endian_ness)381 void endianTest(int *endian_ness)
382 {
383 	if((*(unsigned short *) ("#S") >> 8) == '#')
384 	{
385 		/* printf("Big endian = no change\n"); */
386 		*endian_ness = !(0);
387 	}
388 	else
389 	{
390 		/* printf("Little endian = swap\n"); */
391 		*endian_ness = 0;
392 	}
393 }
394