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