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