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-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
  25 #include <config.h>
  26
  27 #include "sha1.h"
  28
  29 #include <stddef.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 inline 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 alignof(type) offsetof (struct { char c; type x; }, x)
 245 # define UNALIGNED_P(p) (((size_t) p) % alignof (uint32_t) != 0)
 246       if (UNALIGNED_P (buffer))
 247         while (len > 64)
 248           {
 249             sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
 250             buffer = (const char *) buffer + 64;
 251             len -= 64;
 252           }
 253       else
 254 #endif
 255         {
 256           sha1_process_block (buffer, len & ~63, ctx);
 257           buffer = (const char *) buffer + (len & ~63);
 258           len &= 63;
 259         }
 260     }
 261
 262   /* Move remaining bytes in internal buffer.  */
 263   if (len > 0)
 264     {
 265       size_t left_over = ctx->buflen;
 266
 267       memcpy (&((char *) ctx->buffer)[left_over], buffer, len);
 268       left_over += len;
 269       if (left_over >= 64)
 270         {
 271           sha1_process_block (ctx->buffer, 64, ctx);
 272           left_over -= 64;
 273           memcpy (ctx->buffer, &ctx->buffer[16], left_over);
 274         }
 275       ctx->buflen = left_over;
 276     }
 277 }
 278
 279 /* --- Code below is the primary difference between md5.c and sha1.c --- */
 280
 281 /* SHA1 round constants */
 282 #define K1 0x5a827999
 283 #define K2 0x6ed9eba1
 284 #define K3 0x8f1bbcdc
 285 #define K4 0xca62c1d6
 286
 287 /* Round functions.  Note that F2 is the same as F4.  */
 288 #define F1(B,C,D) ( D ^ ( B & ( C ^ D ) ) )
 289 #define F2(B,C,D) (B ^ C ^ D)
 290 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
 291 #define F4(B,C,D) (B ^ C ^ D)
 292
 293 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 294    It is assumed that LEN % 64 == 0.
 295    Most of this code comes from GnuPG's cipher/sha1.c.  */
 296
 297 void
 298 sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
 299 {
 300   const uint32_t *words = buffer;
 301   size_t nwords = len / sizeof (uint32_t);
 302   const uint32_t *endp = words + nwords;
 303   uint32_t x[16];
 304   uint32_t a = ctx->A;
 305   uint32_t b = ctx->B;
 306   uint32_t c = ctx->C;
 307   uint32_t d = ctx->D;
 308   uint32_t e = ctx->E;
 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] += len;
 314   if (ctx->total[0] < len)
 315     ++ctx->total[1];
 316
 317 #define rol(x, n) (((x) << (n)) | ((uint32_t) (x) >> (32 - (n))))
 318
 319 #define M(I) ( tm =   x[I&0x0f] ^ x[(I-14)&0x0f] \
 320                     ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \
 321                , (x[I&0x0f] = rol(tm, 1)) )
 322
 323 #define R(A,B,C,D,E,F,K,M)  do { E += rol( A, 5 )     \
 324                                       + F( B, C, D )  \
 325                                       + K             \
 326                                       + M;            \
 327                                  B = rol( B, 30 );    \
 328                                } while(0)
 329
 330   while (words < endp)
 331     {
 332       uint32_t tm;
 333       int t;
 334       for (t = 0; t < 16; t++)
 335         {
 336           x[t] = SWAP (*words);
 337           words++;
 338         }
 339
 340       R( a, b, c, d, e, F1, K1, x[ 0] );
 341       R( e, a, b, c, d, F1, K1, x[ 1] );
 342       R( d, e, a, b, c, F1, K1, x[ 2] );
 343       R( c, d, e, a, b, F1, K1, x[ 3] );
 344       R( b, c, d, e, a, F1, K1, x[ 4] );
 345       R( a, b, c, d, e, F1, K1, x[ 5] );
 346       R( e, a, b, c, d, F1, K1, x[ 6] );
 347       R( d, e, a, b, c, F1, K1, x[ 7] );
 348       R( c, d, e, a, b, F1, K1, x[ 8] );
 349       R( b, c, d, e, a, F1, K1, x[ 9] );
 350       R( a, b, c, d, e, F1, K1, x[10] );
 351       R( e, a, b, c, d, F1, K1, x[11] );
 352       R( d, e, a, b, c, F1, K1, x[12] );
 353       R( c, d, e, a, b, F1, K1, x[13] );
 354       R( b, c, d, e, a, F1, K1, x[14] );
 355       R( a, b, c, d, e, F1, K1, x[15] );
 356       R( e, a, b, c, d, F1, K1, M(16) );
 357       R( d, e, a, b, c, F1, K1, M(17) );
 358       R( c, d, e, a, b, F1, K1, M(18) );
 359       R( b, c, d, e, a, F1, K1, M(19) );
 360       R( a, b, c, d, e, F2, K2, M(20) );
 361       R( e, a, b, c, d, F2, K2, M(21) );
 362       R( d, e, a, b, c, F2, K2, M(22) );
 363       R( c, d, e, a, b, F2, K2, M(23) );
 364       R( b, c, d, e, a, F2, K2, M(24) );
 365       R( a, b, c, d, e, F2, K2, M(25) );
 366       R( e, a, b, c, d, F2, K2, M(26) );
 367       R( d, e, a, b, c, F2, K2, M(27) );
 368       R( c, d, e, a, b, F2, K2, M(28) );
 369       R( b, c, d, e, a, F2, K2, M(29) );
 370       R( a, b, c, d, e, F2, K2, M(30) );
 371       R( e, a, b, c, d, F2, K2, M(31) );
 372       R( d, e, a, b, c, F2, K2, M(32) );
 373       R( c, d, e, a, b, F2, K2, M(33) );
 374       R( b, c, d, e, a, F2, K2, M(34) );
 375       R( a, b, c, d, e, F2, K2, M(35) );
 376       R( e, a, b, c, d, F2, K2, M(36) );
 377       R( d, e, a, b, c, F2, K2, M(37) );
 378       R( c, d, e, a, b, F2, K2, M(38) );
 379       R( b, c, d, e, a, F2, K2, M(39) );
 380       R( a, b, c, d, e, F3, K3, M(40) );
 381       R( e, a, b, c, d, F3, K3, M(41) );
 382       R( d, e, a, b, c, F3, K3, M(42) );
 383       R( c, d, e, a, b, F3, K3, M(43) );
 384       R( b, c, d, e, a, F3, K3, M(44) );
 385       R( a, b, c, d, e, F3, K3, M(45) );
 386       R( e, a, b, c, d, F3, K3, M(46) );
 387       R( d, e, a, b, c, F3, K3, M(47) );
 388       R( c, d, e, a, b, F3, K3, M(48) );
 389       R( b, c, d, e, a, F3, K3, M(49) );
 390       R( a, b, c, d, e, F3, K3, M(50) );
 391       R( e, a, b, c, d, F3, K3, M(51) );
 392       R( d, e, a, b, c, F3, K3, M(52) );
 393       R( c, d, e, a, b, F3, K3, M(53) );
 394       R( b, c, d, e, a, F3, K3, M(54) );
 395       R( a, b, c, d, e, F3, K3, M(55) );
 396       R( e, a, b, c, d, F3, K3, M(56) );
 397       R( d, e, a, b, c, F3, K3, M(57) );
 398       R( c, d, e, a, b, F3, K3, M(58) );
 399       R( b, c, d, e, a, F3, K3, M(59) );
 400       R( a, b, c, d, e, F4, K4, M(60) );
 401       R( e, a, b, c, d, F4, K4, M(61) );
 402       R( d, e, a, b, c, F4, K4, M(62) );
 403       R( c, d, e, a, b, F4, K4, M(63) );
 404       R( b, c, d, e, a, F4, K4, M(64) );
 405       R( a, b, c, d, e, F4, K4, M(65) );
 406       R( e, a, b, c, d, F4, K4, M(66) );
 407       R( d, e, a, b, c, F4, K4, M(67) );
 408       R( c, d, e, a, b, F4, K4, M(68) );
 409       R( b, c, d, e, a, F4, K4, M(69) );
 410       R( a, b, c, d, e, F4, K4, M(70) );
 411       R( e, a, b, c, d, F4, K4, M(71) );
 412       R( d, e, a, b, c, F4, K4, M(72) );
 413       R( c, d, e, a, b, F4, K4, M(73) );
 414       R( b, c, d, e, a, F4, K4, M(74) );
 415       R( a, b, c, d, e, F4, K4, M(75) );
 416       R( e, a, b, c, d, F4, K4, M(76) );
 417       R( d, e, a, b, c, F4, K4, M(77) );
 418       R( c, d, e, a, b, F4, K4, M(78) );
 419       R( b, c, d, e, a, F4, K4, M(79) );
 420
 421       a = ctx->A += a;
 422       b = ctx->B += b;
 423       c = ctx->C += c;
 424       d = ctx->D += d;
 425       e = ctx->E += e;
 426     }
 427 }