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