osfmk/prng/prng_yarrow.c

   1 /*
   2  * Copyright (c) 1999-2013 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 #include <string.h>
  31 #include <kern/cpu_number.h>
  32 #include <kern/cpu_data.h>
  33 #include <kern/misc_protos.h>
  34 #include <kern/thread.h>
  35 #include <sys/random.h>
  36
  37 #include <corecrypto/ccdrbg.h>
  38
  39 #include <prng/YarrowCoreLib/include/yarrow.h>
  40
  41 #include <libkern/OSByteOrder.h>
  42 #include <libkern/OSAtomic.h>
  43
  44 #include <mach/mach_time.h>
  45
  46 #include <prng/random.h>
  47
  48 #include "fips_sha1.h"
  49
  50
  51 /*
  52         WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
  53
  54         THIS FILE IS NEEDED TO PASS FIPS ACCEPTANCE FOR THE RANDOM NUMBER GENERATOR.
  55         IF YOU ALTER IT IN ANY WAY, WE WILL NEED TO GO THOUGH FIPS ACCEPTANCE AGAIN,
  56         AN OPERATION THAT IS VERY EXPENSIVE AND TIME CONSUMING.  IN OTHER WORDS,
  57         DON'T MESS WITH THIS FILE.
  58
  59         WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
  60 */
  61 /*
  62         WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
  63
  64         ANY CODE PROTECTED UNDER "#ifdef __arm__" IS SERIOUSLY SUPPOSED TO BE THERE!
  65         IF YOU REMOVE ARM CODE, RANDOM WILL NOT MEAN ANYTHING FOR iPHONES ALL OVER.
  66         PLEASE DON'T TOUCH __arm__ CODE IN THIS FILE!
  67
  68         WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
  69 */
  70
  71
  72 #define RESEED_TICKS 50 /* how long a reseed operation can take */
  73
  74
  75 typedef u_int8_t BlockWord;
  76 enum {kBSize = 20};
  77 typedef BlockWord Block[kBSize];
  78 enum {kBlockSize = sizeof(Block)};
  79
  80 struct YarrowContext {
  81         PrngRef         PrngRef;
  82         Block           xkey;
  83         Block           random_data;
  84         int             bytes_used;
  85         unsigned char   SelfTestInitialized;
  86         u_int32_t       LastBlockChecksum;
  87         uint64_t        bytes_since_reseed;
  88 };
  89 typedef struct YarrowContext *YarrowContextp;
  90
  91 /* define prototypes to keep the compiler happy... */
  92
  93 void add_blocks(Block a, Block b, BlockWord carry);
  94 void fips_initialize(YarrowContextp yp);
  95 void random_block(YarrowContextp yp, Block b, int addOptional);
  96 u_int32_t CalculateCRC(u_int8_t* buffer, size_t length);
  97
  98 /*
  99  * Get 120 bits from yarrow
 100  */
 101
 102 /*
 103  * add block b to block a
 104  */
 105 void
 106 add_blocks(Block a, Block b, BlockWord carry)
 107 {
 108         int i = kBlockSize - 1;
 109         while (i >= 0)
 110         {
 111                 u_int32_t c = (u_int32_t)carry +
 112                                           (u_int32_t)a[i] +
 113                                           (u_int32_t)b[i];
 114                 a[i] = c & 0xff;
 115                 carry = c >> 8;
 116                 i -= 1;
 117         }
 118 }
 119
 120
 121
 122 static char zeros[(512 - kBSize * 8) / 8];
 123
 124 static const u_int32_t g_crc_table[] =
 125 {
 126         0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
 127         0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
 128         0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
 129         0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
 130         0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
 131         0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
 132         0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
 133         0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
 134         0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
 135         0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
 136         0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
 137         0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
 138         0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
 139         0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
 140         0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
 141         0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
 142         0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
 143         0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
 144         0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
 145         0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
 146         0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
 147         0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
 148         0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
 149         0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
 150         0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
 151         0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
 152         0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
 153         0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
 154         0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
 155         0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
 156         0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
 157         0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D,
 158 };
 159
 160 /*
 161  * Setup for fips compliance
 162  */
 163
 164 /*
 165  * calculate a crc-32 checksum
 166  */
 167 u_int32_t CalculateCRC(u_int8_t* buffer, size_t length)
 168 {
 169         u_int32_t crc = 0;
 170
 171         size_t i;
 172         for (i = 0; i < length; ++i)
 173         {
 174                 u_int32_t temp = (crc ^ ((u_int32_t) buffer[i])) & 0xFF;
 175                 crc = (crc >> 8) ^ g_crc_table[temp];
 176         }
 177
 178         return crc;
 179 }
 180
 181 /*
 182  * get a random block of data per fips 186-2
 183  */
 184 void
 185 random_block(YarrowContextp pp, Block b, int addOptional)
 186 {
 187         SHA1_CTX sha1_ctx;
 188
 189         int repeatCount = 0;
 190         do
 191         {
 192                 // do one iteration
 193
 194                 if (addOptional)
 195                 {
 196                         // create an xSeed to add.
 197                         Block xSeed;
 198                         prngOutput (pp->PrngRef, (BYTE*) &xSeed, sizeof (xSeed));
 199
 200                         // add the seed to the previous value of xkey
 201                         add_blocks (pp->xkey, xSeed, 0);
 202                 }
 203
 204                 // initialize the value of H
 205                 FIPS_SHA1Init(&sha1_ctx);
 206
 207                 // to stay compatible with the FIPS specification, we need to flip the bytes in
 208                 // xkey to little endian byte order.  In our case, this makes exactly no difference
 209                 // (random is random), but we need to do it anyway to keep FIPS happy
 210
 211                 // compute "G"
 212                 FIPS_SHA1Update(&sha1_ctx, pp->xkey, kBlockSize);
 213
 214                 // add zeros to fill the internal SHA-1 buffer
 215                 FIPS_SHA1Update (&sha1_ctx, (const u_int8_t *)zeros, sizeof (zeros));
 216
 217                 // we have to do a byte order correction here because the sha1 math is being done internally
 218                 // as u_int32_t, not a stream of bytes.  Since we maintain our data as a byte stream, we need
 219                 // to convert
 220
 221                 u_int32_t* finger = (u_int32_t*) b;
 222
 223                 unsigned j;
 224                 for (j = 0; j < kBlockSize / sizeof (u_int32_t); ++j)
 225                 {
 226                         *finger++ = OSSwapHostToBigInt32(sha1_ctx.h.b32[j]);
 227                 }
 228
 229                 // calculate the CRC-32 of the block
 230                 u_int32_t new_crc = CalculateCRC(sha1_ctx.h.b8, sizeof (Block));
 231
 232                 // make sure we don't repeat
 233                 int cmp = new_crc == pp->LastBlockChecksum;
 234                 pp->LastBlockChecksum = new_crc;
 235                 if (!pp->SelfTestInitialized)
 236                 {
 237                         pp->SelfTestInitialized = 1;
 238                         return;
 239                 }
 240                 else if (!cmp)
 241                 {
 242                         return;
 243                 }
 244
 245                 repeatCount += 1;
 246
 247                 // fix up the next value of xkey
 248                 add_blocks (pp->xkey, b, 1);
 249         } while (repeatCount < 2);
 250
 251         /*
 252          * If we got here, three sucessive checksums of the random number
 253          * generator have been the same.  Since the odds of this happening are
 254          * 1 in 18,446,744,073,709,551,616, (1 in 18 quintillion) one of the following has
 255          * most likely happened:
 256          *
 257          * 1: There is a significant bug in this code.
 258          * 2: There has been a massive system failure.
 259          * 3: The universe has ceased to exist.
 260          *
 261          * There is no good way to recover from any of these cases. We
 262          * therefore panic.
 263          */
 264
 265          panic("FIPS random self-test failed.");
 266 }
 267
 268 const Block kKnownAnswer = {0x92, 0xb4, 0x04, 0xe5, 0x56, 0x58, 0x8c, 0xed, 0x6c, 0x1a, 0xcd, 0x4e, 0xbf, 0x05, 0x3f, 0x68, 0x09, 0xf7, 0x3a, 0x93};
 269
 270 void
 271 fips_initialize(YarrowContextp yp)
 272 {
 273         /* So that we can do the self test, set the seed to zero */
 274         memset(&yp->xkey, 0, sizeof(yp->xkey));
 275
 276         /* other initializations */
 277         memset (zeros, 0, sizeof (zeros));
 278         yp->bytes_used = 0;
 279         random_block(yp, yp->random_data, FALSE);
 280
 281         // check here to see if we got the initial data we were expecting
 282         if (memcmp(kKnownAnswer, yp->random_data, kBlockSize) != 0)
 283         {
 284                 panic("FIPS random self test failed");
 285         }
 286
 287         // now do the random block again to make sure that userland doesn't get predicatable data
 288         random_block(yp, yp->random_data, TRUE);
 289 }
 290
 291
 292 static int
 293 yarrow_init(
 294         const struct ccdrbg_info *info,
 295         struct ccdrbg_state *drbg,
 296         unsigned long entropyLength, const void* entropy,
 297         unsigned long nonceLength, const void* nonce,
 298         unsigned long psLength, const void* ps)
 299 {
 300 #pragma unused(info)
 301 #pragma unused(nonceLength)
 302 #pragma unused(nonce)
 303 #pragma unused(psLength)
 304 #pragma unused(ps)
 305         YarrowContextp          yp = (YarrowContextp) drbg;
 306         prng_error_status       perr;
 307         char                    buffer[16];
 308
 309         yp->SelfTestInitialized = 0;
 310
 311         /* create a Yarrow object */
 312         perr = prngInitialize(&yp->PrngRef);
 313         if (perr != 0) {
 314                 panic("Couldn't initialize Yarrow, /dev/random will not work.");
 315         }
 316
 317         perr = prngInput(yp->PrngRef, __DECONST(BYTE*, entropy), (UINT) entropyLength,
 318                         SYSTEM_SOURCE, (UINT) entropyLength * 8);
 319         if (perr != 0) {
 320                 /* an error, complain */
 321                 panic("Couldn't seed Yarrow.\n");
 322         }
 323
 324         /* turn the data around */
 325         perr = prngOutput(yp->PrngRef, (BYTE*) buffer, (UINT) sizeof(buffer));
 326
 327         /* and scramble it some more */
 328         perr = prngForceReseed(yp->PrngRef, RESEED_TICKS);
 329
 330         fips_initialize(yp);
 331
 332         yp->bytes_since_reseed = 0;
 333
 334         return perr;
 335 }
 336
 337 static int
 338 yarrow_generate(
 339         struct ccdrbg_state *prng,
 340         unsigned long outlen, void *out,
 341         unsigned long inlen, const void *in)
 342 {
 343 #pragma unused(inlen)
 344 #pragma unused(in)
 345         YarrowContextp  yp = (YarrowContextp) prng;
 346         int             bytes_read = 0;
 347         int             bytes_remaining = (int) outlen;
 348
 349         yp->bytes_since_reseed += outlen;
 350         /* Reseed needed? But allow any length immediately after reseeding. */
 351         if (yp->bytes_since_reseed != outlen &&
 352             yp->bytes_since_reseed > RESEED_BYTES)
 353                 return CCDRBG_STATUS_NEED_RESEED;
 354
 355         while (bytes_remaining > 0) {
 356                 int bytes_to_read = MIN(bytes_remaining,
 357                                         kBlockSize - yp->bytes_used);
 358                 if (bytes_to_read == 0) {
 359                         random_block(yp, yp->random_data, TRUE);
 360                         yp->bytes_used = 0;
 361                         bytes_to_read = MIN(bytes_remaining, kBlockSize);
 362                 }
 363
 364                 memmove((u_int8_t*) out + bytes_read,
 365                         ((u_int8_t*)yp->random_data) + yp->bytes_used,
 366                         bytes_to_read);
 367                 yp->bytes_used += bytes_to_read;
 368                 bytes_read += bytes_to_read;
 369                 bytes_remaining -= bytes_to_read;
 370         }
 371
 372         return CCDRBG_STATUS_OK;
 373 }
 374
 375 static int
 376 yarrow_reseed(
 377         struct ccdrbg_state *prng,
 378         unsigned long entropylen, const void *entropy,
 379         unsigned long inlen, const void *in)
 380 {
 381 #pragma unused(inlen)
 382 #pragma unused(in)
 383         YarrowContextp  yp = (YarrowContextp) prng;
 384
 385         (void) prngInput(yp->PrngRef, __DECONST(BYTE*, entropy), (UINT) entropylen,
 386                          SYSTEM_SOURCE, (UINT) entropylen * 8);
 387         (void) prngForceReseed(yp->PrngRef, RESEED_TICKS);
 388
 389         yp->bytes_since_reseed = 0;
 390
 391         return CCDRBG_STATUS_OK;
 392 }
 393
 394 static void
 395 yarrow_destroy(
 396         struct ccdrbg_state *prng)
 397 {
 398 #pragma unused(prng)
 399 }
 400
 401
 402 void
 403 ccdrbg_factory_yarrow(
 404         struct ccdrbg_info      *info,
 405         const void              *custom)
 406 {
 407         info->size = sizeof(struct YarrowContext);
 408         info->init = yarrow_init;
 409         info->generate = yarrow_generate;
 410         info->reseed = yarrow_reseed;
 411         info->done = yarrow_destroy;
 412         info->custom = custom;
 413 }