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