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