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 #define SHA1_BLOCK_SIZE  64
  57 #define SHA1_MASK        (SHA1_BLOCK_SIZE - 1)
  58
  59 static void FAST_FUNC sha1_process_block64(sha1_ctx_t *ctx)
  60 {
  61         unsigned i;
  62         uint32_t w[80], a, b, c, d, e, t;
  63         uint32_t *words;
  64
  65         words = (uint32_t*) ctx->wbuffer;
  66         for (i = 0; i < SHA1_BLOCK_SIZE / 4; ++i) {
  67                 w[i] = ntohl(*words);
  68                 words++;
  69         }
  70
  71         for (/*i = SHA1_BLOCK_SIZE / 4*/; i < 80; ++i) {
  72                 t = w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16];
  73                 w[i] = rotl32(t, 1);
  74         }
  75
  76         a = ctx->hash[0];
  77         b = ctx->hash[1];
  78         c = ctx->hash[2];
  79         d = ctx->hash[3];
  80         e = ctx->hash[4];
  81
  82 /* Reverse byte order in 32-bit words   */
  83 #define ch(x,y,z)        ((z) ^ ((x) & ((y) ^ (z))))
  84 #define parity(x,y,z)    ((x) ^ (y) ^ (z))
  85 #define maj(x,y,z)       (((x) & (y)) | ((z) & ((x) | (y))))
  86 /* A normal version as set out in the FIPS. This version uses   */
  87 /* partial loop unrolling and is optimised for the Pentium 4    */
  88 #define rnd(f,k) \
  89         do { \
  90                 t = a; a = rotl32(a,5) + f(b,c,d) + e + k + w[i]; \
  91                 e = d; d = c; c = rotl32(b, 30); b = t; \
  92         } while (0)
  93
  94         for (i = 0; i < 20; ++i)
  95                 rnd(ch, 0x5a827999);
  96
  97         for (/*i = 20*/; i < 40; ++i)
  98                 rnd(parity, 0x6ed9eba1);
  99
 100         for (/*i = 40*/; i < 60; ++i)
 101                 rnd(maj, 0x8f1bbcdc);
 102
 103         for (/*i = 60*/; i < 80; ++i)
 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 SHA256 from FIPS 180-2:4.2.2.  */
 118 static const uint32_t K256[80] = {
 119         0x428a2f98, 0x71374491,
 120         0xb5c0fbcf, 0xe9b5dba5,
 121         0x3956c25b, 0x59f111f1,
 122         0x923f82a4, 0xab1c5ed5,
 123         0xd807aa98, 0x12835b01,
 124         0x243185be, 0x550c7dc3,
 125         0x72be5d74, 0x80deb1fe,
 126         0x9bdc06a7, 0xc19bf174,
 127         0xe49b69c1, 0xefbe4786,
 128         0x0fc19dc6, 0x240ca1cc,
 129         0x2de92c6f, 0x4a7484aa,
 130         0x5cb0a9dc, 0x76f988da,
 131         0x983e5152, 0xa831c66d,
 132         0xb00327c8, 0xbf597fc7,
 133         0xc6e00bf3, 0xd5a79147,
 134         0x06ca6351, 0x14292967,
 135         0x27b70a85, 0x2e1b2138,
 136         0x4d2c6dfc, 0x53380d13,
 137         0x650a7354, 0x766a0abb,
 138         0x81c2c92e, 0x92722c85,
 139         0xa2bfe8a1, 0xa81a664b,
 140         0xc24b8b70, 0xc76c51a3,
 141         0xd192e819, 0xd6990624,
 142         0xf40e3585, 0x106aa070,
 143         0x19a4c116, 0x1e376c08,
 144         0x2748774c, 0x34b0bcb5,
 145         0x391c0cb3, 0x4ed8aa4a,
 146         0x5b9cca4f, 0x682e6ff3,
 147         0x748f82ee, 0x78a5636f,
 148         0x84c87814, 0x8cc70208,
 149         0x90befffa, 0xa4506ceb,
 150         0xbef9a3f7, 0xc67178f2,
 151         0xca273ece, 0xd186b8c7, /* [64]+ are used for sha512 only */
 152         0xeada7dd6, 0xf57d4f7f,
 153         0x06f067aa, 0x0a637dc5,
 154         0x113f9804, 0x1b710b35,
 155         0x28db77f5, 0x32caab7b,
 156         0x3c9ebe0a, 0x431d67c4,
 157         0x4cc5d4be, 0x597f299c,
 158         0x5fcb6fab, 0x6c44198c
 159 };
 160 /* Constants for SHA512 from FIPS 180-2:4.2.3.  */
 161 static const uint32_t K512_lo[80] = {
 162         0xd728ae22, 0x23ef65cd,
 163         0xec4d3b2f, 0x8189dbbc,
 164         0xf348b538, 0xb605d019,
 165         0xaf194f9b, 0xda6d8118,
 166         0xa3030242, 0x45706fbe,
 167         0x4ee4b28c, 0xd5ffb4e2,
 168         0xf27b896f, 0x3b1696b1,
 169         0x25c71235, 0xcf692694,
 170         0x9ef14ad2, 0x384f25e3,
 171         0x8b8cd5b5, 0x77ac9c65,
 172         0x592b0275, 0x6ea6e483,
 173         0xbd41fbd4, 0x831153b5,
 174         0xee66dfab, 0x2db43210,
 175         0x98fb213f, 0xbeef0ee4,
 176         0x3da88fc2, 0x930aa725,
 177         0xe003826f, 0x0a0e6e70,
 178         0x46d22ffc, 0x5c26c926,
 179         0x5ac42aed, 0x9d95b3df,
 180         0x8baf63de, 0x3c77b2a8,
 181         0x47edaee6, 0x1482353b,
 182         0x4cf10364, 0xbc423001,
 183         0xd0f89791, 0x0654be30,
 184         0xd6ef5218, 0x5565a910,
 185         0x5771202a, 0x32bbd1b8,
 186         0xb8d2d0c8, 0x5141ab53,
 187         0xdf8eeb99, 0xe19b48a8,
 188         0xc5c95a63, 0xe3418acb,
 189         0x7763e373, 0xd6b2b8a3,
 190         0x5defb2fc, 0x43172f60,
 191         0xa1f0ab72, 0x1a6439ec,
 192         0x23631e28, 0xde82bde9,
 193         0xb2c67915, 0xe372532b,
 194         0xea26619c, 0x21c0c207,
 195         0xcde0eb1e, 0xee6ed178,
 196         0x72176fba, 0xa2c898a6,
 197         0xbef90dae, 0x131c471b,
 198         0x23047d84, 0x40c72493,
 199         0x15c9bebc, 0x9c100d4c,
 200         0xcb3e42b6, 0xfc657e2a,
 201         0x3ad6faec, 0x4a475817
 202 };
 203
 204 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 205    LEN is rounded _down_ to 64.  */
 206 static void FAST_FUNC sha256_process_block64(sha256_ctx_t *ctx)
 207 {
 208         unsigned t;
 209         uint32_t W[64];
 210         uint32_t a = ctx->hash[0];
 211         uint32_t b = ctx->hash[1];
 212         uint32_t c = ctx->hash[2];
 213         uint32_t d = ctx->hash[3];
 214         uint32_t e = ctx->hash[4];
 215         uint32_t f = ctx->hash[5];
 216         uint32_t g = ctx->hash[6];
 217         uint32_t h = ctx->hash[7];
 218         const uint32_t *words = (uint32_t*) ctx->wbuffer;
 219
 220         /* Operators defined in FIPS 180-2:4.1.2.  */
 221 #define Ch(x, y, z) ((x & y) ^ (~x & z))
 222 #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
 223 #define S0(x) (rotr32(x, 2) ^ rotr32(x, 13) ^ rotr32(x, 22))
 224 #define S1(x) (rotr32(x, 6) ^ rotr32(x, 11) ^ rotr32(x, 25))
 225 #define R0(x) (rotr32(x, 7) ^ rotr32(x, 18) ^ (x >> 3))
 226 #define R1(x) (rotr32(x, 17) ^ rotr32(x, 19) ^ (x >> 10))
 227
 228         /* Compute the message schedule according to FIPS 180-2:6.2.2 step 2.  */
 229         for (t = 0; t < 16; ++t) {
 230                 W[t] = ntohl(*words);
 231                 words++;
 232         }
 233
 234         for (/*t = 16*/; t < 64; ++t)
 235                 W[t] = R1(W[t - 2]) + W[t - 7] + R0(W[t - 15]) + W[t - 16];
 236
 237         /* The actual computation according to FIPS 180-2:6.2.2 step 3.  */
 238         for (t = 0; t < 64; ++t) {
 239                 uint32_t T1 = h + S1(e) + Ch(e, f, g) + K256[t] + W[t];
 240                 uint32_t T2 = S0(a) + Maj(a, b, c);
 241                 h = g;
 242                 g = f;
 243                 f = e;
 244                 e = d + T1;
 245                 d = c;
 246                 c = b;
 247                 b = a;
 248                 a = T1 + T2;
 249         }
 250 #undef Ch
 251 #undef Maj
 252 #undef S0
 253 #undef S1
 254 #undef R0
 255 #undef R1
 256         /* Add the starting values of the context according to FIPS 180-2:6.2.2
 257            step 4.  */
 258         ctx->hash[0] += a;
 259         ctx->hash[1] += b;
 260         ctx->hash[2] += c;
 261         ctx->hash[3] += d;
 262         ctx->hash[4] += e;
 263         ctx->hash[5] += f;
 264         ctx->hash[6] += g;
 265         ctx->hash[7] += h;
 266 }
 267 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 268    LEN is rounded _down_ to 128.  */
 269 static void FAST_FUNC sha512_process_block128(sha512_ctx_t *ctx)
 270 {
 271         unsigned t;
 272         uint64_t W[80];
 273         uint64_t a = ctx->hash[0];
 274         uint64_t b = ctx->hash[1];
 275         uint64_t c = ctx->hash[2];
 276         uint64_t d = ctx->hash[3];
 277         uint64_t e = ctx->hash[4];
 278         uint64_t f = ctx->hash[5];
 279         uint64_t g = ctx->hash[6];
 280         uint64_t h = ctx->hash[7];
 281         const uint64_t *words = (uint64_t*) ctx->wbuffer;
 282
 283         /* Operators defined in FIPS 180-2:4.1.2.  */
 284 #define Ch(x, y, z) ((x & y) ^ (~x & z))
 285 #define Maj(x, y, z) ((x & y) ^ (x & z) ^ (y & z))
 286 #define S0(x) (rotr64(x, 28) ^ rotr64(x, 34) ^ rotr64(x, 39))
 287 #define S1(x) (rotr64(x, 14) ^ rotr64(x, 18) ^ rotr64(x, 41))
 288 #define R0(x) (rotr64(x, 1) ^ rotr64(x, 8) ^ (x >> 7))
 289 #define R1(x) (rotr64(x, 19) ^ rotr64(x, 61) ^ (x >> 6))
 290
 291         /* Compute the message schedule according to FIPS 180-2:6.3.2 step 2.  */
 292         for (t = 0; t < 16; ++t) {
 293                 W[t] = ntoh64(*words);
 294                 words++;
 295         }
 296         for (/*t = 16*/; t < 80; ++t)
 297                 W[t] = R1(W[t - 2]) + W[t - 7] + R0(W[t - 15]) + W[t - 16];
 298
 299         /* The actual computation according to FIPS 180-2:6.3.2 step 3.  */
 300         for (t = 0; t < 80; ++t) {
 301                 uint64_t K512_t = ((uint64_t)(K256[t]) << 32) + K512_lo[t];
 302                 uint64_t T1 = h + S1(e) + Ch(e, f, g) + K512_t + W[t];
 303                 uint64_t T2 = S0(a) + Maj(a, b, c);
 304                 h = g;
 305                 g = f;
 306                 f = e;
 307                 e = d + T1;
 308                 d = c;
 309                 c = b;
 310                 b = a;
 311                 a = T1 + T2;
 312         }
 313 #undef Ch
 314 #undef Maj
 315 #undef S0
 316 #undef S1
 317 #undef R0
 318 #undef R1
 319         /* Add the starting values of the context according to FIPS 180-2:6.3.2
 320            step 4.  */
 321         ctx->hash[0] += a;
 322         ctx->hash[1] += b;
 323         ctx->hash[2] += c;
 324         ctx->hash[3] += d;
 325         ctx->hash[4] += e;
 326         ctx->hash[5] += f;
 327         ctx->hash[6] += g;
 328         ctx->hash[7] += h;
 329 }
 330
 331
 332 void FAST_FUNC sha1_begin(sha1_ctx_t *ctx)
 333 {
 334         ctx->hash[0] = 0x67452301;
 335         ctx->hash[1] = 0xefcdab89;
 336         ctx->hash[2] = 0x98badcfe;
 337         ctx->hash[3] = 0x10325476;
 338         ctx->hash[4] = 0xc3d2e1f0;
 339         ctx->total64 = 0;
 340         ctx->process_block = sha1_process_block64;
 341 }
 342
 343 static const uint32_t init256[] = {
 344         0x6a09e667,
 345         0xbb67ae85,
 346         0x3c6ef372,
 347         0xa54ff53a,
 348         0x510e527f,
 349         0x9b05688c,
 350         0x1f83d9ab,
 351         0x5be0cd19
 352 };
 353 static const uint32_t init512_lo[] = {
 354         0xf3bcc908,
 355         0x84caa73b,
 356         0xfe94f82b,
 357         0x5f1d36f1,
 358         0xade682d1,
 359         0x2b3e6c1f,
 360         0xfb41bd6b,
 361         0x137e2179
 362 };
 363 /* Initialize structure containing state of computation.
 364    (FIPS 180-2:5.3.2)  */
 365 void FAST_FUNC sha256_begin(sha256_ctx_t *ctx)
 366 {
 367         memcpy(ctx->hash, init256, sizeof(init256));
 368         ctx->total64 = 0;
 369         ctx->process_block = sha256_process_block64;
 370 }
 371 /* Initialize structure containing state of computation.
 372    (FIPS 180-2:5.3.3)  */
 373 void FAST_FUNC sha512_begin(sha512_ctx_t *ctx)
 374 {
 375         int i;
 376         for (i = 0; i < 8; i++)
 377                 ctx->hash[i] = ((uint64_t)(init256[i]) << 32) + init512_lo[i];
 378         ctx->total64[0] = ctx->total64[1] = 0;
 379 }
 380
 381
 382 void FAST_FUNC sha1_hash(const void *buffer, size_t len, sha1_ctx_t *ctx)
 383 {
 384         unsigned in_buf = ctx->total64 & SHA1_MASK;
 385         unsigned add = SHA1_BLOCK_SIZE - in_buf;
 386
 387         ctx->total64 += len;
 388
 389         while (len >= add) {    /* transfer whole blocks while possible  */
 390                 memcpy(ctx->wbuffer + in_buf, buffer, add);
 391                 buffer = (const char *)buffer + add;
 392                 len -= add;
 393                 add = SHA1_BLOCK_SIZE;
 394                 in_buf = 0;
 395                 ctx->process_block(ctx);
 396         }
 397
 398         memcpy(ctx->wbuffer + in_buf, buffer, len);
 399 }
 400
 401 void FAST_FUNC sha512_hash(const void *buffer, size_t len, sha512_ctx_t *ctx)
 402 {
 403         unsigned in_buf = ctx->total64[0] & 127;
 404         unsigned add = 128 - in_buf;
 405
 406         /* First increment the byte count.  FIPS 180-2 specifies the possible
 407            length of the file up to 2^128 _bits_.
 408            We compute the number of _bytes_ and convert to bits later.  */
 409         ctx->total64[0] += len;
 410         if (ctx->total64[0] < len)
 411                 ctx->total64[1]++;
 412
 413         while (len >= add) {    /* transfer whole blocks while possible  */
 414                 memcpy(ctx->wbuffer + in_buf, buffer, add);
 415                 buffer = (const char *)buffer + add;
 416                 len -= add;
 417                 add = 128;
 418                 in_buf = 0;
 419                 sha512_process_block128(ctx);
 420         }
 421
 422         memcpy(ctx->wbuffer + in_buf, buffer, len);
 423 }
 424
 425
 426 void FAST_FUNC sha1_end(void *resbuf, sha1_ctx_t *ctx)
 427 {
 428         unsigned i, pad, in_buf;
 429
 430         in_buf = ctx->total64 & SHA1_MASK;
 431         /* Pad the buffer to the next 64-byte boundary with 0x80,0,0,0... */
 432         ctx->wbuffer[in_buf++] = 0x80;
 433
 434         /* This loop iterates either once or twice, no more, no less */
 435         while (1) {
 436                 pad = SHA1_BLOCK_SIZE - in_buf;
 437                 memset(ctx->wbuffer + in_buf, 0, pad);
 438                 in_buf = 0;
 439                 /* Do we have enough space for the length count? */
 440                 if (pad >= 8) {
 441                         /* Store the 64-bit counter of bits in the buffer in BE format */
 442                         uint64_t t = ctx->total64 << 3;
 443                         t = hton64(t);
 444                         /* wbuffer is suitably aligned for this */
 445                         *(uint64_t *) (&ctx->wbuffer[SHA1_BLOCK_SIZE - 8]) = t;
 446                 }
 447                 ctx->process_block(ctx);
 448                 if (pad >= 8)
 449                         break;
 450         }
 451
 452         in_buf = (ctx->process_block == sha1_process_block64) ? 5 : 8;
 453         /* This way we do not impose alignment constraints on resbuf: */
 454 #if BB_LITTLE_ENDIAN
 455         for (i = 0; i < in_buf; ++i)
 456                 ctx->hash[i] = htonl(ctx->hash[i]);
 457 #endif
 458         memcpy(resbuf, ctx->hash, sizeof(ctx->hash[0]) * in_buf);
 459 }
 460
 461 void FAST_FUNC sha512_end(void *resbuf, sha512_ctx_t *ctx)
 462 {
 463         unsigned i, pad, in_buf;
 464
 465         in_buf = ctx->total64[0] & 127;
 466         /* Pad the buffer to the next 128-byte boundary with 0x80,0,0,0...
 467          * (FIPS 180-2:5.1.2)
 468          */
 469         ctx->wbuffer[in_buf++] = 0x80;
 470
 471         while (1) {
 472                 pad = 128 - in_buf;
 473                 memset(ctx->wbuffer + in_buf, 0, pad);
 474                 in_buf = 0;
 475                 if (pad >= 16) {
 476                         /* Store the 128-bit counter of bits in the buffer in BE format */
 477                         uint64_t t;
 478                         t = ctx->total64[0] << 3;
 479                         t = hton64(t);
 480                         *(uint64_t *) (&ctx->wbuffer[128 - 8]) = t;
 481                         t = (ctx->total64[1] << 3) | (ctx->total64[0] >> 61);
 482                         t = hton64(t);
 483                         *(uint64_t *) (&ctx->wbuffer[128 - 16]) = t;
 484                 }
 485                 sha512_process_block128(ctx);
 486                 if (pad >= 16)
 487                         break;
 488         }
 489
 490 #if BB_LITTLE_ENDIAN
 491         for (i = 0; i < ARRAY_SIZE(ctx->hash); ++i)
 492                 ctx->hash[i] = hton64(ctx->hash[i]);
 493 #endif
 494         memcpy(resbuf, ctx->hash, sizeof(ctx->hash));
 495 }