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