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