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
50debug_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
71uint32_t SHA_K0 = 0x5A827999;   /* Kt for 0  <= t <= 19 */
72uint32_t SHA_K1 = 0x6ED9EBA1;   /* Kt for 20 <= t <= 39 */
73uint32_t SHA_K2 = 0x8F1BBCDC;   /* Kt for 40 <= t <= 59 */
74uint32_t SHA_K3 = 0xCA62C1D6;   /* Kt for 60 <= t <= 79 */
75
76void
77sha1(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
98void
99sha1_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
185void
186sha1_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
203void
204sha1_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
251void
252sha1_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