third_party/sha1.cc

   1 /* sha1.cc - Functions to compute SHA1 message digest of data streams
   2  * according to the NIST specification FIPS-180-1.
   3  * part of Cumulus: Smart Filesystem Backup to Dumb Servers
   4  *
   5  * Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
   6  * Copyright (C) 2006-2007  The Regents of the University of California
   7  * Written by Scott G. Miller
   8  * Additional Credits:
   9  *    Robert Klep <robert@ilse.nl>  -- Expansion function fix
  10  * Modifications by Michael Vrable <mvrable@cs.ucsd.edu> to integrate into
  11  * Cumulus.
  12  *
  13  * Original code (in C) is taken from GNU coreutils (Debian package 5.97-5).
  14  *
  15  * This program is free software; you can redistribute it and/or modify
  16  * it under the terms of the GNU General Public License as published by
  17  * the Free Software Foundation; either version 2 of the License, or
  18  * (at your option) any later version.
  19  *
  20  * This program is distributed in the hope that it will be useful,
  21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23  * GNU General Public License for more details.
  24  *
  25  * You should have received a copy of the GNU General Public License along
  26  * with this program; if not, write to the Free Software Foundation, Inc.,
  27  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  28  */
  29
  30 #include "../hash.h"
  31 #include "sha1.h"
  32
  33 #include <stddef.h>
  34 #include <stdio.h>
  35 #include <string.h>
  36 #include <arpa/inet.h>
  37
  38 #include <string.h>
  39
  40 using std::string;
  41
  42 /* SWAP does an endian swap on architectures that are little-endian,
  43    as SHA1 needs some data in a big-endian form.  */
  44 #define SWAP(n) htonl(n)
  45
  46 #define BLOCKSIZE 4096
  47 #if BLOCKSIZE % 64 != 0
  48 # error "invalid BLOCKSIZE"
  49 #endif
  50
  51 /* This array contains the bytes used to pad the buffer to the next
  52    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
  53 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
  54
  55
  56 /*
  57   Takes a pointer to a 160 bit block of data (five 32 bit ints) and
  58   intializes it to the start constants of the SHA1 algorithm.  This
  59   must be called before using hash in the call to sha1_hash.
  60 */
  61 void
  62 sha1_init_ctx (struct sha1_ctx *ctx)
  63 {
  64   ctx->A = 0x67452301;
  65   ctx->B = 0xefcdab89;
  66   ctx->C = 0x98badcfe;
  67   ctx->D = 0x10325476;
  68   ctx->E = 0xc3d2e1f0;
  69
  70   ctx->total[0] = ctx->total[1] = 0;
  71   ctx->buflen = 0;
  72 }
  73
  74 /* Put result from CTX in first 20 bytes following RESBUF.  The result
  75    must be in little endian byte order.
  76
  77    IMPORTANT: On some systems it is required that RESBUF is correctly
  78    aligned for a 32 bits value.  */
  79 void *
  80 sha1_read_ctx (const struct sha1_ctx *ctx, void *resbuf)
  81 {
  82   ((md5_uint32 *) resbuf)[0] = SWAP (ctx->A);
  83   ((md5_uint32 *) resbuf)[1] = SWAP (ctx->B);
  84   ((md5_uint32 *) resbuf)[2] = SWAP (ctx->C);
  85   ((md5_uint32 *) resbuf)[3] = SWAP (ctx->D);
  86   ((md5_uint32 *) resbuf)[4] = SWAP (ctx->E);
  87
  88   return resbuf;
  89 }
  90
  91 /* Process the remaining bytes in the internal buffer and the usual
  92    prolog according to the standard and write the result to RESBUF.
  93
  94    IMPORTANT: On some systems it is required that RESBUF is correctly
  95    aligned for a 32 bits value.  */
  96 void *
  97 sha1_finish_ctx (struct sha1_ctx *ctx, void *resbuf)
  98 {
  99   /* Take yet unprocessed bytes into account.  */
 100   md5_uint32 bytes = ctx->buflen;
 101   size_t pad;
 102
 103   /* Now count remaining bytes.  */
 104   ctx->total[0] += bytes;
 105   if (ctx->total[0] < bytes)
 106     ++ctx->total[1];
 107
 108   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
 109   memcpy (&ctx->buffer[bytes], fillbuf, pad);
 110
 111   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 112   *(md5_uint32 *) &ctx->buffer[bytes + pad + 4] = SWAP (ctx->total[0] << 3);
 113   *(md5_uint32 *) &ctx->buffer[bytes + pad] = SWAP ((ctx->total[1] << 3) |
 114                                                     (ctx->total[0] >> 29));
 115
 116   /* Process last bytes.  */
 117   sha1_process_block (ctx->buffer, bytes + pad + 8, ctx);
 118
 119   return sha1_read_ctx (ctx, resbuf);
 120 }
 121
 122 void
 123 sha1_process_bytes (const void *buffer, size_t len, struct sha1_ctx *ctx)
 124 {
 125   /* When we already have some bits in our internal buffer concatenate
 126      both inputs first.  */
 127   if (ctx->buflen != 0)
 128     {
 129       size_t left_over = ctx->buflen;
 130       size_t add = 128 - left_over > len ? len : 128 - left_over;
 131
 132       memcpy (&ctx->buffer[left_over], buffer, add);
 133       ctx->buflen += add;
 134
 135       if (ctx->buflen > 64)
 136         {
 137           sha1_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
 138
 139           ctx->buflen &= 63;
 140           /* The regions in the following copy operation cannot overlap.  */
 141           memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
 142                   ctx->buflen);
 143         }
 144
 145       buffer = (const char *) buffer + add;
 146       len -= add;
 147     }
 148
 149   /* Process available complete blocks.  */
 150   if (len >= 64)
 151     {
 152 #if !_STRING_ARCH_unaligned
 153 # define alignof(type) offsetof (struct { char c; type x; }, x)
 154 # define UNALIGNED_P(p) (((size_t) p) % alignof (md5_uint32) != 0)
 155       if (UNALIGNED_P (buffer))
 156         while (len > 64)
 157           {
 158             sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
 159             buffer = (const char *) buffer + 64;
 160             len -= 64;
 161           }
 162       else
 163 #endif
 164         {
 165           sha1_process_block (buffer, len & ~63, ctx);
 166           buffer = (const char *) buffer + (len & ~63);
 167           len &= 63;
 168         }
 169     }
 170
 171   /* Move remaining bytes in internal buffer.  */
 172   if (len > 0)
 173     {
 174       size_t left_over = ctx->buflen;
 175
 176       memcpy (&ctx->buffer[left_over], buffer, len);
 177       left_over += len;
 178       if (left_over >= 64)
 179         {
 180           sha1_process_block (ctx->buffer, 64, ctx);
 181           left_over -= 64;
 182           memcpy (ctx->buffer, &ctx->buffer[64], left_over);
 183         }
 184       ctx->buflen = left_over;
 185     }
 186 }
 187
 188 /* --- Code below is the primary difference between md5.c and sha1.c --- */
 189
 190 /* SHA1 round constants */
 191 #define K1 0x5a827999L
 192 #define K2 0x6ed9eba1L
 193 #define K3 0x8f1bbcdcL
 194 #define K4 0xca62c1d6L
 195
 196 /* Round functions.  Note that F2 is the same as F4.  */
 197 #define F1(B,C,D) ( D ^ ( B & ( C ^ D ) ) )
 198 #define F2(B,C,D) (B ^ C ^ D)
 199 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
 200 #define F4(B,C,D) (B ^ C ^ D)
 201
 202 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 203    It is assumed that LEN % 64 == 0.
 204    Most of this code comes from GnuPG's cipher/sha1.c.  */
 205
 206 void
 207 sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
 208 {
 209   const md5_uint32 *words = (const md5_uint32 *)buffer;
 210   size_t nwords = len / sizeof (md5_uint32);
 211   const md5_uint32 *endp = words + nwords;
 212   md5_uint32 x[16];
 213   md5_uint32 a = ctx->A;
 214   md5_uint32 b = ctx->B;
 215   md5_uint32 c = ctx->C;
 216   md5_uint32 d = ctx->D;
 217   md5_uint32 e = ctx->E;
 218
 219   /* First increment the byte count.  RFC 1321 specifies the possible
 220      length of the file up to 2^64 bits.  Here we only compute the
 221      number of bytes.  Do a double word increment.  */
 222   ctx->total[0] += len;
 223   if (ctx->total[0] < len)
 224     ++ctx->total[1];
 225
 226 #define rol(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
 227
 228 #define M(I) ( tm =   x[I&0x0f] ^ x[(I-14)&0x0f] \
 229                     ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \
 230                , (x[I&0x0f] = rol(tm, 1)) )
 231
 232 #define R(A,B,C,D,E,F,K,M)  do { E += rol( A, 5 )     \
 233                                       + F( B, C, D )  \
 234                                       + K             \
 235                                       + M;            \
 236                                  B = rol( B, 30 );    \
 237                                } while(0)
 238
 239   while (words < endp)
 240     {
 241       md5_uint32 tm;
 242       int t;
 243       for (t = 0; t < 16; t++)
 244         {
 245           x[t] = SWAP (*words);
 246           words++;
 247         }
 248
 249       R( a, b, c, d, e, F1, K1, x[ 0] );
 250       R( e, a, b, c, d, F1, K1, x[ 1] );
 251       R( d, e, a, b, c, F1, K1, x[ 2] );
 252       R( c, d, e, a, b, F1, K1, x[ 3] );
 253       R( b, c, d, e, a, F1, K1, x[ 4] );
 254       R( a, b, c, d, e, F1, K1, x[ 5] );
 255       R( e, a, b, c, d, F1, K1, x[ 6] );
 256       R( d, e, a, b, c, F1, K1, x[ 7] );
 257       R( c, d, e, a, b, F1, K1, x[ 8] );
 258       R( b, c, d, e, a, F1, K1, x[ 9] );
 259       R( a, b, c, d, e, F1, K1, x[10] );
 260       R( e, a, b, c, d, F1, K1, x[11] );
 261       R( d, e, a, b, c, F1, K1, x[12] );
 262       R( c, d, e, a, b, F1, K1, x[13] );
 263       R( b, c, d, e, a, F1, K1, x[14] );
 264       R( a, b, c, d, e, F1, K1, x[15] );
 265       R( e, a, b, c, d, F1, K1, M(16) );
 266       R( d, e, a, b, c, F1, K1, M(17) );
 267       R( c, d, e, a, b, F1, K1, M(18) );
 268       R( b, c, d, e, a, F1, K1, M(19) );
 269       R( a, b, c, d, e, F2, K2, M(20) );
 270       R( e, a, b, c, d, F2, K2, M(21) );
 271       R( d, e, a, b, c, F2, K2, M(22) );
 272       R( c, d, e, a, b, F2, K2, M(23) );
 273       R( b, c, d, e, a, F2, K2, M(24) );
 274       R( a, b, c, d, e, F2, K2, M(25) );
 275       R( e, a, b, c, d, F2, K2, M(26) );
 276       R( d, e, a, b, c, F2, K2, M(27) );
 277       R( c, d, e, a, b, F2, K2, M(28) );
 278       R( b, c, d, e, a, F2, K2, M(29) );
 279       R( a, b, c, d, e, F2, K2, M(30) );
 280       R( e, a, b, c, d, F2, K2, M(31) );
 281       R( d, e, a, b, c, F2, K2, M(32) );
 282       R( c, d, e, a, b, F2, K2, M(33) );
 283       R( b, c, d, e, a, F2, K2, M(34) );
 284       R( a, b, c, d, e, F2, K2, M(35) );
 285       R( e, a, b, c, d, F2, K2, M(36) );
 286       R( d, e, a, b, c, F2, K2, M(37) );
 287       R( c, d, e, a, b, F2, K2, M(38) );
 288       R( b, c, d, e, a, F2, K2, M(39) );
 289       R( a, b, c, d, e, F3, K3, M(40) );
 290       R( e, a, b, c, d, F3, K3, M(41) );
 291       R( d, e, a, b, c, F3, K3, M(42) );
 292       R( c, d, e, a, b, F3, K3, M(43) );
 293       R( b, c, d, e, a, F3, K3, M(44) );
 294       R( a, b, c, d, e, F3, K3, M(45) );
 295       R( e, a, b, c, d, F3, K3, M(46) );
 296       R( d, e, a, b, c, F3, K3, M(47) );
 297       R( c, d, e, a, b, F3, K3, M(48) );
 298       R( b, c, d, e, a, F3, K3, M(49) );
 299       R( a, b, c, d, e, F3, K3, M(50) );
 300       R( e, a, b, c, d, F3, K3, M(51) );
 301       R( d, e, a, b, c, F3, K3, M(52) );
 302       R( c, d, e, a, b, F3, K3, M(53) );
 303       R( b, c, d, e, a, F3, K3, M(54) );
 304       R( a, b, c, d, e, F3, K3, M(55) );
 305       R( e, a, b, c, d, F3, K3, M(56) );
 306       R( d, e, a, b, c, F3, K3, M(57) );
 307       R( c, d, e, a, b, F3, K3, M(58) );
 308       R( b, c, d, e, a, F3, K3, M(59) );
 309       R( a, b, c, d, e, F4, K4, M(60) );
 310       R( e, a, b, c, d, F4, K4, M(61) );
 311       R( d, e, a, b, c, F4, K4, M(62) );
 312       R( c, d, e, a, b, F4, K4, M(63) );
 313       R( b, c, d, e, a, F4, K4, M(64) );
 314       R( a, b, c, d, e, F4, K4, M(65) );
 315       R( e, a, b, c, d, F4, K4, M(66) );
 316       R( d, e, a, b, c, F4, K4, M(67) );
 317       R( c, d, e, a, b, F4, K4, M(68) );
 318       R( b, c, d, e, a, F4, K4, M(69) );
 319       R( a, b, c, d, e, F4, K4, M(70) );
 320       R( e, a, b, c, d, F4, K4, M(71) );
 321       R( d, e, a, b, c, F4, K4, M(72) );
 322       R( c, d, e, a, b, F4, K4, M(73) );
 323       R( b, c, d, e, a, F4, K4, M(74) );
 324       R( a, b, c, d, e, F4, K4, M(75) );
 325       R( e, a, b, c, d, F4, K4, M(76) );
 326       R( d, e, a, b, c, F4, K4, M(77) );
 327       R( c, d, e, a, b, F4, K4, M(78) );
 328       R( b, c, d, e, a, F4, K4, M(79) );
 329
 330       a = ctx->A += a;
 331       b = ctx->B += b;
 332       c = ctx->C += c;
 333       d = ctx->D += d;
 334       e = ctx->E += e;
 335     }
 336 }
 337
 338 /* ---- Object-Oriented Wrapper */
 339 SHA1Checksum::SHA1Checksum()
 340 {
 341     sha1_init_ctx(&ctx);
 342 }
 343
 344 SHA1Checksum::~SHA1Checksum()
 345 {
 346 }
 347
 348 void SHA1Checksum::process(const void *data, size_t len)
 349 {
 350     sha1_process_bytes(data, len, &ctx);
 351 }
 352
 353 bool SHA1Checksum::process_file(const char *filename)
 354 {
 355     FILE *f = fopen(filename, "rb");
 356     if (f == NULL)
 357         return false;
 358
 359     while (!feof(f)) {
 360         char buf[4096];
 361         size_t bytes = fread(buf, 1, sizeof(buf), f);
 362
 363         if (ferror(f)) {
 364             fclose(f);
 365             return false;
 366         }
 367
 368         process(buf, bytes);
 369     }
 370
 371     fclose(f);
 372     return true;
 373 }
 374
 375 const uint8_t *SHA1Checksum::checksum()
 376 {
 377     sha1_finish_ctx(&ctx, resbuf);
 378     return (const uint8_t *)resbuf;
 379 }
 380
 381 string SHA1Checksum::checksum_str()
 382 {
 383     uint8_t resbuf[20];
 384     char hexbuf[4];
 385     string result = "sha1=";
 386
 387     sha1_finish_ctx(&ctx, resbuf);
 388
 389     for (int i = 0; i < 20; i++) {
 390         sprintf(hexbuf, "%02x", resbuf[i]);
 391         result += hexbuf;
 392     }
 393
 394     return result;
 395 }
 396
 397 class SHA1Hash : public Hash {
 398 public:
 399     SHA1Hash();
 400     static Hash *New() { return new SHA1Hash; }
 401     virtual void update(const void *data, size_t len);
 402     virtual size_t digest_size() const { return 20; }
 403     virtual std::string name() const { return "sha1"; }
 404
 405 protected:
 406     const uint8_t *finalize();
 407
 408 private:
 409     struct sha1_ctx ctx;
 410     char resbuf[20] __attribute__ ((__aligned__ (__alignof__ (md5_uint32))));
 411 };
 412
 413 SHA1Hash::SHA1Hash()
 414 {
 415     sha1_init_ctx(&ctx);
 416 }
 417
 418 void SHA1Hash::update(const void *data, size_t len)
 419 {
 420     sha1_process_bytes(data, len, &ctx);
 421 }
 422
 423 const uint8_t *SHA1Hash::finalize()
 424 {
 425     sha1_finish_ctx(&ctx, resbuf);
 426     return (const uint8_t *)resbuf;
 427 }
 428
 429 void sha1_register()
 430 {
 431     Hash::Register("sha1", SHA1Hash::New);
 432 }