lib/sha1.c

   1 /* Functions to compute SHA1 message digest of files or memory blocks.
   2    according to the definition of SHA1 in FIPS 180-1 from April 1997.
   3    Copyright (C) 2008-2011, 2015 Red Hat, Inc.
   4    This file is part of elfutils.
   5    Written by Ulrich Drepper <drepper@redhat.com>, 2008.
   6
   7    This file is free software; you can redistribute it and/or modify
   8    it under the terms of either
   9
  10      * the GNU Lesser General Public License as published by the Free
  11        Software Foundation; either version 3 of the License, or (at
  12        your option) any later version
  13
  14    or
  15
  16      * the GNU General Public License as published by the Free
  17        Software Foundation; either version 2 of the License, or (at
  18        your option) any later version
  19
  20    or both in parallel, as here.
  21
  22    elfutils is distributed in the hope that it will be useful, but
  23    WITHOUT ANY WARRANTY; without even the implied warranty of
  24    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25    General Public License for more details.
  26
  27    You should have received copies of the GNU General Public License and
  28    the GNU Lesser General Public License along with this program.  If
  29    not, see <http://www.gnu.org/licenses/>.  */
  30
  31 #ifdef HAVE_CONFIG_H
  32 # include <config.h>
  33 #endif
  34
  35 #include <stdlib.h>
  36 #include <string.h>
  37 #include <sys/types.h>
  38
  39 #include "sha1.h"
  40 #include "system.h"
  41
  42 #define SWAP(n) BE32 (n)
  43
  44 /* This array contains the bytes used to pad the buffer to the next
  45    64-byte boundary.  */
  46 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
  47
  48
  49 /* Initialize structure containing state of computation.  */
  50 void
  51 sha1_init_ctx (struct sha1_ctx *ctx)
  52 {
  53   ctx->A = 0x67452301;
  54   ctx->B = 0xefcdab89;
  55   ctx->C = 0x98badcfe;
  56   ctx->D = 0x10325476;
  57   ctx->E = 0xc3d2e1f0;
  58
  59   ctx->total[0] = ctx->total[1] = 0;
  60   ctx->buflen = 0;
  61 }
  62
  63 /* Put result from CTX in first 20 bytes following RESBUF.  The result
  64    must be in little endian byte order.
  65
  66    IMPORTANT: On some systems it is required that RESBUF is correctly
  67    aligned for a 32 bits value.  */
  68 void *
  69 sha1_read_ctx (const struct sha1_ctx *ctx, void *resbuf)
  70 {
  71   ((sha1_uint32 *) resbuf)[0] = SWAP (ctx->A);
  72   ((sha1_uint32 *) resbuf)[1] = SWAP (ctx->B);
  73   ((sha1_uint32 *) resbuf)[2] = SWAP (ctx->C);
  74   ((sha1_uint32 *) resbuf)[3] = SWAP (ctx->D);
  75   ((sha1_uint32 *) resbuf)[4] = SWAP (ctx->E);
  76
  77   return resbuf;
  78 }
  79
  80 static void
  81 be64_copy (char *dest, uint64_t x)
  82 {
  83   for (size_t i = 8; i-- > 0; x >>= 8)
  84     dest[i] = (uint8_t) x;
  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 bits 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 pad;
  98
  99   /* Now count remaining bytes.  */
 100   ctx->total[0] += bytes;
 101   if (ctx->total[0] < bytes)
 102     ++ctx->total[1];
 103
 104   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
 105   memcpy (&ctx->buffer[bytes], fillbuf, pad);
 106
 107   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 108   const uint64_t bit_length = ((ctx->total[0] << 3)
 109                                + ((uint64_t) ((ctx->total[1] << 3) |
 110                                               (ctx->total[0] >> 29)) << 32));
 111   be64_copy (&ctx->buffer[bytes + pad], bit_length);
 112
 113   /* Process last bytes.  */
 114   sha1_process_block (ctx->buffer, bytes + pad + 8, ctx);
 115
 116   return sha1_read_ctx (ctx, resbuf);
 117 }
 118
 119
 120 void
 121 sha1_process_bytes (const void *buffer, size_t len, struct sha1_ctx *ctx)
 122 {
 123   /* When we already have some bits in our internal buffer concatenate
 124      both inputs first.  */
 125   if (ctx->buflen != 0)
 126     {
 127       size_t left_over = ctx->buflen;
 128       size_t add = 128 - left_over > len ? len : 128 - left_over;
 129
 130       memcpy (&ctx->buffer[left_over], buffer, add);
 131       ctx->buflen += add;
 132
 133       if (ctx->buflen > 64)
 134         {
 135           sha1_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
 136
 137           ctx->buflen &= 63;
 138           /* The regions in the following copy operation cannot overlap.  */
 139           memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
 140                   ctx->buflen);
 141         }
 142
 143       buffer = (const char *) buffer + add;
 144       len -= add;
 145     }
 146
 147   /* Process available complete blocks.  */
 148   if (len >= 64)
 149     {
 150 #if !_STRING_ARCH_unaligned
 151 /* To check alignment gcc has an appropriate operator.  Other
 152    compilers don't.  */
 153 # if __GNUC__ >= 2
 154 #  define UNALIGNED_P(p) (((sha1_uintptr) p) % __alignof__ (sha1_uint32) != 0)
 155 # else
 156 #  define UNALIGNED_P(p) (((sha1_uintptr) p) % sizeof (sha1_uint32) != 0)
 157 # endif
 158       if (UNALIGNED_P (buffer))
 159         while (len > 64)
 160           {
 161             sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
 162             buffer = (const char *) buffer + 64;
 163             len -= 64;
 164           }
 165       else
 166 #endif
 167         {
 168           sha1_process_block (buffer, len & ~63, ctx);
 169           buffer = (const char *) buffer + (len & ~63);
 170           len &= 63;
 171         }
 172     }
 173
 174   /* Move remaining bytes in internal buffer.  */
 175   if (len > 0)
 176     {
 177       size_t left_over = ctx->buflen;
 178
 179       memcpy (&ctx->buffer[left_over], buffer, len);
 180       left_over += len;
 181       if (left_over >= 64)
 182         {
 183           sha1_process_block (ctx->buffer, 64, ctx);
 184           left_over -= 64;
 185           memcpy (ctx->buffer, &ctx->buffer[64], left_over);
 186         }
 187       ctx->buflen = left_over;
 188     }
 189 }
 190
 191
 192 /* These are the four functions used in the four steps of the SHA1 algorithm
 193    and defined in the FIPS 180-1.  */
 194 /* #define FF(b, c, d) ((b & c) | (~b & d)) */
 195 #define FF(b, c, d) (d ^ (b & (c ^ d)))
 196 #define FG(b, c, d) (b ^ c ^ d)
 197 /* define FH(b, c, d) ((b & c) | (b & d) | (c & d)) */
 198 #define FH(b, c, d) (((b | c) & d) | (b & c))
 199
 200 /* It is unfortunate that C does not provide an operator for cyclic
 201    rotation.  Hope the C compiler is smart enough.  */
 202 #define CYCLIC(w, s) (((w) << s) | ((w) >> (32 - s)))
 203
 204 /* Magic constants.  */
 205 #define K0 0x5a827999
 206 #define K1 0x6ed9eba1
 207 #define K2 0x8f1bbcdc
 208 #define K3 0xca62c1d6
 209
 210
 211 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 212    It is assumed that LEN % 64 == 0.  */
 213
 214 void
 215 sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
 216 {
 217   sha1_uint32 computed_words[16];
 218 #define W(i) computed_words[(i) % 16]
 219   const sha1_uint32 *words = buffer;
 220   size_t nwords = len / sizeof (sha1_uint32);
 221   const sha1_uint32 *endp = words + nwords;
 222   sha1_uint32 A = ctx->A;
 223   sha1_uint32 B = ctx->B;
 224   sha1_uint32 C = ctx->C;
 225   sha1_uint32 D = ctx->D;
 226   sha1_uint32 E = ctx->E;
 227
 228   /* First increment the byte count.  FIPS 180-1 specifies the possible
 229      length of the file up to 2^64 bits.  Here we only compute the
 230      number of bytes.  Do a double word increment.  */
 231   ctx->total[0] += len;
 232   if (ctx->total[0] < len)
 233     ++ctx->total[1];
 234
 235   /* Process all bytes in the buffer with 64 bytes in each round of
 236      the loop.  */
 237   while (words < endp)
 238     {
 239       sha1_uint32 A_save = A;
 240       sha1_uint32 B_save = B;
 241       sha1_uint32 C_save = C;
 242       sha1_uint32 D_save = D;
 243       sha1_uint32 E_save = E;
 244
 245       /* First round: using the given function, the context and a constant
 246          the next context is computed.  Because the algorithms processing
 247          unit is a 32-bit word and it is determined to work on words in
 248          little endian byte order we perhaps have to change the byte order
 249          before the computation.  */
 250
 251 #define OP(i, a, b, c, d, e)                                            \
 252       do                                                                \
 253         {                                                               \
 254           W (i) = SWAP (*words);                                        \
 255           e = CYCLIC (a, 5) + FF (b, c, d) + e + W (i) + K0;            \
 256           ++words;                                                      \
 257           b = CYCLIC (b, 30);                                           \
 258         }                                                               \
 259       while (0)
 260
 261       /* Steps 0 to 15.  */
 262       OP (0, A, B, C, D, E);
 263       OP (1, E, A, B, C, D);
 264       OP (2, D, E, A, B, C);
 265       OP (3, C, D, E, A, B);
 266       OP (4, B, C, D, E, A);
 267       OP (5, A, B, C, D, E);
 268       OP (6, E, A, B, C, D);
 269       OP (7, D, E, A, B, C);
 270       OP (8, C, D, E, A, B);
 271       OP (9, B, C, D, E, A);
 272       OP (10, A, B, C, D, E);
 273       OP (11, E, A, B, C, D);
 274       OP (12, D, E, A, B, C);
 275       OP (13, C, D, E, A, B);
 276       OP (14, B, C, D, E, A);
 277       OP (15, A, B, C, D, E);
 278
 279       /* For the remaining 64 steps we have a more complicated
 280          computation of the input data-derived values.  Redefine the
 281          macro to take an additional second argument specifying the
 282          function to use and a new last parameter for the magic
 283          constant.  */
 284 #undef OP
 285 #define OP(i, f, a, b, c, d, e, K) \
 286       do                                                                \
 287         {                                                               \
 288           W (i) = CYCLIC (W (i - 3) ^ W (i - 8) ^ W (i - 14) ^ W (i - 16), 1);\
 289           e = CYCLIC (a, 5) + f (b, c, d) + e + W (i) + K;              \
 290           b = CYCLIC (b, 30);                                           \
 291         }                                                               \
 292       while (0)
 293
 294       /* Steps 16 to 19.  */
 295       OP (16, FF, E, A, B, C, D, K0);
 296       OP (17, FF, D, E, A, B, C, K0);
 297       OP (18, FF, C, D, E, A, B, K0);
 298       OP (19, FF, B, C, D, E, A, K0);
 299
 300       /* Steps 20 to 39.  */
 301       OP (20, FG, A, B, C, D, E, K1);
 302       OP (21, FG, E, A, B, C, D, K1);
 303       OP (22, FG, D, E, A, B, C, K1);
 304       OP (23, FG, C, D, E, A, B, K1);
 305       OP (24, FG, B, C, D, E, A, K1);
 306       OP (25, FG, A, B, C, D, E, K1);
 307       OP (26, FG, E, A, B, C, D, K1);
 308       OP (27, FG, D, E, A, B, C, K1);
 309       OP (28, FG, C, D, E, A, B, K1);
 310       OP (29, FG, B, C, D, E, A, K1);
 311       OP (30, FG, A, B, C, D, E, K1);
 312       OP (31, FG, E, A, B, C, D, K1);
 313       OP (32, FG, D, E, A, B, C, K1);
 314       OP (33, FG, C, D, E, A, B, K1);
 315       OP (34, FG, B, C, D, E, A, K1);
 316       OP (35, FG, A, B, C, D, E, K1);
 317       OP (36, FG, E, A, B, C, D, K1);
 318       OP (37, FG, D, E, A, B, C, K1);
 319       OP (38, FG, C, D, E, A, B, K1);
 320       OP (39, FG, B, C, D, E, A, K1);
 321
 322       /* Steps 40 to 59.  */
 323       OP (40, FH, A, B, C, D, E, K2);
 324       OP (41, FH, E, A, B, C, D, K2);
 325       OP (42, FH, D, E, A, B, C, K2);
 326       OP (43, FH, C, D, E, A, B, K2);
 327       OP (44, FH, B, C, D, E, A, K2);
 328       OP (45, FH, A, B, C, D, E, K2);
 329       OP (46, FH, E, A, B, C, D, K2);
 330       OP (47, FH, D, E, A, B, C, K2);
 331       OP (48, FH, C, D, E, A, B, K2);
 332       OP (49, FH, B, C, D, E, A, K2);
 333       OP (50, FH, A, B, C, D, E, K2);
 334       OP (51, FH, E, A, B, C, D, K2);
 335       OP (52, FH, D, E, A, B, C, K2);
 336       OP (53, FH, C, D, E, A, B, K2);
 337       OP (54, FH, B, C, D, E, A, K2);
 338       OP (55, FH, A, B, C, D, E, K2);
 339       OP (56, FH, E, A, B, C, D, K2);
 340       OP (57, FH, D, E, A, B, C, K2);
 341       OP (58, FH, C, D, E, A, B, K2);
 342       OP (59, FH, B, C, D, E, A, K2);
 343
 344       /* Steps 60 to 79.  */
 345       OP (60, FG, A, B, C, D, E, K3);
 346       OP (61, FG, E, A, B, C, D, K3);
 347       OP (62, FG, D, E, A, B, C, K3);
 348       OP (63, FG, C, D, E, A, B, K3);
 349       OP (64, FG, B, C, D, E, A, K3);
 350       OP (65, FG, A, B, C, D, E, K3);
 351       OP (66, FG, E, A, B, C, D, K3);
 352       OP (67, FG, D, E, A, B, C, K3);
 353       OP (68, FG, C, D, E, A, B, K3);
 354       OP (69, FG, B, C, D, E, A, K3);
 355       OP (70, FG, A, B, C, D, E, K3);
 356       OP (71, FG, E, A, B, C, D, K3);
 357       OP (72, FG, D, E, A, B, C, K3);
 358       OP (73, FG, C, D, E, A, B, K3);
 359       OP (74, FG, B, C, D, E, A, K3);
 360       OP (75, FG, A, B, C, D, E, K3);
 361       OP (76, FG, E, A, B, C, D, K3);
 362       OP (77, FG, D, E, A, B, C, K3);
 363       OP (78, FG, C, D, E, A, B, K3);
 364       OP (79, FG, B, C, D, E, A, K3);
 365
 366       /* Add the starting values of the context.  */
 367       A += A_save;
 368       B += B_save;
 369       C += C_save;
 370       D += D_save;
 371       E += E_save;
 372     }
 373
 374   /* Put checksum in context given as argument.  */
 375   ctx->A = A;
 376   ctx->B = B;
 377   ctx->C = C;
 378   ctx->D = D;
 379   ctx->E = E;
 380 }