1 : /* $Id$ */
2 :
3 : /* sha.c - Implementation of the Secure Hash Algorithm
4 : *
5 : * Copyright (C) 1995, A.M. Kuchling
6 : *
7 : * Distribute and use freely; there are no restrictions on further
8 : * dissemination and usage except those imposed by the laws of your
9 : * country of residence.
10 : *
11 : * Adapted to pike and some cleanup by Niels Möller.
12 : */
13 :
14 : /* $Id$ */
15 :
16 : /* SHA: NIST's Secure Hash Algorithm */
17 :
18 : /* Based on SHA code originally posted to sci.crypt by Peter Gutmann
19 : in message <30ajo5$oe8@ccu2.auckland.ac.nz>.
20 : Modified to test for endianness on creation of SHA objects by AMK.
21 : Also, the original specification of SHA was found to have a weakness
22 : by NSA/NIST. This code implements the fixed version of SHA.
23 : */
24 :
25 : /* Here's the first paragraph of Peter Gutmann's posting:
26 :
27 : The following is my SHA (FIPS 180) code updated to allow use of the "fixed"
28 : SHA, thanks to Jim Gillogly and an anonymous contributor for the information on
29 : what's changed in the new version. The fix is a simple change which involves
30 : adding a single rotate in the initial expansion function. It is unknown
31 : whether this is an optimal solution to the problem which was discovered in the
32 : SHA or whether it's simply a bandaid which fixes the problem with a minimum of
33 : effort (for example the reengineering of a great many Capstone chips).
34 : */
35 :
36 : #include "sha1.h"
37 :
38 : #include <string.h>
39 :
40 : void sha_copy(struct SHA_CTX *dest, struct SHA_CTX *src)
41 0 : {
42 : unsigned int i;
43 :
44 0 : dest->count_l=src->count_l;
45 0 : dest->count_h=src->count_h;
46 0 : for(i=0; i<SHA_DIGESTLEN; i++)
47 0 : dest->digest[i]=src->digest[i];
48 0 : for(i=0; i < src->index; i++)
49 0 : dest->block[i] = src->block[i];
50 0 : dest->index = src->index;
51 0 : }
52 :
53 :
54 : /* The SHA f()-functions. The f1 and f3 functions can be optimized to
55 : save one boolean operation each - thanks to Rich Schroeppel,
56 : rcs@cs.arizona.edu for discovering this */
57 :
58 : /*#define f1(x,y,z) ( ( x & y ) | ( ~x & z ) ) // Rounds 0-19 */
59 : #define f1(x,y,z) ( z ^ ( x & ( y ^ z ) ) ) /* Rounds 0-19 */
60 : #define f2(x,y,z) ( x ^ y ^ z ) /* Rounds 20-39 */
61 : /*#define f3(x,y,z) ( ( x & y ) | ( x & z ) | ( y & z ) ) // Rounds 40-59 */
62 : #define f3(x,y,z) ( ( x & y ) | ( z & ( x | y ) ) ) /* Rounds 40-59 */
63 : #define f4(x,y,z) ( x ^ y ^ z ) /* Rounds 60-79 */
64 :
65 : /* The SHA Mysterious Constants */
66 :
67 : #define K1 0x5A827999L /* Rounds 0-19 */
68 : #define K2 0x6ED9EBA1L /* Rounds 20-39 */
69 : #define K3 0x8F1BBCDCL /* Rounds 40-59 */
70 : #define K4 0xCA62C1D6L /* Rounds 60-79 */
71 :
72 : /* SHA initial values */
73 :
74 : #define h0init 0x67452301L
75 : #define h1init 0xEFCDAB89L
76 : #define h2init 0x98BADCFEL
77 : #define h3init 0x10325476L
78 : #define h4init 0xC3D2E1F0L
79 :
80 : /* 32-bit rotate left - kludged with shifts */
81 :
82 : #define ROTL(n,X) ( ( (X) << (n) ) | ( (X) >> ( 32 - (n) ) ) )
83 :
84 : /* The initial expanding function. The hash function is defined over an
85 : 80-word expanded input array W, where the first 16 are copies of the input
86 : data, and the remaining 64 are defined by
87 :
88 : W[ i ] = W[ i - 16 ] ^ W[ i - 14 ] ^ W[ i - 8 ] ^ W[ i - 3 ]
89 :
90 : This implementation generates these values on the fly in a circular
91 : buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
92 : optimization.
93 :
94 : The updated SHA changes the expanding function by adding a rotate of 1
95 : bit. Thanks to Jim Gillogly, jim@rand.org, and an anonymous contributor
96 : for this information */
97 :
98 : #define expand(W,i) ( W[ i & 15 ] = \
99 : ROTL( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
100 : W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] ) ) )
101 :
102 :
103 : /* The prototype SHA sub-round. The fundamental sub-round is:
104 :
105 : a' = e + ROTL( 5, a ) + f( b, c, d ) + k + data;
106 : b' = a;
107 : c' = ROTL( 30, b );
108 : d' = c;
109 : e' = d;
110 :
111 : but this is implemented by unrolling the loop 5 times and renaming the
112 : variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
113 : This code is then replicated 20 times for each of the 4 functions, using
114 : the next 20 values from the W[] array each time */
115 :
116 : #define subRound(a, b, c, d, e, f, k, data) \
117 : ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
118 :
119 : /* Initialize the SHA values */
120 :
121 : void SHA1_Init(struct SHA_CTX *ctx)
122 22 : {
123 : /* Set the h-vars to their initial values */
124 22 : ctx->digest[ 0 ] = h0init;
125 22 : ctx->digest[ 1 ] = h1init;
126 22 : ctx->digest[ 2 ] = h2init;
127 22 : ctx->digest[ 3 ] = h3init;
128 22 : ctx->digest[ 4 ] = h4init;
129 :
130 : /* Initialize bit count */
131 22 : ctx->count_l = ctx->count_h = 0;
132 :
133 : /* Initialize buffer */
134 22 : ctx->index = 0;
135 22 : }
136 :
137 : /* Perform the SHA transformation. Note that this code, like MD5, seems to
138 : break some optimizing compilers due to the complexity of the expressions
139 : and the size of the basic block. It may be necessary to split it into
140 : sections, e.g. based on the four subrounds
141 :
142 : Note that this function destroys the data area */
143 :
144 : static void sha_transform(struct SHA_CTX *ctx, uint32_t *data )
145 51 : {
146 : uint32_t A, B, C, D, E; /* Local vars */
147 :
148 : /* Set up first buffer and local data buffer */
149 51 : A = ctx->digest[0];
150 51 : B = ctx->digest[1];
151 51 : C = ctx->digest[2];
152 51 : D = ctx->digest[3];
153 51 : E = ctx->digest[4];
154 :
155 : /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
156 51 : subRound( A, B, C, D, E, f1, K1, data[ 0] );
157 51 : subRound( E, A, B, C, D, f1, K1, data[ 1] );
158 51 : subRound( D, E, A, B, C, f1, K1, data[ 2] );
159 51 : subRound( C, D, E, A, B, f1, K1, data[ 3] );
160 51 : subRound( B, C, D, E, A, f1, K1, data[ 4] );
161 51 : subRound( A, B, C, D, E, f1, K1, data[ 5] );
162 51 : subRound( E, A, B, C, D, f1, K1, data[ 6] );
163 51 : subRound( D, E, A, B, C, f1, K1, data[ 7] );
164 51 : subRound( C, D, E, A, B, f1, K1, data[ 8] );
165 51 : subRound( B, C, D, E, A, f1, K1, data[ 9] );
166 51 : subRound( A, B, C, D, E, f1, K1, data[10] );
167 51 : subRound( E, A, B, C, D, f1, K1, data[11] );
168 51 : subRound( D, E, A, B, C, f1, K1, data[12] );
169 51 : subRound( C, D, E, A, B, f1, K1, data[13] );
170 51 : subRound( B, C, D, E, A, f1, K1, data[14] );
171 51 : subRound( A, B, C, D, E, f1, K1, data[15] );
172 51 : subRound( E, A, B, C, D, f1, K1, expand( data, 16 ) );
173 51 : subRound( D, E, A, B, C, f1, K1, expand( data, 17 ) );
174 51 : subRound( C, D, E, A, B, f1, K1, expand( data, 18 ) );
175 51 : subRound( B, C, D, E, A, f1, K1, expand( data, 19 ) );
176 :
177 51 : subRound( A, B, C, D, E, f2, K2, expand( data, 20 ) );
178 51 : subRound( E, A, B, C, D, f2, K2, expand( data, 21 ) );
179 51 : subRound( D, E, A, B, C, f2, K2, expand( data, 22 ) );
180 51 : subRound( C, D, E, A, B, f2, K2, expand( data, 23 ) );
181 51 : subRound( B, C, D, E, A, f2, K2, expand( data, 24 ) );
182 51 : subRound( A, B, C, D, E, f2, K2, expand( data, 25 ) );
183 51 : subRound( E, A, B, C, D, f2, K2, expand( data, 26 ) );
184 51 : subRound( D, E, A, B, C, f2, K2, expand( data, 27 ) );
185 51 : subRound( C, D, E, A, B, f2, K2, expand( data, 28 ) );
186 51 : subRound( B, C, D, E, A, f2, K2, expand( data, 29 ) );
187 51 : subRound( A, B, C, D, E, f2, K2, expand( data, 30 ) );
188 51 : subRound( E, A, B, C, D, f2, K2, expand( data, 31 ) );
189 51 : subRound( D, E, A, B, C, f2, K2, expand( data, 32 ) );
190 51 : subRound( C, D, E, A, B, f2, K2, expand( data, 33 ) );
191 51 : subRound( B, C, D, E, A, f2, K2, expand( data, 34 ) );
192 51 : subRound( A, B, C, D, E, f2, K2, expand( data, 35 ) );
193 51 : subRound( E, A, B, C, D, f2, K2, expand( data, 36 ) );
194 51 : subRound( D, E, A, B, C, f2, K2, expand( data, 37 ) );
195 51 : subRound( C, D, E, A, B, f2, K2, expand( data, 38 ) );
196 51 : subRound( B, C, D, E, A, f2, K2, expand( data, 39 ) );
197 :
198 51 : subRound( A, B, C, D, E, f3, K3, expand( data, 40 ) );
199 51 : subRound( E, A, B, C, D, f3, K3, expand( data, 41 ) );
200 51 : subRound( D, E, A, B, C, f3, K3, expand( data, 42 ) );
201 51 : subRound( C, D, E, A, B, f3, K3, expand( data, 43 ) );
202 51 : subRound( B, C, D, E, A, f3, K3, expand( data, 44 ) );
203 51 : subRound( A, B, C, D, E, f3, K3, expand( data, 45 ) );
204 51 : subRound( E, A, B, C, D, f3, K3, expand( data, 46 ) );
205 51 : subRound( D, E, A, B, C, f3, K3, expand( data, 47 ) );
206 51 : subRound( C, D, E, A, B, f3, K3, expand( data, 48 ) );
207 51 : subRound( B, C, D, E, A, f3, K3, expand( data, 49 ) );
208 51 : subRound( A, B, C, D, E, f3, K3, expand( data, 50 ) );
209 51 : subRound( E, A, B, C, D, f3, K3, expand( data, 51 ) );
210 51 : subRound( D, E, A, B, C, f3, K3, expand( data, 52 ) );
211 51 : subRound( C, D, E, A, B, f3, K3, expand( data, 53 ) );
212 51 : subRound( B, C, D, E, A, f3, K3, expand( data, 54 ) );
213 51 : subRound( A, B, C, D, E, f3, K3, expand( data, 55 ) );
214 51 : subRound( E, A, B, C, D, f3, K3, expand( data, 56 ) );
215 51 : subRound( D, E, A, B, C, f3, K3, expand( data, 57 ) );
216 51 : subRound( C, D, E, A, B, f3, K3, expand( data, 58 ) );
217 51 : subRound( B, C, D, E, A, f3, K3, expand( data, 59 ) );
218 :
219 51 : subRound( A, B, C, D, E, f4, K4, expand( data, 60 ) );
220 51 : subRound( E, A, B, C, D, f4, K4, expand( data, 61 ) );
221 51 : subRound( D, E, A, B, C, f4, K4, expand( data, 62 ) );
222 51 : subRound( C, D, E, A, B, f4, K4, expand( data, 63 ) );
223 51 : subRound( B, C, D, E, A, f4, K4, expand( data, 64 ) );
224 51 : subRound( A, B, C, D, E, f4, K4, expand( data, 65 ) );
225 51 : subRound( E, A, B, C, D, f4, K4, expand( data, 66 ) );
226 51 : subRound( D, E, A, B, C, f4, K4, expand( data, 67 ) );
227 51 : subRound( C, D, E, A, B, f4, K4, expand( data, 68 ) );
228 51 : subRound( B, C, D, E, A, f4, K4, expand( data, 69 ) );
229 51 : subRound( A, B, C, D, E, f4, K4, expand( data, 70 ) );
230 51 : subRound( E, A, B, C, D, f4, K4, expand( data, 71 ) );
231 51 : subRound( D, E, A, B, C, f4, K4, expand( data, 72 ) );
232 51 : subRound( C, D, E, A, B, f4, K4, expand( data, 73 ) );
233 51 : subRound( B, C, D, E, A, f4, K4, expand( data, 74 ) );
234 51 : subRound( A, B, C, D, E, f4, K4, expand( data, 75 ) );
235 51 : subRound( E, A, B, C, D, f4, K4, expand( data, 76 ) );
236 51 : subRound( D, E, A, B, C, f4, K4, expand( data, 77 ) );
237 51 : subRound( C, D, E, A, B, f4, K4, expand( data, 78 ) );
238 51 : subRound( B, C, D, E, A, f4, K4, expand( data, 79 ) );
239 :
240 : /* Build message digest */
241 51 : ctx->digest[0] += A;
242 51 : ctx->digest[1] += B;
243 51 : ctx->digest[2] += C;
244 51 : ctx->digest[3] += D;
245 51 : ctx->digest[4] += E;
246 51 : }
247 :
248 : #if 1
249 :
250 : #ifndef EXTRACT_UCHAR
251 : #define EXTRACT_UCHAR(p) (*(unsigned char *)(p))
252 : #endif
253 :
254 : #define STRING2INT(s) ((((((EXTRACT_UCHAR(s) << 8) \
255 : | EXTRACT_UCHAR(s+1)) << 8) \
256 : | EXTRACT_UCHAR(s+2)) << 8) \
257 : | EXTRACT_UCHAR(s+3))
258 : #else
259 : uint32_t STRING2INT(unsigned char *s)
260 : {
261 : uint32_t r;
262 : unsigned int i;
263 :
264 : for (i = 0, r = 0; i < 4; i++, s++)
265 : r = (r << 8) | *s;
266 : return r;
267 : }
268 : #endif
269 :
270 : static void sha_block(struct SHA_CTX *ctx, const unsigned char *block)
271 28 : {
272 : uint32_t data[SHA_DATALEN];
273 : unsigned int i;
274 :
275 : /* Update block count */
276 28 : if (!++ctx->count_l)
277 0 : ++ctx->count_h;
278 :
279 : /* Endian independent conversion */
280 476 : for (i = 0; i<SHA_DATALEN; i++, block += 4)
281 448 : data[i] = STRING2INT(block);
282 :
283 28 : sha_transform(ctx, data);
284 28 : }
285 :
286 : void SHA1_Update(struct SHA_CTX *ctx, const unsigned char *buffer, uint32_t len)
287 137 : {
288 137 : if (ctx->index)
289 : { /* Try to fill partial block */
290 105 : unsigned left = SHA_DATASIZE - ctx->index;
291 105 : if (len < left)
292 : {
293 95 : memcpy(ctx->block + ctx->index, buffer, len);
294 95 : ctx->index += len;
295 95 : return; /* Finished */
296 : }
297 : else
298 : {
299 10 : memcpy(ctx->block + ctx->index, buffer, left);
300 10 : sha_block(ctx, ctx->block);
301 10 : buffer += left;
302 10 : len -= left;
303 : }
304 : }
305 102 : while (len >= SHA_DATASIZE)
306 : {
307 18 : sha_block(ctx, buffer);
308 18 : buffer += SHA_DATASIZE;
309 18 : len -= SHA_DATASIZE;
310 : }
311 42 : if ((ctx->index = len)) /* This assignment is intended */
312 : /* Buffer leftovers */
313 32 : memcpy(ctx->block, buffer, len);
314 : }
315 :
316 : /* Final wrapup - pad to SHA_DATASIZE-byte boundary with the bit pattern
317 : 1 0* (64-bit count of bits processed, MSB-first) */
318 :
319 : void SHA1_Final(unsigned char *s, struct SHA_CTX *ctx)
320 22 : {
321 : uint32_t data[SHA_DATALEN];
322 : unsigned int i;
323 : unsigned int words;
324 :
325 22 : i = ctx->index;
326 : /* Set the first char of padding to 0x80. This is safe since there is
327 : always at least one byte free */
328 22 : ctx->block[i++] = 0x80;
329 :
330 : /* Fill rest of word */
331 68 : for( ; i & 3; i++)
332 46 : ctx->block[i] = 0;
333 :
334 : /* i is now a multiple of the word size 4 */
335 22 : words = i >> 2;
336 224 : for (i = 0; i < words; i++)
337 202 : data[i] = STRING2INT(ctx->block + 4*i);
338 :
339 22 : if (words > (SHA_DATALEN-2))
340 : { /* No room for length in this block. Process it and
341 : * pad with another one */
342 2 : for (i = words ; i < SHA_DATALEN; i++)
343 1 : data[i] = 0;
344 1 : sha_transform(ctx, data);
345 15 : for (i = 0; i < (SHA_DATALEN-2); i++)
346 14 : data[i] = 0;
347 : }
348 : else
349 128 : for (i = words ; i < SHA_DATALEN - 2; i++)
350 107 : data[i] = 0;
351 : /* Theres 512 = 2^9 bits in one block */
352 22 : data[SHA_DATALEN-2] = (ctx->count_h << 9) | (ctx->count_l >> 23);
353 22 : data[SHA_DATALEN-1] = (ctx->count_l << 9) | (ctx->index << 3);
354 22 : sha_transform(ctx, data);
355 22 : sha_digest(ctx, s);
356 22 : }
357 :
358 : void sha_digest(struct SHA_CTX *ctx, unsigned char *s)
359 22 : {
360 : unsigned int i;
361 :
362 132 : for (i = 0; i < SHA_DIGESTLEN; i++)
363 : {
364 110 : *s++ = ctx->digest[i] >> 24;
365 110 : *s++ = 0xff & (ctx->digest[i] >> 16);
366 110 : *s++ = 0xff & (ctx->digest[i] >> 8);
367 110 : *s++ = 0xff & ctx->digest[i];
368 : }
369 22 : }
|