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/locks.h>
30#include <kern/cpu_number.h>
31#include <libkern/section_keywords.h>
32#include <libkern/crypto/sha2.h>
33#include <machine/machine_cpu.h>
34#include <machine/machine_routines.h>
35#include <pexpert/pexpert.h>
36#include <sys/random.h>
37#include <prng/random.h>
38#include <prng/entropy.h>
39#include <corecrypto/ccdigest.h>
40#include <corecrypto/ccdrbg.h>
41#include <corecrypto/cckprng.h>
42#include <corecrypto/ccsha2.h>
43
44static struct cckprng_ctx *prng_ctx;
45
46static SECURITY_READ_ONLY_LATE(struct cckprng_funcs) prng_funcs;
47static SECURITY_READ_ONLY_LATE(int) prng_ready;
48
49#define SEED_SIZE (SHA256_DIGEST_LENGTH)
50static uint8_t bootseed[SEED_SIZE];
51
52static void
53bootseed_init_bootloader(const struct ccdigest_info * di, ccdigest_ctx_t ctx)
54{
55 uint8_t seed[64];
56 uint32_t n;
57
58 n = PE_get_random_seed(dst_random_seed: seed, request_size: sizeof(seed));
59 if (n < sizeof(seed)) {
60 /*
61 * Insufficient entropy is fatal. We must fill the
62 * entire entropy buffer during initializaton.
63 */
64 panic("Expected %lu seed bytes from bootloader, but got %u.", sizeof(seed), n);
65 }
66
67 ccdigest_update(di, ctx, len: sizeof(seed), data: seed);
68 cc_clear(len: sizeof(seed), dst: seed);
69}
70
71#if defined(__x86_64__)
72#include <i386/cpuid.h>
73
74static void
75bootseed_init_native(const struct ccdigest_info * di, ccdigest_ctx_t ctx)
76{
77 uint64_t x;
78 uint8_t ok;
79 size_t i = 0;
80 size_t n;
81
82 if (cpuid_leaf7_features() & CPUID_LEAF7_FEATURE_RDSEED) {
83 n = SEED_SIZE / sizeof(x);
84
85 while (i < n) {
86 asm volatile ("rdseed %0; setc %1" : "=r"(x), "=qm"(ok) : : "cc");
87 if (ok) {
88 ccdigest_update(di, ctx, sizeof(x), &x);
89 i += 1;
90 } else {
91 // Intel recommends to pause between unsuccessful rdseed attempts.
92 cpu_pause();
93 }
94 }
95 } else if (cpuid_features() & CPUID_FEATURE_RDRAND) {
96 // The Intel documentation guarantees a reseed every 512 rdrand calls.
97 n = (SEED_SIZE / sizeof(x)) * 512;
98
99 while (i < n) {
100 asm volatile ("rdrand %0; setc %1" : "=r"(x), "=qm"(ok) : : "cc");
101 if (ok) {
102 ccdigest_update(di, ctx, sizeof(x), &x);
103 i += 1;
104 } else {
105 // Intel does not recommend pausing between unsuccessful rdrand attempts.
106 }
107 }
108 }
109
110 cc_clear(sizeof(x), &x);
111}
112
113#else
114
115static void
116bootseed_init_native(__unused const struct ccdigest_info * di, __unused ccdigest_ctx_t ctx)
117{
118}
119
120#endif
121
122static void
123bootseed_init(void)
124{
125 const struct ccdigest_info * di = &ccsha256_ltc_di;
126
127 ccdigest_di_decl(di, ctx);
128 ccdigest_init(di, ctx);
129
130 bootseed_init_bootloader(di, ctx);
131 bootseed_init_native(di, ctx);
132
133 ccdigest_final(di, ctx, digest: bootseed);
134 ccdigest_di_clear(di, ctx);
135}
136
137#define EARLY_RANDOM_STATE_STATIC_SIZE (264)
138
139static struct {
140 uint8_t drbg_state[EARLY_RANDOM_STATE_STATIC_SIZE];
141 struct ccdrbg_info drbg_info;
142 const struct ccdrbg_nisthmac_custom drbg_custom;
143} erandom = {.drbg_custom = {
144 .di = &ccsha256_ltc_di,
145 .strictFIPS = 0,
146 }};
147
148static void read_erandom(void * buf, size_t nbytes);
149
150/*
151 * Return a uniformly distributed 64-bit random number.
152 *
153 * This interface should have minimal dependencies on kernel services,
154 * and thus be available very early in the life of the kernel.
155 *
156 * This provides cryptographically secure randomness contingent on the
157 * quality of the seed. It is seeded (lazily) with entropy provided by
158 * the Booter.
159 *
160 * The implementation is a NIST HMAC-SHA256 DRBG instance used as
161 * follows:
162 *
163 * - When first called (on macOS this is very early while page tables
164 * are being built) early_random() calls ccdrbg_factory_hmac() to
165 * set-up a ccdbrg info structure.
166 *
167 * - The boot seed (64 bytes) is hashed with SHA256. Where available,
168 * hardware RNG outputs are mixed into the seed. (See
169 * bootseed_init.) The resulting seed is 32 bytes.
170 *
171 * - The ccdrbg state structure is a statically allocated area which
172 * is then initialized by calling the ccdbrg_init method. The
173 * initial entropy is the 32-byte seed described above. The nonce
174 * is an 8-byte timestamp from ml_get_timebase(). The
175 * personalization data provided is a fixed string.
176 *
177 * - 64-bit outputs are generated via read_erandom, a wrapper around
178 * the ccdbrg_generate method. (Since "strict FIPS" is disabled,
179 * the DRBG will never request a reseed.)
180 *
181 * - After the kernel PRNG is initialized, read_erandom defers
182 * generation to it via read_random_generate. (Note that this
183 * function acquires a per-processor mutex.)
184 */
185uint64_t
186early_random(void)
187{
188 uint64_t result;
189 uint64_t nonce;
190 int rc;
191 const char ps[] = "xnu early random";
192 static int init = 0;
193
194 if (init == 0) {
195 bootseed_init();
196
197 /* Init DRBG for NIST HMAC */
198 ccdrbg_factory_nisthmac(info: &erandom.drbg_info, custom: &erandom.drbg_custom);
199 assert(erandom.drbg_info.size <= sizeof(erandom.drbg_state));
200
201 /*
202 * Init our DBRG from the boot entropy and a timestamp as nonce
203 * and the cpu number as personalization.
204 */
205 assert(sizeof(bootseed) > sizeof(nonce));
206 nonce = ml_get_timebase();
207 rc = ccdrbg_init(info: &erandom.drbg_info, drbg: (struct ccdrbg_state *)erandom.drbg_state, entropyLength: sizeof(bootseed), entropy: bootseed, nonceLength: sizeof(nonce), nonce: &nonce, psLength: sizeof(ps) - 1, ps);
208 if (rc != CCDRBG_STATUS_OK) {
209 panic("ccdrbg_init() returned %d", rc);
210 }
211
212 cc_clear(len: sizeof(nonce), dst: &nonce);
213
214 init = 1;
215 }
216
217 read_erandom(buf: &result, nbytes: sizeof(result));
218
219 return result;
220}
221
222static void
223read_random_generate(uint8_t *buffer, size_t numbytes);
224
225static void
226read_erandom(void * buf, size_t nbytes)
227{
228 uint8_t * buffer_bytes = buf;
229 size_t n;
230 int rc;
231
232 // We defer to the kernel PRNG after it has been installed and
233 // initialized. This happens during corecrypto kext
234 // initialization.
235 if (prng_ready) {
236 read_random_generate(buffer: buf, numbytes: nbytes);
237 return;
238 }
239
240 // The DBRG request size is limited, so we break the request into
241 // chunks.
242 while (nbytes > 0) {
243 n = MIN(nbytes, PAGE_SIZE);
244
245 // Since "strict FIPS" is disabled, the DRBG will never
246 // request a reseed; therefore, we panic on any error
247 rc = ccdrbg_generate(info: &erandom.drbg_info, drbg: (struct ccdrbg_state *)erandom.drbg_state, dataOutLength: n, dataOut: buffer_bytes, additionalLength: 0, NULL);
248 if (rc != CCDRBG_STATUS_OK) {
249 panic("read_erandom ccdrbg error %d", rc);
250 }
251
252 buffer_bytes += n;
253 nbytes -= n;
254 }
255}
256
257void
258read_frandom(void * buffer, u_int numBytes)
259{
260 read_erandom(buf: buffer, nbytes: numBytes);
261}
262
263void
264register_and_init_prng(struct cckprng_ctx *ctx, const struct cckprng_funcs *funcs)
265{
266 assert(cpu_number() == master_cpu);
267 assert(!prng_ready);
268
269 entropy_init();
270
271 prng_ctx = ctx;
272 prng_funcs = *funcs;
273
274 uint64_t nonce = ml_get_timebase();
275 prng_funcs.init_with_getentropy(prng_ctx, MAX_CPUS, sizeof(bootseed), bootseed, sizeof(nonce), &nonce, entropy_provide, NULL);
276 prng_funcs.initgen(prng_ctx, master_cpu);
277 prng_ready = 1;
278
279 cc_clear(len: sizeof(bootseed), dst: bootseed);
280 cc_clear(len: sizeof(erandom), dst: &erandom);
281}
282
283void
284random_cpu_init(int cpu)
285{
286 assert(cpu != master_cpu);
287
288 if (!prng_ready) {
289 panic("random_cpu_init: kernel prng has not been installed");
290 }
291
292 prng_funcs.initgen(prng_ctx, cpu);
293}
294
295/* export good random numbers to the rest of the kernel */
296void
297read_random(void * buffer, u_int numbytes)
298{
299 prng_funcs.refresh(prng_ctx);
300 read_random_generate(buffer, numbytes);
301}
302
303static void
304ensure_gsbase(void)
305{
306#if defined(__x86_64__) && (DEVELOPMENT || DEBUG)
307 /*
308 * Calling cpu_number() before gsbase is initialized is potentially
309 * catastrophic, so assert that it's not set to the magic value set
310 * in i386_init.c before proceeding with the call. We cannot use
311 * assert here because it ultimately calls panic, which executes
312 * operations that involve accessing %gs-relative data (and additionally
313 * causes a debug trap which will not work properly this early in boot.)
314 */
315 if (rdmsr64(MSR_IA32_GS_BASE) == EARLY_GSBASE_MAGIC) {
316 kprintf("[early_random] Cannot proceed: GSBASE is not initialized\n");
317 hlt();
318 /*NOTREACHED*/
319 }
320#endif
321}
322
323static void
324read_random_generate(uint8_t *buffer, size_t numbytes)
325{
326 ensure_gsbase();
327
328 while (numbytes > 0) {
329 size_t n = MIN(numbytes, CCKPRNG_GENERATE_MAX_NBYTES);
330
331 prng_funcs.generate(prng_ctx, cpu_number(), n, buffer);
332
333 buffer += n;
334 numbytes -= n;
335 }
336}
337
338int
339write_random(void * buffer, u_int numbytes)
340{
341 uint8_t seed[SHA256_DIGEST_LENGTH];
342 SHA256_CTX ctx;
343
344 /* hash the input to minimize the time we need to hold the lock */
345 SHA256_Init(ctx: &ctx);
346 SHA256_Update(ctx: &ctx, data: buffer, len: numbytes);
347 SHA256_Final(digest: seed, ctx: &ctx);
348
349 prng_funcs.reseed(prng_ctx, sizeof(seed), seed);
350 cc_clear(len: sizeof(seed), dst: seed);
351
352 return 0;
353}
354
355/*
356 * Boolean PRNG for generating booleans to randomize order of elements
357 * in certain kernel data structures. The algorithm is a
358 * modified version of the KISS RNG proposed in the paper:
359 * http://stat.fsu.edu/techreports/M802.pdf
360 * The modifications have been documented in the technical paper
361 * paper from UCL:
362 * http://www0.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf
363 */
364
365/* Initialize the PRNG structures. */
366void
367random_bool_init(struct bool_gen * bg)
368{
369 /* Seed the random boolean generator */
370 read_frandom(buffer: bg->seed, numBytes: sizeof(bg->seed));
371 bg->state = 0;
372 simple_lock_init(&bg->lock, 0);
373}
374
375/* Generate random bits and add them to an entropy pool. */
376void
377random_bool_gen_entropy(struct bool_gen * bg, unsigned int * buffer, int count)
378{
379 simple_lock(&bg->lock, LCK_GRP_NULL);
380 int i, t;
381 for (i = 0; i < count; i++) {
382 bg->seed[1] ^= (bg->seed[1] << 5);
383 bg->seed[1] ^= (bg->seed[1] >> 7);
384 bg->seed[1] ^= (bg->seed[1] << 22);
385 t = bg->seed[2] + bg->seed[3] + bg->state;
386 bg->seed[2] = bg->seed[3];
387 bg->state = t < 0;
388 bg->seed[3] = t & 2147483647;
389 bg->seed[0] += 1411392427;
390 buffer[i] = (bg->seed[0] + bg->seed[1] + bg->seed[3]);
391 }
392 simple_unlock(&bg->lock);
393}
394
395/* Get some number of bits from the entropy pool, refilling if necessary. */
396unsigned int
397random_bool_gen_bits(struct bool_gen * bg, unsigned int * buffer, unsigned int count, unsigned int numbits)
398{
399 unsigned int index = 0;
400 unsigned int rbits = 0;
401 for (unsigned int bitct = 0; bitct < numbits; bitct++) {
402 /*
403 * Find a portion of the buffer that hasn't been emptied.
404 * We might have emptied our last index in the previous iteration.
405 */
406 while (index < count && buffer[index] == 0) {
407 index++;
408 }
409
410 /* If we've exhausted the pool, refill it. */
411 if (index == count) {
412 random_bool_gen_entropy(bg, buffer, count);
413 index = 0;
414 }
415
416 /* Collect-a-bit */
417 unsigned int bit = buffer[index] & 1;
418 buffer[index] = buffer[index] >> 1;
419 rbits = bit | (rbits << 1);
420 }
421 return rbits;
422}
423