sha1.c revision de2ed97f33139af5c7a0811e4ec66fc896a13cf2 
1/* Functions to compute SHA1 message digest of files or memory blocks.
2   according to the definition of SHA1 in FIPS 180-1 from April 1997.
3   Copyright (C) 2008-2011 Red Hat, Inc.
4   This file is part of elfutils.
5   Written by Ulrich Drepper <drepper@redhat.com>, 2008.
6
7   This file is free software; you can redistribute it and/or modify
8   it under the terms of either
9
10     * the GNU Lesser General Public License as published by the Free
11       Software Foundation; either version 3 of the License, or (at
12       your option) any later version
13
14   or
15
16     * the GNU General Public License as published by the Free
17       Software Foundation; either version 2 of the License, or (at
18       your option) any later version
19
20   or both in parallel, as here.
21
22   elfutils is distributed in the hope that it will be useful, but
23   WITHOUT ANY WARRANTY; without even the implied warranty of
24   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25   General Public License for more details.
26
27   You should have received copies of the GNU General Public License and
28   the GNU Lesser General Public License along with this program.  If
29   not, see <http://www.gnu.org/licenses/>.  */
30
31#ifdef HAVE_CONFIG_H
32# include <config.h>
33#endif
34
35#include <stdlib.h>
36#include <string.h>
37#include <sys/types.h>
38
39#include "sha1.h"
40#include "system.h"
41
42#define SWAP(n) BE32 (n)
43
44/* This array contains the bytes used to pad the buffer to the next
45   64-byte boundary.  */
46static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
47
48
49/* Initialize structure containing state of computation.  */
50void
51sha1_init_ctx (ctx)
52     struct sha1_ctx *ctx;
53{
54  ctx->A = 0x67452301;
55  ctx->B = 0xefcdab89;
56  ctx->C = 0x98badcfe;
57  ctx->D = 0x10325476;
58  ctx->E = 0xc3d2e1f0;
59
60  ctx->total[0] = ctx->total[1] = 0;
61  ctx->buflen = 0;
62}
63
64/* Put result from CTX in first 20 bytes following RESBUF.  The result
65   must be in little endian byte order.
66
67   IMPORTANT: On some systems it is required that RESBUF is correctly
68   aligned for a 32 bits value.  */
69void *
70sha1_read_ctx (ctx, resbuf)
71     const struct sha1_ctx *ctx;
72     void *resbuf;
73{
74  ((sha1_uint32 *) resbuf)[0] = SWAP (ctx->A);
75  ((sha1_uint32 *) resbuf)[1] = SWAP (ctx->B);
76  ((sha1_uint32 *) resbuf)[2] = SWAP (ctx->C);
77  ((sha1_uint32 *) resbuf)[3] = SWAP (ctx->D);
78  ((sha1_uint32 *) resbuf)[4] = SWAP (ctx->E);
79
80  return resbuf;
81}
82
83static void
84be64_copy (char *dest, uint64_t x)
85{
86  for (size_t i = 8; i-- > 0; x >>= 8)
87    dest[i] = (uint8_t) x;
88}
89
90/* Process the remaining bytes in the internal buffer and the usual
91   prolog according to the standard and write the result to RESBUF.
92
93   IMPORTANT: On some systems it is required that RESBUF is correctly
94   aligned for a 32 bits value.  */
95void *
96sha1_finish_ctx (ctx, resbuf)
97     struct sha1_ctx *ctx;
98     void *resbuf;
99{
100  /* Take yet unprocessed bytes into account.  */
101  sha1_uint32 bytes = ctx->buflen;
102  size_t pad;
103
104  /* Now count remaining bytes.  */
105  ctx->total[0] += bytes;
106  if (ctx->total[0] < bytes)
107    ++ctx->total[1];
108
109  pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
110  memcpy (&ctx->buffer[bytes], fillbuf, pad);
111
112  /* Put the 64-bit file length in *bits* at the end of the buffer.  */
113  const uint64_t bit_length = ((ctx->total[0] << 3)
114			       + ((uint64_t) ((ctx->total[1] << 3) |
115					      (ctx->total[0] >> 29)) << 32));
116  be64_copy (&ctx->buffer[bytes + pad], bit_length);
117
118  /* Process last bytes.  */
119  sha1_process_block (ctx->buffer, bytes + pad + 8, ctx);
120
121  return sha1_read_ctx (ctx, resbuf);
122}
123
124
125void
126sha1_process_bytes (buffer, len, ctx)
127     const void *buffer;
128     size_t len;
129     struct sha1_ctx *ctx;
130{
131  /* When we already have some bits in our internal buffer concatenate
132     both inputs first.  */
133  if (ctx->buflen != 0)
134    {
135      size_t left_over = ctx->buflen;
136      size_t add = 128 - left_over > len ? len : 128 - left_over;
137
138      memcpy (&ctx->buffer[left_over], buffer, add);
139      ctx->buflen += add;
140
141      if (ctx->buflen > 64)
142	{
143	  sha1_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
144
145	  ctx->buflen &= 63;
146	  /* The regions in the following copy operation cannot overlap.  */
147	  memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
148		  ctx->buflen);
149	}
150
151      buffer = (const char *) buffer + add;
152      len -= add;
153    }
154
155  /* Process available complete blocks.  */
156  if (len >= 64)
157    {
158#if !_STRING_ARCH_unaligned
159/* To check alignment gcc has an appropriate operator.  Other
160   compilers don't.  */
161# if __GNUC__ >= 2
162#  define UNALIGNED_P(p) (((sha1_uintptr) p) % __alignof__ (sha1_uint32) != 0)
163# else
164#  define UNALIGNED_P(p) (((sha1_uintptr) p) % sizeof (sha1_uint32) != 0)
165# endif
166      if (UNALIGNED_P (buffer))
167	while (len > 64)
168	  {
169	    sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
170	    buffer = (const char *) buffer + 64;
171	    len -= 64;
172	  }
173      else
174#endif
175	{
176	  sha1_process_block (buffer, len & ~63, ctx);
177	  buffer = (const char *) buffer + (len & ~63);
178	  len &= 63;
179	}
180    }
181
182  /* Move remaining bytes in internal buffer.  */
183  if (len > 0)
184    {
185      size_t left_over = ctx->buflen;
186
187      memcpy (&ctx->buffer[left_over], buffer, len);
188      left_over += len;
189      if (left_over >= 64)
190	{
191	  sha1_process_block (ctx->buffer, 64, ctx);
192	  left_over -= 64;
193	  memcpy (ctx->buffer, &ctx->buffer[64], left_over);
194	}
195      ctx->buflen = left_over;
196    }
197}
198
199
200/* These are the four functions used in the four steps of the SHA1 algorithm
201   and defined in the FIPS 180-1.  */
202/* #define FF(b, c, d) ((b & c) | (~b & d)) */
203#define FF(b, c, d) (d ^ (b & (c ^ d)))
204#define FG(b, c, d) (b ^ c ^ d)
205/* define FH(b, c, d) ((b & c) | (b & d) | (c & d)) */
206#define FH(b, c, d) (((b | c) & d) | (b & c))
207
208/* It is unfortunate that C does not provide an operator for cyclic
209   rotation.  Hope the C compiler is smart enough.  */
210#define CYCLIC(w, s) (((w) << s) | ((w) >> (32 - s)))
211
212/* Magic constants.  */
213#define K0 0x5a827999
214#define K1 0x6ed9eba1
215#define K2 0x8f1bbcdc
216#define K3 0xca62c1d6
217
218
219/* Process LEN bytes of BUFFER, accumulating context into CTX.
220   It is assumed that LEN % 64 == 0.  */
221
222void
223sha1_process_block (buffer, len, ctx)
224     const void *buffer;
225     size_t len;
226     struct sha1_ctx *ctx;
227{
228  sha1_uint32 computed_words[16];
229#define W(i) computed_words[(i) % 16]
230  const sha1_uint32 *words = buffer;
231  size_t nwords = len / sizeof (sha1_uint32);
232  const sha1_uint32 *endp = words + nwords;
233  sha1_uint32 A = ctx->A;
234  sha1_uint32 B = ctx->B;
235  sha1_uint32 C = ctx->C;
236  sha1_uint32 D = ctx->D;
237  sha1_uint32 E = ctx->E;
238
239  /* First increment the byte count.  FIPS 180-1 specifies the possible
240     length of the file up to 2^64 bits.  Here we only compute the
241     number of bytes.  Do a double word increment.  */
242  ctx->total[0] += len;
243  if (ctx->total[0] < len)
244    ++ctx->total[1];
245
246  /* Process all bytes in the buffer with 64 bytes in each round of
247     the loop.  */
248  while (words < endp)
249    {
250      sha1_uint32 A_save = A;
251      sha1_uint32 B_save = B;
252      sha1_uint32 C_save = C;
253      sha1_uint32 D_save = D;
254      sha1_uint32 E_save = E;
255
256      /* First round: using the given function, the context and a constant
257	 the next context is computed.  Because the algorithms processing
258	 unit is a 32-bit word and it is determined to work on words in
259	 little endian byte order we perhaps have to change the byte order
260	 before the computation.  */
261
262#define OP(i, a, b, c, d, e)						\
263      do								\
264        {								\
265	  W (i) = SWAP (*words);					\
266	  e = CYCLIC (a, 5) + FF (b, c, d) + e + W (i) + K0;		\
267	  ++words;							\
268	  b = CYCLIC (b, 30);						\
269        }								\
270      while (0)
271
272      /* Steps 0 to 15.  */
273      OP (0, A, B, C, D, E);
274      OP (1, E, A, B, C, D);
275      OP (2, D, E, A, B, C);
276      OP (3, C, D, E, A, B);
277      OP (4, B, C, D, E, A);
278      OP (5, A, B, C, D, E);
279      OP (6, E, A, B, C, D);
280      OP (7, D, E, A, B, C);
281      OP (8, C, D, E, A, B);
282      OP (9, B, C, D, E, A);
283      OP (10, A, B, C, D, E);
284      OP (11, E, A, B, C, D);
285      OP (12, D, E, A, B, C);
286      OP (13, C, D, E, A, B);
287      OP (14, B, C, D, E, A);
288      OP (15, A, B, C, D, E);
289
290      /* For the remaining 64 steps we have a more complicated
291	 computation of the input data-derived values.  Redefine the
292	 macro to take an additional second argument specifying the
293	 function to use and a new last parameter for the magic
294	 constant.  */
295#undef OP
296#define OP(i, f, a, b, c, d, e, K) \
297      do								\
298        {								\
299	  W (i) = CYCLIC (W (i - 3) ^ W (i - 8) ^ W (i - 14) ^ W (i - 16), 1);\
300	  e = CYCLIC (a, 5) + f (b, c, d) + e + W (i) + K;		\
301	  b = CYCLIC (b, 30);						\
302        }								\
303      while (0)
304
305      /* Steps 16 to 19.  */
306      OP (16, FF, E, A, B, C, D, K0);
307      OP (17, FF, D, E, A, B, C, K0);
308      OP (18, FF, C, D, E, A, B, K0);
309      OP (19, FF, B, C, D, E, A, K0);
310
311      /* Steps 20 to 39.  */
312      OP (20, FG, A, B, C, D, E, K1);
313      OP (21, FG, E, A, B, C, D, K1);
314      OP (22, FG, D, E, A, B, C, K1);
315      OP (23, FG, C, D, E, A, B, K1);
316      OP (24, FG, B, C, D, E, A, K1);
317      OP (25, FG, A, B, C, D, E, K1);
318      OP (26, FG, E, A, B, C, D, K1);
319      OP (27, FG, D, E, A, B, C, K1);
320      OP (28, FG, C, D, E, A, B, K1);
321      OP (29, FG, B, C, D, E, A, K1);
322      OP (30, FG, A, B, C, D, E, K1);
323      OP (31, FG, E, A, B, C, D, K1);
324      OP (32, FG, D, E, A, B, C, K1);
325      OP (33, FG, C, D, E, A, B, K1);
326      OP (34, FG, B, C, D, E, A, K1);
327      OP (35, FG, A, B, C, D, E, K1);
328      OP (36, FG, E, A, B, C, D, K1);
329      OP (37, FG, D, E, A, B, C, K1);
330      OP (38, FG, C, D, E, A, B, K1);
331      OP (39, FG, B, C, D, E, A, K1);
332
333      /* Steps 40 to 59.  */
334      OP (40, FH, A, B, C, D, E, K2);
335      OP (41, FH, E, A, B, C, D, K2);
336      OP (42, FH, D, E, A, B, C, K2);
337      OP (43, FH, C, D, E, A, B, K2);
338      OP (44, FH, B, C, D, E, A, K2);
339      OP (45, FH, A, B, C, D, E, K2);
340      OP (46, FH, E, A, B, C, D, K2);
341      OP (47, FH, D, E, A, B, C, K2);
342      OP (48, FH, C, D, E, A, B, K2);
343      OP (49, FH, B, C, D, E, A, K2);
344      OP (50, FH, A, B, C, D, E, K2);
345      OP (51, FH, E, A, B, C, D, K2);
346      OP (52, FH, D, E, A, B, C, K2);
347      OP (53, FH, C, D, E, A, B, K2);
348      OP (54, FH, B, C, D, E, A, K2);
349      OP (55, FH, A, B, C, D, E, K2);
350      OP (56, FH, E, A, B, C, D, K2);
351      OP (57, FH, D, E, A, B, C, K2);
352      OP (58, FH, C, D, E, A, B, K2);
353      OP (59, FH, B, C, D, E, A, K2);
354
355      /* Steps 60 to 79.  */
356      OP (60, FG, A, B, C, D, E, K3);
357      OP (61, FG, E, A, B, C, D, K3);
358      OP (62, FG, D, E, A, B, C, K3);
359      OP (63, FG, C, D, E, A, B, K3);
360      OP (64, FG, B, C, D, E, A, K3);
361      OP (65, FG, A, B, C, D, E, K3);
362      OP (66, FG, E, A, B, C, D, K3);
363      OP (67, FG, D, E, A, B, C, K3);
364      OP (68, FG, C, D, E, A, B, K3);
365      OP (69, FG, B, C, D, E, A, K3);
366      OP (70, FG, A, B, C, D, E, K3);
367      OP (71, FG, E, A, B, C, D, K3);
368      OP (72, FG, D, E, A, B, C, K3);
369      OP (73, FG, C, D, E, A, B, K3);
370      OP (74, FG, B, C, D, E, A, K3);
371      OP (75, FG, A, B, C, D, E, K3);
372      OP (76, FG, E, A, B, C, D, K3);
373      OP (77, FG, D, E, A, B, C, K3);
374      OP (78, FG, C, D, E, A, B, K3);
375      OP (79, FG, B, C, D, E, A, K3);
376
377      /* Add the starting values of the context.  */
378      A += A_save;
379      B += B_save;
380      C += C_save;
381      D += D_save;
382      E += E_save;
383    }
384
385  /* Put checksum in context given as argument.  */
386  ctx->A = A;
387  ctx->B = B;
388  ctx->C = C;
389  ctx->D = D;
390  ctx->E = E;
391}
392