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 "sha1.h"
  31
  32 #include <stddef.h>
  33 #include <stdio.h>
  34 #include <string.h>
  35 #include <arpa/inet.h>
  36
  37 #include <string.h>
  38
  39 using std::string;
  40
  41 /* SWAP does an endian swap on architectures that are little-endian,
  42    as SHA1 needs some data in a big-endian form.  */
  43 #define SWAP(n) htonl(n)
  44
  45 #define BLOCKSIZE 4096
  46 #if BLOCKSIZE % 64 != 0
  47 # error "invalid BLOCKSIZE"
  48 #endif
  49
  50 /* This array contains the bytes used to pad the buffer to the next
  51    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
  52 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
  53
  54
  55 /*
  56   Takes a pointer to a 160 bit block of data (five 32 bit ints) and
  57   intializes it to the start constants of the SHA1 algorithm.  This
  58   must be called before using hash in the call to sha1_hash.
  59 */
  60 void
  61 sha1_init_ctx (struct sha1_ctx *ctx)
  62 {
  63   ctx->A = 0x67452301;
  64   ctx->B = 0xefcdab89;
  65   ctx->C = 0x98badcfe;
  66   ctx->D = 0x10325476;
  67   ctx->E = 0xc3d2e1f0;
  68
  69   ctx->total[0] = ctx->total[1] = 0;
  70   ctx->buflen = 0;
  71 }
  72
  73 /* Put result from CTX in first 20 bytes following RESBUF.  The result
  74    must be in little endian byte order.
  75
  76    IMPORTANT: On some systems it is required that RESBUF is correctly
  77    aligned for a 32 bits value.  */
  78 void *
  79 sha1_read_ctx (const struct sha1_ctx *ctx, void *resbuf)
  80 {
  81   ((md5_uint32 *) resbuf)[0] = SWAP (ctx->A);
  82   ((md5_uint32 *) resbuf)[1] = SWAP (ctx->B);
  83   ((md5_uint32 *) resbuf)[2] = SWAP (ctx->C);
  84   ((md5_uint32 *) resbuf)[3] = SWAP (ctx->D);
  85   ((md5_uint32 *) resbuf)[4] = SWAP (ctx->E);
  86
  87   return resbuf;
  88 }
  89
  90 /* Process the remaining bytes in the internal buffer and the usual
  91    prolog according to the standard and write the result to RESBUF.
  92
  93    IMPORTANT: On some systems it is required that RESBUF is correctly
  94    aligned for a 32 bits value.  */
  95 void *
  96 sha1_finish_ctx (struct sha1_ctx *ctx, void *resbuf)
  97 {
  98   /* Take yet unprocessed bytes into account.  */
  99   md5_uint32 bytes = ctx->buflen;
 100   size_t pad;
 101
 102   /* Now count remaining bytes.  */
 103   ctx->total[0] += bytes;
 104   if (ctx->total[0] < bytes)
 105     ++ctx->total[1];
 106
 107   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
 108   memcpy (&ctx->buffer[bytes], fillbuf, pad);
 109
 110   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 111   *(md5_uint32 *) &ctx->buffer[bytes + pad + 4] = SWAP (ctx->total[0] << 3);
 112   *(md5_uint32 *) &ctx->buffer[bytes + pad] = SWAP ((ctx->total[1] << 3) |
 113                                                     (ctx->total[0] >> 29));
 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 void
 122 sha1_process_bytes (const void *buffer, size_t len, struct sha1_ctx *ctx)
 123 {
 124   /* When we already have some bits in our internal buffer concatenate
 125      both inputs first.  */
 126   if (ctx->buflen != 0)
 127     {
 128       size_t left_over = ctx->buflen;
 129       size_t add = 128 - left_over > len ? len : 128 - left_over;
 130
 131       memcpy (&ctx->buffer[left_over], buffer, add);
 132       ctx->buflen += add;
 133
 134       if (ctx->buflen > 64)
 135         {
 136           sha1_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
 137
 138           ctx->buflen &= 63;
 139           /* The regions in the following copy operation cannot overlap.  */
 140           memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
 141                   ctx->buflen);
 142         }
 143
 144       buffer = (const char *) buffer + add;
 145       len -= add;
 146     }
 147
 148   /* Process available complete blocks.  */
 149   if (len >= 64)
 150     {
 151 #if !_STRING_ARCH_unaligned
 152 # define alignof(type) offsetof (struct { char c; type x; }, x)
 153 # define UNALIGNED_P(p) (((size_t) p) % alignof (md5_uint32) != 0)
 154       if (UNALIGNED_P (buffer))
 155         while (len > 64)
 156           {
 157             sha1_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
 158             buffer = (const char *) buffer + 64;
 159             len -= 64;
 160           }
 161       else
 162 #endif
 163         {
 164           sha1_process_block (buffer, len & ~63, ctx);
 165           buffer = (const char *) buffer + (len & ~63);
 166           len &= 63;
 167         }
 168     }
 169
 170   /* Move remaining bytes in internal buffer.  */
 171   if (len > 0)
 172     {
 173       size_t left_over = ctx->buflen;
 174
 175       memcpy (&ctx->buffer[left_over], buffer, len);
 176       left_over += len;
 177       if (left_over >= 64)
 178         {
 179           sha1_process_block (ctx->buffer, 64, ctx);
 180           left_over -= 64;
 181           memcpy (ctx->buffer, &ctx->buffer[64], left_over);
 182         }
 183       ctx->buflen = left_over;
 184     }
 185 }
 186
 187 /* --- Code below is the primary difference between md5.c and sha1.c --- */
 188
 189 /* SHA1 round constants */
 190 #define K1 0x5a827999L
 191 #define K2 0x6ed9eba1L
 192 #define K3 0x8f1bbcdcL
 193 #define K4 0xca62c1d6L
 194
 195 /* Round functions.  Note that F2 is the same as F4.  */
 196 #define F1(B,C,D) ( D ^ ( B & ( C ^ D ) ) )
 197 #define F2(B,C,D) (B ^ C ^ D)
 198 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
 199 #define F4(B,C,D) (B ^ C ^ D)
 200
 201 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 202    It is assumed that LEN % 64 == 0.
 203    Most of this code comes from GnuPG's cipher/sha1.c.  */
 204
 205 void
 206 sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
 207 {
 208   const md5_uint32 *words = (const md5_uint32 *)buffer;
 209   size_t nwords = len / sizeof (md5_uint32);
 210   const md5_uint32 *endp = words + nwords;
 211   md5_uint32 x[16];
 212   md5_uint32 a = ctx->A;
 213   md5_uint32 b = ctx->B;
 214   md5_uint32 c = ctx->C;
 215   md5_uint32 d = ctx->D;
 216   md5_uint32 e = ctx->E;
 217
 218   /* First increment the byte count.  RFC 1321 specifies the possible
 219      length of the file up to 2^64 bits.  Here we only compute the
 220      number of bytes.  Do a double word increment.  */
 221   ctx->total[0] += len;
 222   if (ctx->total[0] < len)
 223     ++ctx->total[1];
 224
 225 #define rol(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
 226
 227 #define M(I) ( tm =   x[I&0x0f] ^ x[(I-14)&0x0f] \
 228                     ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \
 229                , (x[I&0x0f] = rol(tm, 1)) )
 230
 231 #define R(A,B,C,D,E,F,K,M)  do { E += rol( A, 5 )     \
 232                                       + F( B, C, D )  \
 233                                       + K             \
 234                                       + M;            \
 235                                  B = rol( B, 30 );    \
 236                                } while(0)
 237
 238   while (words < endp)
 239     {
 240       md5_uint32 tm;
 241       int t;
 242       for (t = 0; t < 16; t++)
 243         {
 244           x[t] = SWAP (*words);
 245           words++;
 246         }
 247
 248       R( a, b, c, d, e, F1, K1, x[ 0] );
 249       R( e, a, b, c, d, F1, K1, x[ 1] );
 250       R( d, e, a, b, c, F1, K1, x[ 2] );
 251       R( c, d, e, a, b, F1, K1, x[ 3] );
 252       R( b, c, d, e, a, F1, K1, x[ 4] );
 253       R( a, b, c, d, e, F1, K1, x[ 5] );
 254       R( e, a, b, c, d, F1, K1, x[ 6] );
 255       R( d, e, a, b, c, F1, K1, x[ 7] );
 256       R( c, d, e, a, b, F1, K1, x[ 8] );
 257       R( b, c, d, e, a, F1, K1, x[ 9] );
 258       R( a, b, c, d, e, F1, K1, x[10] );
 259       R( e, a, b, c, d, F1, K1, x[11] );
 260       R( d, e, a, b, c, F1, K1, x[12] );
 261       R( c, d, e, a, b, F1, K1, x[13] );
 262       R( b, c, d, e, a, F1, K1, x[14] );
 263       R( a, b, c, d, e, F1, K1, x[15] );
 264       R( e, a, b, c, d, F1, K1, M(16) );
 265       R( d, e, a, b, c, F1, K1, M(17) );
 266       R( c, d, e, a, b, F1, K1, M(18) );
 267       R( b, c, d, e, a, F1, K1, M(19) );
 268       R( a, b, c, d, e, F2, K2, M(20) );
 269       R( e, a, b, c, d, F2, K2, M(21) );
 270       R( d, e, a, b, c, F2, K2, M(22) );
 271       R( c, d, e, a, b, F2, K2, M(23) );
 272       R( b, c, d, e, a, F2, K2, M(24) );
 273       R( a, b, c, d, e, F2, K2, M(25) );
 274       R( e, a, b, c, d, F2, K2, M(26) );
 275       R( d, e, a, b, c, F2, K2, M(27) );
 276       R( c, d, e, a, b, F2, K2, M(28) );
 277       R( b, c, d, e, a, F2, K2, M(29) );
 278       R( a, b, c, d, e, F2, K2, M(30) );
 279       R( e, a, b, c, d, F2, K2, M(31) );
 280       R( d, e, a, b, c, F2, K2, M(32) );
 281       R( c, d, e, a, b, F2, K2, M(33) );
 282       R( b, c, d, e, a, F2, K2, M(34) );
 283       R( a, b, c, d, e, F2, K2, M(35) );
 284       R( e, a, b, c, d, F2, K2, M(36) );
 285       R( d, e, a, b, c, F2, K2, M(37) );
 286       R( c, d, e, a, b, F2, K2, M(38) );
 287       R( b, c, d, e, a, F2, K2, M(39) );
 288       R( a, b, c, d, e, F3, K3, M(40) );
 289       R( e, a, b, c, d, F3, K3, M(41) );
 290       R( d, e, a, b, c, F3, K3, M(42) );
 291       R( c, d, e, a, b, F3, K3, M(43) );
 292       R( b, c, d, e, a, F3, K3, M(44) );
 293       R( a, b, c, d, e, F3, K3, M(45) );
 294       R( e, a, b, c, d, F3, K3, M(46) );
 295       R( d, e, a, b, c, F3, K3, M(47) );
 296       R( c, d, e, a, b, F3, K3, M(48) );
 297       R( b, c, d, e, a, F3, K3, M(49) );
 298       R( a, b, c, d, e, F3, K3, M(50) );
 299       R( e, a, b, c, d, F3, K3, M(51) );
 300       R( d, e, a, b, c, F3, K3, M(52) );
 301       R( c, d, e, a, b, F3, K3, M(53) );
 302       R( b, c, d, e, a, F3, K3, M(54) );
 303       R( a, b, c, d, e, F3, K3, M(55) );
 304       R( e, a, b, c, d, F3, K3, M(56) );
 305       R( d, e, a, b, c, F3, K3, M(57) );
 306       R( c, d, e, a, b, F3, K3, M(58) );
 307       R( b, c, d, e, a, F3, K3, M(59) );
 308       R( a, b, c, d, e, F4, K4, M(60) );
 309       R( e, a, b, c, d, F4, K4, M(61) );
 310       R( d, e, a, b, c, F4, K4, M(62) );
 311       R( c, d, e, a, b, F4, K4, M(63) );
 312       R( b, c, d, e, a, F4, K4, M(64) );
 313       R( a, b, c, d, e, F4, K4, M(65) );
 314       R( e, a, b, c, d, F4, K4, M(66) );
 315       R( d, e, a, b, c, F4, K4, M(67) );
 316       R( c, d, e, a, b, F4, K4, M(68) );
 317       R( b, c, d, e, a, F4, K4, M(69) );
 318       R( a, b, c, d, e, F4, K4, M(70) );
 319       R( e, a, b, c, d, F4, K4, M(71) );
 320       R( d, e, a, b, c, F4, K4, M(72) );
 321       R( c, d, e, a, b, F4, K4, M(73) );
 322       R( b, c, d, e, a, F4, K4, M(74) );
 323       R( a, b, c, d, e, F4, K4, M(75) );
 324       R( e, a, b, c, d, F4, K4, M(76) );
 325       R( d, e, a, b, c, F4, K4, M(77) );
 326       R( c, d, e, a, b, F4, K4, M(78) );
 327       R( b, c, d, e, a, F4, K4, M(79) );
 328
 329       a = ctx->A += a;
 330       b = ctx->B += b;
 331       c = ctx->C += c;
 332       d = ctx->D += d;
 333       e = ctx->E += e;
 334     }
 335 }
 336
 337 /* ---- Object-Oriented Wrapper */
 338 SHA1Checksum::SHA1Checksum()
 339 {
 340     sha1_init_ctx(&ctx);
 341 }
 342
 343 SHA1Checksum::~SHA1Checksum()
 344 {
 345 }
 346
 347 void SHA1Checksum::process(const void *data, size_t len)
 348 {
 349     sha1_process_bytes(data, len, &ctx);
 350 }
 351
 352 bool SHA1Checksum::process_file(const char *filename)
 353 {
 354     FILE *f = fopen(filename, "rb");
 355     if (f == NULL)
 356         return false;
 357
 358     while (!feof(f)) {
 359         char buf[4096];
 360         size_t bytes = fread(buf, 1, sizeof(buf), f);
 361
 362         if (ferror(f)) {
 363             fclose(f);
 364             return false;
 365         }
 366
 367         process(buf, bytes);
 368     }
 369
 370     fclose(f);
 371     return true;
 372 }
 373
 374 const uint8_t *SHA1Checksum::checksum()
 375 {
 376     sha1_finish_ctx(&ctx, resbuf);
 377     return (const uint8_t *)resbuf;
 378 }
 379
 380 string SHA1Checksum::checksum_str()
 381 {
 382     uint8_t resbuf[20];
 383     char hexbuf[4];
 384     string result = "sha1=";
 385
 386     sha1_finish_ctx(&ctx, resbuf);
 387
 388     for (int i = 0; i < 20; i++) {
 389         sprintf(hexbuf, "%02x", resbuf[i]);
 390         result += hexbuf;
 391     }
 392
 393     return result;
 394 }