2 * Copyright (c) 1999-2009 Apple, Inc. All rights reserved.
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
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.
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
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.
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
30 WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
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.
37 WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
40 #include <sys/param.h>
41 #include <sys/systm.h>
43 #include <sys/errno.h>
44 #include <sys/ioctl.h>
46 #include <sys/fcntl.h>
48 #include <miscfs/devfs/devfs.h>
49 #include <kern/lock.h>
50 #include <kern/clock.h>
52 #include <sys/malloc.h>
53 #include <sys/uio_internal.h>
55 #include <dev/random/randomdev.h>
56 #include <dev/random/YarrowCoreLib/include/yarrow.h>
58 #include <libkern/OSByteOrder.h>
59 #include <libkern/OSAtomic.h>
61 #include <mach/mach_time.h>
62 #include <machine/machine_routines.h>
64 #include "fips_sha1.h"
66 #define RANDOM_MAJOR -1 /* let the kernel pick the device number */
68 d_ioctl_t random_ioctl
;
71 * A struct describing which functions will get invoked for certain
74 static struct cdevsw random_cdevsw
=
76 random_open
, /* open */
77 random_close
, /* close */
78 random_read
, /* read */
79 random_write
, /* write */
80 random_ioctl
, /* ioctl */
81 (stop_fcn_t
*)nulldev
, /* stop */
82 (reset_fcn_t
*)nulldev
, /* reset */
84 eno_select
, /* select */
86 eno_strat
, /* strategy */
94 WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
96 ANY CODE PROTECTED UNDER "#ifdef __arm__" IS SERIOUSLY SUPPOSED TO BE THERE!
97 IF YOU REMOVE ARM CODE, RANDOM WILL NOT MEAN ANYTHING FOR iPHONES ALL OVER.
98 PLEASE DON'T TOUCH __arm__ CODE IN THIS FILE!
100 WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING!
104 /* Used to detect whether we've already been initialized */
105 static UInt8 gRandomInstalled
= 0;
106 static PrngRef gPrngRef
;
107 static int gRandomError
= 1;
108 static lck_grp_t
*gYarrowGrp
;
109 static lck_attr_t
*gYarrowAttr
;
110 static lck_grp_attr_t
*gYarrowGrpAttr
;
111 static lck_mtx_t
*gYarrowMutex
= 0;
112 static UInt8 gYarrowInitializationLock
= 0;
114 #define RESEED_TICKS 50 /* how long a reseed operation can take */
117 typedef u_int8_t BlockWord
;
119 typedef BlockWord Block
[kBSize
];
120 enum {kBlockSize
= sizeof(Block
)};
122 /* define prototypes to keep the compiler happy... */
124 void add_blocks(Block a
, Block b
, BlockWord carry
);
125 void fips_initialize(void);
126 void random_block(Block b
, int addOptional
);
127 u_int32_t
CalculateCRC(u_int8_t
* buffer
, size_t length
);
130 * Get 120 bits from yarrow
134 * add block b to block a
137 add_blocks(Block a
, Block b
, BlockWord carry
)
139 int i
= kBlockSize
- 1;
142 u_int32_t c
= (u_int32_t
)carry
+
153 static char zeros
[(512 - kBSize
* 8) / 8];
155 static Block g_random_data
;
156 static int g_bytes_used
;
157 static unsigned char g_SelfTestInitialized
= 0;
158 static u_int32_t gLastBlockChecksum
;
160 static const u_int32_t g_crc_table
[] =
162 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
163 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
164 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
165 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
166 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
167 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
168 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
169 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
170 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
171 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
172 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
173 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
174 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
175 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
176 0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
177 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
178 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
179 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
180 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
181 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
182 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
183 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
184 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
185 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
186 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
187 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
188 0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
189 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
190 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
191 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
192 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
193 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D,
197 * Setup for fips compliance
201 * calculate a crc-32 checksum
203 u_int32_t
CalculateCRC(u_int8_t
* buffer
, size_t length
)
208 for (i
= 0; i
< length
; ++i
)
210 u_int32_t temp
= (crc
^ ((u_int32_t
) buffer
[i
])) & 0xFF;
211 crc
= (crc
>> 8) ^ g_crc_table
[temp
];
218 * get a random block of data per fips 186-2
221 random_block(Block b
, int addOptional
)
232 // create an xSeed to add.
234 prngOutput (gPrngRef
, (BYTE
*) &xSeed
, sizeof (xSeed
));
236 // add the seed to the previous value of g_xkey
237 add_blocks (g_xkey
, xSeed
, 0);
240 // initialize the value of H
241 FIPS_SHA1Init(&sha1_ctx
);
243 // to stay compatible with the FIPS specification, we need to flip the bytes in
244 // g_xkey to little endian byte order. In our case, this makes exactly no difference
245 // (random is random), but we need to do it anyway to keep FIPS happy
248 FIPS_SHA1Update(&sha1_ctx
, g_xkey
, kBlockSize
);
250 // add zeros to fill the internal SHA-1 buffer
251 FIPS_SHA1Update (&sha1_ctx
, (const u_int8_t
*)zeros
, sizeof (zeros
));
253 // we have to do a byte order correction here because the sha1 math is being done internally
254 // as u_int32_t, not a stream of bytes. Since we maintain our data as a byte stream, we need
257 u_int32_t
* finger
= (u_int32_t
*) b
;
260 for (j
= 0; j
< kBlockSize
/ sizeof (u_int32_t
); ++j
)
262 *finger
++ = OSSwapHostToBigInt32(sha1_ctx
.h
.b32
[j
]);
265 // calculate the CRC-32 of the block
266 u_int32_t new_crc
= CalculateCRC(sha1_ctx
.h
.b8
, sizeof (Block
));
268 // make sure we don't repeat
269 int cmp
= new_crc
== gLastBlockChecksum
;
270 gLastBlockChecksum
= new_crc
;
271 if (!g_SelfTestInitialized
)
273 g_SelfTestInitialized
= 1;
283 // fix up the next value of g_xkey
284 add_blocks (g_xkey
, b
, 1);
285 } while (repeatCount
< 2);
288 * If we got here, three sucessive checksums of the random number
289 * generator have been the same. Since the odds of this happening are
290 * 1 in 18,446,744,073,709,551,616, (1 in 18 quintillion) one of the following has
291 * most likely happened:
293 * 1: There is a significant bug in this code.
294 * 2: There has been a massive system failure.
295 * 3: The universe has ceased to exist.
297 * There is no good way to recover from any of these cases. We
301 panic("FIPS random self-test failed.");
305 *Initialize ONLY the Yarrow generator.
308 PreliminarySetup(void)
310 prng_error_status perr
;
312 /* Multiple threads can enter this as a result of an earlier
313 * check of gYarrowMutex. We make sure that only one of them
314 * can enter at a time. If one of them enters and discovers
315 * that gYarrowMutex is no longer NULL, we know that another
316 * thread has initialized the Yarrow state and we can exit.
319 /* The first thread that enters this function will find
320 * gYarrowInitializationLock set to 0. It will atomically
321 * set the value to 1 and, seeing that it was zero, drop
322 * out of the loop. Other threads will see that the value is
323 * 1 and continue to loop until we are initialized.
326 while (OSTestAndSet(0, &gYarrowInitializationLock
)); /* serialize access to this function */
329 /* we've already been initialized, clear and get out */
333 /* create a Yarrow object */
334 perr
= prngInitialize(&gPrngRef
);
336 printf ("Couldn't initialize Yarrow, /dev/random will not work.\n");
340 /* clear the error flag, reads and write should then work */
346 /* get a little non-deterministic data as an initial seed. */
347 /* On OSX, securityd will add much more entropy as soon as it */
348 /* comes up. On iOS, entropy is added with each system interrupt. */
352 * So how much of the system clock is entropic?
353 * It's hard to say, but assume that at least the
354 * least significant byte of a 64 bit structure
355 * is entropic. It's probably more, how can you figure
356 * the exact time the user turned the computer on, for example.
358 perr
= prngInput(gPrngRef
, (BYTE
*) &tt
, sizeof (tt
), SYSTEM_SOURCE
, 8);
360 /* an error, complain */
361 printf ("Couldn't seed Yarrow.\n");
365 /* turn the data around */
366 perr
= prngOutput(gPrngRef
, (BYTE
*) buffer
, sizeof (buffer
));
368 /* and scramble it some more */
369 perr
= prngForceReseed(gPrngRef
, RESEED_TICKS
);
371 /* make a mutex to control access */
372 gYarrowGrpAttr
= lck_grp_attr_alloc_init();
373 gYarrowGrp
= lck_grp_alloc_init("random", gYarrowGrpAttr
);
374 gYarrowAttr
= lck_attr_alloc_init();
375 gYarrowMutex
= lck_mtx_alloc_init(gYarrowGrp
, gYarrowAttr
);
380 /* allow other threads to figure out whether or not we have been initialized. */
381 gYarrowInitializationLock
= 0;
384 const Block kKnownAnswer
= {0x92, 0xb4, 0x04, 0xe5, 0x56, 0x58, 0x8c, 0xed, 0x6c, 0x1a, 0xcd, 0x4e, 0xbf, 0x05, 0x3f, 0x68, 0x09, 0xf7, 0x3a, 0x93};
387 fips_initialize(void)
389 /* So that we can do the self test, set the seed to zero */
390 memset(&g_xkey
, 0, sizeof(g_xkey
));
392 /* other initializations */
393 memset (zeros
, 0, sizeof (zeros
));
395 random_block(g_random_data
, FALSE
);
397 // check here to see if we got the initial data we were expecting
398 if (memcmp(kKnownAnswer
, g_random_data
, kBlockSize
) != 0)
400 panic("FIPS random self test failed");
403 // now do the random block again to make sure that userland doesn't get predicatable data
404 random_block(g_random_data
, TRUE
);
408 * Called to initialize our device,
409 * and to register ourselves with devfs
416 if (OSTestAndSet(0, &gRandomInstalled
)) {
417 /* do this atomically so that it works correctly with
422 ret
= cdevsw_add(RANDOM_MAJOR
, &random_cdevsw
);
424 printf("random_init: failed to allocate a major number!\n");
425 gRandomInstalled
= 0;
429 devfs_make_node(makedev (ret
, 0), DEVFS_CHAR
,
430 UID_ROOT
, GID_WHEEL
, 0666, "random", 0);
434 * (which is exactly the same thing in our context)
436 devfs_make_node(makedev (ret
, 1), DEVFS_CHAR
,
437 UID_ROOT
, GID_WHEEL
, 0666, "urandom", 0);
439 /* setup yarrow and the mutex if needed*/
444 random_ioctl( __unused dev_t dev
, u_long cmd
, __unused caddr_t data
,
445 __unused
int flag
, __unused
struct proc
*p
)
459 * Open the device. Make sure init happened, and make sure the caller is
464 random_open(__unused dev_t dev
, int flags
, __unused
int devtype
, __unused
struct proc
*p
)
466 if (gRandomError
!= 0) {
467 /* forget it, yarrow didn't come up */
472 * if we are being opened for write,
473 * make sure that we have privledges do so
475 if (flags
& FWRITE
) {
476 if (securelevel
>= 2)
479 if ((securelevel
>= 1) && proc_suser(p
))
481 #endif /* !__APPLE__ */
493 random_close(__unused dev_t dev
, __unused
int flags
, __unused
int mode
, __unused
struct proc
*p
)
500 * Get entropic data from the Security Server, and use it to reseed the
504 random_write (__unused dev_t dev
, struct uio
*uio
, __unused
int ioflag
)
509 if (gRandomError
!= 0) {
513 /* get control of the Yarrow instance, Yarrow is NOT thread safe */
514 lck_mtx_lock(gYarrowMutex
);
516 /* Security server is sending us entropy */
518 while (uio_resid(uio
) > 0 && retCode
== 0) {
519 /* get the user's data */
520 int bytesToInput
= min(uio_resid(uio
), sizeof (rdBuffer
));
521 retCode
= uiomove(rdBuffer
, bytesToInput
, uio
);
523 goto /*ugh*/ error_exit
;
525 /* put it in Yarrow */
526 if (prngInput(gPrngRef
, (BYTE
*) rdBuffer
,
527 bytesToInput
, SYSTEM_SOURCE
,
528 bytesToInput
* 8) != 0) {
535 if (prngForceReseed(gPrngRef
, RESEED_TICKS
) != 0) {
540 /* retCode should be 0 at this point */
542 error_exit
: /* do this to make sure the mutex unlocks. */
543 lck_mtx_unlock(gYarrowMutex
);
548 * return data to the caller. Results unpredictable.
551 random_read(__unused dev_t dev
, struct uio
*uio
, __unused
int ioflag
)
555 if (gRandomError
!= 0)
558 /* lock down the mutex */
559 lck_mtx_lock(gYarrowMutex
);
562 int bytes_remaining
= uio_resid(uio
);
563 while (bytes_remaining
> 0 && retCode
== 0) {
564 /* get the user's data */
565 int bytes_to_read
= 0;
567 int bytes_available
= kBlockSize
- g_bytes_used
;
568 if (bytes_available
== 0)
570 random_block(g_random_data
, TRUE
);
572 bytes_available
= kBlockSize
;
575 bytes_to_read
= min (bytes_remaining
, bytes_available
);
577 retCode
= uiomove(((caddr_t
)g_random_data
)+ g_bytes_used
, bytes_to_read
, uio
);
578 g_bytes_used
+= bytes_to_read
;
583 bytes_remaining
= uio_resid(uio
);
589 lck_mtx_unlock(gYarrowMutex
);
593 /* export good random numbers to the rest of the kernel */
595 read_random(void* buffer
, u_int numbytes
)
597 if (gYarrowMutex
== 0) { /* are we initialized? */
601 lck_mtx_lock(gYarrowMutex
);
604 int bytes_remaining
= numbytes
;
605 while (bytes_remaining
> 0) {
606 int bytes_to_read
= min(bytes_remaining
, kBlockSize
- g_bytes_used
);
607 if (bytes_to_read
== 0)
609 random_block(g_random_data
, TRUE
);
611 bytes_to_read
= min(bytes_remaining
, kBlockSize
);
614 memmove ((u_int8_t
*) buffer
+ bytes_read
, ((u_int8_t
*)g_random_data
)+ g_bytes_used
, bytes_to_read
);
615 g_bytes_used
+= bytes_to_read
;
616 bytes_read
+= bytes_to_read
;
617 bytes_remaining
-= bytes_to_read
;
620 lck_mtx_unlock(gYarrowMutex
);
624 * Return an u_int32_t pseudo-random number.
630 read_random(&buf
, sizeof (buf
));