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 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, write to the Free Software Foundation,
  18    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  19
  20 /* Written by Scott G. Miller
  21    Credits:
  22       Robert Klep <robert@ilse.nl>  -- Expansion function fix
  23 */
  24
  25 #ifdef HAVE_CONFIG_H
  26 # include <config.h>
  27 #endif
  28
  29 #include "sha1.h"
  30
  31 #include <stddef.h>
  32 #include <string.h>
  33
  34 #include "unlocked-io.h"
  35
  36 /*
  37   Not-swap is a macro that does an endian swap on architectures that are
  38   big-endian, as SHA1 needs some data in a little-endian format
  39 */
  40
  41 #ifdef WORDS_BIGENDIAN
  42 # define NOTSWAP(n) (n)
  43 # define SWAP(n)                                                        \
  44     (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
  45 #else
  46 # define NOTSWAP(n)                                                         \
  47     (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
  48 # define SWAP(n) (n)
  49 #endif
  50
  51 #define BLOCKSIZE 4096
  52 /* Ensure that BLOCKSIZE is a multiple of 64.  */
  53 #if BLOCKSIZE % 64 != 0
  54 /* FIXME-someday (soon?): use #error instead of this kludge.  */
  55 "invalid BLOCKSIZE"
  56 #endif
  57
  58 /* This array contains the bytes used to pad the buffer to the next
  59    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
  60 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
  61
  62
  63 /*
  64   Takes a pointer to a 160 bit block of data (five 32 bit ints) and
  65   intializes it to the start constants of the SHA1 algorithm.  This
  66   must be called before using hash in the call to sha1_hash.
  67 */
  68 void
  69 sha1_init_ctx (struct sha1_ctx *ctx)
  70 {
  71   ctx->A = 0x67452301;
  72   ctx->B = 0xefcdab89;
  73   ctx->C = 0x98badcfe;
  74   ctx->D = 0x10325476;
  75   ctx->E = 0xc3d2e1f0;
  76
  77   ctx->total[0] = ctx->total[1] = 0;
  78   ctx->buflen = 0;
  79 }
  80
  81 /* Put result from CTX in first 20 bytes following RESBUF.  The result
  82    must be in little endian byte order.
  83
  84    IMPORTANT: On some systems it is required that RESBUF is correctly
  85    aligned for a 32 bits value.  */
  86 void *
  87 sha1_read_ctx (const struct sha1_ctx *ctx, void *resbuf)
  88 {
  89   ((md5_uint32 *) resbuf)[0] = NOTSWAP (ctx->A);
  90   ((md5_uint32 *) resbuf)[1] = NOTSWAP (ctx->B);
  91   ((md5_uint32 *) resbuf)[2] = NOTSWAP (ctx->C);
  92   ((md5_uint32 *) resbuf)[3] = NOTSWAP (ctx->D);
  93   ((md5_uint32 *) resbuf)[4] = NOTSWAP (ctx->E);
  94
  95   return resbuf;
  96 }
  97
  98 /* Process the remaining bytes in the internal buffer and the usual
  99    prolog according to the standard and write the result to RESBUF.
 100
 101    IMPORTANT: On some systems it is required that RESBUF is correctly
 102    aligned for a 32 bits value.  */
 103 void *
 104 sha1_finish_ctx (struct sha1_ctx *ctx, void *resbuf)
 105 {
 106   /* Take yet unprocessed bytes into account.  */
 107   md5_uint32 bytes = ctx->buflen;
 108   size_t pad;
 109
 110   /* Now count remaining bytes.  */
 111   ctx->total[0] += bytes;
 112   if (ctx->total[0] < bytes)
 113     ++ctx->total[1];
 114
 115   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
 116   memcpy (&ctx->buffer[bytes], fillbuf, pad);
 117
 118   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 119   *(md5_uint32 *) &ctx->buffer[bytes + pad + 4] = NOTSWAP (ctx->total[0] << 3);
 120   *(md5_uint32 *) &ctx->buffer[bytes + pad] = NOTSWAP ((ctx->total[1] << 3) |
 121                                                     (ctx->total[0] >> 29));
 122
 123   /* Process last bytes.  */
 124   sha1_process_block (ctx->buffer, bytes + pad + 8, ctx);
 125
 126   return sha1_read_ctx (ctx, resbuf);
 127 }
 128
 129 /* Compute SHA1 message digest for bytes read from STREAM.  The
 130    resulting message digest number will be written into the 16 bytes
 131    beginning at RESBLOCK.  */
 132 int
 133 sha1_stream (FILE *stream, void *resblock)
 134 {
 135   struct sha1_ctx ctx;
 136   char buffer[BLOCKSIZE + 72];
 137   size_t sum;
 138
 139   /* Initialize the computation context.  */
 140   sha1_init_ctx (&ctx);
 141
 142   /* Iterate over full file contents.  */
 143   while (1)
 144     {
 145       /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
 146          computation function processes the whole buffer so that with the
 147          next round of the loop another block can be read.  */
 148       size_t n;
 149       sum = 0;
 150
 151       /* Read block.  Take care for partial reads.  */
 152       while (1)
 153         {
 154           n = fread (buffer + sum, 1, BLOCKSIZE - sum, stream);
 155
 156           sum += n;
 157
 158           if (sum == BLOCKSIZE)
 159             break;
 160
 161           if (n == 0)
 162             {
 163               /* Check for the error flag IFF N == 0, so that we don't
 164                  exit the loop after a partial read due to e.g., EAGAIN
 165                  or EWOULDBLOCK.  */
 166               if (ferror (stream))
 167                 return 1;
 168               goto process_partial_block;
 169             }
 170
 171           /* We've read at least one byte, so ignore errors.  But always
 172              check for EOF, since feof may be true even though N > 0.
 173              Otherwise, we could end up calling fread after EOF.  */
 174           if (feof (stream))
 175             goto process_partial_block;
 176         }
 177
 178       /* Process buffer with BLOCKSIZE bytes.  Note that
 179                         BLOCKSIZE % 64 == 0
 180        */
 181       sha1_process_block (buffer, BLOCKSIZE, &ctx);
 182     }
 183
 184  process_partial_block:;
 185
 186   /* Process any remaining bytes.  */
 187   if (sum > 0)
 188     sha1_process_bytes (buffer, sum, &ctx);
 189
 190   /* Construct result in desired memory.  */
 191   sha1_finish_ctx (&ctx, resblock);
 192   return 0;
 193 }
 194
 195 /* Compute MD5 message digest for LEN bytes beginning at BUFFER.  The
 196    result is always in little endian byte order, so that a byte-wise
 197    output yields to the wanted ASCII representation of the message
 198    digest.  */
 199 void *
 200 sha1_buffer (const char *buffer, size_t len, void *resblock)
 201 {
 202   struct sha1_ctx ctx;
 203
 204   /* Initialize the computation context.  */
 205   sha1_init_ctx (&ctx);
 206
 207   /* Process whole buffer but last len % 64 bytes.  */
 208   sha1_process_bytes (buffer, len, &ctx);
 209
 210   /* Put result in desired memory area.  */
 211   return sha1_finish_ctx (&ctx, resblock);
 212 }
 213
 214 void
 215 sha1_process_bytes (const void *buffer, size_t len, struct sha1_ctx *ctx)
 216 {
 217   /* When we already have some bits in our internal buffer concatenate
 218      both inputs first.  */
 219   if (ctx->buflen != 0)
 220     {
 221       size_t left_over = ctx->buflen;
 222       size_t add = 128 - left_over > len ? len : 128 - left_over;
 223
 224       memcpy (&ctx->buffer[left_over], buffer, add);
 225       ctx->buflen += add;
 226
 227       if (ctx->buflen > 64)
 228         {
 229           sha1_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
 230
 231           ctx->buflen &= 63;
 232           /* The regions in the following copy operation cannot overlap.  */
 233           memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
 234                   ctx->buflen);
 235         }
 236
 237       buffer = (const char *) buffer + add;
 238       len -= add;
 239     }
 240
 241   /* Process available complete blocks.  */
 242   if (len >= 64)
 243     {
 244 #if !_STRING_ARCH_unaligned
 245 # define alignof(type) offsetof (struct { char c; type x; }, x)
 246 # define UNALIGNED_P(p) (((size_t) p) % alignof (md5_uint32) != 0)
 247       if (UNALIGNED_P (buffer))
 248         while (len > 64)
 249           {
 250             sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
 251             buffer = (const char *) buffer + 64;
 252             len -= 64;
 253           }
 254       else
 255 #endif
 256         {
 257           sha1_process_block (buffer, len & ~63, ctx);
 258           buffer = (const char *) buffer + (len & ~63);
 259           len &= 63;
 260         }
 261     }
 262
 263   /* Move remaining bytes in internal buffer.  */
 264   if (len > 0)
 265     {
 266       size_t left_over = ctx->buflen;
 267
 268       memcpy (&ctx->buffer[left_over], buffer, len);
 269       left_over += len;
 270       if (left_over >= 64)
 271         {
 272           sha1_process_block (ctx->buffer, 64, ctx);
 273           left_over -= 64;
 274           memcpy (ctx->buffer, &ctx->buffer[64], left_over);
 275         }
 276       ctx->buflen = left_over;
 277     }
 278 }
 279
 280 /* --- Code below is the primary difference between md5.c and sha1.c --- */
 281
 282 /* SHA1 round constants */
 283 #define K1 0x5a827999L
 284 #define K2 0x6ed9eba1L
 285 #define K3 0x8f1bbcdcL
 286 #define K4 0xca62c1d6L
 287
 288 /* Round functions.  Note that F2 is the same as F4.  */
 289 #define F1(B,C,D) ( D ^ ( B & ( C ^ D ) ) )
 290 #define F2(B,C,D) (B ^ C ^ D)
 291 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
 292 #define F4(B,C,D) (B ^ C ^ D)
 293
 294 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 295    It is assumed that LEN % 64 == 0.
 296    Most of this code comes from GnuPG's cipher/sha1.c.  */
 297
 298 void
 299 sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
 300 {
 301   const md5_uint32 *words = buffer;
 302   size_t nwords = len / sizeof (md5_uint32);
 303   const md5_uint32 *endp = words + nwords;
 304   md5_uint32 x[16];
 305   md5_uint32 a = ctx->A;
 306   md5_uint32 b = ctx->B;
 307   md5_uint32 c = ctx->C;
 308   md5_uint32 d = ctx->D;
 309   md5_uint32 e = ctx->E;
 310
 311   /* First increment the byte count.  RFC 1321 specifies the possible
 312      length of the file up to 2^64 bits.  Here we only compute the
 313      number of bytes.  Do a double word increment.  */
 314   ctx->total[0] += len;
 315   if (ctx->total[0] < len)
 316     ++ctx->total[1];
 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       md5_uint32 tm;
 332       int t;
 333       /* FIXME: see sha1.c for a better implementation.  */
 334       for (t = 0; t < 16; t++)
 335         {
 336           x[t] = NOTSWAP (*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 }