bsd/dev/random/randomdev.c

   1 /*
   2  * Copyright (c)1999-2004 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22
  23 #include <sys/param.h>
  24 #include <sys/systm.h>
  25 #include <sys/proc.h>
  26 #include <sys/errno.h>
  27 #include <sys/ioctl.h>
  28 #include <sys/conf.h>
  29 #include <sys/fcntl.h>
  30 #include <string.h>
  31 #include <miscfs/devfs/devfs.h>
  32 #include <kern/lock.h>
  33 #include <sys/time.h>
  34 #include <sys/malloc.h>
  35 #include <sys/uio_internal.h>
  36
  37 #include <dev/random/randomdev.h>
  38 #include <dev/random/YarrowCoreLib/include/yarrow.h>
  39 #include <crypto/sha1.h>
  40
  41 #define RANDOM_MAJOR  -1 /* let the kernel pick the device number */
  42
  43 d_ioctl_t       random_ioctl;
  44
  45 /*
  46  * A struct describing which functions will get invoked for certain
  47  * actions.
  48  */
  49 static struct cdevsw random_cdevsw =
  50 {
  51         random_open,            /* open */
  52         random_close,           /* close */
  53         random_read,            /* read */
  54         random_write,           /* write */
  55         random_ioctl,           /* ioctl */
  56         (stop_fcn_t *)nulldev, /* stop */
  57         (reset_fcn_t *)nulldev, /* reset */
  58         NULL,                           /* tty's */
  59         eno_select,                     /* select */
  60         eno_mmap,                       /* mmap */
  61         eno_strat,                      /* strategy */
  62         eno_getc,                       /* getc */
  63         eno_putc,                       /* putc */
  64         0                                       /* type */
  65 };
  66
  67 /* Used to detect whether we've already been initialized */
  68 static int gRandomInstalled = 0;
  69 static PrngRef gPrngRef;
  70 static int gRandomError = 1;
  71 static mutex_t *gYarrowMutex = 0;
  72
  73 #define RESEED_TICKS 50 /* how long a reseed operation can take */
  74
  75
  76 enum {kBSizeInBits = 160}; // MUST be a multiple of 32!!!
  77 enum {kBSizeInBytes = kBSizeInBits / 8};
  78 typedef u_int32_t BlockWord;
  79 enum {kWordSizeInBits = 32};
  80 enum {kBSize = 5};
  81 typedef BlockWord Block[kBSize];
  82
  83 /* define prototypes to keep the compiler happy... */
  84
  85 void add_blocks(Block a, Block b, BlockWord carry);
  86 void fips_initialize(void);
  87 void random_block(Block b, int addOptional);
  88 u_int32_t CalculateCRC(u_int8_t* buffer, size_t length);
  89
  90 /*
  91  * Get 120 bits from yarrow
  92  */
  93
  94 /*
  95  * add block b to block a
  96  */
  97 void
  98 add_blocks(Block a, Block b, BlockWord carry)
  99 {
 100         int i = kBSize;
 101         while (--i >= 0)
 102         {
 103                 u_int64_t c = (u_int64_t)carry +
 104                                           (u_int64_t)a[i] +
 105                                           (u_int64_t)b[i];
 106                 a[i] = c & ((1LL << kWordSizeInBits) - 1);
 107                 carry = c >> kWordSizeInBits;
 108         }
 109 }
 110
 111
 112
 113 struct sha1_ctxt g_sha1_ctx;
 114 char zeros[(512 - kBSizeInBits) / 8];
 115 Block g_xkey;
 116 Block g_random_data;
 117 int g_bytes_used;
 118 unsigned char g_SelfTestInitialized = 0;
 119 u_int32_t gLastBlockChecksum;
 120
 121 static const u_int32_t g_crc_table[] =
 122 {
 123         0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
 124         0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
 125         0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
 126         0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
 127         0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
 128         0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
 129         0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
 130         0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
 131         0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
 132         0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
 133         0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
 134         0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
 135         0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
 136         0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
 137         0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
 138         0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
 139         0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
 140         0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
 141         0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
 142         0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
 143         0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
 144         0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
 145         0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
 146         0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
 147         0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
 148         0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
 149         0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
 150         0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
 151         0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
 152         0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
 153         0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
 154         0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D,
 155 };
 156
 157 /*
 158  * Setup for fips compliance
 159  */
 160
 161 /*
 162  * calculate a crc-32 checksum
 163  */
 164 u_int32_t CalculateCRC(u_int8_t* buffer, size_t length)
 165 {
 166         u_int32_t crc = 0;
 167
 168         size_t i;
 169         for (i = 0; i < length; ++i)
 170         {
 171                 u_int32_t temp = (crc ^ ((u_int32_t) buffer[i])) & 0xFF;
 172                 crc = (crc >> 8) ^ g_crc_table[temp];
 173         }
 174
 175         return crc;
 176 }
 177
 178 /*
 179  * get a random block of data per fips 186-2
 180  */
 181 void
 182 random_block(Block b, int addOptional)
 183 {
 184         int repeatCount = 0;
 185         do
 186         {
 187                 if (addOptional)
 188                 {
 189                         // do one iteration
 190                         Block xSeed;
 191                         prngOutput (gPrngRef, (BYTE*) &xSeed, sizeof (xSeed));
 192
 193                         // add the seed to the previous value of g_xkey
 194                         add_blocks (g_xkey, xSeed, 0);
 195                 }
 196
 197                 // compute "G"
 198                 SHA1Update (&g_sha1_ctx, (const u_int8_t *) &g_xkey, sizeof (g_xkey));
 199
 200                 // add zeros to fill the internal SHA-1 buffer
 201                 SHA1Update (&g_sha1_ctx, (const u_int8_t *)zeros, sizeof (zeros));
 202
 203                 // write the resulting block
 204                 memmove(b, g_sha1_ctx.h.b8, sizeof (Block));
 205
 206                 // calculate the CRC-32 of the block
 207                 u_int32_t new_crc = CalculateCRC(g_sha1_ctx.h.b8, sizeof (Block));
 208
 209                 // make sure we don't repeat
 210                 int cmp = new_crc == gLastBlockChecksum;
 211                 gLastBlockChecksum = new_crc;
 212                 if (!g_SelfTestInitialized)
 213                 {
 214                         g_SelfTestInitialized = 1;
 215                         return;
 216                 }
 217                 else if (!cmp)
 218                 {
 219                         return;
 220                 }
 221
 222                 repeatCount += 1;
 223
 224                 // fix up the next value of g_xkey
 225                 add_blocks (g_xkey, b, 1);
 226         } while (repeatCount < 2);
 227
 228         /*
 229          * If we got here, three sucessive checksums of the random number
 230          * generator have been the same.  Since the odds of this happening are
 231          * 1 in 18,446,744,073,709,551,616, (1 in 18 quintillion) one of the following has
 232          * most likely happened:
 233          *
 234          * 1: There is a significant bug in this code.
 235          * 2: There has been a massive system failure.
 236          * 3: The universe has ceased to exist.
 237          *
 238          * There is no good way to recover from any of these cases. We
 239          * therefore panic.
 240          */
 241
 242          panic("FIPS random self-test failed.");
 243 }
 244
 245 /*
 246  *Initialize ONLY the Yarrow generator.
 247  */
 248 void
 249 PreliminarySetup(void)
 250 {
 251     prng_error_status perr;
 252     struct timeval tt;
 253     char buffer [16];
 254
 255     /* create a Yarrow object */
 256     perr = prngInitialize(&gPrngRef);
 257     if (perr != 0) {
 258         printf ("Couldn't initialize Yarrow, /dev/random will not work.\n");
 259         return;
 260     }
 261
 262         /* clear the error flag, reads and write should then work */
 263     gRandomError = 0;
 264
 265     /* get a little non-deterministic data as an initial seed. */
 266     microtime(&tt);
 267
 268     /*
 269          * So how much of the system clock is entropic?
 270          * It's hard to say, but assume that at least the
 271          * least significant byte of a 64 bit structure
 272          * is entropic.  It's probably more, how can you figure
 273          * the exact time the user turned the computer on, for example.
 274     */
 275     perr = prngInput(gPrngRef, (BYTE*) &tt, sizeof (tt), SYSTEM_SOURCE, 8);
 276     if (perr != 0) {
 277         /* an error, complain */
 278         printf ("Couldn't seed Yarrow.\n");
 279         return;
 280     }
 281
 282     /* turn the data around */
 283     perr = prngOutput(gPrngRef, (BYTE*)buffer, sizeof (buffer));
 284
 285     /* and scramble it some more */
 286     perr = prngForceReseed(gPrngRef, RESEED_TICKS);
 287
 288     /* make a mutex to control access */
 289     gYarrowMutex = mutex_alloc(0);
 290
 291         fips_initialize ();
 292 }
 293
 294 const Block kKnownAnswer = {0x92b404e5, 0x56588ced, 0x6c1acd4e, 0xbf053f68, 0x9f73a93};
 295
 296 void
 297 fips_initialize(void)
 298 {
 299         /* So that we can do the self test, set the seed to zero */
 300         memset(&g_xkey, 0, sizeof(g_xkey));
 301
 302         /* initialize our SHA1 generator */
 303         SHA1Init (&g_sha1_ctx);
 304
 305         /* other initializations */
 306         memset (zeros, 0, sizeof (zeros));
 307         g_bytes_used = 0;
 308         random_block(g_random_data, FALSE);
 309
 310         // check here to see if we got the initial data we were expecting
 311         int i;
 312         for (i = 0; i < kBSize; ++i)
 313         {
 314                 if (kKnownAnswer[i] != g_random_data[i])
 315                 {
 316                         panic("FIPS random self test failed");
 317                 }
 318         }
 319
 320         // now do the random block again to make sure that userland doesn't get predictable data
 321         random_block(g_random_data, TRUE);
 322 }
 323
 324 /*
 325  * Called to initialize our device,
 326  * and to register ourselves with devfs
 327  */
 328 void
 329 random_init(void)
 330 {
 331         int ret;
 332
 333         if (gRandomInstalled)
 334                 return;
 335
 336         /* install us in the file system */
 337         gRandomInstalled = 1;
 338
 339         /* setup yarrow and the mutex */
 340         PreliminarySetup();
 341
 342         ret = cdevsw_add(RANDOM_MAJOR, &random_cdevsw);
 343         if (ret < 0) {
 344                 printf("random_init: failed to allocate a major number!\n");
 345                 gRandomInstalled = 0;
 346                 return;
 347         }
 348
 349         devfs_make_node(makedev (ret, 0), DEVFS_CHAR,
 350                 UID_ROOT, GID_WHEEL, 0666, "random", 0);
 351
 352         /*
 353          * also make urandom
 354          * (which is exactly the same thing in our context)
 355          */
 356         devfs_make_node(makedev (ret, 1), DEVFS_CHAR,
 357                 UID_ROOT, GID_WHEEL, 0666, "urandom", 0);
 358 }
 359
 360 int
 361 random_ioctl(   __unused dev_t dev, u_long cmd, __unused caddr_t data,
 362                                 __unused int flag, __unused struct proc *p  )
 363 {
 364         switch (cmd) {
 365         case FIONBIO:
 366         case FIOASYNC:
 367                 break;
 368         default:
 369                 return ENODEV;
 370         }
 371
 372         return (0);
 373 }
 374
 375 /*
 376  * Open the device.  Make sure init happened, and make sure the caller is
 377  * authorized.
 378  */
 379
 380 int
 381 random_open(__unused dev_t dev, int flags, __unused int devtype, __unused struct proc *p)
 382 {
 383         if (gRandomError != 0) {
 384                 /* forget it, yarrow didn't come up */
 385                 return (ENOTSUP);
 386         }
 387
 388         /*
 389          * if we are being opened for write,
 390          * make sure that we have privledges do so
 391          */
 392         if (flags & FWRITE) {
 393                 if (securelevel >= 2)
 394                         return (EPERM);
 395 #ifndef __APPLE__
 396                 if ((securelevel >= 1) && proc_suser(p))
 397                         return (EPERM);
 398 #endif  /* !__APPLE__ */
 399         }
 400
 401         return (0);
 402 }
 403
 404
 405 /*
 406  * close the device.
 407  */
 408
 409 int
 410 random_close(__unused dev_t dev, __unused int flags, __unused int mode, __unused struct proc *p)
 411 {
 412         return (0);
 413 }
 414
 415
 416 /*
 417  * Get entropic data from the Security Server, and use it to reseed the
 418  * prng.
 419  */
 420 int
 421 random_write (__unused dev_t dev, struct uio *uio, __unused int ioflag)
 422 {
 423     int retCode = 0;
 424     char rdBuffer[256];
 425
 426     if (gRandomError != 0) {
 427         return (ENOTSUP);
 428     }
 429
 430     /* get control of the Yarrow instance, Yarrow is NOT thread safe */
 431     mutex_lock(gYarrowMutex);
 432
 433     /* Security server is sending us entropy */
 434
 435     while (uio_resid(uio) > 0 && retCode == 0) {
 436         /* get the user's data */
 437         // LP64todo - fix this!  uio_resid may be 64-bit value
 438         int bytesToInput = min(uio_resid(uio), sizeof (rdBuffer));
 439         retCode = uiomove(rdBuffer, bytesToInput, uio);
 440         if (retCode != 0)
 441             goto /*ugh*/ error_exit;
 442
 443         /* put it in Yarrow */
 444         if (prngInput(gPrngRef, (BYTE*)rdBuffer,
 445                         bytesToInput, SYSTEM_SOURCE,
 446                 bytesToInput * 8) != 0) {
 447             retCode = EIO;
 448             goto error_exit;
 449         }
 450     }
 451
 452     /* force a reseed */
 453     if (prngForceReseed(gPrngRef, RESEED_TICKS) != 0) {
 454         retCode = EIO;
 455         goto error_exit;
 456     }
 457
 458     /* retCode should be 0 at this point */
 459
 460 error_exit: /* do this to make sure the mutex unlocks. */
 461     mutex_unlock(gYarrowMutex);
 462     return (retCode);
 463 }
 464
 465 /*
 466  * return data to the caller.  Results unpredictable.
 467  */
 468 int random_read(__unused dev_t dev, struct uio *uio, __unused int ioflag)
 469 {
 470     int retCode = 0;
 471
 472     if (gRandomError != 0)
 473         return (ENOTSUP);
 474
 475    /* lock down the mutex */
 476     mutex_lock(gYarrowMutex);
 477
 478         int bytes_remaining = uio_resid(uio);
 479     while (bytes_remaining > 0 && retCode == 0) {
 480         /* get the user's data */
 481                 int bytes_to_read = 0;
 482
 483                 int bytes_available = kBSizeInBytes - g_bytes_used;
 484         if (bytes_available == 0)
 485                 {
 486                         random_block(g_random_data, TRUE);
 487                         g_bytes_used = 0;
 488                         bytes_available = kBSizeInBytes;
 489                 }
 490
 491                 bytes_to_read = min (bytes_remaining, bytes_available);
 492
 493         retCode = uiomove(((u_int8_t*)g_random_data)+ g_bytes_used, bytes_to_read, uio);
 494         g_bytes_used += bytes_to_read;
 495
 496         if (retCode != 0)
 497             goto error_exit;
 498
 499                 bytes_remaining = uio_resid(uio);
 500     }
 501
 502     retCode = 0;
 503
 504 error_exit:
 505     mutex_unlock(gYarrowMutex);
 506     return retCode;
 507 }
 508
 509 /* export good random numbers to the rest of the kernel */
 510 void
 511 read_random(void* buffer, u_int numbytes)
 512 {
 513     if (gYarrowMutex == 0) { /* are we initialized? */
 514         PreliminarySetup ();
 515     }
 516
 517     mutex_lock(gYarrowMutex);
 518
 519         int bytes_read = 0;
 520
 521         int bytes_remaining = numbytes;
 522     while (bytes_remaining > 0) {
 523         int bytes_to_read = min(bytes_remaining, kBSizeInBytes - g_bytes_used);
 524         if (bytes_to_read == 0)
 525                 {
 526                         random_block(g_random_data, TRUE);
 527                         g_bytes_used = 0;
 528                         bytes_to_read = min(bytes_remaining, kBSizeInBytes);
 529                 }
 530
 531                 memmove (buffer, ((u_int8_t*)g_random_data)+ bytes_read, bytes_to_read);
 532                 g_bytes_used += bytes_to_read;
 533                 bytes_read += bytes_to_read;
 534                 bytes_remaining -= bytes_to_read;
 535     }
 536
 537     mutex_unlock(gYarrowMutex);
 538 }
 539
 540 /*
 541  * Return an unsigned long pseudo-random number.
 542  */
 543 u_long
 544 RandomULong(void)
 545 {
 546         u_long buf;
 547         read_random(&buf, sizeof (buf));
 548         return (buf);
 549 }
 550