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 #if BB_BIG_ENDIAN
 201                 uint32_t K_t = ((uint32_t*)(sha_K + t))[0];
 202 #else
 203                 uint32_t K_t = ((uint32_t*)(sha_K + t))[1];
 204 #endif
 205                 uint32_t T1 = h + S1(e) + Ch(e, f, g) + K_t + W[t];
 206                 uint32_t T2 = S0(a) + Maj(a, b, c);
 207                 h = g;
 208                 g = f;
 209                 f = e;
 210                 e = d + T1;
 211                 d = c;
 212                 c = b;
 213                 b = a;
 214                 a = T1 + T2;
 215         }
 216 #undef Ch
 217 #undef Maj
 218 #undef S0
 219 #undef S1
 220 #undef R0
 221 #undef R1
 222         /* Add the starting values of the context according to FIPS 180-2:6.2.2
 223            step 4.  */
 224         ctx->hash[0] += a;
 225         ctx->hash[1] += b;
 226         ctx->hash[2] += c;
 227         ctx->hash[3] += d;
 228         ctx->hash[4] += e;
 229         ctx->hash[5] += f;
 230         ctx->hash[6] += g;
 231         ctx->hash[7] += h;
 232 }
 233
 234 static void FAST_FUNC sha512_process_block128(sha512_ctx_t *ctx)
 235 {
 236         unsigned t;
 237         uint64_t W[80];
 238         /* On i386, having assignments here (not later as sha256 does)
 239          * produces 99 bytes smaller code with gcc 4.3.1
 240          */
 241         uint64_t a = ctx->hash[0];
 242         uint64_t b = ctx->hash[1];
 243         uint64_t c = ctx->hash[2];
 244         uint64_t d = ctx->hash[3];
 245         uint64_t e = ctx->hash[4];
 246         uint64_t f = ctx->hash[5];
 247         uint64_t g = ctx->hash[6];
 248         uint64_t h = ctx->hash[7];
 249         const uint64_t *words = (uint64_t*) ctx->wbuffer;
 250
 251         /* Operators defined in FIPS 180-2:4.1.2.  */
 252 #define Ch(x, y, z) ((x & y) ^ (~x & z))
 253 #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
 254 #define S0(x) (rotr64(x, 28) ^ rotr64(x, 34) ^ rotr64(x, 39))
 255 #define S1(x) (rotr64(x, 14) ^ rotr64(x, 18) ^ rotr64(x, 41))
 256 #define R0(x) (rotr64(x, 1) ^ rotr64(x, 8) ^ (x >> 7))
 257 #define R1(x) (rotr64(x, 19) ^ rotr64(x, 61) ^ (x >> 6))
 258
 259         /* Compute the message schedule according to FIPS 180-2:6.3.2 step 2.  */
 260         for (t = 0; t < 16; ++t) {
 261                 W[t] = ntoh64(*words);
 262                 words++;
 263         }
 264         for (/*t = 16*/; t < 80; ++t)
 265                 W[t] = R1(W[t - 2]) + W[t - 7] + R0(W[t - 15]) + W[t - 16];
 266
 267         /* The actual computation according to FIPS 180-2:6.3.2 step 3.  */
 268         for (t = 0; t < 80; ++t) {
 269                 uint64_t T1 = h + S1(e) + Ch(e, f, g) + sha_K[t] + W[t];
 270                 uint64_t T2 = S0(a) + Maj(a, b, c);
 271                 h = g;
 272                 g = f;
 273                 f = e;
 274                 e = d + T1;
 275                 d = c;
 276                 c = b;
 277                 b = a;
 278                 a = T1 + T2;
 279         }
 280 #undef Ch
 281 #undef Maj
 282 #undef S0
 283 #undef S1
 284 #undef R0
 285 #undef R1
 286         /* Add the starting values of the context according to FIPS 180-2:6.3.2
 287            step 4.  */
 288         ctx->hash[0] += a;
 289         ctx->hash[1] += b;
 290         ctx->hash[2] += c;
 291         ctx->hash[3] += d;
 292         ctx->hash[4] += e;
 293         ctx->hash[5] += f;
 294         ctx->hash[6] += g;
 295         ctx->hash[7] += h;
 296 }
 297
 298
 299 void FAST_FUNC sha1_begin(sha1_ctx_t *ctx)
 300 {
 301         ctx->hash[0] = 0x67452301;
 302         ctx->hash[1] = 0xefcdab89;
 303         ctx->hash[2] = 0x98badcfe;
 304         ctx->hash[3] = 0x10325476;
 305         ctx->hash[4] = 0xc3d2e1f0;
 306         ctx->total64 = 0;
 307         ctx->process_block = sha1_process_block64;
 308 }
 309
 310 static const uint32_t init256[] = {
 311         0x6a09e667,
 312         0xbb67ae85,
 313         0x3c6ef372,
 314         0xa54ff53a,
 315         0x510e527f,
 316         0x9b05688c,
 317         0x1f83d9ab,
 318         0x5be0cd19
 319 };
 320 static const uint32_t init512_lo[] = {
 321         0xf3bcc908,
 322         0x84caa73b,
 323         0xfe94f82b,
 324         0x5f1d36f1,
 325         0xade682d1,
 326         0x2b3e6c1f,
 327         0xfb41bd6b,
 328         0x137e2179
 329 };
 330
 331 /* Initialize structure containing state of computation.
 332    (FIPS 180-2:5.3.2)  */
 333 void FAST_FUNC sha256_begin(sha256_ctx_t *ctx)
 334 {
 335         memcpy(ctx->hash, init256, sizeof(init256));
 336         ctx->total64 = 0;
 337         ctx->process_block = sha256_process_block64;
 338 }
 339
 340 /* Initialize structure containing state of computation.
 341    (FIPS 180-2:5.3.3)  */
 342 void FAST_FUNC sha512_begin(sha512_ctx_t *ctx)
 343 {
 344         int i;
 345         for (i = 0; i < 8; i++)
 346                 ctx->hash[i] = ((uint64_t)(init256[i]) << 32) + init512_lo[i];
 347         ctx->total64[0] = ctx->total64[1] = 0;
 348 }
 349
 350
 351 /* Used also for sha256 */
 352 void FAST_FUNC sha1_hash(const void *buffer, size_t len, sha1_ctx_t *ctx)
 353 {
 354         unsigned in_buf = ctx->total64 & 63;
 355         unsigned add = 64 - in_buf;
 356
 357         ctx->total64 += len;
 358
 359         while (len >= add) {    /* transfer whole blocks while possible  */
 360                 memcpy(ctx->wbuffer + in_buf, buffer, add);
 361                 buffer = (const char *)buffer + add;
 362                 len -= add;
 363                 add = 64;
 364                 in_buf = 0;
 365                 ctx->process_block(ctx);
 366         }
 367
 368         memcpy(ctx->wbuffer + in_buf, buffer, len);
 369 }
 370
 371 void FAST_FUNC sha512_hash(const void *buffer, size_t len, sha512_ctx_t *ctx)
 372 {
 373         unsigned in_buf = ctx->total64[0] & 127;
 374         unsigned add = 128 - in_buf;
 375
 376         /* First increment the byte count.  FIPS 180-2 specifies the possible
 377            length of the file up to 2^128 _bits_.
 378            We compute the number of _bytes_ and convert to bits later.  */
 379         ctx->total64[0] += len;
 380         if (ctx->total64[0] < len)
 381                 ctx->total64[1]++;
 382
 383         while (len >= add) {    /* transfer whole blocks while possible  */
 384                 memcpy(ctx->wbuffer + in_buf, buffer, add);
 385                 buffer = (const char *)buffer + add;
 386                 len -= add;
 387                 add = 128;
 388                 in_buf = 0;
 389                 sha512_process_block128(ctx);
 390         }
 391
 392         memcpy(ctx->wbuffer + in_buf, buffer, len);
 393 }
 394
 395
 396 /* Used also for sha256 */
 397 void FAST_FUNC sha1_end(void *resbuf, sha1_ctx_t *ctx)
 398 {
 399         unsigned i, pad, in_buf;
 400
 401         in_buf = ctx->total64 & 63;
 402         /* Pad the buffer to the next 64-byte boundary with 0x80,0,0,0... */
 403         ctx->wbuffer[in_buf++] = 0x80;
 404
 405         /* This loop iterates either once or twice, no more, no less */
 406         while (1) {
 407                 pad = 64 - in_buf;
 408                 memset(ctx->wbuffer + in_buf, 0, pad);
 409                 in_buf = 0;
 410                 /* Do we have enough space for the length count? */
 411                 if (pad >= 8) {
 412                         /* Store the 64-bit counter of bits in the buffer in BE format */
 413                         uint64_t t = ctx->total64 << 3;
 414                         t = hton64(t);
 415                         /* wbuffer is suitably aligned for this */
 416                         *(uint64_t *) (&ctx->wbuffer[64 - 8]) = t;
 417                 }
 418                 ctx->process_block(ctx);
 419                 if (pad >= 8)
 420                         break;
 421         }
 422
 423         in_buf = (ctx->process_block == sha1_process_block64) ? 5 : 8;
 424         /* This way we do not impose alignment constraints on resbuf: */
 425 #if BB_LITTLE_ENDIAN
 426         for (i = 0; i < in_buf; ++i)
 427                 ctx->hash[i] = htonl(ctx->hash[i]);
 428 #endif
 429         memcpy(resbuf, ctx->hash, sizeof(ctx->hash[0]) * in_buf);
 430 }
 431
 432 void FAST_FUNC sha512_end(void *resbuf, sha512_ctx_t *ctx)
 433 {
 434         unsigned i, pad, in_buf;
 435
 436         in_buf = ctx->total64[0] & 127;
 437         /* Pad the buffer to the next 128-byte boundary with 0x80,0,0,0...
 438          * (FIPS 180-2:5.1.2)
 439          */
 440         ctx->wbuffer[in_buf++] = 0x80;
 441
 442         while (1) {
 443                 pad = 128 - in_buf;
 444                 memset(ctx->wbuffer + in_buf, 0, pad);
 445                 in_buf = 0;
 446                 if (pad >= 16) {
 447                         /* Store the 128-bit counter of bits in the buffer in BE format */
 448                         uint64_t t;
 449                         t = ctx->total64[0] << 3;
 450                         t = hton64(t);
 451                         *(uint64_t *) (&ctx->wbuffer[128 - 8]) = t;
 452                         t = (ctx->total64[1] << 3) | (ctx->total64[0] >> 61);
 453                         t = hton64(t);
 454                         *(uint64_t *) (&ctx->wbuffer[128 - 16]) = t;
 455                 }
 456                 sha512_process_block128(ctx);
 457                 if (pad >= 16)
 458                         break;
 459         }
 460
 461 #if BB_LITTLE_ENDIAN
 462         for (i = 0; i < ARRAY_SIZE(ctx->hash); ++i)
 463                 ctx->hash[i] = hton64(ctx->hash[i]);
 464 #endif
 465         memcpy(resbuf, ctx->hash, sizeof(ctx->hash));
 466 }