1 /* Copyright (c) (2018,2019) Apple Inc. All rights reserved. 2 * 3 * corecrypto is licensed under Apple Inc.’s Internal Use License Agreement (which 4 * is contained in the License.txt file distributed with corecrypto) and only to 5 * people who accept that license. IMPORTANT: Any license rights granted to you by 6 * Apple Inc. (if any) are limited to internal use within your organization only on 7 * devices and computers you own or control, for the sole purpose of verifying the 8 * security characteristics and correct functioning of the Apple Software. You may 9 * not, directly or indirectly, redistribute the Apple Software or any portions thereof. 10 */ 11 12 #ifndef _CORECRYPTO_CCKPRNG_H_ 13 #define _CORECRYPTO_CCKPRNG_H_ 14 15 #include <stdbool.h> 16 17 #include <corecrypto/cc.h> 18 19 // This is a Fortuna-inspired PRNG. While it differs from Fortuna in 20 // many minor details, the biggest difference is its support for 21 // multiple independent output generators. This is to make it suitable 22 // for use in concurrent environments. 23 // 24 // This PRNG targets a 256-bit security level. 25 // 26 // First, the user should call cckprng_init. The user must specify the 27 // maximum number of output generators that might be 28 // needed. (Typically, users should align this argument with the 29 // number of available CPUs.) 30 // 31 // The user must also provide a read-only handle to an entropy 32 // source. This is a fixed-size buffer that will receive entropy 33 // updates out of band from the PRNG (e.g. in an interrupt 34 // handler). The PRNG will consume entropy from this buffer according 35 // to an internal schedule driven by calls to cckprng_refresh (see 36 // below). 37 // 38 // The user should call cckprng_initgen for as many output generators 39 // as are needed. The numeric argument is an identifier to be reused 40 // during calls to cckprng_generate (see below) and must be less than 41 // the maximum number of generators specified to cckprng_init. 42 // 43 // After initialization, the user is free to call cckprng_generate to 44 // generate random bytes. The user must specify the generator in this 45 // call using a numeric identifier passed in the call to 46 // cckprng_initgen. 47 // 48 // Output generation is limited to 256 bytes per request. Users should 49 // make multiple requests if more output is needed. 50 // 51 // The user is expected to call cckprng_refresh regularly. This 52 // function consumes entropy and mixes it into the output generators 53 // according to an internal schedule. 54 // 55 // This implementation is thread-safe. Internally, a set of mutexes 56 // guard access to internal state. Most functions rely on a single 57 // mutex to protect shared state. The main exception is the 58 // cckprng_generate function, which uses a per-generator mutex to 59 // allow concurrent output generation on different threads. 60 // 61 // Another important exception is cckprng_refresh. While this function 62 // relies on the shared mutex, it returns immediately if it cannot 63 // acquire it. 64 // 65 // The PRNG also supports user-initiated reseeds. This is to support a 66 // user-writable random device. 67 // 68 // This PRNG supports reseeds concurrent with output generation, 69 // i.e. it is safe to call cckprng_reseed or cckprng_refresh while 70 // another thread is calling cckprng_generate. 71 72 #define CCKPRNG_NPOOLS 32 73 #define CCKPRNG_SEED_NBYTES 32 74 #define CCKPRNG_POOL_NBYTES 32 75 #define CCKPRNG_KEY_NBYTES 32 76 77 struct cckprng_gen_diag { 78 // The number of times this generator has been rekeyed from the master seed 79 uint64_t nrekeys; 80 81 // The number of requests this generator has fulfilled 82 uint64_t out_nreqs; 83 84 // The total number of bytes this generator has generated over all requests 85 uint64_t out_nbytes; 86 87 // The maximum number of bytes this generator has generated in any one request 88 uint64_t out_nbytes_req_max; 89 90 // The total number of bytes this generator has generated since the last rekey 91 uint64_t out_nbytes_key; 92 93 // The maximum total number of bytes this generator has generated between two rekeys 94 uint64_t out_nbytes_key_max; 95 }; 96 97 struct cckprng_pool_diag { 98 // The number of samples currently resident in the pool 99 uint64_t nsamples; 100 101 // The number of times this pool has been drained in a reseed 102 uint64_t ndrains; 103 104 // The maximum number of samples this pool has held at any one time 105 uint64_t nsamples_max; 106 }; 107 108 struct cckprng_diag { 109 // The number of reseeds via user input (e.g. by writing to /dev/random) 110 uint64_t userreseed_nreseeds; 111 112 // The number of reseeds via the scheduler 113 uint64_t schedreseed_nreseeds; 114 115 // The maximum number of samples included in any one scheduler reseed 116 uint64_t schedreseed_nsamples_max; 117 118 // The maximum number of samples included in any one entropy input 119 uint64_t addentropy_nsamples_max; 120 121 // Diagnostics corresponding to individual output generators 122 unsigned ngens; 123 CC_ALIGNED(8) struct cckprng_gen_diag *gens; 124 125 // Diagnostics corresponding to internal entropy pools 126 struct cckprng_pool_diag pools[CCKPRNG_NPOOLS]; 127 }; 128 129 #if CC_KERNEL 130 131 #include <kern/locks.h> 132 133 typedef lck_grp_t *cckprng_lock_group; 134 typedef lck_mtx_t *cckprng_lock_mutex; 135 136 struct cckprng_lock_ctx { 137 cckprng_lock_group group; 138 cckprng_lock_mutex mutex; 139 }; 140 141 #elif CC_ANDROID || CC_LINUX 142 143 #include <pthread.h> 144 145 typedef pthread_mutex_t cckprng_lock_mutex; 146 147 struct cckprng_lock_ctx { 148 cckprng_lock_mutex mutex; 149 }; 150 151 #else 152 153 #include <os/lock.h> 154 155 typedef os_unfair_lock cckprng_lock_mutex; 156 157 struct cckprng_lock_ctx { 158 cckprng_lock_mutex mutex; 159 }; 160 161 #endif 162 163 struct cckprng_key_ctx { 164 uint8_t data[CCKPRNG_KEY_NBYTES]; 165 }; 166 167 struct cckprng_gen_ctx { 168 // We maintain two keys (one live and one idle) to allow 169 // concurrent generation and reseeding 170 struct cckprng_key_ctx keys[2]; 171 _Atomic unsigned swap; 172 unsigned key_live_idx; 173 unsigned key_idle_idx; 174 175 // A counter used in CTR mode 176 uint8_t ctr[16]; 177 178 // Whether the generator has been initialized 179 bool init; 180 181 // A mutex governing this generator's state (but note the idle key 182 // context is under control of the PRNG's shared mutex) 183 struct { 184 cckprng_lock_mutex mutex; 185 } lock; 186 }; 187 188 struct cckprng_pool_ctx { 189 uint8_t data[CCKPRNG_POOL_NBYTES]; 190 }; 191 192 // This is a handle to an "entropy buffer" to be managed externally 193 // (i.e. in xnu). This is a non-cryptographic 194 // accumulator. Practically, the buffer is filled with timestamps 195 // collected during interrupts. The existing state of the buffer is 196 // rotated and new timestamps are added in. A counter of raw timing 197 // samples is also managed externally. The buffer and the counter are 198 // both subject to data races, which we tolerate. 199 200 struct cckprng_entropybuf { 201 202 // A read-only handle to an "entropy buffer" (a non-cryptographic accumulator) to be managed externally 203 const void *buf; 204 205 // The size of the entropy buffer 206 size_t nbytes; 207 208 // A read-only handle to a count of raw samples in the buffer 209 const uint32_t *nsamples; 210 211 // The count of raw samples in the buffer at time of last read 212 uint32_t nsamples_last; 213 }; 214 215 struct cckprng_sched_ctx { 216 // A counter governing the set of entropy pools to drain 217 uint64_t reseed_sched; 218 219 // An index used to add entropy to pools in a round-robin style 220 unsigned pool_idx; 221 }; 222 223 // A function pointer to fill an entropy buffer. It should return some 224 // estimate of entropy (e.g. the number of timing samples resident in 225 // the buffer). The implementation may return zero if no entropy is 226 // available. The implementation should return negative in case of an 227 // error (e.g. a failure in continuous health tests). 228 // 229 // The caller should set entropy_nbytes to the maximum size of the 230 // input buffer, and the implementation should set it to the number of 231 // bytes it has initialized. The third argument is arbitrary state the 232 // implementation provides and receives back on each call. 233 typedef int32_t (*cckprng_getentropy)(size_t *entropy_nbytes, 234 void *entropy, 235 void *arg); 236 237 struct cckprng_ctx { 238 // The master secret of the PRNG 239 struct cckprng_key_ctx key; 240 241 // A counter used in CTR mode (with the master secret) 242 uint8_t ctr[16]; 243 244 // State used to schedule entropy consumption and reseeds 245 struct cckprng_sched_ctx sched; 246 247 // A mutex governing access to shared state 248 struct cckprng_lock_ctx lock; 249 250 // The maximum number of generators that may be allocated 251 unsigned max_ngens; 252 253 // The actual number of generators that have been initialized 254 unsigned ngens; 255 256 // An array of output generators (allocated dynamically) of length max_ngens 257 struct cckprng_gen_ctx *gens; 258 259 // A set of entropy pools 260 struct cckprng_pool_ctx pools[CCKPRNG_NPOOLS]; 261 262 // A handle to an entropy source managed externally 263 struct cckprng_entropybuf entropybuf; 264 265 // Diagnostics for the PRNG 266 struct cckprng_diag diag; 267 268 // A function pointer to get entropy 269 cckprng_getentropy getentropy; 270 271 // An arbitrary piece of state to be provided to the entropy function 272 void *getentropy_arg; 273 }; 274 275 // This collection of function pointers is just a convenience for 276 // registering the PRNG with xnu 277 struct cckprng_funcs { 278 void (*CC_SPTR(cckprng_funcs, init))(struct cckprng_ctx *ctx, 279 unsigned max_ngens, 280 size_t entropybuf_nbytes, 281 const void *entropybuf, 282 const uint32_t *entropybuf_nsamples, 283 size_t seed_nbytes, 284 const void *seed, 285 size_t nonce_nbytes, 286 const void *nonce); 287 void (*CC_SPTR(cckprng_funcs, initgen))(struct cckprng_ctx *ctx, unsigned gen_idx); 288 void (*CC_SPTR(cckprng_funcs, reseed))(struct cckprng_ctx *ctx, size_t nbytes, const void *seed); 289 void (*CC_SPTR(cckprng_funcs, refresh))(struct cckprng_ctx *ctx); 290 void (*CC_SPTR(cckprng_funcs, generate))(struct cckprng_ctx *ctx, unsigned gen_idx, size_t nbytes, void *out); 291 void (*CC_SPTR(cckprng_funcs, init_with_getentropy))(struct cckprng_ctx *ctx, 292 unsigned max_ngens, 293 size_t seed_nbytes, 294 const void *seed, 295 size_t nonce_nbytes, 296 const void *nonce, 297 cckprng_getentropy getentropy, 298 void *getentropy_arg); 299 }; 300 301 /* 302 @function cckprng_init 303 @abstract Initialize a kernel PRNG context. 304 305 @param ctx Context for this instance 306 @param max_ngens Maximum count of generators that may be allocated 307 @param entropybuf_nbytes Length of the entropy buffer in bytes 308 @param entropybuf Read-only pointer to a long-lived entropy buffer 309 @param entropybuf_nsamples Read-only pointer to a counter of samples in the entropy buffer 310 @param seed_nbytes Length of the seed in bytes 311 @param seed Pointer to a high-entropy seed 312 @param nonce_nbytes Length of the nonce in bytes 313 314 @discussion @p max_ngens should be set based on an upper bound of CPUs available on the device. The entropy buffer should be managed outside the PRNG and updated continuously (e.g. by an interrupt handler). The count of samples in the entropy buffer needn't be better than a rough estimate. 315 */ 316 void cckprng_init(struct cckprng_ctx *ctx, 317 unsigned max_ngens, 318 size_t entropybuf_nbytes, 319 const void *entropybuf, 320 const uint32_t *entropybuf_nsamples, 321 size_t seed_nbytes, 322 const void *seed, 323 size_t nonce_nbytes, 324 const void *nonce); 325 326 /* 327 @function cckprng_init_with_getentropy 328 @abstract Initialize a kernel PRNG context. 329 330 @param ctx Context for this instance 331 @param max_ngens Maximum count of generators that may be allocated 332 @param seed_nbytes Length of the seed in bytes 333 @param seed Pointer to a high-entropy seed 334 @param nonce_nbytes Length of the nonce in bytes 335 @param seed Pointer to a single-use nonce 336 @param getentropy A function pointer to fill an entropy buffer 337 @param getentropy_arg State provided to the entropy function 338 339 @discussion @p max_ngens should be set based on an upper bound of CPUs available on the device. See the @p cckprng_getentropy type definition for discussion on its semantics. 340 */ 341 void cckprng_init_with_getentropy(struct cckprng_ctx *ctx, 342 unsigned max_ngens, 343 size_t seed_nbytes, 344 const void *seed, 345 size_t nonce_nbytes, 346 const void *nonce, 347 cckprng_getentropy getentropy, 348 void *getentropy_arg); 349 350 /* 351 @function cckprng_initgen 352 @abstract Initialize an output generator. 353 354 @param ctx Context for this instance 355 @param gen_idx Index of the generator 356 357 @discussion @p gen_idx must be less than @p max_ngens provided to @cckprng_init and must be unique within the lifetime of a PRNG context. This function will abort if these contracts are violated. 358 */ 359 void cckprng_initgen(struct cckprng_ctx *ctx, unsigned gen_idx); 360 361 /* 362 @function cckprng_reseed 363 @abstract Reseed a kernel PRNG context with a user-supplied seed. 364 365 @param ctx Context for this instance 366 @param nbytes Length of the seed in bytes 367 @param seed Pointer to a high-entropy seed 368 369 @discussion It is safe to expose this function to attacker-controlled requests (e.g. writes to /dev/random). 370 */ 371 void cckprng_reseed(struct cckprng_ctx *ctx, size_t nbytes, const void *seed); 372 373 /* 374 @function cckprng_refresh 375 @abstract Consume entropy and reseed according to an internal schedule. 376 377 @param ctx Context for this instance 378 379 @discussion This function should be called on a regular basis. (For example, it is reasonable to call this inline before a call to @p cckprng_generate.) This function will not necessarily consume entropy or reseed the internal state on any given invocation. To force an immediate reseed, call @p cckprng_reseed. 380 */ 381 void cckprng_refresh(struct cckprng_ctx *ctx); 382 383 #define CCKPRNG_GENERATE_MAX_NBYTES 256 384 385 /* 386 @function cckprng_generate 387 @abstract Generate random values for use in applications. 388 389 @param ctx Context for this instance 390 @param gen_idx Index of the output generator 391 @param nbytes Length of the desired output in bytes 392 @param out Pointer to the output buffer 393 394 @discussion @p gen_idx must be a previous argument to @p cckprng_initgen. @p nbytes must be less than or equal to @p CCKPRNG_GENERATE_MAX_NBYTES. (Callers may invoke this function in a loop to generate larger outputs.) This function will abort if these contracts are violated. 395 */ 396 void cckprng_generate(struct cckprng_ctx *ctx, unsigned gen_idx, size_t nbytes, void *out); 397 398 #endif /* _CORECRYPTO_CCKPRNG_H_ */ 399