1/*
2 * Copyright (c) 2019 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 <libkern/crypto/sha2.h>
30#include <libkern/crypto/crypto.h>
31#include <os/atomic_private.h>
32#include <kern/assert.h>
33#include <kern/percpu.h>
34#include <kern/zalloc.h>
35#include <kern/lock_group.h>
36#include <kern/locks.h>
37#include <kern/misc_protos.h>
38#include <pexpert/pexpert.h>
39#include <prng/entropy.h>
40#include <machine/machine_routines.h>
41#include <libkern/section_keywords.h>
42#include <sys/cdefs.h>
43
44// The number of samples we can hold in an entropy buffer.
45#define ENTROPY_MAX_SAMPLE_COUNT (2048)
46
47// The length of a bitmap_t array with one bit per sample of an
48// entropy buffer.
49#define ENTROPY_MAX_FILTER_COUNT (BITMAP_LEN(ENTROPY_MAX_SAMPLE_COUNT))
50
51// The threshold of approximate linearity used in the entropy
52// filter. See the entropy_filter function for more discussion.
53#define ENTROPY_FILTER_THRESHOLD (8)
54
55// The state for a per-CPU entropy buffer.
56typedef struct entropy_cpu_data {
57 // A buffer to hold entropy samples.
58 entropy_sample_t samples[ENTROPY_MAX_SAMPLE_COUNT];
59
60 // A count of samples resident in the buffer. It also functions as
61 // an index to the buffer. All entries at indices less than the
62 // sample count are considered valid for consumption by the
63 // reader. The reader resets this to zero after consuming the
64 // available entropy.
65 uint32_t _Atomic sample_count;
66} entropy_cpu_data_t;
67
68// This structure holds the state for an instance of a FIPS continuous
69// health test. In practice, we do not expect these tests to fail.
70typedef struct entropy_health_test {
71 // The initial sample observed in this test instance. Tests look
72 // for some repetition of the sample, either consecutively or
73 // within a window.
74 entropy_sample_t init_observation;
75
76 // The count of times the initial observation has recurred within
77 // the span of the current test.
78 uint64_t observation_count;
79
80 // The statistics are only relevant for telemetry and parameter
81 // tuning. They do not drive any actual logic in the module.
82 entropy_health_stats_t *stats;
83} entropy_health_test_t;
84
85typedef enum health_test_result {
86 health_test_failure,
87 health_test_success
88} health_test_result_t;
89
90// Along with various counters and the buffer itself, this includes
91// the state for two FIPS continuous health tests.
92typedef struct entropy_data {
93 // State for a SHA512 computation. This is used to accumulate
94 // entropy samples from across all CPUs. It is finalized when
95 // entropy is provided to the consumer of this module.
96 SHA512_CTX sha512_ctx;
97
98 // A buffer to hold a bitmap with one bit per sample of an entropy
99 // buffer. We are able to reuse this instance across all the
100 // per-CPU entropy buffers to save space.
101 bitmap_t filter[ENTROPY_MAX_FILTER_COUNT];
102
103 // A total count of entropy samples that have passed through this
104 // structure. It is incremented as new samples are accumulated
105 // from the various per-CPU structures. The "current" count of
106 // samples is the difference between this field and the "read"
107 // sample count below (which see).
108 uint64_t total_sample_count;
109
110 // Initially zero, this flag is reset to the current sample count
111 // if and when we fail a health test. We consider the startup
112 // health tests to be complete when the difference between the
113 // total sample count and this field is at least 1024. In other
114 // words, we must accumulate 1024 good samples to demonstrate
115 // viability. We refuse to provide any entropy before that
116 // threshold is reached.
117 uint64_t startup_sample_count;
118
119 // The count of samples from the last time we provided entropy to
120 // the kernel RNG. We use this to compute how many new samples we
121 // have to contribute. This value is also reset to the current
122 // sample count in case of health test failure.
123 uint64_t read_sample_count;
124
125 // The lock group for this structure; see below.
126 lck_grp_t lock_group;
127
128 // This structure accumulates entropy samples from across all CPUs
129 // for a single point of consumption protected by a mutex.
130 lck_mtx_t mutex;
131
132 // State for the Repetition Count Test.
133 entropy_health_test_t repetition_count_test;
134
135 // State for the Adaptive Proportion Test.
136 entropy_health_test_t adaptive_proportion_test;
137} entropy_data_t;
138
139static entropy_cpu_data_t PERCPU_DATA(entropy_cpu_data);
140
141int entropy_health_startup_done;
142entropy_health_stats_t entropy_health_rct_stats;
143entropy_health_stats_t entropy_health_apt_stats;
144uint64_t entropy_filter_accepted_sample_count;
145uint64_t entropy_filter_rejected_sample_count;
146uint64_t entropy_filter_total_sample_count;
147
148static entropy_data_t entropy_data = {
149 .repetition_count_test = {
150 .init_observation = -1,
151 .stats = &entropy_health_rct_stats,
152 },
153 .adaptive_proportion_test = {
154 .init_observation = -1,
155 .stats = &entropy_health_apt_stats,
156 },
157};
158
159#if ENTROPY_ANALYSIS_SUPPORTED
160
161__security_const_late int entropy_analysis_enabled;
162__security_const_late entropy_sample_t *entropy_analysis_buffer;
163__security_const_late uint32_t entropy_analysis_buffer_size;
164__security_const_late uint32_t entropy_analysis_filter_size;
165__security_const_late uint32_t entropy_analysis_max_sample_count;
166uint32_t entropy_analysis_sample_count;
167
168__startup_func
169static void
170entropy_analysis_init(uint32_t sample_count)
171{
172 entropy_analysis_enabled = 1;
173 entropy_analysis_max_sample_count = sample_count;
174 entropy_analysis_buffer_size = sample_count * sizeof(entropy_sample_t);
175 entropy_analysis_buffer = zalloc_permanent(entropy_analysis_buffer_size, ZALIGN(entropy_sample_t));
176 entropy_analysis_filter_size = (uint32_t) BITMAP_SIZE(entropy_analysis_max_sample_count);
177}
178
179static void
180entropy_analysis_store(entropy_sample_t sample)
181{
182 uint32_t sample_count;
183 uint32_t next_sample_count;
184
185 os_atomic_rmw_loop(&entropy_analysis_sample_count, sample_count, next_sample_count, relaxed, {
186 if (sample_count >= entropy_analysis_max_sample_count) {
187 os_atomic_rmw_loop_give_up(return );
188 }
189
190 next_sample_count = sample_count + 1;
191 });
192
193 entropy_analysis_buffer[sample_count] = sample;
194}
195
196#endif // ENTROPY_ANALYSIS_SUPPORTED
197
198__startup_func
199void
200entropy_init(void)
201{
202 SHA512_Init(ctx: &entropy_data.sha512_ctx);
203
204 lck_grp_init(grp: &entropy_data.lock_group, grp_name: "entropy-data", LCK_GRP_ATTR_NULL);
205 lck_mtx_init(lck: &entropy_data.mutex, grp: &entropy_data.lock_group, LCK_ATTR_NULL);
206
207#if ENTROPY_ANALYSIS_SUPPORTED
208 // The below path is used only for testing. This boot arg is used
209 // to collect raw entropy samples for offline analysis.
210 uint32_t sample_count = 0;
211 if (__improbable(PE_parse_boot_argn(ENTROPY_ANALYSIS_BOOTARG, &sample_count, sizeof(sample_count)))) {
212 entropy_analysis_init(sample_count);
213 }
214#endif // ENTROPY_ANALYSIS_SUPPORTED
215}
216
217void
218entropy_collect(void)
219{
220 // This function is called from within the interrupt handler, so
221 // we do not need to disable interrupts.
222
223 entropy_cpu_data_t *e = PERCPU_GET(entropy_cpu_data);
224
225 uint32_t sample_count = os_atomic_load(&e->sample_count, relaxed);
226
227 assert(sample_count <= ENTROPY_MAX_SAMPLE_COUNT);
228
229 // If the buffer is full, we return early without collecting
230 // entropy.
231 if (sample_count == ENTROPY_MAX_SAMPLE_COUNT) {
232 return;
233 }
234
235 entropy_sample_t sample = (entropy_sample_t)ml_get_timebase_entropy();
236 e->samples[sample_count] = sample;
237
238 // If the consumer has reset the sample count on us, the only
239 // consequence is a dropped sample. We effectively abort the
240 // entropy collection in this case.
241 (void)os_atomic_cmpxchg(&e->sample_count, sample_count, sample_count + 1, release);
242
243#if ENTROPY_ANALYSIS_SUPPORTED
244 // This code path is only used for testing. Its use is governed by
245 // a boot arg; see its initialization above.
246 if (__improbable(entropy_analysis_buffer)) {
247 entropy_analysis_store(sample);
248 }
249#endif // ENTROPY_ANALYSIS_SUPPORTED
250}
251
252// This filter looks at the 1st differential (differences of subsequent
253// timestamp values) and the 2nd differential (differences of subsequent
254// 1st differentials). This filter will detect sequences of timestamps
255// that are linear (that is, the 2nd differential is close to zero).
256// Timestamps with a 2nd differential above the threshold ENTROPY_FILTER_THRESHOLD
257// will be marked in the filter bitmap. 2nd differentials below the threshold
258// will not be counted nor included in the filter bitmap.
259//
260// For example imagine the following sequence of 8-bit timestamps:
261//
262// [25, 100, 175, 250, 69, 144, 219, 38, 113, 188]
263//
264// The 1st differential between timestamps is as follows:
265//
266// [75, 75, 75, 75, 75, 75, 75, 75, 75]
267//
268// The 2nd differential is as follows:
269//
270// [0, 0, 0, 0, 0, 0, 0, 0]
271//
272// The first two samples of any set of samples are always included as
273// there is no 2nd differential to compare against. Thus all but
274// the first two samples in this example will be removed.
275uint32_t
276entropy_filter(uint32_t sample_count, entropy_sample_t *samples, __assert_only uint32_t filter_count, bitmap_t *filter)
277{
278 assert(filter_count >= BITMAP_LEN(sample_count));
279
280 bitmap_zero(map: filter, nbits: sample_count);
281
282 // We always keep the first one (or two) sample(s) if we have at least one (or more) samples
283 if (sample_count == 0) {
284 return 0;
285 } else if (sample_count == 1) {
286 bitmap_set(map: filter, n: 0);
287 return 1;
288 } else if (sample_count == 2) {
289 bitmap_set(map: filter, n: 0);
290 bitmap_set(map: filter, n: 1);
291 return 2;
292 } else {
293 bitmap_set(map: filter, n: 0);
294 bitmap_set(map: filter, n: 1);
295 }
296
297 uint32_t filtered_sample_count = 2;
298
299 // We don't care about underflows when computing any differential
300 entropy_sample_t prev_1st_differential = samples[1] - samples[0];
301
302 for (uint i = 2; i < sample_count; i++) {
303 entropy_sample_t curr_1st_differential = samples[i] - samples[i - 1];
304
305 entropy_sample_t curr_2nd_differential = curr_1st_differential - prev_1st_differential;
306
307 if (curr_2nd_differential > ENTROPY_FILTER_THRESHOLD && curr_2nd_differential < ((entropy_sample_t) -ENTROPY_FILTER_THRESHOLD)) {
308 bitmap_set(map: filter, n: i);
309 filtered_sample_count += 1;
310 }
311
312 prev_1st_differential = curr_1st_differential;
313 }
314
315 return filtered_sample_count;
316}
317
318// For information on the following tests, see NIST SP 800-90B 4
319// Health Tests. These tests are intended to detect catastrophic
320// degradations in entropy. As noted in that document:
321//
322// > Health tests are expected to raise an alarm in three cases:
323// > 1. When there is a significant decrease in the entropy of the
324// > outputs,
325// > 2. When noise source failures occur, or
326// > 3. When hardware fails, and implementations do not work
327// > correctly.
328//
329// Each entropy accumulator declines to release entropy until the
330// startup tests required by NIST are complete. In the event that a
331// health test does fail, all entropy accumulators are reset and
332// decline to release further entropy until their startup tests can be
333// repeated.
334
335static health_test_result_t
336add_observation(entropy_health_test_t *t, uint64_t bound)
337{
338 t->observation_count += 1;
339 t->stats->max_observation_count = MAX(t->stats->max_observation_count, (uint32_t)t->observation_count);
340 if (__improbable(t->observation_count >= bound)) {
341 t->stats->failure_count += 1;
342 return health_test_failure;
343 }
344
345 return health_test_success;
346}
347
348static void
349reset_test(entropy_health_test_t *t, entropy_sample_t observation)
350{
351 t->stats->reset_count += 1;
352 t->init_observation = observation;
353 t->observation_count = 1;
354 t->stats->max_observation_count = MAX(t->stats->max_observation_count, (uint32_t)t->observation_count);
355}
356
357// 4.4.1 Repetition Count Test
358//
359// Like the name implies, this test counts consecutive occurrences of
360// the same value.
361//
362// We compute the bound C as:
363//
364// A = 2^-40
365// H = 1
366// C = 1 + ceil(-log(A, 2) / H) = 41
367//
368// With A the acceptable chance of false positive and H a conservative
369// estimate for the min-entropy (in bits) of each sample.
370//
371// For more information, see tools/entropy_health_test_bounds.py.
372
373#define REPETITION_COUNT_BOUND (41)
374
375static health_test_result_t
376repetition_count_test(entropy_sample_t observation)
377{
378 entropy_health_test_t *t = &entropy_data.repetition_count_test;
379
380 if (t->init_observation == observation) {
381 return add_observation(t, REPETITION_COUNT_BOUND);
382 } else {
383 reset_test(t, observation);
384 }
385
386 return health_test_success;
387}
388
389// 4.4.2 Adaptive Proportion Test
390//
391// This test counts occurrences of a value within a window of samples.
392//
393// We use a non-binary alphabet, giving us a window size of 512. (In
394// particular, we consider the least-significant byte of each time
395// sample.)
396//
397// Assuming one bit of entropy, we can compute the binomial cumulative
398// distribution function over 512 trials and choose a bound such that
399// the false positive rate is less than our target.
400//
401// For false positive rate and min-entropy estimate as above:
402//
403// A = 2^-40
404// H = 1
405//
406// We have our bound:
407//
408// C = 336
409//
410// For more information, see tools/entropy_health_test_bounds.py.
411
412#define ADAPTIVE_PROPORTION_BOUND (336)
413#define ADAPTIVE_PROPORTION_WINDOW (512)
414
415// This mask definition requires the window be a power of two.
416static_assert(__builtin_popcount(ADAPTIVE_PROPORTION_WINDOW) == 1);
417#define ADAPTIVE_PROPORTION_INDEX_MASK (ADAPTIVE_PROPORTION_WINDOW - 1)
418
419static health_test_result_t
420adaptive_proportion_test(entropy_sample_t observation, uint32_t offset)
421{
422 entropy_health_test_t *t = &entropy_data.adaptive_proportion_test;
423
424 // We work in windows of size ADAPTIVE_PROPORTION_WINDOW, so we
425 // can compute our index by taking the entropy buffer's overall
426 // sample count plus the offset of this observation modulo the
427 // window size.
428 uint32_t index = (entropy_data.total_sample_count + offset) & ADAPTIVE_PROPORTION_INDEX_MASK;
429
430 if (index == 0) {
431 reset_test(t, observation);
432 } else if (t->init_observation == observation) {
433 return add_observation(t, ADAPTIVE_PROPORTION_BOUND);
434 }
435
436 return health_test_success;
437}
438
439static health_test_result_t
440entropy_health_test(uint32_t sample_count, entropy_sample_t *samples, __assert_only uint32_t filter_count, bitmap_t *filter)
441{
442 health_test_result_t result = health_test_success;
443
444 assert(filter_count >= BITMAP_LEN(sample_count));
445
446 for (uint32_t i = 0; i < sample_count; i += 1) {
447 // We use the filter to determine if a given sample "counts"
448 // or not. We skip the health tests on those samples that
449 // failed the filter, since they are not expected to provide
450 // any entropy.
451 if (!bitmap_test(map: filter, n: i)) {
452 continue;
453 }
454
455 // We only consider the low bits of each sample, since that is
456 // where we expect the entropy to be concentrated.
457 entropy_sample_t observation = samples[i] & 0xff;
458
459 if (__improbable(repetition_count_test(observation) == health_test_failure)) {
460 result = health_test_failure;
461 }
462
463 if (__improbable(adaptive_proportion_test(observation, i) == health_test_failure)) {
464 result = health_test_failure;
465 }
466 }
467
468 return result;
469}
470
471int32_t
472entropy_provide(size_t *entropy_size, void *entropy, __unused void *arg)
473{
474#if (DEVELOPMENT || DEBUG)
475 if (*entropy_size < SHA512_DIGEST_LENGTH) {
476 panic("[entropy_provide] recipient entropy buffer is too small");
477 }
478#endif
479
480 int32_t sample_count = 0;
481 *entropy_size = 0;
482
483 // There is only one consumer (the kernel PRNG), but they could
484 // try to consume entropy from different threads. We simply fail
485 // if a consumption is already in progress.
486 if (!lck_mtx_try_lock(lck: &entropy_data.mutex)) {
487 return sample_count;
488 }
489
490 health_test_result_t health_test_result = health_test_success;
491
492 // We accumulate entropy from all CPUs.
493 percpu_foreach(e, entropy_cpu_data) {
494 // On each CPU, the sample count functions as an index into
495 // the entropy buffer. All samples before that index are valid
496 // for consumption.
497 uint32_t cpu_sample_count = os_atomic_load(&e->sample_count, acquire);
498
499 assert(cpu_sample_count <= ENTROPY_MAX_SAMPLE_COUNT);
500
501 // We'll calculate how many samples that we would filter out
502 // and only add that many to the total_sample_count. The bitmap
503 // is not used during this operation.
504 uint32_t filtered_sample_count = entropy_filter(sample_count: cpu_sample_count, samples: e->samples, ENTROPY_MAX_FILTER_COUNT, filter: entropy_data.filter);
505 assert(filtered_sample_count <= cpu_sample_count);
506
507 entropy_filter_total_sample_count += cpu_sample_count;
508 entropy_filter_accepted_sample_count += filtered_sample_count;
509 entropy_filter_rejected_sample_count += (cpu_sample_count - filtered_sample_count);
510
511 // The health test depends in part on the current state of
512 // the entropy data, so we test the new sample before
513 // accumulating it.
514 health_test_result_t cpu_health_test_result = entropy_health_test(sample_count: cpu_sample_count, samples: e->samples, ENTROPY_MAX_FILTER_COUNT, filter: entropy_data.filter);
515 if (__improbable(cpu_health_test_result == health_test_failure)) {
516 health_test_result = health_test_failure;
517 }
518
519 // We accumulate the samples regardless of whether the test
520 // failed or a particular sample was filtered. It cannot hurt.
521 entropy_data.total_sample_count += filtered_sample_count;
522 SHA512_Update(ctx: &entropy_data.sha512_ctx, data: e->samples, len: cpu_sample_count * sizeof(e->samples[0]));
523
524 // "Drain" the per-CPU buffer by resetting its sample count.
525 os_atomic_store(&e->sample_count, 0, relaxed);
526 }
527
528 // We expect this never to happen.
529 //
530 // But if it does happen, we need to return negative to signal the
531 // consumer (i.e. the kernel PRNG) that there has been a failure.
532 if (__improbable(health_test_result == health_test_failure)) {
533 entropy_health_startup_done = 0;
534 entropy_data.startup_sample_count = entropy_data.total_sample_count;
535 entropy_data.read_sample_count = entropy_data.total_sample_count;
536 sample_count = -1;
537 goto out;
538 }
539
540 // FIPS requires we pass our startup health tests before providing
541 // any entropy. This condition is only true during startup and in
542 // case of reset due to test failure.
543 if (__improbable((entropy_data.total_sample_count - entropy_data.startup_sample_count) < 1024)) {
544 goto out;
545 }
546
547 entropy_health_startup_done = 1;
548
549 // The count of new samples from the consumer's perspective.
550 int32_t n = (int32_t)(entropy_data.total_sample_count - entropy_data.read_sample_count);
551
552 // Assuming one bit of entropy per sample, we buffer at least 512
553 // samples before delivering a high-entropy payload. In theory,
554 // each payload will be a 512-bit seed with full entropy.
555 //
556 // We buffer an additional 64 bits of entropy to satisfy
557 // over-sampling requirements in FIPS 140-3 IG.
558 if (n < (512 + 64)) {
559 goto out;
560 }
561
562 // Extract the entropy seed from the digest context and adjust
563 // counters accordingly.
564 SHA512_Final(digest: entropy, ctx: &entropy_data.sha512_ctx);
565 entropy_data.read_sample_count = entropy_data.total_sample_count;
566 sample_count = n;
567 *entropy_size = SHA512_DIGEST_LENGTH;
568
569 // Reinitialize the digest context for future entropy
570 // conditioning.
571 SHA512_Init(ctx: &entropy_data.sha512_ctx);
572
573 // To harden the entropy conditioner against an attacker with
574 // partial or temporary control of interrupts, we roll the
575 // extracted seed back into the new digest context. Assuming
576 // we are able to reach a threshold of entropy, we can prevent
577 // the attacker from predicting future output seeds.
578 //
579 // Along with the seed, we mix in a fixed label to personalize
580 // this context.
581 const char label[SHA512_BLOCK_LENGTH - SHA512_DIGEST_LENGTH] = "xnu entropy extract seed";
582
583 // We need the combined size of our inputs to equal the
584 // internal SHA512 block size. This will force an additional
585 // compression to provide backtracking resistance.
586 assert(sizeof(label) + *entropy_size == SHA512_BLOCK_LENGTH);
587 SHA512_Update(ctx: &entropy_data.sha512_ctx, data: label, len: sizeof(label));
588 SHA512_Update(ctx: &entropy_data.sha512_ctx, data: entropy, len: *entropy_size);
589
590out:
591 lck_mtx_unlock(lck: &entropy_data.mutex);
592
593 return sample_count;
594}
595