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