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