X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/6601e61aa18bf4f09af135ff61fc7f4771d23b06..8a3053a07cee346dca737a5670e546fd26a7c9d6:/bsd/dev/random/randomdev.c?ds=sidebyside diff --git a/bsd/dev/random/randomdev.c b/bsd/dev/random/randomdev.c index 04e1883a4..c73553994 100644 --- a/bsd/dev/random/randomdev.c +++ b/bsd/dev/random/randomdev.c @@ -1,25 +1,42 @@ /* - * Copyright (c)1999-2004 Apple Computer, Inc. All rights reserved. + * Copyright (c) 1999-2009 Apple, Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * - * The contents of this file constitute Original Code as defined in and - * are subject to the Apple Public Source License Version 1.1 (the - * "License"). You may not use this file except in compliance with the - * License. Please obtain a copy of the License at - * http://www.apple.com/publicsource and read it before using this file. + * This file contains Original Code and/or Modifications of Original Code + * as defined in and that are subject to the Apple Public Source License + * Version 2.0 (the 'License'). You may not use this file except in + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. * - * This Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this file. + * + * The Original Code and all software distributed under the License are + * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the - * License for the specific language governing rights and limitations - * under the License. + * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * Please see the License for the specific language governing rights and + * limitations under the License. * - * @APPLE_LICENSE_HEADER_END@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ +/* + WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! + + THIS FILE IS NEEDED TO PASS FIPS ACCEPTANCE FOR THE RANDOM NUMBER GENERATOR. + IF YOU ALTER IT IN ANY WAY, WE WILL NEED TO GO THOUGH FIPS ACCEPTANCE AGAIN, + AN OPERATION THAT IS VERY EXPENSIVE AND TIME CONSUMING. IN OTHER WORDS, + DON'T MESS WITH THIS FILE. + + WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! +*/ + #include #include #include @@ -30,18 +47,29 @@ #include #include #include +#include #include #include #include #include #include -#include + +#include +#include + +#include +#include + +#include "fips_sha1.h" #define RANDOM_MAJOR -1 /* let the kernel pick the device number */ d_ioctl_t random_ioctl; +/* To generate the seed for the RNG */ +extern uint64_t early_random(); + /* * A struct describing which functions will get invoked for certain * actions. @@ -64,21 +92,35 @@ static struct cdevsw random_cdevsw = 0 /* type */ }; + +/* + WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! + + ANY CODE PROTECTED UNDER "#ifdef __arm__" IS SERIOUSLY SUPPOSED TO BE THERE! + IF YOU REMOVE ARM CODE, RANDOM WILL NOT MEAN ANYTHING FOR iPHONES ALL OVER. + PLEASE DON'T TOUCH __arm__ CODE IN THIS FILE! + + WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! +*/ + + /* Used to detect whether we've already been initialized */ -static int gRandomInstalled = 0; +static UInt8 gRandomInstalled = 0; static PrngRef gPrngRef; static int gRandomError = 1; -static mutex_t *gYarrowMutex = 0; +static lck_grp_t *gYarrowGrp; +static lck_attr_t *gYarrowAttr; +static lck_grp_attr_t *gYarrowGrpAttr; +static lck_mtx_t *gYarrowMutex = 0; +static UInt8 gYarrowInitializationLock = 0; #define RESEED_TICKS 50 /* how long a reseed operation can take */ -enum {kBSizeInBits = 160}; // MUST be a multiple of 32!!! -enum {kBSizeInBytes = kBSizeInBits / 8}; -typedef u_int32_t BlockWord; -enum {kWordSizeInBits = 32}; -enum {kBSize = 5}; +typedef u_int8_t BlockWord; +enum {kBSize = 20}; typedef BlockWord Block[kBSize]; +enum {kBlockSize = sizeof(Block)}; /* define prototypes to keep the compiler happy... */ @@ -97,26 +139,26 @@ u_int32_t CalculateCRC(u_int8_t* buffer, size_t length); void add_blocks(Block a, Block b, BlockWord carry) { - int i = kBSize; - while (--i >= 0) + int i = kBlockSize - 1; + while (i >= 0) { - u_int64_t c = (u_int64_t)carry + - (u_int64_t)a[i] + - (u_int64_t)b[i]; - a[i] = c & ((1LL << kWordSizeInBits) - 1); - carry = c >> kWordSizeInBits; + u_int32_t c = (u_int32_t)carry + + (u_int32_t)a[i] + + (u_int32_t)b[i]; + a[i] = c & 0xff; + carry = c >> 8; + i -= 1; } } -struct sha1_ctxt g_sha1_ctx; -char zeros[(512 - kBSizeInBits) / 8]; -Block g_xkey; -Block g_random_data; -int g_bytes_used; -unsigned char g_SelfTestInitialized = 0; -u_int32_t gLastBlockChecksum; +static char zeros[(512 - kBSize * 8) / 8]; +static Block g_xkey; +static Block g_random_data; +static int g_bytes_used; +static unsigned char g_SelfTestInitialized = 0; +static u_int32_t gLastBlockChecksum; static const u_int32_t g_crc_table[] = { @@ -181,12 +223,16 @@ u_int32_t CalculateCRC(u_int8_t* buffer, size_t length) void random_block(Block b, int addOptional) { + SHA1_CTX sha1_ctx; + int repeatCount = 0; do { + // do one iteration + if (addOptional) { - // do one iteration + // create an xSeed to add. Block xSeed; prngOutput (gPrngRef, (BYTE*) &xSeed, sizeof (xSeed)); @@ -194,17 +240,33 @@ random_block(Block b, int addOptional) add_blocks (g_xkey, xSeed, 0); } + // initialize the value of H + FIPS_SHA1Init(&sha1_ctx); + + // to stay compatible with the FIPS specification, we need to flip the bytes in + // g_xkey to little endian byte order. In our case, this makes exactly no difference + // (random is random), but we need to do it anyway to keep FIPS happy + // compute "G" - SHA1Update (&g_sha1_ctx, (const u_int8_t *) &g_xkey, sizeof (g_xkey)); + FIPS_SHA1Update(&sha1_ctx, g_xkey, kBlockSize); // add zeros to fill the internal SHA-1 buffer - SHA1Update (&g_sha1_ctx, (const u_int8_t *)zeros, sizeof (zeros)); + FIPS_SHA1Update (&sha1_ctx, (const u_int8_t *)zeros, sizeof (zeros)); + + // we have to do a byte order correction here because the sha1 math is being done internally + // as u_int32_t, not a stream of bytes. Since we maintain our data as a byte stream, we need + // to convert - // write the resulting block - memmove(b, g_sha1_ctx.h.b8, sizeof (Block)); + u_int32_t* finger = (u_int32_t*) b; + + unsigned j; + for (j = 0; j < kBlockSize / sizeof (u_int32_t); ++j) + { + *finger++ = OSSwapHostToBigInt32(sha1_ctx.h.b32[j]); + } // calculate the CRC-32 of the block - u_int32_t new_crc = CalculateCRC(g_sha1_ctx.h.b8, sizeof (Block)); + u_int32_t new_crc = CalculateCRC(sha1_ctx.h.b8, sizeof (Block)); // make sure we don't repeat int cmp = new_crc == gLastBlockChecksum; @@ -249,8 +311,27 @@ void PreliminarySetup(void) { prng_error_status perr; - struct timeval tt; - char buffer [16]; + + /* Multiple threads can enter this as a result of an earlier + * check of gYarrowMutex. We make sure that only one of them + * can enter at a time. If one of them enters and discovers + * that gYarrowMutex is no longer NULL, we know that another + * thread has initialized the Yarrow state and we can exit. + */ + + /* The first thread that enters this function will find + * gYarrowInitializationLock set to 0. It will atomically + * set the value to 1 and, seeing that it was zero, drop + * out of the loop. Other threads will see that the value is + * 1 and continue to loop until we are initialized. + */ + + while (OSTestAndSet(0, &gYarrowInitializationLock)); /* serialize access to this function */ + + if (gYarrowMutex) { + /* we've already been initialized, clear and get out */ + goto function_exit; + } /* create a Yarrow object */ perr = prngInitialize(&gPrngRef); @@ -262,36 +343,41 @@ PreliminarySetup(void) /* clear the error flag, reads and write should then work */ gRandomError = 0; + uint64_t tt; + char buffer [16]; + /* get a little non-deterministic data as an initial seed. */ - microtime(&tt); - - /* - * So how much of the system clock is entropic? - * It's hard to say, but assume that at least the - * least significant byte of a 64 bit structure - * is entropic. It's probably more, how can you figure - * the exact time the user turned the computer on, for example. - */ + /* On OSX, securityd will add much more entropy as soon as it */ + /* comes up. On iOS, entropy is added with each system interrupt. */ + tt = early_random(); + perr = prngInput(gPrngRef, (BYTE*) &tt, sizeof (tt), SYSTEM_SOURCE, 8); if (perr != 0) { /* an error, complain */ printf ("Couldn't seed Yarrow.\n"); - return; + goto function_exit; } /* turn the data around */ - perr = prngOutput(gPrngRef, (BYTE*)buffer, sizeof (buffer)); + perr = prngOutput(gPrngRef, (BYTE*) buffer, sizeof (buffer)); /* and scramble it some more */ perr = prngForceReseed(gPrngRef, RESEED_TICKS); /* make a mutex to control access */ - gYarrowMutex = mutex_alloc(0); + gYarrowGrpAttr = lck_grp_attr_alloc_init(); + gYarrowGrp = lck_grp_alloc_init("random", gYarrowGrpAttr); + gYarrowAttr = lck_attr_alloc_init(); + gYarrowMutex = lck_mtx_alloc_init(gYarrowGrp, gYarrowAttr); fips_initialize (); + +function_exit: + /* allow other threads to figure out whether or not we have been initialized. */ + gYarrowInitializationLock = 0; } -const Block kKnownAnswer = {0x92b404e5, 0x56588ced, 0x6c1acd4e, 0xbf053f68, 0x9f73a93}; +const Block kKnownAnswer = {0x92, 0xb4, 0x04, 0xe5, 0x56, 0x58, 0x8c, 0xed, 0x6c, 0x1a, 0xcd, 0x4e, 0xbf, 0x05, 0x3f, 0x68, 0x09, 0xf7, 0x3a, 0x93}; void fips_initialize(void) @@ -299,25 +385,18 @@ fips_initialize(void) /* So that we can do the self test, set the seed to zero */ memset(&g_xkey, 0, sizeof(g_xkey)); - /* initialize our SHA1 generator */ - SHA1Init (&g_sha1_ctx); - /* other initializations */ memset (zeros, 0, sizeof (zeros)); g_bytes_used = 0; random_block(g_random_data, FALSE); // check here to see if we got the initial data we were expecting - int i; - for (i = 0; i < kBSize; ++i) + if (memcmp(kKnownAnswer, g_random_data, kBlockSize) != 0) { - if (kKnownAnswer[i] != g_random_data[i]) - { - panic("FIPS random self test failed"); - } + panic("FIPS random self test failed"); } - - // now do the random block again to make sure that userland doesn't get predictable data + + // now do the random block again to make sure that userland doesn't get predicatable data random_block(g_random_data, TRUE); } @@ -330,14 +409,11 @@ random_init(void) { int ret; - if (gRandomInstalled) + if (OSTestAndSet(0, &gRandomInstalled)) { + /* do this atomically so that it works correctly with + multiple threads */ return; - - /* install us in the file system */ - gRandomInstalled = 1; - - /* setup yarrow and the mutex */ - PreliminarySetup(); + } ret = cdevsw_add(RANDOM_MAJOR, &random_cdevsw); if (ret < 0) { @@ -355,6 +431,9 @@ random_init(void) */ devfs_make_node(makedev (ret, 1), DEVFS_CHAR, UID_ROOT, GID_WHEEL, 0666, "urandom", 0); + + /* setup yarrow and the mutex if needed*/ + PreliminarySetup(); } int @@ -428,20 +507,19 @@ random_write (__unused dev_t dev, struct uio *uio, __unused int ioflag) } /* get control of the Yarrow instance, Yarrow is NOT thread safe */ - mutex_lock(gYarrowMutex); + lck_mtx_lock(gYarrowMutex); /* Security server is sending us entropy */ while (uio_resid(uio) > 0 && retCode == 0) { /* get the user's data */ - // LP64todo - fix this! uio_resid may be 64-bit value int bytesToInput = min(uio_resid(uio), sizeof (rdBuffer)); retCode = uiomove(rdBuffer, bytesToInput, uio); if (retCode != 0) goto /*ugh*/ error_exit; /* put it in Yarrow */ - if (prngInput(gPrngRef, (BYTE*)rdBuffer, + if (prngInput(gPrngRef, (BYTE*) rdBuffer, bytesToInput, SYSTEM_SOURCE, bytesToInput * 8) != 0) { retCode = EIO; @@ -458,53 +536,10 @@ random_write (__unused dev_t dev, struct uio *uio, __unused int ioflag) /* retCode should be 0 at this point */ error_exit: /* do this to make sure the mutex unlocks. */ - mutex_unlock(gYarrowMutex); + lck_mtx_unlock(gYarrowMutex); return (retCode); } -/* - * return data to the caller. Results unpredictable. - */ -int random_read(__unused dev_t dev, struct uio *uio, __unused int ioflag) -{ - int retCode = 0; - - if (gRandomError != 0) - return (ENOTSUP); - - /* lock down the mutex */ - mutex_lock(gYarrowMutex); - - int bytes_remaining = uio_resid(uio); - while (bytes_remaining > 0 && retCode == 0) { - /* get the user's data */ - int bytes_to_read = 0; - - int bytes_available = kBSizeInBytes - g_bytes_used; - if (bytes_available == 0) - { - random_block(g_random_data, TRUE); - g_bytes_used = 0; - bytes_available = kBSizeInBytes; - } - - bytes_to_read = min (bytes_remaining, bytes_available); - - retCode = uiomove(((u_int8_t*)g_random_data)+ g_bytes_used, bytes_to_read, uio); - g_bytes_used += bytes_to_read; - - if (retCode != 0) - goto error_exit; - - bytes_remaining = uio_resid(uio); - } - - retCode = 0; - -error_exit: - mutex_unlock(gYarrowMutex); - return retCode; -} /* export good random numbers to the rest of the kernel */ void @@ -514,36 +549,67 @@ read_random(void* buffer, u_int numbytes) PreliminarySetup (); } - mutex_lock(gYarrowMutex); - + lck_mtx_lock(gYarrowMutex); + + int bytes_read = 0; int bytes_remaining = numbytes; while (bytes_remaining > 0) { - int bytes_to_read = min(bytes_remaining, kBSizeInBytes - g_bytes_used); + int bytes_to_read = min(bytes_remaining, kBlockSize - g_bytes_used); if (bytes_to_read == 0) { random_block(g_random_data, TRUE); g_bytes_used = 0; - bytes_to_read = min(bytes_remaining, kBSizeInBytes); + bytes_to_read = min(bytes_remaining, kBlockSize); } - memmove (buffer, ((u_int8_t*)g_random_data)+ bytes_read, bytes_to_read); + memmove ((u_int8_t*) buffer + bytes_read, ((u_int8_t*)g_random_data)+ g_bytes_used, bytes_to_read); g_bytes_used += bytes_to_read; bytes_read += bytes_to_read; bytes_remaining -= bytes_to_read; } - mutex_unlock(gYarrowMutex); + lck_mtx_unlock(gYarrowMutex); } /* - * Return an unsigned long pseudo-random number. + * return data to the caller. Results unpredictable. + */ +int +random_read(__unused dev_t dev, struct uio *uio, __unused int ioflag) +{ + int retCode = 0; + + if (gRandomError != 0) + return (ENOTSUP); + + char buffer[64]; + + user_ssize_t bytes_remaining = uio_resid(uio); + while (bytes_remaining > 0 && retCode == 0) { + user_ssize_t bytesToRead = min(sizeof(buffer), bytes_remaining); + read_random(buffer, bytesToRead); + retCode = uiomove(buffer, bytesToRead, uio); + + if (retCode != 0) + goto error_exit; + + bytes_remaining = uio_resid(uio); + } + + retCode = 0; + +error_exit: + return retCode; +} +/* + * Return an u_int32_t pseudo-random number. */ -u_long +u_int32_t RandomULong(void) { - u_long buf; + u_int32_t buf; read_random(&buf, sizeof (buf)); return (buf); }