1 /*
2 * sha1.c
3 *
4 * an implementation of the Secure Hash Algorithm v.1 (SHA-1),
5 * specified in FIPS 180-1
6 *
7 * David A. McGrew
8 * Cisco Systems, Inc.
9 */
10
11 /*
12 *
13 * Copyright (c) 2001-2006, Cisco Systems, Inc.
14 * All rights reserved.
15 *
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions
18 * are met:
19 *
20 * Redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer.
22 *
23 * Redistributions in binary form must reproduce the above
24 * copyright notice, this list of conditions and the following
25 * disclaimer in the documentation and/or other materials provided
26 * with the distribution.
27 *
28 * Neither the name of the Cisco Systems, Inc. nor the names of its
29 * contributors may be used to endorse or promote products derived
30 * from this software without specific prior written permission.
31 *
32 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
33 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
34 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
35 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
36 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
37 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
38 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
39 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
40 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
41 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
42 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
43 * OF THE POSSIBILITY OF SUCH DAMAGE.
44 *
45 */
46
47
48 #include "sha1.h"
49
50 debug_module_t mod_sha1 = {
51 0, /* debugging is off by default */
52 "sha-1" /* printable module name */
53 };
54
55 /* SN == Rotate left N bits */
56 #define S1(X) ((X << 1) | (X >> 31))
57 #define S5(X) ((X << 5) | (X >> 27))
58 #define S30(X) ((X << 30) | (X >> 2))
59
60 #define f0(B,C,D) ((B & C) | (~B & D))
61 #define f1(B,C,D) (B ^ C ^ D)
62 #define f2(B,C,D) ((B & C) | (B & D) | (C & D))
63 #define f3(B,C,D) (B ^ C ^ D)
64
65 /*
66 * nota bene: the variable K0 appears in the curses library, so we
67 * give longer names to these variables to avoid spurious warnings
68 * on systems that uses curses
69 */
70
71 uint32_t SHA_K0 = 0x5A827999; /* Kt for 0 <= t <= 19 */
72 uint32_t SHA_K1 = 0x6ED9EBA1; /* Kt for 20 <= t <= 39 */
73 uint32_t SHA_K2 = 0x8F1BBCDC; /* Kt for 40 <= t <= 59 */
74 uint32_t SHA_K3 = 0xCA62C1D6; /* Kt for 60 <= t <= 79 */
75
76 void
sha1(const uint8_t * msg,int octets_in_msg,uint32_t hash_value[5])77 sha1(const uint8_t *msg, int octets_in_msg, uint32_t hash_value[5]) {
78 sha1_ctx_t ctx;
79
80 sha1_init(&ctx);
81 sha1_update(&ctx, msg, octets_in_msg);
82 sha1_final(&ctx, hash_value);
83
84 }
85
86 /*
87 * sha1_core(M, H) computes the core compression function, where M is
88 * the next part of the message (in network byte order) and H is the
89 * intermediate state { H0, H1, ...} (in host byte order)
90 *
91 * this function does not do any of the padding required in the
92 * complete SHA1 function
93 *
94 * this function is used in the SEAL 3.0 key setup routines
95 * (crypto/cipher/seal.c)
96 */
97
98 void
sha1_core(const uint32_t M[16],uint32_t hash_value[5])99 sha1_core(const uint32_t M[16], uint32_t hash_value[5]) {
100 uint32_t H0;
101 uint32_t H1;
102 uint32_t H2;
103 uint32_t H3;
104 uint32_t H4;
105 uint32_t W[80];
106 uint32_t A, B, C, D, E, TEMP;
107 int t;
108
109 /* copy hash_value into H0, H1, H2, H3, H4 */
110 H0 = hash_value[0];
111 H1 = hash_value[1];
112 H2 = hash_value[2];
113 H3 = hash_value[3];
114 H4 = hash_value[4];
115
116 /* copy/xor message into array */
117
118 W[0] = be32_to_cpu(M[0]);
119 W[1] = be32_to_cpu(M[1]);
120 W[2] = be32_to_cpu(M[2]);
121 W[3] = be32_to_cpu(M[3]);
122 W[4] = be32_to_cpu(M[4]);
123 W[5] = be32_to_cpu(M[5]);
124 W[6] = be32_to_cpu(M[6]);
125 W[7] = be32_to_cpu(M[7]);
126 W[8] = be32_to_cpu(M[8]);
127 W[9] = be32_to_cpu(M[9]);
128 W[10] = be32_to_cpu(M[10]);
129 W[11] = be32_to_cpu(M[11]);
130 W[12] = be32_to_cpu(M[12]);
131 W[13] = be32_to_cpu(M[13]);
132 W[14] = be32_to_cpu(M[14]);
133 W[15] = be32_to_cpu(M[15]);
134 TEMP = W[13] ^ W[8] ^ W[2] ^ W[0]; W[16] = S1(TEMP);
135 TEMP = W[14] ^ W[9] ^ W[3] ^ W[1]; W[17] = S1(TEMP);
136 TEMP = W[15] ^ W[10] ^ W[4] ^ W[2]; W[18] = S1(TEMP);
137 TEMP = W[16] ^ W[11] ^ W[5] ^ W[3]; W[19] = S1(TEMP);
138 TEMP = W[17] ^ W[12] ^ W[6] ^ W[4]; W[20] = S1(TEMP);
139 TEMP = W[18] ^ W[13] ^ W[7] ^ W[5]; W[21] = S1(TEMP);
140 TEMP = W[19] ^ W[14] ^ W[8] ^ W[6]; W[22] = S1(TEMP);
141 TEMP = W[20] ^ W[15] ^ W[9] ^ W[7]; W[23] = S1(TEMP);
142 TEMP = W[21] ^ W[16] ^ W[10] ^ W[8]; W[24] = S1(TEMP);
143 TEMP = W[22] ^ W[17] ^ W[11] ^ W[9]; W[25] = S1(TEMP);
144 TEMP = W[23] ^ W[18] ^ W[12] ^ W[10]; W[26] = S1(TEMP);
145 TEMP = W[24] ^ W[19] ^ W[13] ^ W[11]; W[27] = S1(TEMP);
146 TEMP = W[25] ^ W[20] ^ W[14] ^ W[12]; W[28] = S1(TEMP);
147 TEMP = W[26] ^ W[21] ^ W[15] ^ W[13]; W[29] = S1(TEMP);
148 TEMP = W[27] ^ W[22] ^ W[16] ^ W[14]; W[30] = S1(TEMP);
149 TEMP = W[28] ^ W[23] ^ W[17] ^ W[15]; W[31] = S1(TEMP);
150
151 /* process the remainder of the array */
152 for (t=32; t < 80; t++) {
153 TEMP = W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16];
154 W[t] = S1(TEMP);
155 }
156
157 A = H0; B = H1; C = H2; D = H3; E = H4;
158
159 for (t=0; t < 20; t++) {
160 TEMP = S5(A) + f0(B,C,D) + E + W[t] + SHA_K0;
161 E = D; D = C; C = S30(B); B = A; A = TEMP;
162 }
163 for ( ; t < 40; t++) {
164 TEMP = S5(A) + f1(B,C,D) + E + W[t] + SHA_K1;
165 E = D; D = C; C = S30(B); B = A; A = TEMP;
166 }
167 for ( ; t < 60; t++) {
168 TEMP = S5(A) + f2(B,C,D) + E + W[t] + SHA_K2;
169 E = D; D = C; C = S30(B); B = A; A = TEMP;
170 }
171 for ( ; t < 80; t++) {
172 TEMP = S5(A) + f3(B,C,D) + E + W[t] + SHA_K3;
173 E = D; D = C; C = S30(B); B = A; A = TEMP;
174 }
175
176 hash_value[0] = H0 + A;
177 hash_value[1] = H1 + B;
178 hash_value[2] = H2 + C;
179 hash_value[3] = H3 + D;
180 hash_value[4] = H4 + E;
181
182 return;
183 }
184
185 void
sha1_init(sha1_ctx_t * ctx)186 sha1_init(sha1_ctx_t *ctx) {
187
188 /* initialize state vector */
189 ctx->H[0] = 0x67452301;
190 ctx->H[1] = 0xefcdab89;
191 ctx->H[2] = 0x98badcfe;
192 ctx->H[3] = 0x10325476;
193 ctx->H[4] = 0xc3d2e1f0;
194
195 /* indicate that message buffer is empty */
196 ctx->octets_in_buffer = 0;
197
198 /* reset message bit-count to zero */
199 ctx->num_bits_in_msg = 0;
200
201 }
202
203 void
sha1_update(sha1_ctx_t * ctx,const uint8_t * msg,int octets_in_msg)204 sha1_update(sha1_ctx_t *ctx, const uint8_t *msg, int octets_in_msg) {
205 int i;
206 uint8_t *buf = (uint8_t *)ctx->M;
207
208 /* update message bit-count */
209 ctx->num_bits_in_msg += octets_in_msg * 8;
210
211 /* loop over 16-word blocks of M */
212 while (octets_in_msg > 0) {
213
214 if (octets_in_msg + ctx->octets_in_buffer >= 64) {
215
216 /*
217 * copy words of M into msg buffer until that buffer is full,
218 * converting them into host byte order as needed
219 */
220 octets_in_msg -= (64 - ctx->octets_in_buffer);
221 for (i=ctx->octets_in_buffer; i < 64; i++)
222 buf[i] = *msg++;
223 ctx->octets_in_buffer = 0;
224
225 /* process a whole block */
226
227 debug_print(mod_sha1, "(update) running sha1_core()", NULL);
228
229 sha1_core(ctx->M, ctx->H);
230
231 } else {
232
233 debug_print(mod_sha1, "(update) not running sha1_core()", NULL);
234
235 for (i=ctx->octets_in_buffer;
236 i < (ctx->octets_in_buffer + octets_in_msg); i++)
237 buf[i] = *msg++;
238 ctx->octets_in_buffer += octets_in_msg;
239 octets_in_msg = 0;
240 }
241
242 }
243
244 }
245
246 /*
247 * sha1_final(ctx, output) computes the result for ctx and copies it
248 * into the twenty octets located at *output
249 */
250
251 void
sha1_final(sha1_ctx_t * ctx,uint32_t * output)252 sha1_final(sha1_ctx_t *ctx, uint32_t *output) {
253 uint32_t A, B, C, D, E, TEMP;
254 uint32_t W[80];
255 int i, t;
256
257 /*
258 * process the remaining octets_in_buffer, padding and terminating as
259 * necessary
260 */
261 {
262 int tail = ctx->octets_in_buffer % 4;
263
264 /* copy/xor message into array */
265 for (i=0; i < (ctx->octets_in_buffer+3)/4; i++)
266 W[i] = be32_to_cpu(ctx->M[i]);
267
268 /* set the high bit of the octet immediately following the message */
269 switch (tail) {
270 case (3):
271 W[i-1] = (be32_to_cpu(ctx->M[i-1]) & 0xffffff00) | 0x80;
272 W[i] = 0x0;
273 break;
274 case (2):
275 W[i-1] = (be32_to_cpu(ctx->M[i-1]) & 0xffff0000) | 0x8000;
276 W[i] = 0x0;
277 break;
278 case (1):
279 W[i-1] = (be32_to_cpu(ctx->M[i-1]) & 0xff000000) | 0x800000;
280 W[i] = 0x0;
281 break;
282 case (0):
283 W[i] = 0x80000000;
284 break;
285 }
286
287 /* zeroize remaining words */
288 for (i++ ; i < 15; i++)
289 W[i] = 0x0;
290
291 /*
292 * if there is room at the end of the word array, then set the
293 * last word to the bit-length of the message; otherwise, set that
294 * word to zero and then we need to do one more run of the
295 * compression algo.
296 */
297 if (ctx->octets_in_buffer < 56)
298 W[15] = ctx->num_bits_in_msg;
299 else if (ctx->octets_in_buffer < 60)
300 W[15] = 0x0;
301
302 /* process the word array */
303 for (t=16; t < 80; t++) {
304 TEMP = W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16];
305 W[t] = S1(TEMP);
306 }
307
308 A = ctx->H[0];
309 B = ctx->H[1];
310 C = ctx->H[2];
311 D = ctx->H[3];
312 E = ctx->H[4];
313
314 for (t=0; t < 20; t++) {
315 TEMP = S5(A) + f0(B,C,D) + E + W[t] + SHA_K0;
316 E = D; D = C; C = S30(B); B = A; A = TEMP;
317 }
318 for ( ; t < 40; t++) {
319 TEMP = S5(A) + f1(B,C,D) + E + W[t] + SHA_K1;
320 E = D; D = C; C = S30(B); B = A; A = TEMP;
321 }
322 for ( ; t < 60; t++) {
323 TEMP = S5(A) + f2(B,C,D) + E + W[t] + SHA_K2;
324 E = D; D = C; C = S30(B); B = A; A = TEMP;
325 }
326 for ( ; t < 80; t++) {
327 TEMP = S5(A) + f3(B,C,D) + E + W[t] + SHA_K3;
328 E = D; D = C; C = S30(B); B = A; A = TEMP;
329 }
330
331 ctx->H[0] += A;
332 ctx->H[1] += B;
333 ctx->H[2] += C;
334 ctx->H[3] += D;
335 ctx->H[4] += E;
336
337 }
338
339 debug_print(mod_sha1, "(final) running sha1_core()", NULL);
340
341 if (ctx->octets_in_buffer >= 56) {
342
343 debug_print(mod_sha1, "(final) running sha1_core() again", NULL);
344
345 /* we need to do one final run of the compression algo */
346
347 /*
348 * set initial part of word array to zeros, and set the
349 * final part to the number of bits in the message
350 */
351 for (i=0; i < 15; i++)
352 W[i] = 0x0;
353 W[15] = ctx->num_bits_in_msg;
354
355 /* process the word array */
356 for (t=16; t < 80; t++) {
357 TEMP = W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16];
358 W[t] = S1(TEMP);
359 }
360
361 A = ctx->H[0];
362 B = ctx->H[1];
363 C = ctx->H[2];
364 D = ctx->H[3];
365 E = ctx->H[4];
366
367 for (t=0; t < 20; t++) {
368 TEMP = S5(A) + f0(B,C,D) + E + W[t] + SHA_K0;
369 E = D; D = C; C = S30(B); B = A; A = TEMP;
370 }
371 for ( ; t < 40; t++) {
372 TEMP = S5(A) + f1(B,C,D) + E + W[t] + SHA_K1;
373 E = D; D = C; C = S30(B); B = A; A = TEMP;
374 }
375 for ( ; t < 60; t++) {
376 TEMP = S5(A) + f2(B,C,D) + E + W[t] + SHA_K2;
377 E = D; D = C; C = S30(B); B = A; A = TEMP;
378 }
379 for ( ; t < 80; t++) {
380 TEMP = S5(A) + f3(B,C,D) + E + W[t] + SHA_K3;
381 E = D; D = C; C = S30(B); B = A; A = TEMP;
382 }
383
384 ctx->H[0] += A;
385 ctx->H[1] += B;
386 ctx->H[2] += C;
387 ctx->H[3] += D;
388 ctx->H[4] += E;
389 }
390
391 /* copy result into output buffer */
392 output[0] = be32_to_cpu(ctx->H[0]);
393 output[1] = be32_to_cpu(ctx->H[1]);
394 output[2] = be32_to_cpu(ctx->H[2]);
395 output[3] = be32_to_cpu(ctx->H[3]);
396 output[4] = be32_to_cpu(ctx->H[4]);
397
398 /* indicate that message buffer in context is empty */
399 ctx->octets_in_buffer = 0;
400
401 return;
402 }
403
404
405
406