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