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, 2004, 2005, 2006, 2008 Free Software
   5    Foundation, Inc.
   6
   7    This program is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by the
   9    Free Software Foundation; either version 2, or (at your option) any
  10    later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software Foundation,
  19    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  20
  21 /* Written by Scott G. Miller
  22    Credits:
  23       Robert Klep <robert@ilse.nl>  -- Expansion function fix
  24 */
  25
  26 #include <config.h>
  27
  28 #include "sha1.h"
  29
  30 #include <stddef.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 4096
  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   char buffer[BLOCKSIZE + 72];
 128   size_t sum;
 129
 130   /* Initialize the computation context.  */
 131   sha1_init_ctx (&ctx);
 132
 133   /* Iterate over full file contents.  */
 134   while (1)
 135     {
 136       /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
 137          computation function processes the whole buffer so that with the
 138          next round of the loop another block can be read.  */
 139       size_t n;
 140       sum = 0;
 141
 142       /* Read block.  Take care for partial reads.  */
 143       while (1)
 144         {
 145           n = fread (buffer + sum, 1, BLOCKSIZE - sum, stream);
 146
 147           sum += n;
 148
 149           if (sum == BLOCKSIZE)
 150             break;
 151
 152           if (n == 0)
 153             {
 154               /* Check for the error flag IFF N == 0, so that we don't
 155                  exit the loop after a partial read due to e.g., EAGAIN
 156                  or EWOULDBLOCK.  */
 157               if (ferror (stream))
 158                 return 1;
 159               goto process_partial_block;
 160             }
 161
 162           /* We've read at least one byte, so ignore errors.  But always
 163              check for EOF, since feof may be true even though N > 0.
 164              Otherwise, we could end up calling fread after EOF.  */
 165           if (feof (stream))
 166             goto process_partial_block;
 167         }
 168
 169       /* Process buffer with BLOCKSIZE bytes.  Note that
 170                         BLOCKSIZE % 64 == 0
 171        */
 172       sha1_process_block (buffer, BLOCKSIZE, &ctx);
 173     }
 174
 175  process_partial_block:;
 176
 177   /* Process any remaining bytes.  */
 178   if (sum > 0)
 179     sha1_process_bytes (buffer, sum, &ctx);
 180
 181   /* Construct result in desired memory.  */
 182   sha1_finish_ctx (&ctx, resblock);
 183   return 0;
 184 }
 185
 186 /* Compute SHA1 message digest for LEN bytes beginning at BUFFER.  The
 187    result is always in little endian byte order, so that a byte-wise
 188    output yields to the wanted ASCII representation of the message
 189    digest.  */
 190 void *
 191 sha1_buffer (const char *buffer, size_t len, void *resblock)
 192 {
 193   struct sha1_ctx ctx;
 194
 195   /* Initialize the computation context.  */
 196   sha1_init_ctx (&ctx);
 197
 198   /* Process whole buffer but last len % 64 bytes.  */
 199   sha1_process_bytes (buffer, len, &ctx);
 200
 201   /* Put result in desired memory area.  */
 202   return sha1_finish_ctx (&ctx, resblock);
 203 }
 204
 205 void
 206 sha1_process_bytes (const void *buffer, size_t len, struct sha1_ctx *ctx)
 207 {
 208   /* When we already have some bits in our internal buffer concatenate
 209      both inputs first.  */
 210   if (ctx->buflen != 0)
 211     {
 212       size_t left_over = ctx->buflen;
 213       size_t add = 128 - left_over > len ? len : 128 - left_over;
 214
 215       memcpy (&((char *) ctx->buffer)[left_over], buffer, add);
 216       ctx->buflen += add;
 217
 218       if (ctx->buflen > 64)
 219         {
 220           ctx->buflen &= 63;
 221           sha1_process_block (ctx->buffer, ctx->buflen, ctx);
 222
 223           /* The regions in the following copy operation cannot overlap.  */
 224           memcpy (ctx->buffer,
 225                   &((char *) ctx->buffer)[(left_over + add) & ~63],
 226                   ctx->buflen);
 227         }
 228
 229       buffer = (const char *) buffer + add;
 230       len -= add;
 231     }
 232
 233   /* Process available complete blocks.  */
 234   if (len >= 64)
 235     {
 236 #if !_STRING_ARCH_unaligned
 237 # define alignof(type) offsetof (struct { char c; type x; }, x)
 238 # define UNALIGNED_P(p) (((size_t) p) % alignof (uint32_t) != 0)
 239       if (UNALIGNED_P (buffer))
 240         while (len > 64)
 241           {
 242             sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
 243             buffer = (const char *) buffer + 64;
 244             len -= 64;
 245           }
 246       else
 247 #endif
 248         {
 249           sha1_process_block (buffer, len & ~63, ctx);
 250           buffer = (const char *) buffer + (len & ~63);
 251           len &= 63;
 252         }
 253     }
 254
 255   /* Move remaining bytes in internal buffer.  */
 256   if (len > 0)
 257     {
 258       size_t left_over = ctx->buflen;
 259
 260       memcpy (&((char *) ctx->buffer)[left_over], buffer, len);
 261       left_over += len;
 262       if (left_over >= 64)
 263         {
 264           sha1_process_block (ctx->buffer, 64, ctx);
 265           left_over -= 64;
 266           memcpy (ctx->buffer, &ctx->buffer[16], left_over);
 267         }
 268       ctx->buflen = left_over;
 269     }
 270 }
 271
 272 /* --- Code below is the primary difference between md5.c and sha1.c --- */
 273
 274 /* SHA1 round constants */
 275 #define K1 0x5a827999
 276 #define K2 0x6ed9eba1
 277 #define K3 0x8f1bbcdc
 278 #define K4 0xca62c1d6
 279
 280 /* Round functions.  Note that F2 is the same as F4.  */
 281 #define F1(B,C,D) ( D ^ ( B & ( C ^ D ) ) )
 282 #define F2(B,C,D) (B ^ C ^ D)
 283 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
 284 #define F4(B,C,D) (B ^ C ^ D)
 285
 286 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 287    It is assumed that LEN % 64 == 0.
 288    Most of this code comes from GnuPG's cipher/sha1.c.  */
 289
 290 void
 291 sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
 292 {
 293   const uint32_t *words = buffer;
 294   size_t nwords = len / sizeof (uint32_t);
 295   const uint32_t *endp = words + nwords;
 296   uint32_t x[16];
 297   uint32_t a = ctx->A;
 298   uint32_t b = ctx->B;
 299   uint32_t c = ctx->C;
 300   uint32_t d = ctx->D;
 301   uint32_t e = ctx->E;
 302
 303   /* First increment the byte count.  RFC 1321 specifies the possible
 304      length of the file up to 2^64 bits.  Here we only compute the
 305      number of bytes.  Do a double word increment.  */
 306   ctx->total[0] += len;
 307   if (ctx->total[0] < len)
 308     ++ctx->total[1];
 309
 310 #define rol(x, n) (((x) << (n)) | ((uint32_t) (x) >> (32 - (n))))
 311
 312 #define M(I) ( tm =   x[I&0x0f] ^ x[(I-14)&0x0f] \
 313                     ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \
 314                , (x[I&0x0f] = rol(tm, 1)) )
 315
 316 #define R(A,B,C,D,E,F,K,M)  do { E += rol( A, 5 )     \
 317                                       + F( B, C, D )  \
 318                                       + K             \
 319                                       + M;            \
 320                                  B = rol( B, 30 );    \
 321                                } while(0)
 322
 323   while (words < endp)
 324     {
 325       uint32_t tm;
 326       int t;
 327       for (t = 0; t < 16; t++)
 328         {
 329           x[t] = SWAP (*words);
 330           words++;
 331         }
 332
 333       R( a, b, c, d, e, F1, K1, x[ 0] );
 334       R( e, a, b, c, d, F1, K1, x[ 1] );
 335       R( d, e, a, b, c, F1, K1, x[ 2] );
 336       R( c, d, e, a, b, F1, K1, x[ 3] );
 337       R( b, c, d, e, a, F1, K1, x[ 4] );
 338       R( a, b, c, d, e, F1, K1, x[ 5] );
 339       R( e, a, b, c, d, F1, K1, x[ 6] );
 340       R( d, e, a, b, c, F1, K1, x[ 7] );
 341       R( c, d, e, a, b, F1, K1, x[ 8] );
 342       R( b, c, d, e, a, F1, K1, x[ 9] );
 343       R( a, b, c, d, e, F1, K1, x[10] );
 344       R( e, a, b, c, d, F1, K1, x[11] );
 345       R( d, e, a, b, c, F1, K1, x[12] );
 346       R( c, d, e, a, b, F1, K1, x[13] );
 347       R( b, c, d, e, a, F1, K1, x[14] );
 348       R( a, b, c, d, e, F1, K1, x[15] );
 349       R( e, a, b, c, d, F1, K1, M(16) );
 350       R( d, e, a, b, c, F1, K1, M(17) );
 351       R( c, d, e, a, b, F1, K1, M(18) );
 352       R( b, c, d, e, a, F1, K1, M(19) );
 353       R( a, b, c, d, e, F2, K2, M(20) );
 354       R( e, a, b, c, d, F2, K2, M(21) );
 355       R( d, e, a, b, c, F2, K2, M(22) );
 356       R( c, d, e, a, b, F2, K2, M(23) );
 357       R( b, c, d, e, a, F2, K2, M(24) );
 358       R( a, b, c, d, e, F2, K2, M(25) );
 359       R( e, a, b, c, d, F2, K2, M(26) );
 360       R( d, e, a, b, c, F2, K2, M(27) );
 361       R( c, d, e, a, b, F2, K2, M(28) );
 362       R( b, c, d, e, a, F2, K2, M(29) );
 363       R( a, b, c, d, e, F2, K2, M(30) );
 364       R( e, a, b, c, d, F2, K2, M(31) );
 365       R( d, e, a, b, c, F2, K2, M(32) );
 366       R( c, d, e, a, b, F2, K2, M(33) );
 367       R( b, c, d, e, a, F2, K2, M(34) );
 368       R( a, b, c, d, e, F2, K2, M(35) );
 369       R( e, a, b, c, d, F2, K2, M(36) );
 370       R( d, e, a, b, c, F2, K2, M(37) );
 371       R( c, d, e, a, b, F2, K2, M(38) );
 372       R( b, c, d, e, a, F2, K2, M(39) );
 373       R( a, b, c, d, e, F3, K3, M(40) );
 374       R( e, a, b, c, d, F3, K3, M(41) );
 375       R( d, e, a, b, c, F3, K3, M(42) );
 376       R( c, d, e, a, b, F3, K3, M(43) );
 377       R( b, c, d, e, a, F3, K3, M(44) );
 378       R( a, b, c, d, e, F3, K3, M(45) );
 379       R( e, a, b, c, d, F3, K3, M(46) );
 380       R( d, e, a, b, c, F3, K3, M(47) );
 381       R( c, d, e, a, b, F3, K3, M(48) );
 382       R( b, c, d, e, a, F3, K3, M(49) );
 383       R( a, b, c, d, e, F3, K3, M(50) );
 384       R( e, a, b, c, d, F3, K3, M(51) );
 385       R( d, e, a, b, c, F3, K3, M(52) );
 386       R( c, d, e, a, b, F3, K3, M(53) );
 387       R( b, c, d, e, a, F3, K3, M(54) );
 388       R( a, b, c, d, e, F3, K3, M(55) );
 389       R( e, a, b, c, d, F3, K3, M(56) );
 390       R( d, e, a, b, c, F3, K3, M(57) );
 391       R( c, d, e, a, b, F3, K3, M(58) );
 392       R( b, c, d, e, a, F3, K3, M(59) );
 393       R( a, b, c, d, e, F4, K4, M(60) );
 394       R( e, a, b, c, d, F4, K4, M(61) );
 395       R( d, e, a, b, c, F4, K4, M(62) );
 396       R( c, d, e, a, b, F4, K4, M(63) );
 397       R( b, c, d, e, a, F4, K4, M(64) );
 398       R( a, b, c, d, e, F4, K4, M(65) );
 399       R( e, a, b, c, d, F4, K4, M(66) );
 400       R( d, e, a, b, c, F4, K4, M(67) );
 401       R( c, d, e, a, b, F4, K4, M(68) );
 402       R( b, c, d, e, a, F4, K4, M(69) );
 403       R( a, b, c, d, e, F4, K4, M(70) );
 404       R( e, a, b, c, d, F4, K4, M(71) );
 405       R( d, e, a, b, c, F4, K4, M(72) );
 406       R( c, d, e, a, b, F4, K4, M(73) );
 407       R( b, c, d, e, a, F4, K4, M(74) );
 408       R( a, b, c, d, e, F4, K4, M(75) );
 409       R( e, a, b, c, d, F4, K4, M(76) );
 410       R( d, e, a, b, c, F4, K4, M(77) );
 411       R( c, d, e, a, b, F4, K4, M(78) );
 412       R( b, c, d, e, a, F4, K4, M(79) );
 413
 414       a = ctx->A += a;
 415       b = ctx->B += b;
 416       c = ctx->C += c;
 417       d = ctx->D += d;
 418       e = ctx->E += e;
 419     }
 420 }