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