libkern/crypto/sha1.c

   1 /*
   2  * Copyright (c) 2000-2006 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 /*
  30  * This SHA1 code is based on the basic framework from the reference
  31  * implementation for MD5.  That implementation is Copyright (C)
  32  * 1991-2, RSA Data Security, Inc. Created 1991. All rights reserved.
  33  *
  34  * License to copy and use this software is granted provided that it
  35  * is identified as the "RSA Data Security, Inc. MD5 Message-Digest
  36  * Algorithm" in all material mentioning or referencing this software
  37  * or this function.
  38  *
  39  * License is also granted to make and use derivative works provided
  40  * that such works are identified as "derived from the RSA Data
  41  * Security, Inc. MD5 Message-Digest Algorithm" in all material
  42  * mentioning or referencing the derived work.
  43  *
  44  * RSA Data Security, Inc. makes no representations concerning either
  45  * the merchantability of this software or the suitability of this
  46  * software for any particular purpose. It is provided "as is"
  47  * without express or implied warranty of any kind.
  48  *
  49  * These notices must be retained in any copies of any part of this
  50  * documentation and/or software.
  51  *
  52  * Based on the FIPS 180-1: Secure Hash Algorithm (SHA-1) available at
  53  * http://www.itl.nist.gov/div897/pubs/fip180-1.htm
  54  */
  55
  56 #include <sys/types.h>
  57 #include <sys/systm.h>
  58 #include <libkern/crypto/sha1.h>
  59
  60 #define memset(x, y, z) bzero(x, z);
  61 #define memcpy(x, y, z) bcopy(y, x, z)
  62
  63 /* Internal mappings to the legacy sha1_ctxt structure. */
  64 #define state   h.b32
  65 #define bcount  c.b32
  66 #define buffer  m.b8
  67
  68 /*
  69  * The digest algorithm interprets the input message as a sequence of 32-bit
  70  * big-endian words.  We must reverse bytes in each word on x86/64 platforms,
  71  * but not on big-endian ones such as PPC.  For performance, we take advantage
  72  * of the bswap instruction on x86/64 to perform byte-reversal.  On PPC, we
  73  * could do 4-byte load if the address is 4-byte aligned which should further
  74  * improve the performance.  But for code simplicity, we punt and do 1-byte
  75  * loads instead.
  76  */
  77 #if (defined(__i386__) || defined(__x86_64__)) && defined(__GNUC__)
  78 #define FETCH_32(p) ({                                                  \
  79         register u_int32_t l = (u_int32_t)*((const u_int32_t *)(p));    \
  80         __asm__ __volatile__("bswap %0" : "=r" (l) : "0" (l));          \
  81         l;                                                              \
  82 })
  83 #else
  84 #define FETCH_32(p)                                                     \
  85         (((u_int32_t)*((const u_int8_t *)(p) + 3)) |                    \
  86         (((u_int32_t)*((const u_int8_t *)(p) + 2)) << 8) |              \
  87         (((u_int32_t)*((const u_int8_t *)(p) + 1)) << 16) |             \
  88         (((u_int32_t)*((const u_int8_t *)(p))) << 24))
  89 #endif /* __i386__ || __x86_64__ */
  90
  91 /*
  92  * Encodes input (u_int32_t) into output (unsigned char). Assumes len is
  93  * a multiple of 4. This is not compatible with memcpy().
  94  */
  95 static void
  96 Encode(unsigned char *output, u_int32_t *input, unsigned int len)
  97 {
  98         unsigned int i, j;
  99
 100         for (i = 0, j = 0; j < len; i++, j += 4) {
 101                 output[j + 3] = input[i] & 0xff;
 102                 output[j + 2] = (input[i] >> 8) & 0xff;
 103                 output[j + 1] = (input[i] >> 16) & 0xff;
 104                 output[j] = (input[i] >> 24) & 0xff;
 105         }
 106 }
 107
 108 static unsigned char PADDING[64] = { 0x80, /* zeros */ };
 109
 110 /* Constants from FIPS 180-1 */
 111 #define K_00_19         0x5a827999UL
 112 #define K_20_39         0x6ed9eba1UL
 113 #define K_40_59         0x8f1bbcdcUL
 114 #define K_60_79         0xca62c1d6UL
 115
 116 /* F, G, H and I are basic SHA1 functions. */
 117 #define F(b, c, d)      ((((c) ^ (d)) & (b)) ^ (d))
 118 #define G(b, c, d)      ((b) ^ (c) ^ (d))
 119 #define H(b, c, d)      (((b) & (c)) | (((b) | (c)) & (d)))
 120
 121 /* ROTATE_LEFT rotates x left n bits. */
 122 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
 123
 124 /* R, R1-R4 are macros used during each transformation round. */
 125 #define R(f, k, v, w, x, y, z, i) {                             \
 126         (v) = ROTATE_LEFT(w, 5) + f(x, y, z) + (v) + (i) + (k); \
 127         (x) = ROTATE_LEFT(x, 30);                               \
 128 }
 129
 130 #define R1(v, w, x, y, z, i)    R(F, K_00_19, v, w, x, y, z, i)
 131 #define R2(v, w, x, y, z, i)    R(G, K_20_39, v, w, x, y, z, i)
 132 #define R3(v, w, x, y, z, i)    R(H, K_40_59, v, w, x, y, z, i)
 133 #define R4(v, w, x, y, z, i)    R(G, K_60_79, v, w, x, y, z, i)
 134
 135 /* WUPDATE represents Wt variable that gets updated for steps 16-79 */
 136 #define WUPDATE(p, q, r, s) {           \
 137         (p) = ((q) ^ (r) ^ (s) ^ (p));  \
 138         (p) = ROTATE_LEFT(p, 1);        \
 139 }
 140
 141 static void SHA1Transform(u_int32_t, u_int32_t, u_int32_t, u_int32_t,
 142     u_int32_t, const u_int8_t *, SHA1_CTX *);
 143
 144 void SHA1Final_r(SHA1_CTX *, void *);
 145
 146 /*
 147  * SHA1 initialization. Begins a SHA1 operation, writing a new context.
 148  */
 149 void
 150 SHA1Init(SHA1_CTX *context)
 151 {
 152         context->bcount[0] = context->bcount[1] = 0;
 153         context->count = 0;
 154
 155         /* Load magic initialization constants.  */
 156         context->state[0] = 0x67452301UL;
 157         context->state[1] = 0xefcdab89UL;
 158         context->state[2] = 0x98badcfeUL;
 159         context->state[3] = 0x10325476UL;
 160         context->state[4] = 0xc3d2e1f0UL;
 161 }
 162
 163 /*
 164  * SHA1 block update operation. Continues a SHA1 message-digest
 165  * operation, processing another message block, and updating the
 166  * context.
 167  */
 168 void
 169 SHA1Update(SHA1_CTX *context, const void *inpp, size_t inputLen)
 170 {
 171         u_int32_t i, index, partLen;
 172         const unsigned char *input = (const unsigned char *)inpp;
 173
 174         if (inputLen == 0)
 175                 return;
 176
 177         /* Compute number of bytes mod 64 */
 178         index = (context->bcount[1] >> 3) & 0x3F;
 179
 180         /* Update number of bits */
 181         if ((context->bcount[1] += (inputLen << 3)) < (inputLen << 3))
 182                 context->bcount[0]++;
 183         context->bcount[0] += (inputLen >> 29);
 184
 185         partLen = 64 - index;
 186
 187         /* Transform as many times as possible. */
 188         i = 0;
 189         if (inputLen >= partLen) {
 190                 if (index != 0) {
 191                         memcpy(&context->buffer[index], input, partLen);
 192                         SHA1Transform(context->state[0], context->state[1],
 193                             context->state[2], context->state[3],
 194                             context->state[4], context->buffer, context);
 195                         i = partLen;
 196                 }
 197
 198                 for (; i + 63 < inputLen; i += 64)
 199                         SHA1Transform(context->state[0], context->state[1],
 200                             context->state[2], context->state[3],
 201                             context->state[4], &input[i], context);
 202
 203                 if (inputLen == i)
 204                         return;
 205
 206                 index = 0;
 207         }
 208
 209         /* Buffer remaining input */
 210         memcpy(&context->buffer[index], &input[i], inputLen - i);
 211 }
 212
 213 /*
 214  * For backwards compatibility, sha1_result symbol is mapped to this
 215  * routine since it's equivalent to SHA1Final with reversed parameters.
 216  */
 217 void
 218 SHA1Final_r(SHA1_CTX *context, void *digest)
 219 {
 220         SHA1Final(digest, context);
 221 }
 222
 223 /*
 224  * SHA1 finalization. Ends an SHA1 message-digest operation, writing the
 225  * the message digest and zeroizing the context.
 226  */
 227 void
 228 SHA1Final(void *digest, SHA1_CTX *context)
 229 {
 230         unsigned char bits[8];
 231         u_int32_t index = (context->bcount[1] >> 3) & 0x3f;
 232
 233         /* Save number of bits */
 234         Encode(bits, context->bcount, 8);
 235
 236         /* Pad out to 56 mod 64. */
 237         SHA1Update(context, PADDING, ((index < 56) ? 56 : 120) - index);
 238
 239         /* Append length (before padding) */
 240         SHA1Update(context, bits, 8);
 241
 242         /* Store state in digest */
 243         Encode(digest, context->state, 20);
 244
 245         /* Zeroize sensitive information. */
 246         memset(context, 0, sizeof (*context));
 247 }
 248
 249 /*
 250  * SHA1 basic transformation. Transforms state based on block.
 251  */
 252 static void
 253 SHA1Transform(u_int32_t a, u_int32_t b, u_int32_t c, u_int32_t d,
 254     u_int32_t e, const u_int8_t block[64], SHA1_CTX *context)
 255 {
 256         /* Register (instead of array) is a win in most cases */
 257         register u_int32_t w0, w1, w2, w3, w4, w5, w6, w7;
 258         register u_int32_t w8, w9, w10, w11, w12, w13, w14, w15;
 259
 260         w15 = FETCH_32(block + 60);
 261         w14 = FETCH_32(block + 56);
 262         w13 = FETCH_32(block + 52);
 263         w12 = FETCH_32(block + 48);
 264         w11 = FETCH_32(block + 44);
 265         w10 = FETCH_32(block + 40);
 266         w9  = FETCH_32(block + 36);
 267         w8  = FETCH_32(block + 32);
 268         w7  = FETCH_32(block + 28);
 269         w6  = FETCH_32(block + 24);
 270         w5  = FETCH_32(block + 20);
 271         w4  = FETCH_32(block + 16);
 272         w3  = FETCH_32(block + 12);
 273         w2  = FETCH_32(block +  8);
 274         w1  = FETCH_32(block +  4);
 275         w0  = FETCH_32(block +  0);
 276
 277         /* Round 1 */
 278                                         R1(e, a, b, c, d,  w0);         /*  0 */
 279                                         R1(d, e, a, b, c,  w1);         /*  1 */
 280                                         R1(c, d, e, a, b,  w2);         /*  2 */
 281                                         R1(b, c, d, e, a,  w3);         /*  3 */
 282                                         R1(a, b, c, d, e,  w4);         /*  4 */
 283                                         R1(e, a, b, c, d,  w5);         /*  5 */
 284                                         R1(d, e, a, b, c,  w6);         /*  6 */
 285                                         R1(c, d, e, a, b,  w7);         /*  7 */
 286                                         R1(b, c, d, e, a,  w8);         /*  8 */
 287                                         R1(a, b, c, d, e,  w9);         /*  9 */
 288                                         R1(e, a, b, c, d, w10);         /* 10 */
 289                                         R1(d, e, a, b, c, w11);         /* 11 */
 290                                         R1(c, d, e, a, b, w12);         /* 12 */
 291                                         R1(b, c, d, e, a, w13);         /* 13 */
 292                                         R1(a, b, c, d, e, w14);         /* 14 */
 293                                         R1(e, a, b, c, d, w15);         /* 15 */
 294         WUPDATE( w0, w13,  w8,  w2);    R1(d, e, a, b, c,  w0);         /* 16 */
 295         WUPDATE( w1, w14,  w9,  w3);    R1(c, d, e, a, b,  w1);         /* 17 */
 296         WUPDATE( w2, w15, w10,  w4);    R1(b, c, d, e, a,  w2);         /* 18 */
 297         WUPDATE( w3,  w0, w11,  w5);    R1(a, b, c, d, e,  w3);         /* 19 */
 298
 299         /* Round 2 */
 300         WUPDATE( w4,  w1, w12,  w6);    R2(e, a, b, c, d,  w4);         /* 20 */
 301         WUPDATE( w5,  w2, w13,  w7);    R2(d, e, a, b, c,  w5);         /* 21 */
 302         WUPDATE( w6,  w3, w14,  w8);    R2(c, d, e, a, b,  w6);         /* 22 */
 303         WUPDATE( w7,  w4, w15,  w9);    R2(b, c, d, e, a,  w7);         /* 23 */
 304         WUPDATE( w8,  w5,  w0, w10);    R2(a, b, c, d, e,  w8);         /* 24 */
 305         WUPDATE( w9,  w6,  w1, w11);    R2(e, a, b, c, d,  w9);         /* 25 */
 306         WUPDATE(w10,  w7,  w2, w12);    R2(d, e, a, b, c, w10);         /* 26 */
 307         WUPDATE(w11,  w8,  w3, w13);    R2(c, d, e, a, b, w11);         /* 27 */
 308         WUPDATE(w12,  w9,  w4, w14);    R2(b, c, d, e, a, w12);         /* 28 */
 309         WUPDATE(w13, w10,  w5, w15);    R2(a, b, c, d, e, w13);         /* 29 */
 310         WUPDATE(w14, w11,  w6,  w0);    R2(e, a, b, c, d, w14);         /* 30 */
 311         WUPDATE(w15, w12,  w7,  w1);    R2(d, e, a, b, c, w15);         /* 31 */
 312         WUPDATE( w0, w13,  w8,  w2);    R2(c, d, e, a, b,  w0);         /* 32 */
 313         WUPDATE( w1, w14,  w9,  w3);    R2(b, c, d, e, a,  w1);         /* 33 */
 314         WUPDATE( w2, w15, w10,  w4);    R2(a, b, c, d, e,  w2);         /* 34 */
 315         WUPDATE( w3,  w0, w11,  w5);    R2(e, a, b, c, d,  w3);         /* 35 */
 316         WUPDATE( w4,  w1, w12,  w6);    R2(d, e, a, b, c,  w4);         /* 36 */
 317         WUPDATE( w5,  w2, w13,  w7);    R2(c, d, e, a, b,  w5);         /* 37 */
 318         WUPDATE( w6,  w3, w14,  w8);    R2(b, c, d, e, a,  w6);         /* 38 */
 319         WUPDATE( w7,  w4, w15,  w9);    R2(a, b, c, d, e,  w7);         /* 39 */
 320
 321         /* Round 3 */
 322         WUPDATE( w8,  w5,  w0, w10);    R3(e, a, b, c, d,  w8);         /* 40 */
 323         WUPDATE( w9,  w6,  w1, w11);    R3(d, e, a, b, c,  w9);         /* 41 */
 324         WUPDATE(w10,  w7,  w2, w12);    R3(c, d, e, a, b, w10);         /* 42 */
 325         WUPDATE(w11,  w8,  w3, w13);    R3(b, c, d, e, a, w11);         /* 43 */
 326         WUPDATE(w12,  w9,  w4, w14);    R3(a, b, c, d, e, w12);         /* 44 */
 327         WUPDATE(w13, w10,  w5, w15);    R3(e, a, b, c, d, w13);         /* 45 */
 328         WUPDATE(w14, w11,  w6,  w0);    R3(d, e, a, b, c, w14);         /* 46 */
 329         WUPDATE(w15, w12,  w7,  w1);    R3(c, d, e, a, b, w15);         /* 47 */
 330         WUPDATE( w0, w13,  w8,  w2);    R3(b, c, d, e, a,  w0);         /* 48 */
 331         WUPDATE( w1, w14,  w9,  w3);    R3(a, b, c, d, e,  w1);         /* 49 */
 332         WUPDATE( w2, w15, w10,  w4);    R3(e, a, b, c, d,  w2);         /* 50 */
 333         WUPDATE( w3,  w0, w11,  w5);    R3(d, e, a, b, c,  w3);         /* 51 */
 334         WUPDATE( w4,  w1, w12,  w6);    R3(c, d, e, a, b,  w4);         /* 52 */
 335         WUPDATE( w5,  w2, w13,  w7);    R3(b, c, d, e, a,  w5);         /* 53 */
 336         WUPDATE( w6,  w3, w14,  w8);    R3(a, b, c, d, e,  w6);         /* 54 */
 337         WUPDATE( w7,  w4, w15,  w9);    R3(e, a, b, c, d,  w7);         /* 55 */
 338         WUPDATE( w8,  w5,  w0, w10);    R3(d, e, a, b, c,  w8);         /* 56 */
 339         WUPDATE( w9,  w6,  w1, w11);    R3(c, d, e, a, b,  w9);         /* 57 */
 340         WUPDATE(w10,  w7,  w2, w12);    R3(b, c, d, e, a, w10);         /* 58 */
 341         WUPDATE(w11,  w8,  w3, w13);    R3(a, b, c, d, e, w11);         /* 59 */
 342
 343         WUPDATE(w12,  w9,  w4, w14);    R4(e, a, b, c, d, w12);         /* 60 */
 344         WUPDATE(w13, w10,  w5, w15);    R4(d, e, a, b, c, w13);         /* 61 */
 345         WUPDATE(w14, w11,  w6,  w0);    R4(c, d, e, a, b, w14);         /* 62 */
 346         WUPDATE(w15, w12,  w7,  w1);    R4(b, c, d, e, a, w15);         /* 63 */
 347         WUPDATE( w0, w13,  w8,  w2);    R4(a, b, c, d, e,  w0);         /* 64 */
 348         WUPDATE( w1, w14,  w9,  w3);    R4(e, a, b, c, d,  w1);         /* 65 */
 349         WUPDATE( w2, w15, w10,  w4);    R4(d, e, a, b, c,  w2);         /* 66 */
 350         WUPDATE( w3,  w0, w11,  w5);    R4(c, d, e, a, b,  w3);         /* 67 */
 351         WUPDATE( w4,  w1, w12,  w6);    R4(b, c, d, e, a,  w4);         /* 68 */
 352         WUPDATE( w5,  w2, w13,  w7);    R4(a, b, c, d, e,  w5);         /* 69 */
 353         WUPDATE( w6,  w3, w14,  w8);    R4(e, a, b, c, d,  w6);         /* 70 */
 354         WUPDATE( w7,  w4, w15,  w9);    R4(d, e, a, b, c,  w7);         /* 71 */
 355         WUPDATE( w8,  w5,  w0, w10);    R4(c, d, e, a, b,  w8);         /* 72 */
 356         WUPDATE( w9,  w6,  w1, w11);    R4(b, c, d, e, a,  w9);         /* 73 */
 357         WUPDATE(w10,  w7,  w2, w12);    R4(a, b, c, d, e, w10);         /* 74 */
 358         WUPDATE(w11,  w8,  w3, w13);    R4(e, a, b, c, d, w11);         /* 75 */
 359         WUPDATE(w12,  w9,  w4, w14);    R4(d, e, a, b, c, w12);         /* 76 */
 360         WUPDATE(w13, w10,  w5, w15);    R4(c, d, e, a, b, w13);         /* 77 */
 361         WUPDATE(w14, w11,  w6,  w0);    R4(b, c, d, e, a, w14);         /* 78 */
 362         WUPDATE(w15, w12,  w7,  w1);    R4(a, b, c, d, e, w15);         /* 79 */
 363
 364         context->state[0] += a;
 365         context->state[1] += b;
 366         context->state[2] += c;
 367         context->state[3] += d;
 368         context->state[4] += e;
 369
 370         /* Zeroize sensitive information. */
 371         w15 = w14 = w13 = w12 = w11 = w10 = w9 = w8 = 0;
 372         w7 = w6 = w5 = w4 = w3 = w2 = w1 = w0 = 0;
 373 }