bsd/dev/random/randomdev.c

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