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