libbb/sha1.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * Based on shasum from http://www.netsw.org/crypto/hash/
   4  * Majorly hacked up to use Dr Brian Gladman's sha1 code
   5  *
   6  * Copyright (C) 2002 Dr Brian Gladman <brg@gladman.me.uk>, Worcester, UK.
   7  * Copyright (C) 2003 Glenn L. McGrath
   8  * Copyright (C) 2003 Erik Andersen
   9  *
  10  * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
  11  *
  12  * ---------------------------------------------------------------------------
  13  * Issue Date: 10/11/2002
  14  *
  15  * This is a byte oriented version of SHA1 that operates on arrays of bytes
  16  * stored in memory. It runs at 22 cycles per byte on a Pentium P4 processor
  17  *
  18  * ---------------------------------------------------------------------------
  19  *
  20  * SHA256 and SHA512 parts are:
  21  * Released into the Public Domain by Ulrich Drepper <drepper@redhat.com>.
  22  * Shrank by Denys Vlasenko.
  23  *
  24  * ---------------------------------------------------------------------------
  25  *
  26  * The best way to test random blocksizes is to go to coreutils/md5_sha1_sum.c
  27  * and replace "4096" with something like "2000 + time(NULL) % 2097",
  28  * then rebuild and compare "shaNNNsum bigfile" results.
  29  */
  30
  31 #include "libbb.h"
  32
  33 #define rotl32(x,n) (((x) << (n)) | ((x) >> (32 - (n))))
  34 #define rotr32(x,n) (((x) >> (n)) | ((x) << (32 - (n))))
  35 /* for sha512: */
  36 #define rotr64(x,n) (((x) >> (n)) | ((x) << (64 - (n))))
  37 #if BB_LITTLE_ENDIAN
  38 static inline uint64_t hton64(uint64_t v)
  39 {
  40         return (((uint64_t)htonl(v)) << 32) | htonl(v >> 32);
  41 }
  42 #else
  43 #define hton64(v) (v)
  44 #endif
  45 #define ntoh64(v) hton64(v)
  46
  47 /* To check alignment gcc has an appropriate operator.  Other
  48    compilers don't.  */
  49 #if defined(__GNUC__) && __GNUC__ >= 2
  50 # define UNALIGNED_P(p,type) (((uintptr_t) p) % __alignof__(type) != 0)
  51 #else
  52 # define UNALIGNED_P(p,type) (((uintptr_t) p) % sizeof(type) != 0)
  53 #endif
  54
  55
  56 static void FAST_FUNC sha1_process_block64(sha1_ctx_t *ctx)
  57 {
  58         unsigned t;
  59         uint32_t W[80], a, b, c, d, e;
  60         const uint32_t *words = (uint32_t*) ctx->wbuffer;
  61
  62         for (t = 0; t < 16; ++t) {
  63                 W[t] = ntohl(*words);
  64                 words++;
  65         }
  66
  67         for (/*t = 16*/; t < 80; ++t) {
  68                 uint32_t T = W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16];
  69                 W[t] = rotl32(T, 1);
  70         }
  71
  72         a = ctx->hash[0];
  73         b = ctx->hash[1];
  74         c = ctx->hash[2];
  75         d = ctx->hash[3];
  76         e = ctx->hash[4];
  77
  78 /* Reverse byte order in 32-bit words   */
  79 #define ch(x,y,z)        ((z) ^ ((x) & ((y) ^ (z))))
  80 #define parity(x,y,z)    ((x) ^ (y) ^ (z))
  81 #define maj(x,y,z)       (((x) & (y)) | ((z) & ((x) | (y))))
  82 /* A normal version as set out in the FIPS. This version uses   */
  83 /* partial loop unrolling and is optimised for the Pentium 4    */
  84 #define rnd(f,k) \
  85         do { \
  86                 uint32_t T = a; \
  87                 a = rotl32(a, 5) + f(b, c, d) + e + k + W[t]; \
  88                 e = d; \
  89                 d = c; \
  90                 c = rotl32(b, 30); \
  91                 b = T; \
  92         } while (0)
  93
  94         for (t = 0; t < 20; ++t)
  95                 rnd(ch, 0x5a827999);
  96
  97         for (/*t = 20*/; t < 40; ++t)
  98                 rnd(parity, 0x6ed9eba1);
  99
 100         for (/*t = 40*/; t < 60; ++t)
 101                 rnd(maj, 0x8f1bbcdc);
 102
 103         for (/*t = 60*/; t < 80; ++t)
 104                 rnd(parity, 0xca62c1d6);
 105 #undef ch
 106 #undef parity
 107 #undef maj
 108 #undef rnd
 109
 110         ctx->hash[0] += a;
 111         ctx->hash[1] += b;
 112         ctx->hash[2] += c;
 113         ctx->hash[3] += d;
 114         ctx->hash[4] += e;
 115 }
 116
 117 /* Constants for SHA512 from FIPS 180-2:4.2.3.
 118  * SHA256 constants from FIPS 180-2:4.2.2
 119  * are the most significant half of first 64 elements
 120  * of the same array.
 121  */
 122 static const uint64_t sha_K[80] = {
 123         0x428a2f98d728ae22ULL, 0x7137449123ef65cdULL,
 124         0xb5c0fbcfec4d3b2fULL, 0xe9b5dba58189dbbcULL,
 125         0x3956c25bf348b538ULL, 0x59f111f1b605d019ULL,
 126         0x923f82a4af194f9bULL, 0xab1c5ed5da6d8118ULL,
 127         0xd807aa98a3030242ULL, 0x12835b0145706fbeULL,
 128         0x243185be4ee4b28cULL, 0x550c7dc3d5ffb4e2ULL,
 129         0x72be5d74f27b896fULL, 0x80deb1fe3b1696b1ULL,
 130         0x9bdc06a725c71235ULL, 0xc19bf174cf692694ULL,
 131         0xe49b69c19ef14ad2ULL, 0xefbe4786384f25e3ULL,
 132         0x0fc19dc68b8cd5b5ULL, 0x240ca1cc77ac9c65ULL,
 133         0x2de92c6f592b0275ULL, 0x4a7484aa6ea6e483ULL,
 134         0x5cb0a9dcbd41fbd4ULL, 0x76f988da831153b5ULL,
 135         0x983e5152ee66dfabULL, 0xa831c66d2db43210ULL,
 136         0xb00327c898fb213fULL, 0xbf597fc7beef0ee4ULL,
 137         0xc6e00bf33da88fc2ULL, 0xd5a79147930aa725ULL,
 138         0x06ca6351e003826fULL, 0x142929670a0e6e70ULL,
 139         0x27b70a8546d22ffcULL, 0x2e1b21385c26c926ULL,
 140         0x4d2c6dfc5ac42aedULL, 0x53380d139d95b3dfULL,
 141         0x650a73548baf63deULL, 0x766a0abb3c77b2a8ULL,
 142         0x81c2c92e47edaee6ULL, 0x92722c851482353bULL,
 143         0xa2bfe8a14cf10364ULL, 0xa81a664bbc423001ULL,
 144         0xc24b8b70d0f89791ULL, 0xc76c51a30654be30ULL,
 145         0xd192e819d6ef5218ULL, 0xd69906245565a910ULL,
 146         0xf40e35855771202aULL, 0x106aa07032bbd1b8ULL,
 147         0x19a4c116b8d2d0c8ULL, 0x1e376c085141ab53ULL,
 148         0x2748774cdf8eeb99ULL, 0x34b0bcb5e19b48a8ULL,
 149         0x391c0cb3c5c95a63ULL, 0x4ed8aa4ae3418acbULL,
 150         0x5b9cca4f7763e373ULL, 0x682e6ff3d6b2b8a3ULL,
 151         0x748f82ee5defb2fcULL, 0x78a5636f43172f60ULL,
 152         0x84c87814a1f0ab72ULL, 0x8cc702081a6439ecULL,
 153         0x90befffa23631e28ULL, 0xa4506cebde82bde9ULL,
 154         0xbef9a3f7b2c67915ULL, 0xc67178f2e372532bULL,
 155         0xca273eceea26619cULL, 0xd186b8c721c0c207ULL, /* [64]+ are used for sha512 only */
 156         0xeada7dd6cde0eb1eULL, 0xf57d4f7fee6ed178ULL,
 157         0x06f067aa72176fbaULL, 0x0a637dc5a2c898a6ULL,
 158         0x113f9804bef90daeULL, 0x1b710b35131c471bULL,
 159         0x28db77f523047d84ULL, 0x32caab7b40c72493ULL,
 160         0x3c9ebe0a15c9bebcULL, 0x431d67c49c100d4cULL,
 161         0x4cc5d4becb3e42b6ULL, 0x597f299cfc657e2aULL,
 162         0x5fcb6fab3ad6faecULL, 0x6c44198c4a475817ULL
 163 };
 164
 165 static void FAST_FUNC sha256_process_block64(sha256_ctx_t *ctx)
 166 {
 167         unsigned t;
 168         uint32_t W[64], a, b, c, d, e, f, g, h;
 169         const uint32_t *words = (uint32_t*) ctx->wbuffer;
 170
 171         /* Operators defined in FIPS 180-2:4.1.2.  */
 172 #define Ch(x, y, z) ((x & y) ^ (~x & z))
 173 #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
 174 #define S0(x) (rotr32(x, 2) ^ rotr32(x, 13) ^ rotr32(x, 22))
 175 #define S1(x) (rotr32(x, 6) ^ rotr32(x, 11) ^ rotr32(x, 25))
 176 #define R0(x) (rotr32(x, 7) ^ rotr32(x, 18) ^ (x >> 3))
 177 #define R1(x) (rotr32(x, 17) ^ rotr32(x, 19) ^ (x >> 10))
 178
 179         /* Compute the message schedule according to FIPS 180-2:6.2.2 step 2.  */
 180         for (t = 0; t < 16; ++t) {
 181                 W[t] = ntohl(*words);
 182                 words++;
 183         }
 184
 185         for (/*t = 16*/; t < 64; ++t)
 186                 W[t] = R1(W[t - 2]) + W[t - 7] + R0(W[t - 15]) + W[t - 16];
 187
 188         a = ctx->hash[0];
 189         b = ctx->hash[1];
 190         c = ctx->hash[2];
 191         d = ctx->hash[3];
 192         e = ctx->hash[4];
 193         f = ctx->hash[5];
 194         g = ctx->hash[6];
 195         h = ctx->hash[7];
 196
 197         /* The actual computation according to FIPS 180-2:6.2.2 step 3.  */
 198         for (t = 0; t < 64; ++t) {
 199                 /* Need to fetch upper half of sha_K[t]
 200                  * (I hope compiler is clever enough to just fetch
 201                  * upper half)
 202                  */
 203                 uint32_t K_t = sha_K[t] >> 32;
 204                 uint32_t T1 = h + S1(e) + Ch(e, f, g) + K_t + W[t];
 205                 uint32_t T2 = S0(a) + Maj(a, b, c);
 206                 h = g;
 207                 g = f;
 208                 f = e;
 209                 e = d + T1;
 210                 d = c;
 211                 c = b;
 212                 b = a;
 213                 a = T1 + T2;
 214         }
 215 #undef Ch
 216 #undef Maj
 217 #undef S0
 218 #undef S1
 219 #undef R0
 220 #undef R1
 221         /* Add the starting values of the context according to FIPS 180-2:6.2.2
 222            step 4.  */
 223         ctx->hash[0] += a;
 224         ctx->hash[1] += b;
 225         ctx->hash[2] += c;
 226         ctx->hash[3] += d;
 227         ctx->hash[4] += e;
 228         ctx->hash[5] += f;
 229         ctx->hash[6] += g;
 230         ctx->hash[7] += h;
 231 }
 232
 233 static void FAST_FUNC sha512_process_block128(sha512_ctx_t *ctx)
 234 {
 235         unsigned t;
 236         uint64_t W[80];
 237         /* On i386, having assignments here (not later as sha256 does)
 238          * produces 99 bytes smaller code with gcc 4.3.1
 239          */
 240         uint64_t a = ctx->hash[0];
 241         uint64_t b = ctx->hash[1];
 242         uint64_t c = ctx->hash[2];
 243         uint64_t d = ctx->hash[3];
 244         uint64_t e = ctx->hash[4];
 245         uint64_t f = ctx->hash[5];
 246         uint64_t g = ctx->hash[6];
 247         uint64_t h = ctx->hash[7];
 248         const uint64_t *words = (uint64_t*) ctx->wbuffer;
 249
 250         /* Operators defined in FIPS 180-2:4.1.2.  */
 251 #define Ch(x, y, z) ((x & y) ^ (~x & z))
 252 #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
 253 #define S0(x) (rotr64(x, 28) ^ rotr64(x, 34) ^ rotr64(x, 39))
 254 #define S1(x) (rotr64(x, 14) ^ rotr64(x, 18) ^ rotr64(x, 41))
 255 #define R0(x) (rotr64(x, 1) ^ rotr64(x, 8) ^ (x >> 7))
 256 #define R1(x) (rotr64(x, 19) ^ rotr64(x, 61) ^ (x >> 6))
 257
 258         /* Compute the message schedule according to FIPS 180-2:6.3.2 step 2.  */
 259         for (t = 0; t < 16; ++t) {
 260                 W[t] = ntoh64(*words);
 261                 words++;
 262         }
 263         for (/*t = 16*/; t < 80; ++t)
 264                 W[t] = R1(W[t - 2]) + W[t - 7] + R0(W[t - 15]) + W[t - 16];
 265
 266         /* The actual computation according to FIPS 180-2:6.3.2 step 3.  */
 267         for (t = 0; t < 80; ++t) {
 268                 uint64_t T1 = h + S1(e) + Ch(e, f, g) + sha_K[t] + W[t];
 269                 uint64_t T2 = S0(a) + Maj(a, b, c);
 270                 h = g;
 271                 g = f;
 272                 f = e;
 273                 e = d + T1;
 274                 d = c;
 275                 c = b;
 276                 b = a;
 277                 a = T1 + T2;
 278         }
 279 #undef Ch
 280 #undef Maj
 281 #undef S0
 282 #undef S1
 283 #undef R0
 284 #undef R1
 285         /* Add the starting values of the context according to FIPS 180-2:6.3.2
 286            step 4.  */
 287         ctx->hash[0] += a;
 288         ctx->hash[1] += b;
 289         ctx->hash[2] += c;
 290         ctx->hash[3] += d;
 291         ctx->hash[4] += e;
 292         ctx->hash[5] += f;
 293         ctx->hash[6] += g;
 294         ctx->hash[7] += h;
 295 }
 296
 297
 298 void FAST_FUNC sha1_begin(sha1_ctx_t *ctx)
 299 {
 300         ctx->hash[0] = 0x67452301;
 301         ctx->hash[1] = 0xefcdab89;
 302         ctx->hash[2] = 0x98badcfe;
 303         ctx->hash[3] = 0x10325476;
 304         ctx->hash[4] = 0xc3d2e1f0;
 305         ctx->total64 = 0;
 306         ctx->process_block = sha1_process_block64;
 307 }
 308
 309 static const uint32_t init256[] = {
 310         0x6a09e667,
 311         0xbb67ae85,
 312         0x3c6ef372,
 313         0xa54ff53a,
 314         0x510e527f,
 315         0x9b05688c,
 316         0x1f83d9ab,
 317         0x5be0cd19
 318 };
 319 static const uint32_t init512_lo[] = {
 320         0xf3bcc908,
 321         0x84caa73b,
 322         0xfe94f82b,
 323         0x5f1d36f1,
 324         0xade682d1,
 325         0x2b3e6c1f,
 326         0xfb41bd6b,
 327         0x137e2179
 328 };
 329
 330 /* Initialize structure containing state of computation.
 331    (FIPS 180-2:5.3.2)  */
 332 void FAST_FUNC sha256_begin(sha256_ctx_t *ctx)
 333 {
 334         memcpy(ctx->hash, init256, sizeof(init256));
 335         ctx->total64 = 0;
 336         ctx->process_block = sha256_process_block64;
 337 }
 338
 339 /* Initialize structure containing state of computation.
 340    (FIPS 180-2:5.3.3)  */
 341 void FAST_FUNC sha512_begin(sha512_ctx_t *ctx)
 342 {
 343         int i;
 344         for (i = 0; i < 8; i++)
 345                 ctx->hash[i] = ((uint64_t)(init256[i]) << 32) + init512_lo[i];
 346         ctx->total64[0] = ctx->total64[1] = 0;
 347 }
 348
 349
 350 /* Used also for sha256 */
 351 void FAST_FUNC sha1_hash(const void *buffer, size_t len, sha1_ctx_t *ctx)
 352 {
 353         unsigned in_buf = ctx->total64 & 63;
 354         unsigned add = 64 - in_buf;
 355
 356         ctx->total64 += len;
 357
 358         while (len >= add) {    /* transfer whole blocks while possible  */
 359                 memcpy(ctx->wbuffer + in_buf, buffer, add);
 360                 buffer = (const char *)buffer + add;
 361                 len -= add;
 362                 add = 64;
 363                 in_buf = 0;
 364                 ctx->process_block(ctx);
 365         }
 366
 367         memcpy(ctx->wbuffer + in_buf, buffer, len);
 368 }
 369
 370 void FAST_FUNC sha512_hash(const void *buffer, size_t len, sha512_ctx_t *ctx)
 371 {
 372         unsigned in_buf = ctx->total64[0] & 127;
 373         unsigned add = 128 - in_buf;
 374
 375         /* First increment the byte count.  FIPS 180-2 specifies the possible
 376            length of the file up to 2^128 _bits_.
 377            We compute the number of _bytes_ and convert to bits later.  */
 378         ctx->total64[0] += len;
 379         if (ctx->total64[0] < len)
 380                 ctx->total64[1]++;
 381
 382         while (len >= add) {    /* transfer whole blocks while possible  */
 383                 memcpy(ctx->wbuffer + in_buf, buffer, add);
 384                 buffer = (const char *)buffer + add;
 385                 len -= add;
 386                 add = 128;
 387                 in_buf = 0;
 388                 sha512_process_block128(ctx);
 389         }
 390
 391         memcpy(ctx->wbuffer + in_buf, buffer, len);
 392 }
 393
 394
 395 /* Used also for sha256 */
 396 void FAST_FUNC sha1_end(void *resbuf, sha1_ctx_t *ctx)
 397 {
 398         unsigned i, pad, in_buf;
 399
 400         in_buf = ctx->total64 & 63;
 401         /* Pad the buffer to the next 64-byte boundary with 0x80,0,0,0... */
 402         ctx->wbuffer[in_buf++] = 0x80;
 403
 404         /* This loop iterates either once or twice, no more, no less */
 405         while (1) {
 406                 pad = 64 - in_buf;
 407                 memset(ctx->wbuffer + in_buf, 0, pad);
 408                 in_buf = 0;
 409                 /* Do we have enough space for the length count? */
 410                 if (pad >= 8) {
 411                         /* Store the 64-bit counter of bits in the buffer in BE format */
 412                         uint64_t t = ctx->total64 << 3;
 413                         t = hton64(t);
 414                         /* wbuffer is suitably aligned for this */
 415                         *(uint64_t *) (&ctx->wbuffer[64 - 8]) = t;
 416                 }
 417                 ctx->process_block(ctx);
 418                 if (pad >= 8)
 419                         break;
 420         }
 421
 422         in_buf = (ctx->process_block == sha1_process_block64) ? 5 : 8;
 423         /* This way we do not impose alignment constraints on resbuf: */
 424 #if BB_LITTLE_ENDIAN
 425         for (i = 0; i < in_buf; ++i)
 426                 ctx->hash[i] = htonl(ctx->hash[i]);
 427 #endif
 428         memcpy(resbuf, ctx->hash, sizeof(ctx->hash[0]) * in_buf);
 429 }
 430
 431 void FAST_FUNC sha512_end(void *resbuf, sha512_ctx_t *ctx)
 432 {
 433         unsigned i, pad, in_buf;
 434
 435         in_buf = ctx->total64[0] & 127;
 436         /* Pad the buffer to the next 128-byte boundary with 0x80,0,0,0...
 437          * (FIPS 180-2:5.1.2)
 438          */
 439         ctx->wbuffer[in_buf++] = 0x80;
 440
 441         while (1) {
 442                 pad = 128 - in_buf;
 443                 memset(ctx->wbuffer + in_buf, 0, pad);
 444                 in_buf = 0;
 445                 if (pad >= 16) {
 446                         /* Store the 128-bit counter of bits in the buffer in BE format */
 447                         uint64_t t;
 448                         t = ctx->total64[0] << 3;
 449                         t = hton64(t);
 450                         *(uint64_t *) (&ctx->wbuffer[128 - 8]) = t;
 451                         t = (ctx->total64[1] << 3) | (ctx->total64[0] >> 61);
 452                         t = hton64(t);
 453                         *(uint64_t *) (&ctx->wbuffer[128 - 16]) = t;
 454                 }
 455                 sha512_process_block128(ctx);
 456                 if (pad >= 16)
 457                         break;
 458         }
 459
 460 #if BB_LITTLE_ENDIAN
 461         for (i = 0; i < ARRAY_SIZE(ctx->hash); ++i)
 462                 ctx->hash[i] = hton64(ctx->hash[i]);
 463 #endif
 464         memcpy(resbuf, ctx->hash, sizeof(ctx->hash));
 465 }