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