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