1/*
2 * Copyright (c) 2013 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#include <kern/cpu_data.h>
30#include <kern/cpu_number.h>
31#include <kern/kalloc.h>
32#include <kern/machine.h>
33#include <kern/misc_protos.h>
34#include <kern/processor.h>
35#include <kern/sched.h>
36#include <kern/startup.h>
37#include <kern/thread.h>
38#include <kern/thread_call.h>
39#include <mach/machine.h>
40#include <mach/processor.h>
41#include <machine/cpu_data.h>
42#include <machine/simple_lock.h>
43#include <sys/errno.h>
44#include <sys/kdebug.h>
45#include <sys/random.h>
46#include <vm/pmap.h>
47#include <vm/vm_page.h>
48
49#include <corecrypto/ccdigest.h>
50#include <corecrypto/ccdrbg.h>
51#include <corecrypto/cckprng.h>
52#include <corecrypto/ccsha1.h>
53#include <corecrypto/ccsha2.h>
54#include <prng/random.h>
55
56#include <IOKit/IOPlatformExpert.h>
57#include <console/serial_protos.h>
58#include <pexpert/pexpert.h>
59
60#include <libkern/section_keywords.h>
61
62#if defined(__arm__) || defined(__arm64__)
63#include <arm/cpu_data_internal.h> // For MAX_CPUS
64#endif
65
66#if defined(__x86_64__)
67#include <i386/cpuid.h>
68
69static int
70rdseed_step(uint64_t * seed)
71{
72 uint8_t ok;
73
74 asm volatile("rdseed %0; setc %1" : "=r"(*seed), "=qm"(ok));
75
76 return (int)ok;
77}
78
79static int
80rdseed_retry(uint64_t * seed, size_t nretries)
81{
82 size_t i;
83
84 for (i = 0; i < nretries; i += 1) {
85 if (rdseed_step(seed)) {
86 return 1;
87 } else {
88 asm volatile("pause");
89 }
90 }
91
92 return 0;
93}
94
95static size_t
96rdseed_seed(void * buf, size_t nwords)
97{
98 uint64_t * buf_words;
99 size_t i;
100
101 if (nwords > 8) {
102 nwords = 8;
103 }
104
105 buf_words = buf;
106 for (i = 0; i < nwords; i += 1) {
107 if (!rdseed_retry(buf_words + i, 10)) {
108 return i;
109 }
110 }
111
112 return nwords;
113}
114
115static int
116rdrand_step(uint64_t * rand)
117{
118 uint8_t ok;
119
120 asm volatile("rdrand %0; setc %1" : "=r"(*rand), "=qm"(ok));
121
122 return (int)ok;
123}
124
125static int
126rdrand_retry(uint64_t * rand, size_t nretries)
127{
128 size_t i;
129
130 for (i = 0; i < nretries; i += 1) {
131 if (rdrand_step(rand)) {
132 return 1;
133 }
134 }
135
136 return 0;
137}
138
139static size_t
140rdrand_seed(void * buf, size_t nwords)
141{
142 size_t i;
143 uint64_t w;
144 uint8_t hash[CCSHA256_OUTPUT_SIZE];
145 const struct ccdigest_info * di = &ccsha256_ltc_di;
146
147 ccdigest_di_decl(di, ctx);
148 ccdigest_init(di, ctx);
149
150 for (i = 0; i < 1023; i += 1) {
151 if (!rdrand_retry(&w, 10)) {
152 nwords = 0;
153 goto out;
154 }
155 ccdigest_update(di, ctx, sizeof w, &w);
156 }
157
158 ccdigest_final(di, ctx, hash);
159
160 if (nwords > 2) {
161 nwords = 2;
162 }
163
164 memcpy(buf, hash, nwords * sizeof(uint64_t));
165
166out:
167 ccdigest_di_clear(di, ctx);
168 bzero(hash, sizeof hash);
169 bzero(&w, sizeof w);
170
171 return nwords;
172}
173
174static void
175intel_entropysource(void * buf, size_t * nbytes)
176{
177 size_t nwords;
178
179 /* only handle complete words */
180 assert(*nbytes % sizeof(uint64_t) == 0);
181
182 nwords = (*nbytes) / sizeof(uint64_t);
183 if (cpuid_leaf7_features() & CPUID_LEAF7_FEATURE_RDSEED) {
184 nwords = rdseed_seed(buf, nwords);
185 *nbytes = nwords * sizeof(uint64_t);
186 } else if (cpuid_features() & CPUID_FEATURE_RDRAND) {
187 nwords = rdrand_seed(buf, nwords);
188 *nbytes = nwords * sizeof(uint64_t);
189 } else {
190 *nbytes = 0;
191 }
192}
193
194#endif /* defined(__x86_64__) */
195
196void entropy_buffer_read(void * buffer, size_t * count);
197
198typedef void (*entropysource)(void * buf, size_t * nbytes);
199
200static const entropysource entropysources[] = {
201 entropy_buffer_read,
202#if defined(__x86_64__)
203 intel_entropysource,
204#endif
205};
206
207static const size_t nsources = sizeof entropysources / sizeof entropysources[0];
208
209static size_t
210entropy_readall(void * buf, size_t nbytes_persource)
211{
212 uint8_t * buf_bytes = buf;
213 size_t i;
214 size_t nbytes_total = 0;
215
216 for (i = 0; i < nsources; i += 1) {
217 size_t nbytes = nbytes_persource;
218 entropysources[i](buf_bytes, &nbytes);
219 bzero(buf_bytes + nbytes, nbytes_persource - nbytes);
220 nbytes_total += nbytes;
221 buf_bytes += nbytes_persource;
222 }
223
224 return nbytes_total;
225}
226
227static struct {
228 struct cckprng_ctx ctx;
229 struct {
230 lck_grp_t * group;
231 lck_attr_t * attrs;
232 lck_grp_attr_t * group_attrs;
233 lck_mtx_t * mutex;
234 } lock;
235} prng;
236
237static SECURITY_READ_ONLY_LATE(prng_fns_t) prng_fns = NULL;
238
239static int
240prng_init(cckprng_ctx_t ctx, size_t nbytes, const void * seed)
241{
242 int err = prng_fns->init(ctx, nbytes, seed);
243 if (err == CCKPRNG_ABORT) {
244 panic("prng_init");
245 }
246 return err;
247}
248
249#define PERMIT_WRITE_RANDOM 0
250
251#if PERMIT_WRITE_RANDOM
252static int
253prng_reseed(cckprng_ctx_t ctx, size_t nbytes, const void * seed)
254{
255 int err = prng_fns->reseed(ctx, nbytes, seed);
256 if (err == CCKPRNG_ABORT) {
257 panic("prng_reseed");
258 }
259 return err;
260}
261#endif
262
263static int
264prng_addentropy(cckprng_ctx_t ctx, size_t nbytes, const void * entropy)
265{
266 int err = prng_fns->addentropy(ctx, nbytes, entropy);
267 if (err == CCKPRNG_ABORT) {
268 panic("prng_addentropy");
269 }
270 return err;
271}
272
273static int
274prng_generate(cckprng_ctx_t ctx, size_t nbytes, void * out)
275{
276 int err = prng_fns->generate(ctx, nbytes, out);
277 if (err == CCKPRNG_ABORT) {
278 panic("prng_generate");
279 }
280 return err;
281}
282
283entropy_data_t EntropyData = {.index_ptr = EntropyData.buffer};
284
285static struct {
286 uint8_t seed[nsources][EARLY_RANDOM_SEED_SIZE];
287 int seedset;
288 uint8_t master_drbg_state[EARLY_RANDOM_STATE_STATIC_SIZE];
289 struct ccdrbg_state * drbg_states[MAX_CPUS];
290 struct ccdrbg_info drbg_info;
291 const struct ccdrbg_nisthmac_custom drbg_custom;
292} erandom = {.drbg_custom = {
293 .di = &ccsha1_eay_di,
294 .strictFIPS = 0,
295 }};
296
297static void read_erandom(void * buf, uint32_t nbytes);
298
299void
300entropy_buffer_read(void * buffer, size_t * count)
301{
302 boolean_t current_state;
303 unsigned int i, j;
304
305 if (!erandom.seedset) {
306 panic("early_random was never invoked");
307 }
308
309 if (*count > ENTROPY_BUFFER_BYTE_SIZE) {
310 *count = ENTROPY_BUFFER_BYTE_SIZE;
311 }
312
313 current_state = ml_set_interrupts_enabled(FALSE);
314
315 memcpy(buffer, EntropyData.buffer, *count);
316
317 /* Consider removing this mixing step rdar://problem/31668239 */
318 for (i = 0, j = (ENTROPY_BUFFER_SIZE - 1); i < ENTROPY_BUFFER_SIZE; j = i, i++)
319 EntropyData.buffer[i] = EntropyData.buffer[i] ^ EntropyData.buffer[j];
320
321 (void)ml_set_interrupts_enabled(current_state);
322
323#if DEVELOPMENT || DEBUG
324 uint32_t * word = buffer;
325 /* Good for both 32-bit and 64-bit kernels. */
326 for (i = 0; i < ENTROPY_BUFFER_SIZE; i += 4)
327 /*
328 * We use "EARLY" here so that we can grab early entropy on
329 * ARM, where tracing is not started until after PRNG is
330 * initialized.
331 */
332 KERNEL_DEBUG_EARLY(ENTROPY_READ(i / 4), word[i + 0], word[i + 1], word[i + 2], word[i + 3]);
333#endif
334}
335
336/*
337 * Return a uniformly distributed 64-bit random number.
338 *
339 * This interface should have minimal dependencies on kernel
340 * services, and thus be available very early in the life
341 * of the kernel.
342 * This provides cryptographically secure randomness.
343 * Each processor has its own generator instance.
344 * It is seeded (lazily) with entropy provided by the Booter.
345 *
346 * For <rdar://problem/17292592> the algorithm switched from LCG to
347 * NIST HMAC DBRG as follows:
348 * - When first called (on OSX this is very early while page tables are being
349 * built) early_random() calls ccdrbg_factory_hmac() to set-up a ccdbrg info
350 * structure.
351 * - The boot processor's ccdrbg state structure is a statically allocated area
352 * which is then initialized by calling the ccdbrg_init method.
353 * The initial entropy is 16 bytes of boot entropy.
354 * The nonce is the first 8 bytes of entropy xor'ed with a timestamp
355 * from ml_get_timebase().
356 * The personalization data provided is null.
357 * - The first 64-bit random value is returned on the boot processor from
358 * an invocation of the ccdbrg_generate method.
359 * - Non-boot processor's DRBG state structures are allocated dynamically
360 * from prng_init(). Each is initialized with the same 16 bytes of entropy
361 * but with a different timestamped nonce and cpu number as personalization.
362 * - Subsequent calls to early_random() pass to read_erandom() to generate
363 * an 8-byte random value. read_erandom() ensures that pre-emption is
364 * disabled and selects the DBRG state from the current processor.
365 * The ccdbrg_generate method is called for the required random output.
366 * If this method returns CCDRBG_STATUS_NEED_RESEED, the erandom.seed buffer
367 * is re-filled with kernel-harvested entropy and the ccdbrg_reseed method is
368 * called with this new entropy. The kernel panics if a reseed fails.
369 */
370uint64_t
371early_random(void)
372{
373 uint32_t cnt = 0;
374 uint64_t result;
375 uint64_t nonce;
376 int rc;
377 int ps;
378 struct ccdrbg_state * state;
379
380 if (!erandom.seedset) {
381 erandom.seedset = 1;
382 cnt = PE_get_random_seed((unsigned char *)EntropyData.buffer, sizeof(EntropyData.buffer));
383
384 if (cnt < sizeof(EntropyData.buffer)) {
385 /*
386 * Insufficient entropy is fatal. We must fill the
387 * entire entropy buffer during initializaton.
388 */
389 panic("EntropyData needed %lu bytes, but got %u.\n", sizeof(EntropyData.buffer), cnt);
390 }
391
392 entropy_readall(&erandom.seed, EARLY_RANDOM_SEED_SIZE);
393
394 /* Init DRBG for NIST HMAC */
395 ccdrbg_factory_nisthmac(&erandom.drbg_info, &erandom.drbg_custom);
396 assert(erandom.drbg_info.size <= sizeof(erandom.master_drbg_state));
397 state = (struct ccdrbg_state *)erandom.master_drbg_state;
398 erandom.drbg_states[master_cpu] = state;
399
400 /*
401 * Init our DBRG from the boot entropy and a timestamp as nonce
402 * and the cpu number as personalization.
403 */
404 assert(sizeof(erandom.seed) > sizeof(nonce));
405 nonce = ml_get_timebase();
406 ps = 0; /* boot cpu */
407 rc = ccdrbg_init(&erandom.drbg_info, state, sizeof(erandom.seed), erandom.seed, sizeof(nonce), &nonce, sizeof(ps), &ps);
408 cc_clear(sizeof(nonce), &nonce);
409 if (rc != CCDRBG_STATUS_OK)
410 panic("ccdrbg_init() returned %d", rc);
411
412 /* Generate output */
413 rc = ccdrbg_generate(&erandom.drbg_info, state, sizeof(result), &result, 0, NULL);
414 if (rc != CCDRBG_STATUS_OK)
415 panic("ccdrbg_generate() returned %d", rc);
416
417 return result;
418 };
419
420 read_erandom(&result, sizeof(result));
421
422 return result;
423}
424
425static void
426read_erandom(void * buffer, u_int numBytes)
427{
428 int cpu;
429 int rc;
430 size_t nbytes;
431 struct ccdrbg_state * state;
432
433 mp_disable_preemption();
434 cpu = cpu_number();
435 state = erandom.drbg_states[cpu];
436 assert(state);
437 for (;;) {
438 /* Generate output */
439 rc = ccdrbg_generate(&erandom.drbg_info, state, numBytes, buffer, 0, NULL);
440 if (rc == CCDRBG_STATUS_OK)
441 break;
442 if (rc == CCDRBG_STATUS_NEED_RESEED) {
443 /* It's time to reseed. Get more entropy */
444 nbytes = entropy_readall(erandom.seed, EARLY_RANDOM_SEED_SIZE);
445 assert(nbytes >= EARLY_RANDOM_SEED_SIZE);
446 rc = ccdrbg_reseed(&erandom.drbg_info, state, sizeof(erandom.seed), erandom.seed, 0, NULL);
447 cc_clear(sizeof(erandom.seed), erandom.seed);
448 if (rc == CCDRBG_STATUS_OK)
449 continue;
450 panic("read_erandom reseed error %d\n", rc);
451 }
452 panic("read_erandom ccdrbg error %d\n", rc);
453 }
454 mp_enable_preemption();
455}
456
457void
458read_frandom(void * buffer, u_int numBytes)
459{
460 uint8_t * buffer_bytes = buffer;
461 int nbytes;
462
463 /*
464 * Split up into requests for blocks smaller than
465 * than the DBRG request limit. iThis limit is private but
466 * for NISTHMAC it's known to be greater then 4096.
467 */
468 while (numBytes) {
469 nbytes = MIN(numBytes, PAGE_SIZE);
470 read_erandom(buffer_bytes, nbytes);
471 buffer_bytes += nbytes;
472 numBytes -= nbytes;
473 }
474}
475
476void
477early_random_cpu_init(int cpu)
478{
479 uint64_t nonce;
480 int rc;
481 struct ccdrbg_state * state;
482
483 /*
484 * Allocate state and initialize DBRG state for early_random()
485 * for this processor.
486 */
487 assert(cpu != master_cpu);
488 assert(erandom.drbg_states[cpu] == NULL);
489
490 state = kalloc(erandom.drbg_info.size);
491 if (state == NULL) {
492 panic("prng_init kalloc failed\n");
493 }
494 erandom.drbg_states[cpu] = state;
495
496 /*
497 * Init our DBRG from boot entropy, nonce as timestamp
498 * and use the cpu number as the personalization parameter.
499 */
500 nonce = ml_get_timebase();
501 rc = ccdrbg_init(&erandom.drbg_info, state, sizeof(erandom.seed), erandom.seed, sizeof(nonce), &nonce, sizeof(cpu), &cpu);
502 cc_clear(sizeof(nonce), &nonce);
503 if (rc != CCDRBG_STATUS_OK)
504 panic("ccdrbg_init() returned %d", rc);
505}
506
507void
508register_and_init_prng(prng_fns_t fns)
509{
510 uint8_t buf[nsources][ENTROPY_BUFFER_BYTE_SIZE];
511 size_t nbytes;
512
513 assert(cpu_number() == master_cpu);
514 assert(prng_fns == NULL);
515
516 prng_fns = fns;
517
518 /* make a mutex to control access */
519 prng.lock.group_attrs = lck_grp_attr_alloc_init();
520 prng.lock.group = lck_grp_alloc_init("random", prng.lock.group_attrs);
521 prng.lock.attrs = lck_attr_alloc_init();
522 prng.lock.mutex = lck_mtx_alloc_init(prng.lock.group, prng.lock.attrs);
523
524 nbytes = entropy_readall(buf, ENTROPY_BUFFER_BYTE_SIZE);
525 (void)prng_init(&prng.ctx, nbytes, buf);
526 cc_clear(sizeof(buf), buf);
527}
528
529static void
530Reseed(void)
531{
532 uint8_t buf[nsources][ENTROPY_BUFFER_BYTE_SIZE];
533 size_t nbytes;
534
535 lck_mtx_assert(prng.lock.mutex, LCK_MTX_ASSERT_OWNED);
536
537 nbytes = entropy_readall(buf, ENTROPY_BUFFER_BYTE_SIZE);
538 PRNG_CCKPRNG((void)prng_addentropy(&prng.ctx, nbytes, buf));
539 cc_clear(sizeof(buf), buf);
540}
541
542/* export good random numbers to the rest of the kernel */
543void
544read_random(void * buffer, u_int numbytes)
545{
546 int err;
547
548 lck_mtx_lock(prng.lock.mutex);
549
550 /*
551 * Call PRNG, reseeding and retrying if requested.
552 */
553 for (;;) {
554 PRNG_CCKPRNG(err = prng_generate(&prng.ctx, numbytes, buffer));
555 if (err == CCKPRNG_OK)
556 break;
557 if (err == CCKPRNG_NEED_ENTROPY) {
558 Reseed();
559 continue;
560 }
561 panic("read_random() error %d\n", err);
562 }
563
564 lck_mtx_unlock(prng.lock.mutex);
565}
566
567int
568write_random(void * buffer, u_int numbytes)
569{
570#if PERMIT_WRITE_RANDOM
571 int err;
572
573 lck_mtx_lock(prng.lock.mutex);
574 err = prng_reseed(&prng.ctx, numbytes, buffer);
575 lck_mtx_unlock(prng.lock.mutex);
576
577 return err ? EIO : 0;
578#else
579#pragma unused(buffer, numbytes)
580 return 0;
581#endif
582}
583
584/*
585 * Boolean PRNG for generating booleans to randomize order of elements
586 * in certain kernel data structures. The algorithm is a
587 * modified version of the KISS RNG proposed in the paper:
588 * http://stat.fsu.edu/techreports/M802.pdf
589 * The modifications have been documented in the technical paper
590 * paper from UCL:
591 * http://www0.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf
592 */
593
594/* Initialize the PRNG structures. */
595void
596random_bool_init(struct bool_gen * bg)
597{
598 /* Seed the random boolean generator */
599 for (int i = 0; i < RANDOM_BOOL_GEN_SEED_COUNT; i++) {
600 bg->seed[i] = (unsigned int)early_random();
601 }
602 bg->state = 0;
603 simple_lock_init(&bg->lock, 0);
604}
605
606/* Generate random bits and add them to an entropy pool. */
607void
608random_bool_gen_entropy(struct bool_gen * bg, unsigned int * buffer, int count)
609{
610 simple_lock(&bg->lock);
611 int i, t;
612 for (i = 0; i < count; i++) {
613 bg->seed[1] ^= (bg->seed[1] << 5);
614 bg->seed[1] ^= (bg->seed[1] >> 7);
615 bg->seed[1] ^= (bg->seed[1] << 22);
616 t = bg->seed[2] + bg->seed[3] + bg->state;
617 bg->seed[2] = bg->seed[3];
618 bg->state = t < 0;
619 bg->seed[3] = t & 2147483647;
620 bg->seed[0] += 1411392427;
621 buffer[i] = (bg->seed[0] + bg->seed[1] + bg->seed[3]);
622 }
623 simple_unlock(&bg->lock);
624}
625
626/* Get some number of bits from the entropy pool, refilling if necessary. */
627unsigned int
628random_bool_gen_bits(struct bool_gen * bg, unsigned int * buffer, unsigned int count, unsigned int numbits)
629{
630 unsigned int index = 0;
631 unsigned int rbits = 0;
632 for (unsigned int bitct = 0; bitct < numbits; bitct++) {
633 /*
634 * Find a portion of the buffer that hasn't been emptied.
635 * We might have emptied our last index in the previous iteration.
636 */
637 while (index < count && buffer[index] == 0)
638 index++;
639
640 /* If we've exhausted the pool, refill it. */
641 if (index == count) {
642 random_bool_gen_entropy(bg, buffer, count);
643 index = 0;
644 }
645
646 /* Collect-a-bit */
647 unsigned int bit = buffer[index] & 1;
648 buffer[index] = buffer[index] >> 1;
649 rbits = bit | (rbits << 1);
650 }
651 return rbits;
652}
653