bsd/dev/random/fips_sha1.c

   1 /*
   2  * Copyright (c) 2000-2009 Apple, 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 /*
  57         WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
  58
  59         THIS FILE IS NEEDED TO PASS FIPS ACCEPTANCE FOR THE RANDOM NUMBER GENERATOR.
  60         IF YOU ALTER IT IN ANY WAY, WE WILL NEED TO GO THOUGH FIPS ACCEPTANCE AGAIN,
  61         AN OPERATION THAT IS VERY EXPENSIVE AND TIME CONSUMING.  IN OTHER WORDS,
  62         DON'T MESS WITH THIS FILE.
  63
  64         WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
  65 */
  66
  67 #include <sys/types.h>
  68 #include <string.h>
  69
  70 #include "fips_sha1.h"
  71
  72 typedef int Boolean;
  73
  74 /* Internal mappings to the legacy sha1_ctxt structure. */
  75 #define state   h.b32
  76 #define bcount  c.b32
  77 #define buffer  m.b8
  78
  79 /*
  80  * The digest algorithm interprets the input message as a sequence of 32-bit
  81  * big-endian words.  We must reverse bytes in each word on x86/64 platforms,
  82  * but not on big-endian ones such as PPC.  For performance, we take advantage
  83  * of the bswap instruction on x86/64 to perform byte-reversal.  On PPC, we
  84  * could do 4-byte load if the address is 4-byte aligned which should further
  85  * improve the performance.  But for code simplicity, we punt and do 1-byte
  86  * loads instead.
  87  */
  88 #if (defined(__i386__) || defined(__x86_64__)) && defined(__GNUC__)
  89 #define FETCH_32(p) ({                                                  \
  90         register u_int32_t l = (u_int32_t)*((const u_int32_t *)(p));    \
  91         __asm__ __volatile__("bswap %0" : "=r" (l) : "0" (l));          \
  92         l;                                                              \
  93 })
  94 #else
  95 #define FETCH_32(p)                                                     \
  96         (((u_int32_t)*((const u_int8_t *)(p) + 3)) |                    \
  97         (((u_int32_t)*((const u_int8_t *)(p) + 2)) << 8) |              \
  98         (((u_int32_t)*((const u_int8_t *)(p) + 1)) << 16) |             \
  99         (((u_int32_t)*((const u_int8_t *)(p))) << 24))
 100 #endif /* __i386__ || __x86_64__ */
 101
 102 /*
 103  * Encodes input (u_int32_t) into output (unsigned char). Assumes len is
 104  * a multiple of 4. This is not compatible with memcpy().
 105  */
 106 static void
 107 Encode(unsigned char *output, u_int32_t *input, unsigned int len)
 108 {
 109         unsigned int i, j;
 110
 111         for (i = 0, j = 0; j < len; i++, j += 4) {
 112                 output[j + 3] = input[i] & 0xff;
 113                 output[j + 2] = (input[i] >> 8) & 0xff;
 114                 output[j + 1] = (input[i] >> 16) & 0xff;
 115                 output[j] = (input[i] >> 24) & 0xff;
 116         }
 117 }
 118
 119 static unsigned char PADDING[64] = { 0x80, /* zeros */ };
 120
 121 /* Constants from FIPS 180-1 */
 122 #define K_00_19         0x5a827999UL
 123 #define K_20_39         0x6ed9eba1UL
 124 #define K_40_59         0x8f1bbcdcUL
 125 #define K_60_79         0xca62c1d6UL
 126
 127 /* F, G, H and I are basic SHA1 functions. */
 128 #define F(b, c, d)      ((((c) ^ (d)) & (b)) ^ (d))
 129 #define G(b, c, d)      ((b) ^ (c) ^ (d))
 130 #define H(b, c, d)      (((b) & (c)) | (((b) | (c)) & (d)))
 131
 132 /* ROTATE_LEFT rotates x left n bits. */
 133 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
 134
 135 /* R, R1-R4 are macros used during each transformation round. */
 136 #define R(f, k, v, w, x, y, z, i) {                             \
 137         (v) = ROTATE_LEFT(w, 5) + f(x, y, z) + (v) + (i) + (k); \
 138         (x) = ROTATE_LEFT(x, 30);                               \
 139 }
 140
 141 #define R1(v, w, x, y, z, i)    R(F, K_00_19, v, w, x, y, z, i)
 142 #define R2(v, w, x, y, z, i)    R(G, K_20_39, v, w, x, y, z, i)
 143 #define R3(v, w, x, y, z, i)    R(H, K_40_59, v, w, x, y, z, i)
 144 #define R4(v, w, x, y, z, i)    R(G, K_60_79, v, w, x, y, z, i)
 145
 146 /* WUPDATE represents Wt variable that gets updated for steps 16-79 */
 147 #define WUPDATE(p, q, r, s) {           \
 148         (p) = ((q) ^ (r) ^ (s) ^ (p));  \
 149         (p) = ROTATE_LEFT(p, 1);        \
 150 }
 151
 152 static void SHA1Transform(u_int32_t, u_int32_t, u_int32_t, u_int32_t,
 153     u_int32_t, const u_int8_t *, SHA1_CTX *);
 154
 155 /*
 156  * SHA1 initialization. Begins a SHA1 operation, writing a new context.
 157  */
 158 void
 159 FIPS_SHA1Init(SHA1_CTX *context)
 160 {
 161         context->bcount[0] = context->bcount[1] = 0;
 162         context->count = 0;
 163
 164         /* Load magic initialization constants.  */
 165         context->state[0] = 0x67452301UL;
 166         context->state[1] = 0xefcdab89UL;
 167         context->state[2] = 0x98badcfeUL;
 168         context->state[3] = 0x10325476UL;
 169         context->state[4] = 0xc3d2e1f0UL;
 170 }
 171
 172 /*
 173  * SHA1 block update operation. Continues a SHA1 message-digest
 174  * operation, processing another message block, and updating the
 175  * context.
 176  */
 177 void FIPS_SHA1Update(SHA1_CTX *context, const void *inpp, size_t inputLen)
 178 {
 179         u_int32_t i, index, partLen;
 180         const unsigned char *input = (const unsigned char *)inpp;
 181
 182         if (inputLen == 0)
 183                 return;
 184
 185         /* Compute number of bytes mod 64 */
 186         index = (context->bcount[1] >> 3) & 0x3F;
 187
 188         /* Update number of bits */
 189         if ((context->bcount[1] += (inputLen << 3)) < (inputLen << 3))
 190                 context->bcount[0]++;
 191         context->bcount[0] += (inputLen >> 29);
 192
 193         partLen = 64 - index;
 194
 195         /* Transform as many times as possible. */
 196         i = 0;
 197         if (inputLen >= partLen) {
 198                 if (index != 0) {
 199                         memcpy(&context->buffer[index], input, partLen);
 200                         SHA1Transform(context->state[0], context->state[1],
 201                             context->state[2], context->state[3],
 202                             context->state[4], context->buffer, context);
 203                         i = partLen;
 204                 }
 205
 206                 for (; i + 63 < inputLen; i += 64)
 207                         SHA1Transform(context->state[0], context->state[1],
 208                             context->state[2], context->state[3],
 209                             context->state[4], &input[i], context);
 210
 211                 if (inputLen == i)
 212                         return;
 213
 214                 index = 0;
 215         }
 216
 217         /* Buffer remaining input */
 218         memcpy(&context->buffer[index], &input[i], inputLen - i);
 219 }
 220
 221
 222
 223
 224 /*
 225  * This is function is only called in from the pagefault path or from page_copy().
 226  * So we assume that we can safely convert the virtual address to the physical address and use it.
 227  * Assumptions: The passed in address(inpp) is a kernel virtual address
 228  * and a physical page has been faulted in.
 229  * The inputLen passed in should always be less than or equal to a  page size (4096)
 230  * and inpp should be on a page boundary.
 231  * "performSHA1WithinKernelOnly" is initialized only when the hardware driver exists and is ready.
 232  */
 233
 234
 235
 236 /*
 237  * SHA1 finalization. Ends an SHA1 message-digest operation, writing the
 238  * the message digest and zeroizing the context.
 239  */
 240 void
 241 FIPS_SHA1Final(void *digest, SHA1_CTX *context)
 242 {
 243         unsigned char bits[8];
 244         u_int32_t index = (context->bcount[1] >> 3) & 0x3f;
 245
 246         /* Save number of bits */
 247         Encode(bits, context->bcount, 8);
 248
 249         /* Pad out to 56 mod 64. */
 250         FIPS_SHA1Update(context, PADDING, ((index < 56) ? 56 : 120) - index);
 251
 252         /* Append length (before padding) */
 253         FIPS_SHA1Update(context, bits, 8);
 254
 255         /* Store state in digest */
 256         Encode(digest, context->state, 20);
 257
 258         /* Zeroize sensitive information. */
 259         memset(context, 0, sizeof (*context));
 260 }
 261
 262 /*
 263  * SHA1 basic transformation. Transforms state based on block.
 264  */
 265 static void
 266 SHA1Transform(u_int32_t a, u_int32_t b, u_int32_t c, u_int32_t d,
 267     u_int32_t e, const u_int8_t block[64], SHA1_CTX *context)
 268 {
 269         /* Register (instead of array) is a win in most cases */
 270         register u_int32_t w0, w1, w2, w3, w4, w5, w6, w7;
 271         register u_int32_t w8, w9, w10, w11, w12, w13, w14, w15;
 272
 273         w15 = FETCH_32(block + 60);
 274         w14 = FETCH_32(block + 56);
 275         w13 = FETCH_32(block + 52);
 276         w12 = FETCH_32(block + 48);
 277         w11 = FETCH_32(block + 44);
 278         w10 = FETCH_32(block + 40);
 279         w9  = FETCH_32(block + 36);
 280         w8  = FETCH_32(block + 32);
 281         w7  = FETCH_32(block + 28);
 282         w6  = FETCH_32(block + 24);
 283         w5  = FETCH_32(block + 20);
 284         w4  = FETCH_32(block + 16);
 285         w3  = FETCH_32(block + 12);
 286         w2  = FETCH_32(block +  8);
 287         w1  = FETCH_32(block +  4);
 288         w0  = FETCH_32(block +  0);
 289
 290         /* Round 1 */
 291                                         R1(e, a, b, c, d,  w0);         /*  0 */
 292                                         R1(d, e, a, b, c,  w1);         /*  1 */
 293                                         R1(c, d, e, a, b,  w2);         /*  2 */
 294                                         R1(b, c, d, e, a,  w3);         /*  3 */
 295                                         R1(a, b, c, d, e,  w4);         /*  4 */
 296                                         R1(e, a, b, c, d,  w5);         /*  5 */
 297                                         R1(d, e, a, b, c,  w6);         /*  6 */
 298                                         R1(c, d, e, a, b,  w7);         /*  7 */
 299                                         R1(b, c, d, e, a,  w8);         /*  8 */
 300                                         R1(a, b, c, d, e,  w9);         /*  9 */
 301                                         R1(e, a, b, c, d, w10);         /* 10 */
 302                                         R1(d, e, a, b, c, w11);         /* 11 */
 303                                         R1(c, d, e, a, b, w12);         /* 12 */
 304                                         R1(b, c, d, e, a, w13);         /* 13 */
 305                                         R1(a, b, c, d, e, w14);         /* 14 */
 306                                         R1(e, a, b, c, d, w15);         /* 15 */
 307         WUPDATE( w0, w13,  w8,  w2);    R1(d, e, a, b, c,  w0);         /* 16 */
 308         WUPDATE( w1, w14,  w9,  w3);    R1(c, d, e, a, b,  w1);         /* 17 */
 309         WUPDATE( w2, w15, w10,  w4);    R1(b, c, d, e, a,  w2);         /* 18 */
 310         WUPDATE( w3,  w0, w11,  w5);    R1(a, b, c, d, e,  w3);         /* 19 */
 311
 312         /* Round 2 */
 313         WUPDATE( w4,  w1, w12,  w6);    R2(e, a, b, c, d,  w4);         /* 20 */
 314         WUPDATE( w5,  w2, w13,  w7);    R2(d, e, a, b, c,  w5);         /* 21 */
 315         WUPDATE( w6,  w3, w14,  w8);    R2(c, d, e, a, b,  w6);         /* 22 */
 316         WUPDATE( w7,  w4, w15,  w9);    R2(b, c, d, e, a,  w7);         /* 23 */
 317         WUPDATE( w8,  w5,  w0, w10);    R2(a, b, c, d, e,  w8);         /* 24 */
 318         WUPDATE( w9,  w6,  w1, w11);    R2(e, a, b, c, d,  w9);         /* 25 */
 319         WUPDATE(w10,  w7,  w2, w12);    R2(d, e, a, b, c, w10);         /* 26 */
 320         WUPDATE(w11,  w8,  w3, w13);    R2(c, d, e, a, b, w11);         /* 27 */
 321         WUPDATE(w12,  w9,  w4, w14);    R2(b, c, d, e, a, w12);         /* 28 */
 322         WUPDATE(w13, w10,  w5, w15);    R2(a, b, c, d, e, w13);         /* 29 */
 323         WUPDATE(w14, w11,  w6,  w0);    R2(e, a, b, c, d, w14);         /* 30 */
 324         WUPDATE(w15, w12,  w7,  w1);    R2(d, e, a, b, c, w15);         /* 31 */
 325         WUPDATE( w0, w13,  w8,  w2);    R2(c, d, e, a, b,  w0);         /* 32 */
 326         WUPDATE( w1, w14,  w9,  w3);    R2(b, c, d, e, a,  w1);         /* 33 */
 327         WUPDATE( w2, w15, w10,  w4);    R2(a, b, c, d, e,  w2);         /* 34 */
 328         WUPDATE( w3,  w0, w11,  w5);    R2(e, a, b, c, d,  w3);         /* 35 */
 329         WUPDATE( w4,  w1, w12,  w6);    R2(d, e, a, b, c,  w4);         /* 36 */
 330         WUPDATE( w5,  w2, w13,  w7);    R2(c, d, e, a, b,  w5);         /* 37 */
 331         WUPDATE( w6,  w3, w14,  w8);    R2(b, c, d, e, a,  w6);         /* 38 */
 332         WUPDATE( w7,  w4, w15,  w9);    R2(a, b, c, d, e,  w7);         /* 39 */
 333
 334         /* Round 3 */
 335         WUPDATE( w8,  w5,  w0, w10);    R3(e, a, b, c, d,  w8);         /* 40 */
 336         WUPDATE( w9,  w6,  w1, w11);    R3(d, e, a, b, c,  w9);         /* 41 */
 337         WUPDATE(w10,  w7,  w2, w12);    R3(c, d, e, a, b, w10);         /* 42 */
 338         WUPDATE(w11,  w8,  w3, w13);    R3(b, c, d, e, a, w11);         /* 43 */
 339         WUPDATE(w12,  w9,  w4, w14);    R3(a, b, c, d, e, w12);         /* 44 */
 340         WUPDATE(w13, w10,  w5, w15);    R3(e, a, b, c, d, w13);         /* 45 */
 341         WUPDATE(w14, w11,  w6,  w0);    R3(d, e, a, b, c, w14);         /* 46 */
 342         WUPDATE(w15, w12,  w7,  w1);    R3(c, d, e, a, b, w15);         /* 47 */
 343         WUPDATE( w0, w13,  w8,  w2);    R3(b, c, d, e, a,  w0);         /* 48 */
 344         WUPDATE( w1, w14,  w9,  w3);    R3(a, b, c, d, e,  w1);         /* 49 */
 345         WUPDATE( w2, w15, w10,  w4);    R3(e, a, b, c, d,  w2);         /* 50 */
 346         WUPDATE( w3,  w0, w11,  w5);    R3(d, e, a, b, c,  w3);         /* 51 */
 347         WUPDATE( w4,  w1, w12,  w6);    R3(c, d, e, a, b,  w4);         /* 52 */
 348         WUPDATE( w5,  w2, w13,  w7);    R3(b, c, d, e, a,  w5);         /* 53 */
 349         WUPDATE( w6,  w3, w14,  w8);    R3(a, b, c, d, e,  w6);         /* 54 */
 350         WUPDATE( w7,  w4, w15,  w9);    R3(e, a, b, c, d,  w7);         /* 55 */
 351         WUPDATE( w8,  w5,  w0, w10);    R3(d, e, a, b, c,  w8);         /* 56 */
 352         WUPDATE( w9,  w6,  w1, w11);    R3(c, d, e, a, b,  w9);         /* 57 */
 353         WUPDATE(w10,  w7,  w2, w12);    R3(b, c, d, e, a, w10);         /* 58 */
 354         WUPDATE(w11,  w8,  w3, w13);    R3(a, b, c, d, e, w11);         /* 59 */
 355
 356         WUPDATE(w12,  w9,  w4, w14);    R4(e, a, b, c, d, w12);         /* 60 */
 357         WUPDATE(w13, w10,  w5, w15);    R4(d, e, a, b, c, w13);         /* 61 */
 358         WUPDATE(w14, w11,  w6,  w0);    R4(c, d, e, a, b, w14);         /* 62 */
 359         WUPDATE(w15, w12,  w7,  w1);    R4(b, c, d, e, a, w15);         /* 63 */
 360         WUPDATE( w0, w13,  w8,  w2);    R4(a, b, c, d, e,  w0);         /* 64 */
 361         WUPDATE( w1, w14,  w9,  w3);    R4(e, a, b, c, d,  w1);         /* 65 */
 362         WUPDATE( w2, w15, w10,  w4);    R4(d, e, a, b, c,  w2);         /* 66 */
 363         WUPDATE( w3,  w0, w11,  w5);    R4(c, d, e, a, b,  w3);         /* 67 */
 364         WUPDATE( w4,  w1, w12,  w6);    R4(b, c, d, e, a,  w4);         /* 68 */
 365         WUPDATE( w5,  w2, w13,  w7);    R4(a, b, c, d, e,  w5);         /* 69 */
 366         WUPDATE( w6,  w3, w14,  w8);    R4(e, a, b, c, d,  w6);         /* 70 */
 367         WUPDATE( w7,  w4, w15,  w9);    R4(d, e, a, b, c,  w7);         /* 71 */
 368         WUPDATE( w8,  w5,  w0, w10);    R4(c, d, e, a, b,  w8);         /* 72 */
 369         WUPDATE( w9,  w6,  w1, w11);    R4(b, c, d, e, a,  w9);         /* 73 */
 370         WUPDATE(w10,  w7,  w2, w12);    R4(a, b, c, d, e, w10);         /* 74 */
 371         WUPDATE(w11,  w8,  w3, w13);    R4(e, a, b, c, d, w11);         /* 75 */
 372         WUPDATE(w12,  w9,  w4, w14);    R4(d, e, a, b, c, w12);         /* 76 */
 373         WUPDATE(w13, w10,  w5, w15);    R4(c, d, e, a, b, w13);         /* 77 */
 374         WUPDATE(w14, w11,  w6,  w0);    R4(b, c, d, e, a, w14);         /* 78 */
 375         WUPDATE(w15, w12,  w7,  w1);    R4(a, b, c, d, e, w15);         /* 79 */
 376
 377         context->state[0] += a;
 378         context->state[1] += b;
 379         context->state[2] += c;
 380         context->state[3] += d;
 381         context->state[4] += e;
 382
 383         /* Zeroize sensitive information. */
 384         w15 = w14 = w13 = w12 = w11 = w10 = w9 = w8 = 0;
 385         w7 = w6 = w5 = w4 = w3 = w2 = w1 = w0 = 0;
 386 }