wimlib.net Git - wimlib/blob - src/sha1.c

   1 /* sha1.c - Functions to compute SHA1 message digest of files or
   2    memory blocks according to the NIST specification FIPS-180-1.
   3
   4    Copyright (C) 2000-2001, 2003-2006, 2008-2011 Free Software Foundation, Inc.
   5
   6    This program is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by the
   8    Free Software Foundation; either version 3, or (at your option) any
   9    later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software Foundation,
  18    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  19
  20 /* Written by Scott G. Miller
  21    Credits:
  22       Robert Klep <robert@ilse.nl>  -- Expansion function fix
  23
  24    Modified by Eric Biggers for wimlib:  Conditionally compile in the use of
  25    OpenSSL or Intel's assembly code for SHA1 block updates
  26 */
  27
  28 #include "util.h"
  29 #include "wimlib.h"
  30 #include "sha1.h"
  31 #include "endianness.h"
  32 #include <string.h>
  33
  34 #define SWAP(n) to_be32(n)
  35
  36 #define BLOCKSIZE 32768
  37 #if BLOCKSIZE % 64 != 0
  38 #error "invalid BLOCKSIZE"
  39 #endif
  40
  41 const u8 empty_file_sha1sum[SHA1_HASH_SIZE] = {
  42         0xda, 0x39, 0xa3, 0xee, 0x5e, 0x6b, 0x4b, 0x0d, 0x32, 0x55,
  43         0xbf, 0xef, 0x95, 0x60, 0x18, 0x90, 0xaf, 0xd8, 0x07, 0x09,
  44 };
  45
  46
  47 #ifdef WITH_LIBCRYPTO
  48
  49 static inline void sha1_init_ctx(SHA_CTX *ctx)
  50 {
  51         SHA1_Init(ctx);
  52 }
  53
  54 static inline void sha1_process_block(const void *buffer, size_t len,
  55                                       SHA_CTX *ctx)
  56 {
  57         SHA1_Update(ctx, buffer, len);
  58 }
  59
  60 static inline void sha1_process_bytes(const void *buffer, size_t len,
  61                                       SHA_CTX *ctx)
  62 {
  63         SHA1_Update(ctx, buffer, len);
  64 }
  65
  66
  67 static inline void *sha1_finish_ctx(SHA_CTX *ctx, void *resbuf)
  68 {
  69         SHA1_Final(resbuf, ctx);
  70 }
  71 #else /* WITH_LIBCRYPTO */
  72
  73 /* Structure to save state of computation between the single steps.  */
  74 struct sha1_ctx {
  75         uint32_t A;
  76         uint32_t B;
  77         uint32_t C;
  78         uint32_t D;
  79         uint32_t E;
  80
  81         uint32_t total[2];
  82         uint32_t buflen;
  83         uint32_t buffer[32];
  84 };
  85
  86 typedef struct sha1_ctx SHA_CTX;
  87
  88 #ifdef ENABLE_SSSE3_SHA1
  89 extern void sha1_update_intel(int *hash, const char* input, size_t num_blocks);
  90
  91 static inline void sha1_process_block(const void *buffer, size_t len,
  92                                       SHA_CTX *ctx)
  93 {
  94         sha1_update_intel((int*)ctx, buffer, len / 64);
  95         ctx->total[0] += len;
  96         if (ctx->total[0] < len)
  97                 ++ctx->total[1];
  98 }
  99
 100 #include <stdlib.h>
 101 void ssse3_not_found()
 102 {
 103         fprintf(stderr,
 104 "Cannot calculate SHA1 message digest: CPU does not support SSSE3\n"
 105 "instructions!  Recompile wimlib without the --enable-ssse3-sha1 flag\n"
 106 "to use wimlib on this CPU.\n");
 107         abort();
 108 }
 109 #else /* ENABLE_SSSE3_SHA1 */
 110
 111 static void sha1_process_block(const void *buffer, size_t len,
 112                                SHA_CTX *ctx);
 113
 114 #endif /* ENABLE_SSSE3_SHA1 */
 115
 116
 117 /* This array contains the bytes used to pad the buffer to the next
 118    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
 119 static const u8 fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */  };
 120
 121 /* Initialize structure containing state of computation. */
 122 static void sha1_init_ctx(SHA_CTX *ctx);
 123
 124 /* Starting with the result of former calls of this function (or the
 125    initialization function update the context for the next LEN bytes
 126    starting at BUFFER.
 127    It is NOT required that LEN is a multiple of 64.  */
 128 static void sha1_process_bytes(const void *buffer, size_t len,
 129                                SHA_CTX *ctx);
 130
 131 /* Process the remaining bytes in the buffer and put result from CTX
 132    in first 20 bytes following RESBUF.  The result is always in little
 133    endian byte order, so that a byte-wise output yields to the wanted
 134    ASCII representation of the message digest.  */
 135 static void *sha1_finish_ctx(SHA_CTX *ctx, void *resbuf);
 136
 137 /* Put result from CTX in first 20 bytes following RESBUF.  The result is
 138    always in little endian byte order, so that a byte-wise output yields
 139    to the wanted ASCII representation of the message digest.  */
 140 static void *sha1_read_ctx(const SHA_CTX *ctx, void *resbuf);
 141
 142 #endif /* WITH_LIBCRYPTO */
 143
 144
 145
 146 /* Compute SHA1 message digest for bytes read from STREAM.  The resulting
 147  * message digest number will be written into the 20 bytes beginning at
 148  * RESBLOCK.  */
 149 int sha1_stream(FILE * stream, void *resblock)
 150 {
 151         SHA_CTX ctx;
 152
 153         size_t sum;
 154
 155         char *buffer = MALLOC(BLOCKSIZE + 72);
 156         if (!buffer) {
 157                 ERROR("Out of memory!\n");
 158                 return WIMLIB_ERR_NOMEM;
 159         }
 160
 161         /* Initialize the computation context.  */
 162         sha1_init_ctx(&ctx);
 163
 164         /* Iterate over full file contents.  */
 165         while (1) {
 166                 /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
 167                    computation function processes the whole buffer so that with the
 168                    next round of the loop another block can be read.  */
 169                 size_t n;
 170                 sum = 0;
 171
 172                 /* Read block.  Take care for partial reads.  */
 173                 while (1) {
 174                         n = fread(buffer + sum, 1, BLOCKSIZE - sum, stream);
 175
 176                         sum += n;
 177
 178                         if (sum == BLOCKSIZE)
 179                                 break;
 180
 181                         if (n == 0) {
 182                                 /* Check for the error flag IFF N == 0, so that
 183                                  * we don't exit the loop after a partial read
 184                                  * due to e.g., EAGAIN or EWOULDBLOCK.  */
 185                                 if (ferror(stream)) {
 186                                         FREE(buffer);
 187                                         ERROR("Read error while calculating "
 188                                                 "SHA1 message digest: %m\n");
 189                                         return WIMLIB_ERR_READ;
 190                                 }
 191                                 goto process_partial_block;
 192                         }
 193
 194                         /* We've read at least one byte, so ignore errors.  But always
 195                            check for EOF, since feof may be true even though N > 0.
 196                            Otherwise, we could end up calling fread after EOF.  */
 197                         if (feof(stream))
 198                                 goto process_partial_block;
 199                 }
 200
 201                 /* Process buffer with BLOCKSIZE bytes.  Note that
 202                    BLOCKSIZE % 64 == 0
 203                  */
 204                 sha1_process_block(buffer, BLOCKSIZE, &ctx);
 205         }
 206
 207  process_partial_block:;
 208
 209         /* Process any remaining bytes.  */
 210         if (sum > 0)
 211                 sha1_process_bytes(buffer, sum, &ctx);
 212
 213         /* Construct result in desired memory.  */
 214         sha1_finish_ctx(&ctx, resblock);
 215         FREE(buffer);
 216         return 0;
 217 }
 218
 219 #ifndef WITH_LIBCRYPTO
 220 /* Compute SHA1 message digest for LEN bytes beginning at BUFFER.  The
 221    result is always in little endian byte order, so that a byte-wise
 222    output yields to the wanted ASCII representation of the message
 223    digest.  */
 224 void *sha1_buffer(const char *buffer, size_t len, void *resblock)
 225 {
 226         SHA_CTX ctx;
 227
 228         /* Initialize the computation context.  */
 229         sha1_init_ctx(&ctx);
 230
 231         /* Process whole buffer but last len % 64 bytes.  */
 232         sha1_process_bytes(buffer, len, &ctx);
 233
 234         /* Put result in desired memory area.  */
 235         return sha1_finish_ctx(&ctx, resblock);
 236 }
 237
 238 /* Take a pointer to a 160 bit block of data (five 32 bit ints) and
 239    initialize it to the start constants of the SHA1 algorithm.  This
 240    must be called before using hash in the call to sha1_hash.  */
 241 static void sha1_init_ctx(SHA_CTX *ctx)
 242 {
 243         ctx->A = 0x67452301;
 244         ctx->B = 0xefcdab89;
 245         ctx->C = 0x98badcfe;
 246         ctx->D = 0x10325476;
 247         ctx->E = 0xc3d2e1f0;
 248
 249         ctx->total[0] = ctx->total[1] = 0;
 250         ctx->buflen = 0;
 251 }
 252
 253 /* Copy the 4 byte value from v into the memory location pointed to by *cp,
 254    If your architecture allows unaligned access this is equivalent to
 255    * (uint32_t *) cp = v  */
 256 static inline void set_uint32(char *cp, uint32_t v)
 257 {
 258         memcpy(cp, &v, sizeof v);
 259 }
 260
 261 /* Put result from CTX in first 20 bytes following RESBUF.  The result
 262    must be in little endian byte order.  */
 263 static void *sha1_read_ctx(const SHA_CTX *ctx, void *resbuf)
 264 {
 265         char *r = resbuf;
 266         set_uint32(r + 0 * sizeof ctx->A, SWAP(ctx->A));
 267         set_uint32(r + 1 * sizeof ctx->B, SWAP(ctx->B));
 268         set_uint32(r + 2 * sizeof ctx->C, SWAP(ctx->C));
 269         set_uint32(r + 3 * sizeof ctx->D, SWAP(ctx->D));
 270         set_uint32(r + 4 * sizeof ctx->E, SWAP(ctx->E));
 271
 272         return resbuf;
 273 }
 274
 275 /* Process the remaining bytes in the internal buffer and the usual
 276    prolog according to the standard and write the result to RESBUF.  */
 277 static void *sha1_finish_ctx(SHA_CTX *ctx, void *resbuf)
 278 {
 279         /* Take yet unprocessed bytes into account.  */
 280         uint32_t bytes = ctx->buflen;
 281         size_t size = (bytes < 56) ? 64 / 4 : 64 * 2 / 4;
 282
 283         /* Now count remaining bytes.  */
 284         ctx->total[0] += bytes;
 285         if (ctx->total[0] < bytes)
 286                 ++ctx->total[1];
 287
 288         /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 289         ctx->buffer[size - 2] =
 290             SWAP((ctx->total[1] << 3) | (ctx->total[0] >> 29));
 291         ctx->buffer[size - 1] = SWAP(ctx->total[0] << 3);
 292
 293         memcpy(&((char *)ctx->buffer)[bytes], fillbuf, (size - 2) * 4 - bytes);
 294
 295         /* Process last bytes.  */
 296         sha1_process_block(ctx->buffer, size * 4, ctx);
 297
 298         return sha1_read_ctx(ctx, resbuf);
 299 }
 300
 301
 302 static void sha1_process_bytes(const void *buffer, size_t len, SHA_CTX *ctx)
 303 {
 304         /* When we already have some bits in our internal buffer concatenate
 305            both inputs first.  */
 306         if (ctx->buflen != 0) {
 307                 size_t left_over = ctx->buflen;
 308                 size_t add = 128 - left_over > len ? len : 128 - left_over;
 309
 310                 memcpy(&((char *)ctx->buffer)[left_over], buffer, add);
 311                 ctx->buflen += add;
 312
 313                 if (ctx->buflen > 64) {
 314                         sha1_process_block(ctx->buffer, ctx->buflen & ~63, ctx);
 315
 316                         ctx->buflen &= 63;
 317                         /* The regions in the following copy operation cannot overlap.  */
 318                         memcpy(ctx->buffer,
 319                                &((char *)ctx->buffer)[(left_over + add) & ~63],
 320                                ctx->buflen);
 321                 }
 322
 323                 buffer = (const char *)buffer + add;
 324                 len -= add;
 325         }
 326
 327         /* Process available complete blocks.  */
 328         if (len >= 64) {
 329 #if !_STRING_ARCH_unaligned
 330 #define alignof(type) offsetof (struct { char c; type x; }, x)
 331 #define UNALIGNED_P(p) (((size_t) p) % alignof (uint32_t) != 0)
 332                 if (UNALIGNED_P(buffer))
 333                         while (len > 64) {
 334                                 sha1_process_block(memcpy
 335                                                    (ctx->buffer, buffer, 64),
 336                                                    64, ctx);
 337                                 buffer = (const char *)buffer + 64;
 338                                 len -= 64;
 339                 } else
 340 #endif
 341                 {
 342                         sha1_process_block(buffer, len & ~63, ctx);
 343                         buffer = (const char *)buffer + (len & ~63);
 344                         len &= 63;
 345                 }
 346         }
 347
 348         /* Move remaining bytes in internal buffer.  */
 349         if (len > 0) {
 350                 size_t left_over = ctx->buflen;
 351
 352                 memcpy(&((char *)ctx->buffer)[left_over], buffer, len);
 353                 left_over += len;
 354                 if (left_over >= 64) {
 355                         sha1_process_block(ctx->buffer, 64, ctx);
 356                         left_over -= 64;
 357                         memcpy(ctx->buffer, &ctx->buffer[16], left_over);
 358                 }
 359                 ctx->buflen = left_over;
 360         }
 361 }
 362
 363 /* --- Code below is the primary difference between md5.c and sha1.c --- */
 364
 365 /* SHA1 round constants */
 366 #define K1 0x5a827999
 367 #define K2 0x6ed9eba1
 368 #define K3 0x8f1bbcdc
 369 #define K4 0xca62c1d6
 370
 371 /* Round functions.  Note that F2 is the same as F4.  */
 372 #define F1(B,C,D) ( D ^ ( B & ( C ^ D ) ) )
 373 #define F2(B,C,D) (B ^ C ^ D)
 374 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
 375 #define F4(B,C,D) (B ^ C ^ D)
 376
 377 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 378    It is assumed that LEN % 64 == 0.
 379    Most of this code comes from GnuPG's cipher/sha1.c.  */
 380
 381 #ifndef ENABLE_SSSE3_SHA1
 382 static void sha1_process_block(const void *buffer, size_t len, SHA_CTX *ctx)
 383 {
 384         const uint32_t *words = buffer;
 385         size_t nwords = len / sizeof(uint32_t);
 386         const uint32_t *endp = words + nwords;
 387         uint32_t x[16];
 388         uint32_t a = ctx->A;
 389         uint32_t b = ctx->B;
 390         uint32_t c = ctx->C;
 391         uint32_t d = ctx->D;
 392         uint32_t e = ctx->E;
 393
 394         /* First increment the byte count.  RFC 1321 specifies the possible
 395            length of the file up to 2^64 bits.  Here we only compute the
 396            number of bytes.  Do a double word increment.  */
 397         ctx->total[0] += len;
 398         if (ctx->total[0] < len)
 399                 ++ctx->total[1];
 400
 401 #define rol(x, n) (((x) << (n)) | ((uint32_t) (x) >> (32 - (n))))
 402
 403 #define M(I) ( tm =   x[I&0x0f] ^ x[(I-14)&0x0f] \
 404                     ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \
 405                , (x[I&0x0f] = rol(tm, 1)) )
 406
 407 #define R(A,B,C,D,E,F,K,M)  do { E += rol( A, 5 )     \
 408                                       + F( B, C, D )  \
 409                                       + K             \
 410                                       + M;            \
 411                                  B = rol( B, 30 );    \
 412                                } while(0)
 413
 414         while (words < endp) {
 415                 uint32_t tm;
 416                 int t;
 417                 for (t = 0; t < 16; t++) {
 418                         x[t] = SWAP(*words);
 419                         words++;
 420                 }
 421
 422                 R(a, b, c, d, e, F1, K1, x[0]);
 423                 R(e, a, b, c, d, F1, K1, x[1]);
 424                 R(d, e, a, b, c, F1, K1, x[2]);
 425                 R(c, d, e, a, b, F1, K1, x[3]);
 426                 R(b, c, d, e, a, F1, K1, x[4]);
 427                 R(a, b, c, d, e, F1, K1, x[5]);
 428                 R(e, a, b, c, d, F1, K1, x[6]);
 429                 R(d, e, a, b, c, F1, K1, x[7]);
 430                 R(c, d, e, a, b, F1, K1, x[8]);
 431                 R(b, c, d, e, a, F1, K1, x[9]);
 432                 R(a, b, c, d, e, F1, K1, x[10]);
 433                 R(e, a, b, c, d, F1, K1, x[11]);
 434                 R(d, e, a, b, c, F1, K1, x[12]);
 435                 R(c, d, e, a, b, F1, K1, x[13]);
 436                 R(b, c, d, e, a, F1, K1, x[14]);
 437                 R(a, b, c, d, e, F1, K1, x[15]);
 438                 R(e, a, b, c, d, F1, K1, M(16));
 439                 R(d, e, a, b, c, F1, K1, M(17));
 440                 R(c, d, e, a, b, F1, K1, M(18));
 441                 R(b, c, d, e, a, F1, K1, M(19));
 442                 R(a, b, c, d, e, F2, K2, M(20));
 443                 R(e, a, b, c, d, F2, K2, M(21));
 444                 R(d, e, a, b, c, F2, K2, M(22));
 445                 R(c, d, e, a, b, F2, K2, M(23));
 446                 R(b, c, d, e, a, F2, K2, M(24));
 447                 R(a, b, c, d, e, F2, K2, M(25));
 448                 R(e, a, b, c, d, F2, K2, M(26));
 449                 R(d, e, a, b, c, F2, K2, M(27));
 450                 R(c, d, e, a, b, F2, K2, M(28));
 451                 R(b, c, d, e, a, F2, K2, M(29));
 452                 R(a, b, c, d, e, F2, K2, M(30));
 453                 R(e, a, b, c, d, F2, K2, M(31));
 454                 R(d, e, a, b, c, F2, K2, M(32));
 455                 R(c, d, e, a, b, F2, K2, M(33));
 456                 R(b, c, d, e, a, F2, K2, M(34));
 457                 R(a, b, c, d, e, F2, K2, M(35));
 458                 R(e, a, b, c, d, F2, K2, M(36));
 459                 R(d, e, a, b, c, F2, K2, M(37));
 460                 R(c, d, e, a, b, F2, K2, M(38));
 461                 R(b, c, d, e, a, F2, K2, M(39));
 462                 R(a, b, c, d, e, F3, K3, M(40));
 463                 R(e, a, b, c, d, F3, K3, M(41));
 464                 R(d, e, a, b, c, F3, K3, M(42));
 465                 R(c, d, e, a, b, F3, K3, M(43));
 466                 R(b, c, d, e, a, F3, K3, M(44));
 467                 R(a, b, c, d, e, F3, K3, M(45));
 468                 R(e, a, b, c, d, F3, K3, M(46));
 469                 R(d, e, a, b, c, F3, K3, M(47));
 470                 R(c, d, e, a, b, F3, K3, M(48));
 471                 R(b, c, d, e, a, F3, K3, M(49));
 472                 R(a, b, c, d, e, F3, K3, M(50));
 473                 R(e, a, b, c, d, F3, K3, M(51));
 474                 R(d, e, a, b, c, F3, K3, M(52));
 475                 R(c, d, e, a, b, F3, K3, M(53));
 476                 R(b, c, d, e, a, F3, K3, M(54));
 477                 R(a, b, c, d, e, F3, K3, M(55));
 478                 R(e, a, b, c, d, F3, K3, M(56));
 479                 R(d, e, a, b, c, F3, K3, M(57));
 480                 R(c, d, e, a, b, F3, K3, M(58));
 481                 R(b, c, d, e, a, F3, K3, M(59));
 482                 R(a, b, c, d, e, F4, K4, M(60));
 483                 R(e, a, b, c, d, F4, K4, M(61));
 484                 R(d, e, a, b, c, F4, K4, M(62));
 485                 R(c, d, e, a, b, F4, K4, M(63));
 486                 R(b, c, d, e, a, F4, K4, M(64));
 487                 R(a, b, c, d, e, F4, K4, M(65));
 488                 R(e, a, b, c, d, F4, K4, M(66));
 489                 R(d, e, a, b, c, F4, K4, M(67));
 490                 R(c, d, e, a, b, F4, K4, M(68));
 491                 R(b, c, d, e, a, F4, K4, M(69));
 492                 R(a, b, c, d, e, F4, K4, M(70));
 493                 R(e, a, b, c, d, F4, K4, M(71));
 494                 R(d, e, a, b, c, F4, K4, M(72));
 495                 R(c, d, e, a, b, F4, K4, M(73));
 496                 R(b, c, d, e, a, F4, K4, M(74));
 497                 R(a, b, c, d, e, F4, K4, M(75));
 498                 R(e, a, b, c, d, F4, K4, M(76));
 499                 R(d, e, a, b, c, F4, K4, M(77));
 500                 R(c, d, e, a, b, F4, K4, M(78));
 501                 R(b, c, d, e, a, F4, K4, M(79));
 502
 503                 a = ctx->A += a;
 504                 b = ctx->B += b;
 505                 c = ctx->C += c;
 506                 d = ctx->D += d;
 507                 e = ctx->E += e;
 508         }
 509 }
 510 #endif /* ENABLE_SSSE3_SHA1 */
 511
 512 #endif /* WITH_LIBCRYPTO */