random.c 47.8 KB
Newer Older
1
// SPDX-License-Identifier: (GPL-2.0 OR BSD-3-Clause)
L
Linus Torvalds 已提交
2
/*
3
 * Copyright (C) 2017-2022 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
4
 * Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005
5 6 7 8 9 10 11 12 13 14 15 16 17
 * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All rights reserved.
 *
 * This driver produces cryptographically secure pseudorandom data. It is divided
 * into roughly six sections, each with a section header:
 *
 *   - Initialization and readiness waiting.
 *   - Fast key erasure RNG, the "crng".
 *   - Entropy accumulation and extraction routines.
 *   - Entropy collection routines.
 *   - Userspace reader/writer interfaces.
 *   - Sysctl interface.
 *
 * The high level overview is that there is one input pool, into which
18 19 20 21 22 23
 * various pieces of data are hashed. Prior to initialization, some of that
 * data is then "credited" as having a certain number of bits of entropy.
 * When enough bits of entropy are available, the hash is finalized and
 * handed as a key to a stream cipher that expands it indefinitely for
 * various consumers. This key is periodically refreshed as the various
 * entropy collectors, described below, add data to the input pool.
L
Linus Torvalds 已提交
24 25
 */

Y
Yangtao Li 已提交
26 27
#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

L
Linus Torvalds 已提交
28 29 30 31 32 33 34 35 36 37 38
#include <linux/utsname.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/major.h>
#include <linux/string.h>
#include <linux/fcntl.h>
#include <linux/slab.h>
#include <linux/random.h>
#include <linux/poll.h>
#include <linux/init.h>
#include <linux/fs.h>
C
Christoph Hellwig 已提交
39
#include <linux/blkdev.h>
L
Linus Torvalds 已提交
40
#include <linux/interrupt.h>
41
#include <linux/mm.h>
42
#include <linux/nodemask.h>
L
Linus Torvalds 已提交
43
#include <linux/spinlock.h>
44
#include <linux/kthread.h>
L
Linus Torvalds 已提交
45
#include <linux/percpu.h>
46
#include <linux/ptrace.h>
47
#include <linux/workqueue.h>
48
#include <linux/irq.h>
49
#include <linux/ratelimit.h>
50 51
#include <linux/syscalls.h>
#include <linux/completion.h>
52
#include <linux/uuid.h>
53
#include <linux/uaccess.h>
54
#include <linux/suspend.h>
55
#include <linux/siphash.h>
56
#include <crypto/chacha.h>
57
#include <crypto/blake2s.h>
L
Linus Torvalds 已提交
58 59
#include <asm/processor.h>
#include <asm/irq.h>
60
#include <asm/irq_regs.h>
L
Linus Torvalds 已提交
61 62
#include <asm/io.h>

63 64 65 66 67 68 69 70 71
/*********************************************************************
 *
 * Initialization and readiness waiting.
 *
 * Much of the RNG infrastructure is devoted to various dependencies
 * being able to wait until the RNG has collected enough entropy and
 * is ready for safe consumption.
 *
 *********************************************************************/
72

73
/*
74
 * crng_init is protected by base_crng->lock, and only increases
75
 * its value (from empty->early->ready).
76
 */
77 78 79 80
static enum {
	CRNG_EMPTY = 0, /* Little to no entropy collected */
	CRNG_EARLY = 1, /* At least POOL_EARLY_BITS collected */
	CRNG_READY = 2  /* Fully initialized with POOL_READY_BITS collected */
81 82 83
} crng_init __read_mostly = CRNG_EMPTY;
static DEFINE_STATIC_KEY_FALSE(crng_is_ready);
#define crng_ready() (static_branch_likely(&crng_is_ready) || crng_init >= CRNG_READY)
84
/* Various types of waiters for crng_init->CRNG_READY transition. */
85 86
static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait);
static struct fasync_struct *fasync;
87

88
/* Control how we warn userspace. */
89
static struct ratelimit_state urandom_warning =
90
	RATELIMIT_STATE_INIT_FLAGS("urandom_warning", HZ, 3, RATELIMIT_MSG_ON_RELEASE);
91 92
static int ratelimit_disable __read_mostly =
	IS_ENABLED(CONFIG_WARN_ALL_UNSEEDED_RANDOM);
93 94 95
module_param_named(ratelimit_disable, ratelimit_disable, int, 0644);
MODULE_PARM_DESC(ratelimit_disable, "Disable random ratelimit suppression");

96 97
/*
 * Returns whether or not the input pool has been seeded and thus guaranteed
98 99 100
 * to supply cryptographically secure random numbers. This applies to: the
 * /dev/urandom device, the get_random_bytes function, and the get_random_{u32,
 * ,u64,int,long} family of functions.
101 102 103 104 105 106 107 108 109 110
 *
 * Returns: true if the input pool has been seeded.
 *          false if the input pool has not been seeded.
 */
bool rng_is_initialized(void)
{
	return crng_ready();
}
EXPORT_SYMBOL(rng_is_initialized);

111
static void __cold crng_set_ready(struct work_struct *work)
112 113 114 115
{
	static_branch_enable(&crng_is_ready);
}

116 117 118 119 120
/* Used by wait_for_random_bytes(), and considered an entropy collector, below. */
static void try_to_generate_entropy(void);

/*
 * Wait for the input pool to be seeded and thus guaranteed to supply
121 122 123 124
 * cryptographically secure random numbers. This applies to: the /dev/urandom
 * device, the get_random_bytes function, and the get_random_{u32,u64,int,long}
 * family of functions. Using any of these functions without first calling
 * this function forfeits the guarantee of security.
125 126 127 128 129 130
 *
 * Returns: 0 if the input pool has been seeded.
 *          -ERESTARTSYS if the function was interrupted by a signal.
 */
int wait_for_random_bytes(void)
{
131
	while (!crng_ready()) {
132
		int ret;
133 134

		try_to_generate_entropy();
135 136 137
		ret = wait_event_interruptible_timeout(crng_init_wait, crng_ready(), HZ);
		if (ret)
			return ret > 0 ? 0 : ret;
138
	}
139 140 141 142
	return 0;
}
EXPORT_SYMBOL(wait_for_random_bytes);

143
#define warn_unseeded_randomness() \
144 145 146
	if (IS_ENABLED(CONFIG_WARN_ALL_UNSEEDED_RANDOM) && !crng_ready()) \
		printk_deferred(KERN_NOTICE "random: %s called from %pS with crng_init=%d\n", \
				__func__, (void *)_RET_IP_, crng_init)
147 148


149
/*********************************************************************
L
Linus Torvalds 已提交
150
 *
151
 * Fast key erasure RNG, the "crng".
L
Linus Torvalds 已提交
152
 *
153 154 155
 * These functions expand entropy from the entropy extractor into
 * long streams for external consumption using the "fast key erasure"
 * RNG described at <https://blog.cr.yp.to/20170723-random.html>.
156
 *
157 158
 * There are a few exported interfaces for use by other drivers:
 *
159
 *	void get_random_bytes(void *buf, size_t len)
160 161 162 163 164 165
 *	u32 get_random_u32()
 *	u64 get_random_u64()
 *	unsigned int get_random_int()
 *	unsigned long get_random_long()
 *
 * These interfaces will return the requested number of random bytes
166
 * into the given buffer or as a return value. This is equivalent to
167 168 169 170
 * a read from /dev/urandom. The u32, u64, int, and long family of
 * functions may be higher performance for one-off random integers,
 * because they do a bit of buffering and do not invoke reseeding
 * until the buffer is emptied.
171 172 173
 *
 *********************************************************************/

174 175 176 177
enum {
	CRNG_RESEED_START_INTERVAL = HZ,
	CRNG_RESEED_INTERVAL = 60 * HZ
};
178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197

static struct {
	u8 key[CHACHA_KEY_SIZE] __aligned(__alignof__(long));
	unsigned long birth;
	unsigned long generation;
	spinlock_t lock;
} base_crng = {
	.lock = __SPIN_LOCK_UNLOCKED(base_crng.lock)
};

struct crng {
	u8 key[CHACHA_KEY_SIZE];
	unsigned long generation;
	local_lock_t lock;
};

static DEFINE_PER_CPU(struct crng, crngs) = {
	.generation = ULONG_MAX,
	.lock = INIT_LOCAL_LOCK(crngs.lock),
};
198

199
/* Used by crng_reseed() and crng_make_state() to extract a new seed from the input pool. */
200
static void extract_entropy(void *buf, size_t len);
201

202 203
/* This extracts a new crng key from the input pool. */
static void crng_reseed(void)
204
{
205
	unsigned long flags;
206 207
	unsigned long next_gen;
	u8 key[CHACHA_KEY_SIZE];
208

209
	extract_entropy(key, sizeof(key));
210

211 212 213 214 215 216 217 218 219 220 221 222 223
	/*
	 * We copy the new key into the base_crng, overwriting the old one,
	 * and update the generation counter. We avoid hitting ULONG_MAX,
	 * because the per-cpu crngs are initialized to ULONG_MAX, so this
	 * forces new CPUs that come online to always initialize.
	 */
	spin_lock_irqsave(&base_crng.lock, flags);
	memcpy(base_crng.key, key, sizeof(base_crng.key));
	next_gen = base_crng.generation + 1;
	if (next_gen == ULONG_MAX)
		++next_gen;
	WRITE_ONCE(base_crng.generation, next_gen);
	WRITE_ONCE(base_crng.birth, jiffies);
224
	if (!static_branch_likely(&crng_is_ready))
225
		crng_init = CRNG_READY;
226 227
	spin_unlock_irqrestore(&base_crng.lock, flags);
	memzero_explicit(key, sizeof(key));
228 229
}

230
/*
231
 * This generates a ChaCha block using the provided key, and then
232
 * immediately overwrites that key with half the block. It returns
233 234 235
 * the resultant ChaCha state to the user, along with the second
 * half of the block containing 32 bytes of random data that may
 * be used; random_data_len may not be greater than 32.
236 237 238 239 240 241 242
 *
 * The returned ChaCha state contains within it a copy of the old
 * key value, at index 4, so the state should always be zeroed out
 * immediately after using in order to maintain forward secrecy.
 * If the state cannot be erased in a timely manner, then it is
 * safer to set the random_data parameter to &chacha_state[4] so
 * that this function overwrites it before returning.
243 244 245 246
 */
static void crng_fast_key_erasure(u8 key[CHACHA_KEY_SIZE],
				  u32 chacha_state[CHACHA_STATE_WORDS],
				  u8 *random_data, size_t random_data_len)
247
{
248
	u8 first_block[CHACHA_BLOCK_SIZE];
249

250 251 252 253 254 255 256 257
	BUG_ON(random_data_len > 32);

	chacha_init_consts(chacha_state);
	memcpy(&chacha_state[4], key, CHACHA_KEY_SIZE);
	memset(&chacha_state[12], 0, sizeof(u32) * 4);
	chacha20_block(chacha_state, first_block);

	memcpy(key, first_block, CHACHA_KEY_SIZE);
258
	memcpy(random_data, first_block + CHACHA_KEY_SIZE, random_data_len);
259
	memzero_explicit(first_block, sizeof(first_block));
260 261
}

262
/*
263 264
 * Return the interval until the next reseeding, which is normally
 * CRNG_RESEED_INTERVAL, but during early boot, it is at an interval
265
 * proportional to the uptime.
266
 */
267
static unsigned int crng_reseed_interval(void)
268 269 270 271 272 273 274 275
{
	static bool early_boot = true;

	if (unlikely(READ_ONCE(early_boot))) {
		time64_t uptime = ktime_get_seconds();
		if (uptime >= CRNG_RESEED_INTERVAL / HZ * 2)
			WRITE_ONCE(early_boot, false);
		else
276 277
			return max_t(unsigned int, CRNG_RESEED_START_INTERVAL,
				     (unsigned int)uptime / 2 * HZ);
278
	}
279
	return CRNG_RESEED_INTERVAL;
280 281
}

282
/*
283 284 285
 * This function returns a ChaCha state that you may use for generating
 * random data. It also returns up to 32 bytes on its own of random data
 * that may be used; random_data_len may not be greater than 32.
286
 */
287 288
static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS],
			    u8 *random_data, size_t random_data_len)
289
{
290
	unsigned long flags;
291
	struct crng *crng;
292

293 294 295 296 297
	BUG_ON(random_data_len > 32);

	/*
	 * For the fast path, we check whether we're ready, unlocked first, and
	 * then re-check once locked later. In the case where we're really not
298
	 * ready, we do fast key erasure with the base_crng directly, extracting
299
	 * when crng_init is CRNG_EMPTY.
300
	 */
301
	if (!crng_ready()) {
302 303 304 305
		bool ready;

		spin_lock_irqsave(&base_crng.lock, flags);
		ready = crng_ready();
306
		if (!ready) {
307
			if (crng_init == CRNG_EMPTY)
308
				extract_entropy(base_crng.key, sizeof(base_crng.key));
309 310
			crng_fast_key_erasure(base_crng.key, chacha_state,
					      random_data, random_data_len);
311
		}
312 313 314
		spin_unlock_irqrestore(&base_crng.lock, flags);
		if (!ready)
			return;
315
	}
316 317

	/*
318 319
	 * If the base_crng is old enough, we reseed, which in turn bumps the
	 * generation counter that we check below.
320
	 */
321
	if (unlikely(time_is_before_jiffies(READ_ONCE(base_crng.birth) + crng_reseed_interval())))
322
		crng_reseed();
323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349

	local_lock_irqsave(&crngs.lock, flags);
	crng = raw_cpu_ptr(&crngs);

	/*
	 * If our per-cpu crng is older than the base_crng, then it means
	 * somebody reseeded the base_crng. In that case, we do fast key
	 * erasure on the base_crng, and use its output as the new key
	 * for our per-cpu crng. This brings us up to date with base_crng.
	 */
	if (unlikely(crng->generation != READ_ONCE(base_crng.generation))) {
		spin_lock(&base_crng.lock);
		crng_fast_key_erasure(base_crng.key, chacha_state,
				      crng->key, sizeof(crng->key));
		crng->generation = base_crng.generation;
		spin_unlock(&base_crng.lock);
	}

	/*
	 * Finally, when we've made it this far, our per-cpu crng has an up
	 * to date key, and we can do fast key erasure with it to produce
	 * some random data and a ChaCha state for the caller. All other
	 * branches of this function are "unlikely", so most of the time we
	 * should wind up here immediately.
	 */
	crng_fast_key_erasure(crng->key, chacha_state, random_data, random_data_len);
	local_unlock_irqrestore(&crngs.lock, flags);
350 351
}

352
static void _get_random_bytes(void *buf, size_t len)
353
{
354
	u32 chacha_state[CHACHA_STATE_WORDS];
355
	u8 tmp[CHACHA_BLOCK_SIZE];
356
	size_t first_block_len;
357

358
	if (!len)
359 360
		return;

361 362 363 364
	first_block_len = min_t(size_t, 32, len);
	crng_make_state(chacha_state, buf, first_block_len);
	len -= first_block_len;
	buf += first_block_len;
365

366 367
	while (len) {
		if (len < CHACHA_BLOCK_SIZE) {
368
			chacha20_block(chacha_state, tmp);
369
			memcpy(buf, tmp, len);
370 371 372 373 374 375 376
			memzero_explicit(tmp, sizeof(tmp));
			break;
		}

		chacha20_block(chacha_state, buf);
		if (unlikely(chacha_state[12] == 0))
			++chacha_state[13];
377
		len -= CHACHA_BLOCK_SIZE;
378 379 380 381 382 383 384 385 386
		buf += CHACHA_BLOCK_SIZE;
	}

	memzero_explicit(chacha_state, sizeof(chacha_state));
}

/*
 * This function is the exported kernel interface.  It returns some
 * number of good random numbers, suitable for key generation, seeding
387 388 389
 * TCP sequence numbers, etc. In order to ensure that the randomness
 * by this function is okay, the function wait_for_random_bytes()
 * should be called and return 0 at least once at any point prior.
390
 */
391
void get_random_bytes(void *buf, size_t len)
392
{
393
	warn_unseeded_randomness();
394
	_get_random_bytes(buf, len);
395 396 397
}
EXPORT_SYMBOL(get_random_bytes);

398
static ssize_t get_random_bytes_user(struct iov_iter *iter)
399 400
{
	u32 chacha_state[CHACHA_STATE_WORDS];
401 402
	u8 block[CHACHA_BLOCK_SIZE];
	size_t ret = 0, copied;
403

404
	if (unlikely(!iov_iter_count(iter)))
405 406
		return 0;

407 408
	/*
	 * Immediately overwrite the ChaCha key at index 4 with random
409
	 * bytes, in case userspace causes copy_to_iter() below to sleep
410 411 412 413 414 415 416 417
	 * forever, so that we still retain forward secrecy in that case.
	 */
	crng_make_state(chacha_state, (u8 *)&chacha_state[4], CHACHA_KEY_SIZE);
	/*
	 * However, if we're doing a read of len <= 32, we don't need to
	 * use chacha_state after, so we can simply return those bytes to
	 * the user directly.
	 */
418 419
	if (iov_iter_count(iter) <= CHACHA_KEY_SIZE) {
		ret = copy_to_iter(&chacha_state[4], CHACHA_KEY_SIZE, iter);
420 421
		goto out_zero_chacha;
	}
422

423
	for (;;) {
424
		chacha20_block(chacha_state, block);
425 426 427
		if (unlikely(chacha_state[12] == 0))
			++chacha_state[13];

428 429 430
		copied = copy_to_iter(block, sizeof(block), iter);
		ret += copied;
		if (!iov_iter_count(iter) || copied != sizeof(block))
431
			break;
432

433
		BUILD_BUG_ON(PAGE_SIZE % sizeof(block) != 0);
434
		if (ret % PAGE_SIZE == 0) {
435 436 437 438
			if (signal_pending(current))
				break;
			cond_resched();
		}
439
	}
440

441
	memzero_explicit(block, sizeof(block));
442 443
out_zero_chacha:
	memzero_explicit(chacha_state, sizeof(chacha_state));
444
	return ret ? ret : -EFAULT;
445 446 447 448 449 450 451 452 453
}

/*
 * Batched entropy returns random integers. The quality of the random
 * number is good as /dev/urandom. In order to ensure that the randomness
 * provided by this function is okay, the function wait_for_random_bytes()
 * should be called and return 0 at least once at any point prior.
 */

454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508
#define DEFINE_BATCHED_ENTROPY(type)						\
struct batch_ ##type {								\
	/*									\
	 * We make this 1.5x a ChaCha block, so that we get the			\
	 * remaining 32 bytes from fast key erasure, plus one full		\
	 * block from the detached ChaCha state. We can increase		\
	 * the size of this later if needed so long as we keep the		\
	 * formula of (integer_blocks + 0.5) * CHACHA_BLOCK_SIZE.		\
	 */									\
	type entropy[CHACHA_BLOCK_SIZE * 3 / (2 * sizeof(type))];		\
	local_lock_t lock;							\
	unsigned long generation;						\
	unsigned int position;							\
};										\
										\
static DEFINE_PER_CPU(struct batch_ ##type, batched_entropy_ ##type) = {	\
	.lock = INIT_LOCAL_LOCK(batched_entropy_ ##type.lock),			\
	.position = UINT_MAX							\
};										\
										\
type get_random_ ##type(void)							\
{										\
	type ret;								\
	unsigned long flags;							\
	struct batch_ ##type *batch;						\
	unsigned long next_gen;							\
										\
	warn_unseeded_randomness();						\
										\
	if  (!crng_ready()) {							\
		_get_random_bytes(&ret, sizeof(ret));				\
		return ret;							\
	}									\
										\
	local_lock_irqsave(&batched_entropy_ ##type.lock, flags);		\
	batch = raw_cpu_ptr(&batched_entropy_##type);				\
										\
	next_gen = READ_ONCE(base_crng.generation);				\
	if (batch->position >= ARRAY_SIZE(batch->entropy) ||			\
	    next_gen != batch->generation) {					\
		_get_random_bytes(batch->entropy, sizeof(batch->entropy));	\
		batch->position = 0;						\
		batch->generation = next_gen;					\
	}									\
										\
	ret = batch->entropy[batch->position];					\
	batch->entropy[batch->position] = 0;					\
	++batch->position;							\
	local_unlock_irqrestore(&batched_entropy_ ##type.lock, flags);		\
	return ret;								\
}										\
EXPORT_SYMBOL(get_random_ ##type);

DEFINE_BATCHED_ENTROPY(u64)
DEFINE_BATCHED_ENTROPY(u32)
509

510 511 512 513 514
#ifdef CONFIG_SMP
/*
 * This function is called when the CPU is coming up, with entry
 * CPUHP_RANDOM_PREPARE, which comes before CPUHP_WORKQUEUE_PREP.
 */
515
int __cold random_prepare_cpu(unsigned int cpu)
516 517 518 519 520 521 522 523 524 525 526 527 528
{
	/*
	 * When the cpu comes back online, immediately invalidate both
	 * the per-cpu crng and all batches, so that we serve fresh
	 * randomness.
	 */
	per_cpu_ptr(&crngs, cpu)->generation = ULONG_MAX;
	per_cpu_ptr(&batched_entropy_u32, cpu)->position = UINT_MAX;
	per_cpu_ptr(&batched_entropy_u64, cpu)->position = UINT_MAX;
	return 0;
}
#endif

529 530 531 532 533 534 535

/**********************************************************************
 *
 * Entropy accumulation and extraction routines.
 *
 * Callers may add entropy via:
 *
536
 *     static void mix_pool_bytes(const void *buf, size_t len)
537 538 539
 *
 * After which, if added entropy should be credited:
 *
540
 *     static void credit_init_bits(size_t bits)
541
 *
542
 * Finally, extract entropy via:
543
 *
544
 *     static void extract_entropy(void *buf, size_t len)
545 546 547
 *
 **********************************************************************/

548 549
enum {
	POOL_BITS = BLAKE2S_HASH_SIZE * 8,
550 551
	POOL_READY_BITS = POOL_BITS, /* When crng_init->CRNG_READY */
	POOL_EARLY_BITS = POOL_READY_BITS / 2 /* When crng_init->CRNG_EARLY */
552 553 554 555 556
};

static struct {
	struct blake2s_state hash;
	spinlock_t lock;
557
	unsigned int init_bits;
558 559 560 561 562 563 564 565
} input_pool = {
	.hash.h = { BLAKE2S_IV0 ^ (0x01010000 | BLAKE2S_HASH_SIZE),
		    BLAKE2S_IV1, BLAKE2S_IV2, BLAKE2S_IV3, BLAKE2S_IV4,
		    BLAKE2S_IV5, BLAKE2S_IV6, BLAKE2S_IV7 },
	.hash.outlen = BLAKE2S_HASH_SIZE,
	.lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
};

566
static void _mix_pool_bytes(const void *buf, size_t len)
567
{
568
	blake2s_update(&input_pool.hash, buf, len);
569
}
570 571

/*
572 573 574
 * This function adds bytes into the input pool. It does not
 * update the initialization bit counter; the caller should call
 * credit_init_bits if this is appropriate.
575
 */
576
static void mix_pool_bytes(const void *buf, size_t len)
577
{
578 579 580
	unsigned long flags;

	spin_lock_irqsave(&input_pool.lock, flags);
581
	_mix_pool_bytes(buf, len);
582
	spin_unlock_irqrestore(&input_pool.lock, flags);
583 584
}

585 586 587 588
/*
 * This is an HKDF-like construction for using the hashed collected entropy
 * as a PRF key, that's then expanded block-by-block.
 */
589
static void extract_entropy(void *buf, size_t len)
590 591
{
	unsigned long flags;
592 593 594 595 596
	u8 seed[BLAKE2S_HASH_SIZE], next_key[BLAKE2S_HASH_SIZE];
	struct {
		unsigned long rdseed[32 / sizeof(long)];
		size_t counter;
	} block;
597
	size_t i, longs;
598

599 600 601 602 603 604 605 606 607 608 609 610
	for (i = 0; i < ARRAY_SIZE(block.rdseed);) {
		longs = arch_get_random_seed_longs(&block.rdseed[i], ARRAY_SIZE(block.rdseed) - i);
		if (longs) {
			i += longs;
			continue;
		}
		longs = arch_get_random_longs(&block.rdseed[i], ARRAY_SIZE(block.rdseed) - i);
		if (longs) {
			i += longs;
			continue;
		}
		block.rdseed[i++] = random_get_entropy();
611
	}
612 613

	spin_lock_irqsave(&input_pool.lock, flags);
614 615 616 617 618 619 620 621 622

	/* seed = HASHPRF(last_key, entropy_input) */
	blake2s_final(&input_pool.hash, seed);

	/* next_key = HASHPRF(seed, RDSEED || 0) */
	block.counter = 0;
	blake2s(next_key, (u8 *)&block, seed, sizeof(next_key), sizeof(block), sizeof(seed));
	blake2s_init_key(&input_pool.hash, BLAKE2S_HASH_SIZE, next_key, sizeof(next_key));

623
	spin_unlock_irqrestore(&input_pool.lock, flags);
624 625
	memzero_explicit(next_key, sizeof(next_key));

626 627
	while (len) {
		i = min_t(size_t, len, BLAKE2S_HASH_SIZE);
628 629 630
		/* output = HASHPRF(seed, RDSEED || ++counter) */
		++block.counter;
		blake2s(buf, (u8 *)&block, seed, i, sizeof(block), sizeof(seed));
631
		len -= i;
632 633 634 635 636 637 638
		buf += i;
	}

	memzero_explicit(seed, sizeof(seed));
	memzero_explicit(&block, sizeof(block));
}

639 640 641
#define credit_init_bits(bits) if (!crng_ready()) _credit_init_bits(bits)

static void __cold _credit_init_bits(size_t bits)
642
{
643
	static struct execute_work set_ready;
644
	unsigned int new, orig, add;
645 646
	unsigned long flags;

647
	if (!bits)
648 649
		return;

650
	add = min_t(size_t, bits, POOL_BITS);
651

652
	orig = READ_ONCE(input_pool.init_bits);
653
	do {
654
		new = min_t(unsigned int, POOL_BITS, orig + add);
655
	} while (!try_cmpxchg(&input_pool.init_bits, &orig, new));
656

657 658
	if (orig < POOL_READY_BITS && new >= POOL_READY_BITS) {
		crng_reseed(); /* Sets crng_init to CRNG_READY under base_crng.lock. */
659 660
		if (static_key_initialized)
			execute_in_process_context(crng_set_ready, &set_ready);
661 662 663
		wake_up_interruptible(&crng_init_wait);
		kill_fasync(&fasync, SIGIO, POLL_IN);
		pr_notice("crng init done\n");
664
		if (urandom_warning.missed)
665 666 667
			pr_notice("%d urandom warning(s) missed due to ratelimiting\n",
				  urandom_warning.missed);
	} else if (orig < POOL_EARLY_BITS && new >= POOL_EARLY_BITS) {
668
		spin_lock_irqsave(&base_crng.lock, flags);
669
		/* Check if crng_init is CRNG_EMPTY, to avoid race with crng_reseed(). */
670
		if (crng_init == CRNG_EMPTY) {
671
			extract_entropy(base_crng.key, sizeof(base_crng.key));
672
			crng_init = CRNG_EARLY;
673 674 675 676 677
		}
		spin_unlock_irqrestore(&base_crng.lock, flags);
	}
}

678 679 680 681 682 683 684 685

/**********************************************************************
 *
 * Entropy collection routines.
 *
 * The following exported functions are used for pushing entropy into
 * the above entropy accumulation routines:
 *
686 687 688 689
 *	void add_device_randomness(const void *buf, size_t len);
 *	void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy);
 *	void add_bootloader_randomness(const void *buf, size_t len);
 *	void add_vmfork_randomness(const void *unique_vm_id, size_t len);
690
 *	void add_interrupt_randomness(int irq);
691
 *	void add_input_randomness(unsigned int type, unsigned int code, unsigned int value);
692
 *	void add_disk_randomness(struct gendisk *disk);
693 694 695 696 697 698 699 700 701 702 703 704 705
 *
 * add_device_randomness() adds data to the input pool that
 * is likely to differ between two devices (or possibly even per boot).
 * This would be things like MAC addresses or serial numbers, or the
 * read-out of the RTC. This does *not* credit any actual entropy to
 * the pool, but it initializes the pool to different values for devices
 * that might otherwise be identical and have very little entropy
 * available to them (particularly common in the embedded world).
 *
 * add_hwgenerator_randomness() is for true hardware RNGs, and will credit
 * entropy as specified by the caller. If the entropy pool is full it will
 * block until more entropy is needed.
 *
706 707 708
 * add_bootloader_randomness() is called by bootloader drivers, such as EFI
 * and device tree, and credits its input depending on whether or not the
 * configuration option CONFIG_RANDOM_TRUST_BOOTLOADER is set.
709
 *
710 711 712 713
 * add_vmfork_randomness() adds a unique (but not necessarily secret) ID
 * representing the current instance of a VM to the pool, without crediting,
 * and then force-reseeds the crng so that it takes effect immediately.
 *
714 715 716 717 718
 * add_interrupt_randomness() uses the interrupt timing as random
 * inputs to the entropy pool. Using the cycle counters and the irq source
 * as inputs, it feeds the input pool roughly once a second or after 64
 * interrupts, crediting 1 bit of entropy for whichever comes first.
 *
719 720 721 722 723 724 725 726 727 728 729 730 731
 * add_input_randomness() uses the input layer interrupt timing, as well
 * as the event type information from the hardware.
 *
 * add_disk_randomness() uses what amounts to the seek time of block
 * layer request events, on a per-disk_devt basis, as input to the
 * entropy pool. Note that high-speed solid state drives with very low
 * seek times do not make for good sources of entropy, as their seek
 * times are usually fairly consistent.
 *
 * The last two routines try to estimate how many bits of entropy
 * to credit. They do this by keeping track of the first and second
 * order deltas of the event timings.
 *
732 733
 **********************************************************************/

734 735
static bool trust_cpu __initdata = IS_ENABLED(CONFIG_RANDOM_TRUST_CPU);
static bool trust_bootloader __initdata = IS_ENABLED(CONFIG_RANDOM_TRUST_BOOTLOADER);
736 737 738 739
static int __init parse_trust_cpu(char *arg)
{
	return kstrtobool(arg, &trust_cpu);
}
740 741 742 743
static int __init parse_trust_bootloader(char *arg)
{
	return kstrtobool(arg, &trust_bootloader);
}
744
early_param("random.trust_cpu", parse_trust_cpu);
745
early_param("random.trust_bootloader", parse_trust_bootloader);
746

747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763
static int random_pm_notification(struct notifier_block *nb, unsigned long action, void *data)
{
	unsigned long flags, entropy = random_get_entropy();

	/*
	 * Encode a representation of how long the system has been suspended,
	 * in a way that is distinct from prior system suspends.
	 */
	ktime_t stamps[] = { ktime_get(), ktime_get_boottime(), ktime_get_real() };

	spin_lock_irqsave(&input_pool.lock, flags);
	_mix_pool_bytes(&action, sizeof(action));
	_mix_pool_bytes(stamps, sizeof(stamps));
	_mix_pool_bytes(&entropy, sizeof(entropy));
	spin_unlock_irqrestore(&input_pool.lock, flags);

	if (crng_ready() && (action == PM_RESTORE_PREPARE ||
764 765
	    (action == PM_POST_SUSPEND && !IS_ENABLED(CONFIG_PM_AUTOSLEEP) &&
	     !IS_ENABLED(CONFIG_PM_USERSPACE_AUTOSLEEP)))) {
766
		crng_reseed();
767 768 769 770 771 772 773
		pr_notice("crng reseeded on system resumption\n");
	}
	return 0;
}

static struct notifier_block pm_notifier = { .notifier_call = random_pm_notification };

774
/*
775
 * The first collection of entropy occurs at system boot while interrupts
776 777 778 779 780
 * are still turned off. Here we push in latent entropy, RDSEED, a timestamp,
 * utsname(), and the command line. Depending on the above configuration knob,
 * RDSEED may be considered sufficient for initialization. Note that much
 * earlier setup may already have pushed entropy into the input pool by the
 * time we get here.
781
 */
782
int __init random_init(const char *command_line)
783
{
784
	ktime_t now = ktime_get_real();
785 786
	size_t i, longs, arch_bits;
	unsigned long entropy[BLAKE2S_BLOCK_SIZE / sizeof(long)];
787

788 789 790 791 792
#if defined(LATENT_ENTROPY_PLUGIN)
	static const u8 compiletime_seed[BLAKE2S_BLOCK_SIZE] __initconst __latent_entropy;
	_mix_pool_bytes(compiletime_seed, sizeof(compiletime_seed));
#endif

793 794 795 796 797 798 799 800 801 802 803 804
	for (i = 0, arch_bits = sizeof(entropy) * 8; i < ARRAY_SIZE(entropy);) {
		longs = arch_get_random_seed_longs(entropy, ARRAY_SIZE(entropy) - i);
		if (longs) {
			_mix_pool_bytes(entropy, sizeof(*entropy) * longs);
			i += longs;
			continue;
		}
		longs = arch_get_random_longs(entropy, ARRAY_SIZE(entropy) - i);
		if (longs) {
			_mix_pool_bytes(entropy, sizeof(*entropy) * longs);
			i += longs;
			continue;
805
		}
806 807 808 809
		entropy[0] = random_get_entropy();
		_mix_pool_bytes(entropy, sizeof(*entropy));
		arch_bits -= sizeof(*entropy) * 8;
		++i;
810
	}
811 812
	_mix_pool_bytes(&now, sizeof(now));
	_mix_pool_bytes(utsname(), sizeof(*(utsname())));
813 814
	_mix_pool_bytes(command_line, strlen(command_line));
	add_latent_entropy();
815

816 817 818 819 820 821 822 823
	/*
	 * If we were initialized by the bootloader before jump labels are
	 * initialized, then we should enable the static branch here, where
	 * it's guaranteed that jump labels have been initialized.
	 */
	if (!static_branch_likely(&crng_is_ready) && crng_init >= CRNG_READY)
		crng_set_ready(NULL);

824 825
	if (crng_ready())
		crng_reseed();
826
	else if (trust_cpu)
827
		_credit_init_bits(arch_bits);
828

829 830
	WARN_ON(register_pm_notifier(&pm_notifier));

831 832
	WARN(!random_get_entropy(), "Missing cycle counter and fallback timer; RNG "
				    "entropy collection will consequently suffer.");
833
	return 0;
834
}
835

836
/*
837 838
 * Add device- or boot-specific data to the input pool to help
 * initialize it.
839
 *
840 841 842
 * None of this adds any entropy; it is meant to avoid the problem of
 * the entropy pool having similar initial state across largely
 * identical devices.
843
 */
844
void add_device_randomness(const void *buf, size_t len)
845
{
846 847
	unsigned long entropy = random_get_entropy();
	unsigned long flags;
848

849
	spin_lock_irqsave(&input_pool.lock, flags);
850
	_mix_pool_bytes(&entropy, sizeof(entropy));
851
	_mix_pool_bytes(buf, len);
852
	spin_unlock_irqrestore(&input_pool.lock, flags);
853 854 855
}
EXPORT_SYMBOL(add_device_randomness);

856 857 858 859 860
/*
 * Interface for in-kernel drivers of true hardware RNGs.
 * Those devices may produce endless random bits and will be throttled
 * when our pool is full.
 */
861
void add_hwgenerator_randomness(const void *buf, size_t len, size_t entropy)
862
{
863
	mix_pool_bytes(buf, len);
864 865
	credit_init_bits(entropy);

866
	/*
867
	 * Throttle writing to once every reseed interval, unless we're not yet
868
	 * initialized or no entropy is credited.
869
	 */
870
	if (!kthread_should_stop() && (crng_ready() || !entropy))
871
		schedule_timeout_interruptible(crng_reseed_interval());
872 873 874 875
}
EXPORT_SYMBOL_GPL(add_hwgenerator_randomness);

/*
876 877
 * Handle random seed passed by bootloader, and credit it if
 * CONFIG_RANDOM_TRUST_BOOTLOADER is set.
878
 */
879
void __init add_bootloader_randomness(const void *buf, size_t len)
880
{
881
	mix_pool_bytes(buf, len);
882
	if (trust_bootloader)
883
		credit_init_bits(len * 8);
884 885
}

886
#if IS_ENABLED(CONFIG_VMGENID)
887 888
static BLOCKING_NOTIFIER_HEAD(vmfork_chain);

889 890 891 892 893
/*
 * Handle a new unique VM ID, which is unique, not secret, so we
 * don't credit it, but we do immediately force a reseed after so
 * that it's used by the crng posthaste.
 */
894
void __cold add_vmfork_randomness(const void *unique_vm_id, size_t len)
895
{
896
	add_device_randomness(unique_vm_id, len);
897
	if (crng_ready()) {
898
		crng_reseed();
899 900
		pr_notice("crng reseeded due to virtual machine fork\n");
	}
901
	blocking_notifier_call_chain(&vmfork_chain, 0, NULL);
902
}
903
#if IS_MODULE(CONFIG_VMGENID)
904
EXPORT_SYMBOL_GPL(add_vmfork_randomness);
905
#endif
906

907
int __cold register_random_vmfork_notifier(struct notifier_block *nb)
908 909 910 911 912
{
	return blocking_notifier_chain_register(&vmfork_chain, nb);
}
EXPORT_SYMBOL_GPL(register_random_vmfork_notifier);

913
int __cold unregister_random_vmfork_notifier(struct notifier_block *nb)
914 915 916 917
{
	return blocking_notifier_chain_unregister(&vmfork_chain, nb);
}
EXPORT_SYMBOL_GPL(unregister_random_vmfork_notifier);
918
#endif
919

920
struct fast_pool {
921
	unsigned long pool[4];
922
	unsigned long last;
923
	unsigned int count;
924
	struct timer_list mix;
925 926
};

927 928
static void mix_interrupt_randomness(struct timer_list *work);

929 930
static DEFINE_PER_CPU(struct fast_pool, irq_randomness) = {
#ifdef CONFIG_64BIT
931
#define FASTMIX_PERM SIPHASH_PERMUTATION
932
	.pool = { SIPHASH_CONST_0, SIPHASH_CONST_1, SIPHASH_CONST_2, SIPHASH_CONST_3 },
933
#else
934
#define FASTMIX_PERM HSIPHASH_PERMUTATION
935
	.pool = { HSIPHASH_CONST_0, HSIPHASH_CONST_1, HSIPHASH_CONST_2, HSIPHASH_CONST_3 },
936
#endif
937
	.mix = __TIMER_INITIALIZER(mix_interrupt_randomness, 0)
938 939
};

940
/*
941 942 943
 * This is [Half]SipHash-1-x, starting from an empty key. Because
 * the key is fixed, it assumes that its inputs are non-malicious,
 * and therefore this has no security on its own. s represents the
944
 * four-word SipHash state, while v represents a two-word input.
945
 */
946
static void fast_mix(unsigned long s[4], unsigned long v1, unsigned long v2)
947
{
948
	s[3] ^= v1;
949
	FASTMIX_PERM(s[0], s[1], s[2], s[3]);
950 951
	s[0] ^= v1;
	s[3] ^= v2;
952
	FASTMIX_PERM(s[0], s[1], s[2], s[3]);
953
	s[0] ^= v2;
954 955
}

956 957 958 959 960
#ifdef CONFIG_SMP
/*
 * This function is called when the CPU has just come online, with
 * entry CPUHP_AP_RANDOM_ONLINE, just after CPUHP_AP_WORKQUEUE_ONLINE.
 */
961
int __cold random_online_cpu(unsigned int cpu)
962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978
{
	/*
	 * During CPU shutdown and before CPU onlining, add_interrupt_
	 * randomness() may schedule mix_interrupt_randomness(), and
	 * set the MIX_INFLIGHT flag. However, because the worker can
	 * be scheduled on a different CPU during this period, that
	 * flag will never be cleared. For that reason, we zero out
	 * the flag here, which runs just after workqueues are onlined
	 * for the CPU again. This also has the effect of setting the
	 * irq randomness count to zero so that new accumulated irqs
	 * are fresh.
	 */
	per_cpu_ptr(&irq_randomness, cpu)->count = 0;
	return 0;
}
#endif

979
static void mix_interrupt_randomness(struct timer_list *work)
980 981
{
	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
982
	/*
983 984 985 986 987
	 * The size of the copied stack pool is explicitly 2 longs so that we
	 * only ever ingest half of the siphash output each time, retaining
	 * the other half as the next "key" that carries over. The entropy is
	 * supposed to be sufficiently dispersed between bits so on average
	 * we don't wind up "losing" some.
988
	 */
989
	unsigned long pool[2];
990
	unsigned int count;
991 992 993 994 995 996 997 998 999 1000 1001 1002

	/* Check to see if we're running on the wrong CPU due to hotplug. */
	local_irq_disable();
	if (fast_pool != this_cpu_ptr(&irq_randomness)) {
		local_irq_enable();
		return;
	}

	/*
	 * Copy the pool to the stack so that the mixer always has a
	 * consistent view, before we reenable irqs again.
	 */
1003
	memcpy(pool, fast_pool->pool, sizeof(pool));
1004
	count = fast_pool->count;
1005
	fast_pool->count = 0;
1006 1007 1008
	fast_pool->last = jiffies;
	local_irq_enable();

1009
	mix_pool_bytes(pool, sizeof(pool));
1010
	credit_init_bits(clamp_t(unsigned int, (count & U16_MAX) / 64, 1, sizeof(pool) * 8));
1011

1012 1013 1014
	memzero_explicit(pool, sizeof(pool));
}

1015
void add_interrupt_randomness(int irq)
L
Linus Torvalds 已提交
1016
{
1017
	enum { MIX_INFLIGHT = 1U << 31 };
1018
	unsigned long entropy = random_get_entropy();
1019 1020
	struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness);
	struct pt_regs *regs = get_irq_regs();
1021
	unsigned int new_count;
1022

1023 1024
	fast_mix(fast_pool->pool, entropy,
		 (regs ? instruction_pointer(regs) : _RET_IP_) ^ swab(irq));
1025
	new_count = ++fast_pool->count;
1026

1027
	if (new_count & MIX_INFLIGHT)
L
Linus Torvalds 已提交
1028 1029
		return;

1030
	if (new_count < 1024 && !time_is_before_jiffies(fast_pool->last + HZ))
1031
		return;
1032

1033
	fast_pool->count |= MIX_INFLIGHT;
1034 1035 1036 1037
	if (!timer_pending(&fast_pool->mix)) {
		fast_pool->mix.expires = jiffies;
		add_timer_on(&fast_pool->mix, raw_smp_processor_id());
	}
L
Linus Torvalds 已提交
1038
}
1039
EXPORT_SYMBOL_GPL(add_interrupt_randomness);
L
Linus Torvalds 已提交
1040

1041 1042 1043 1044 1045 1046 1047 1048
/* There is one of these per entropy source */
struct timer_rand_state {
	unsigned long last_time;
	long last_delta, last_delta2;
};

/*
 * This function adds entropy to the entropy "pool" by using timing
1049 1050 1051 1052
 * delays. It uses the timer_rand_state structure to make an estimate
 * of how many bits of entropy this call has added to the pool. The
 * value "num" is also added to the pool; it should somehow describe
 * the type of event that just happened.
1053 1054 1055 1056 1057
 */
static void add_timer_randomness(struct timer_rand_state *state, unsigned int num)
{
	unsigned long entropy = random_get_entropy(), now = jiffies, flags;
	long delta, delta2, delta3;
1058
	unsigned int bits;
1059

1060 1061 1062 1063 1064
	/*
	 * If we're in a hard IRQ, add_interrupt_randomness() will be called
	 * sometime after, so mix into the fast pool.
	 */
	if (in_hardirq()) {
1065
		fast_mix(this_cpu_ptr(&irq_randomness)->pool, entropy, num);
1066 1067 1068 1069 1070 1071
	} else {
		spin_lock_irqsave(&input_pool.lock, flags);
		_mix_pool_bytes(&entropy, sizeof(entropy));
		_mix_pool_bytes(&num, sizeof(num));
		spin_unlock_irqrestore(&input_pool.lock, flags);
	}
1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101

	if (crng_ready())
		return;

	/*
	 * Calculate number of bits of randomness we probably added.
	 * We take into account the first, second and third-order deltas
	 * in order to make our estimate.
	 */
	delta = now - READ_ONCE(state->last_time);
	WRITE_ONCE(state->last_time, now);

	delta2 = delta - READ_ONCE(state->last_delta);
	WRITE_ONCE(state->last_delta, delta);

	delta3 = delta2 - READ_ONCE(state->last_delta2);
	WRITE_ONCE(state->last_delta2, delta2);

	if (delta < 0)
		delta = -delta;
	if (delta2 < 0)
		delta2 = -delta2;
	if (delta3 < 0)
		delta3 = -delta3;
	if (delta > delta2)
		delta = delta2;
	if (delta > delta3)
		delta = delta3;

	/*
1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112
	 * delta is now minimum absolute delta. Round down by 1 bit
	 * on general principles, and limit entropy estimate to 11 bits.
	 */
	bits = min(fls(delta >> 1), 11);

	/*
	 * As mentioned above, if we're in a hard IRQ, add_interrupt_randomness()
	 * will run after this, which uses a different crediting scheme of 1 bit
	 * per every 64 interrupts. In order to let that function do accounting
	 * close to the one in this function, we credit a full 64/64 bit per bit,
	 * and then subtract one to account for the extra one added.
1113
	 */
1114 1115 1116
	if (in_hardirq())
		this_cpu_ptr(&irq_randomness)->count += max(1u, bits * 64) - 1;
	else
1117
		_credit_init_bits(bits);
1118 1119
}

1120
void add_input_randomness(unsigned int type, unsigned int code, unsigned int value)
1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144
{
	static unsigned char last_value;
	static struct timer_rand_state input_timer_state = { INITIAL_JIFFIES };

	/* Ignore autorepeat and the like. */
	if (value == last_value)
		return;

	last_value = value;
	add_timer_randomness(&input_timer_state,
			     (type << 4) ^ code ^ (code >> 4) ^ value);
}
EXPORT_SYMBOL_GPL(add_input_randomness);

#ifdef CONFIG_BLOCK
void add_disk_randomness(struct gendisk *disk)
{
	if (!disk || !disk->random)
		return;
	/* First major is 1, so we get >= 0x200 here. */
	add_timer_randomness(disk->random, 0x100 + disk_devt(disk));
}
EXPORT_SYMBOL_GPL(add_disk_randomness);

1145
void __cold rand_initialize_disk(struct gendisk *disk)
1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160
{
	struct timer_rand_state *state;

	/*
	 * If kzalloc returns null, we just won't use that entropy
	 * source.
	 */
	state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
	if (state) {
		state->last_time = INITIAL_JIFFIES;
		disk->random = state;
	}
}
#endif

1161 1162 1163 1164 1165 1166
struct entropy_timer_state {
	unsigned long entropy;
	struct timer_list timer;
	unsigned int samples, samples_per_bit;
};

1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179
/*
 * Each time the timer fires, we expect that we got an unpredictable
 * jump in the cycle counter. Even if the timer is running on another
 * CPU, the timer activity will be touching the stack of the CPU that is
 * generating entropy..
 *
 * Note that we don't re-arm the timer in the timer itself - we are
 * happy to be scheduled away, since that just makes the load more
 * complex, but we do not want the timer to keep ticking unless the
 * entropy loop is running.
 *
 * So the re-arming always happens in the entropy loop itself.
 */
1180
static void __cold entropy_timer(struct timer_list *timer)
1181
{
1182 1183 1184
	struct entropy_timer_state *state = container_of(timer, struct entropy_timer_state, timer);

	if (++state->samples == state->samples_per_bit) {
1185
		credit_init_bits(1);
1186 1187
		state->samples = 0;
	}
1188 1189 1190 1191 1192 1193
}

/*
 * If we have an actual cycle counter, see if we can
 * generate enough entropy with timing noise
 */
1194
static void __cold try_to_generate_entropy(void)
1195
{
1196
	enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = HZ / 30 };
1197 1198 1199
	struct entropy_timer_state stack;
	unsigned int i, num_different = 0;
	unsigned long last = random_get_entropy();
1200

1201 1202 1203 1204 1205 1206 1207 1208
	for (i = 0; i < NUM_TRIAL_SAMPLES - 1; ++i) {
		stack.entropy = random_get_entropy();
		if (stack.entropy != last)
			++num_different;
		last = stack.entropy;
	}
	stack.samples_per_bit = DIV_ROUND_UP(NUM_TRIAL_SAMPLES, num_different + 1);
	if (stack.samples_per_bit > MAX_SAMPLES_PER_BIT)
1209 1210
		return;

1211
	stack.samples = 0;
1212
	timer_setup_on_stack(&stack.timer, entropy_timer, 0);
1213
	while (!crng_ready() && !signal_pending(current)) {
1214
		if (!timer_pending(&stack.timer))
1215
			mod_timer(&stack.timer, jiffies + 1);
1216
		mix_pool_bytes(&stack.entropy, sizeof(stack.entropy));
1217
		schedule();
1218
		stack.entropy = random_get_entropy();
1219 1220 1221 1222
	}

	del_timer_sync(&stack.timer);
	destroy_timer_on_stack(&stack.timer);
1223
	mix_pool_bytes(&stack.entropy, sizeof(stack.entropy));
1224 1225
}

1226 1227 1228 1229 1230 1231 1232 1233

/**********************************************************************
 *
 * Userspace reader/writer interfaces.
 *
 * getrandom(2) is the primary modern interface into the RNG and should
 * be used in preference to anything else.
 *
1234 1235 1236 1237 1238 1239 1240 1241
 * Reading from /dev/random has the same functionality as calling
 * getrandom(2) with flags=0. In earlier versions, however, it had
 * vastly different semantics and should therefore be avoided, to
 * prevent backwards compatibility issues.
 *
 * Reading from /dev/urandom has the same functionality as calling
 * getrandom(2) with flags=GRND_INSECURE. Because it does not block
 * waiting for the RNG to be ready, it should not be used.
1242 1243 1244 1245
 *
 * Writing to either /dev/random or /dev/urandom adds entropy to
 * the input pool but does not credit it.
 *
1246 1247
 * Polling on /dev/random indicates when the RNG is initialized, on
 * the read side, and when it wants new entropy, on the write side.
1248 1249 1250 1251 1252 1253 1254
 *
 * Both /dev/random and /dev/urandom have the same set of ioctls for
 * adding entropy, getting the entropy count, zeroing the count, and
 * reseeding the crng.
 *
 **********************************************************************/

1255
SYSCALL_DEFINE3(getrandom, char __user *, ubuf, size_t, len, unsigned int, flags)
L
Linus Torvalds 已提交
1256
{
1257 1258 1259 1260
	struct iov_iter iter;
	struct iovec iov;
	int ret;

1261 1262
	if (flags & ~(GRND_NONBLOCK | GRND_RANDOM | GRND_INSECURE))
		return -EINVAL;
1263

1264 1265 1266 1267 1268 1269
	/*
	 * Requesting insecure and blocking randomness at the same time makes
	 * no sense.
	 */
	if ((flags & (GRND_INSECURE | GRND_RANDOM)) == (GRND_INSECURE | GRND_RANDOM))
		return -EINVAL;
1270

1271
	if (!crng_ready() && !(flags & GRND_INSECURE)) {
1272 1273 1274 1275 1276 1277
		if (flags & GRND_NONBLOCK)
			return -EAGAIN;
		ret = wait_for_random_bytes();
		if (unlikely(ret))
			return ret;
	}
1278 1279 1280 1281 1282

	ret = import_single_range(READ, ubuf, len, &iov, &iter);
	if (unlikely(ret))
		return ret;
	return get_random_bytes_user(&iter);
1283 1284
}

1285
static __poll_t random_poll(struct file *file, poll_table *wait)
L
Linus Torvalds 已提交
1286
{
1287
	poll_wait(file, &crng_init_wait, wait);
1288
	return crng_ready() ? EPOLLIN | EPOLLRDNORM : EPOLLOUT | EPOLLWRNORM;
L
Linus Torvalds 已提交
1289 1290
}

1291
static ssize_t write_pool_user(struct iov_iter *iter)
L
Linus Torvalds 已提交
1292
{
1293
	u8 block[BLAKE2S_BLOCK_SIZE];
1294 1295
	ssize_t ret = 0;
	size_t copied;
L
Linus Torvalds 已提交
1296

1297 1298 1299 1300 1301 1302 1303 1304 1305
	if (unlikely(!iov_iter_count(iter)))
		return 0;

	for (;;) {
		copied = copy_from_iter(block, sizeof(block), iter);
		ret += copied;
		mix_pool_bytes(block, copied);
		if (!iov_iter_count(iter) || copied != sizeof(block))
			break;
1306 1307 1308 1309 1310 1311 1312

		BUILD_BUG_ON(PAGE_SIZE % sizeof(block) != 0);
		if (ret % PAGE_SIZE == 0) {
			if (signal_pending(current))
				break;
			cond_resched();
		}
L
Linus Torvalds 已提交
1313
	}
1314

1315
	memzero_explicit(block, sizeof(block));
1316
	return ret ? ret : -EFAULT;
1317 1318
}

1319
static ssize_t random_write_iter(struct kiocb *kiocb, struct iov_iter *iter)
1320
{
1321
	return write_pool_user(iter);
L
Linus Torvalds 已提交
1322 1323
}

1324
static ssize_t urandom_read_iter(struct kiocb *kiocb, struct iov_iter *iter)
1325 1326 1327
{
	static int maxwarn = 10;

1328 1329 1330 1331 1332 1333 1334
	/*
	 * Opportunistically attempt to initialize the RNG on platforms that
	 * have fast cycle counters, but don't (for now) require it to succeed.
	 */
	if (!crng_ready())
		try_to_generate_entropy();

1335 1336 1337 1338 1339
	if (!crng_ready()) {
		if (!ratelimit_disable && maxwarn <= 0)
			++urandom_warning.missed;
		else if (ratelimit_disable || __ratelimit(&urandom_warning)) {
			--maxwarn;
1340 1341
			pr_notice("%s: uninitialized urandom read (%zu bytes read)\n",
				  current->comm, iov_iter_count(iter));
1342
		}
1343 1344
	}

1345
	return get_random_bytes_user(iter);
1346 1347
}

1348
static ssize_t random_read_iter(struct kiocb *kiocb, struct iov_iter *iter)
1349 1350 1351
{
	int ret;

1352 1353 1354 1355 1356
	if (!crng_ready() &&
	    ((kiocb->ki_flags & (IOCB_NOWAIT | IOCB_NOIO)) ||
	     (kiocb->ki_filp->f_flags & O_NONBLOCK)))
		return -EAGAIN;

1357 1358 1359
	ret = wait_for_random_bytes();
	if (ret != 0)
		return ret;
1360
	return get_random_bytes_user(iter);
1361 1362
}

M
Matt Mackall 已提交
1363
static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
L
Linus Torvalds 已提交
1364 1365
{
	int __user *p = (int __user *)arg;
1366
	int ent_count;
L
Linus Torvalds 已提交
1367 1368 1369

	switch (cmd) {
	case RNDGETENTCNT:
1370
		/* Inherently racy, no point locking. */
1371
		if (put_user(input_pool.init_bits, p))
L
Linus Torvalds 已提交
1372 1373 1374 1375 1376 1377 1378
			return -EFAULT;
		return 0;
	case RNDADDTOENTCNT:
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
		if (get_user(ent_count, p))
			return -EFAULT;
1379 1380
		if (ent_count < 0)
			return -EINVAL;
1381
		credit_init_bits(ent_count);
1382
		return 0;
1383 1384 1385 1386 1387 1388
	case RNDADDENTROPY: {
		struct iov_iter iter;
		struct iovec iov;
		ssize_t ret;
		int len;

L
Linus Torvalds 已提交
1389 1390 1391 1392 1393 1394
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
		if (get_user(ent_count, p++))
			return -EFAULT;
		if (ent_count < 0)
			return -EINVAL;
1395 1396 1397 1398 1399
		if (get_user(len, p++))
			return -EFAULT;
		ret = import_single_range(WRITE, p, len, &iov, &iter);
		if (unlikely(ret))
			return ret;
1400
		ret = write_pool_user(&iter);
1401 1402 1403 1404
		if (unlikely(ret < 0))
			return ret;
		/* Since we're crediting, enforce that it was all written into the pool. */
		if (unlikely(ret != len))
L
Linus Torvalds 已提交
1405
			return -EFAULT;
1406
		credit_init_bits(ent_count);
1407
		return 0;
1408
	}
L
Linus Torvalds 已提交
1409 1410
	case RNDZAPENTCNT:
	case RNDCLEARPOOL:
1411
		/* No longer has any effect. */
L
Linus Torvalds 已提交
1412 1413 1414
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
		return 0;
1415 1416 1417
	case RNDRESEEDCRNG:
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
1418
		if (!crng_ready())
1419
			return -ENODATA;
1420
		crng_reseed();
1421
		return 0;
L
Linus Torvalds 已提交
1422 1423 1424 1425 1426
	default:
		return -EINVAL;
	}
}

1427 1428 1429 1430 1431
static int random_fasync(int fd, struct file *filp, int on)
{
	return fasync_helper(fd, filp, on, &fasync);
}

1432
const struct file_operations random_fops = {
1433
	.read_iter = random_read_iter,
1434
	.write_iter = random_write_iter,
1435
	.poll = random_poll,
M
Matt Mackall 已提交
1436
	.unlocked_ioctl = random_ioctl,
1437
	.compat_ioctl = compat_ptr_ioctl,
1438
	.fasync = random_fasync,
1439
	.llseek = noop_llseek,
1440 1441
	.splice_read = generic_file_splice_read,
	.splice_write = iter_file_splice_write,
L
Linus Torvalds 已提交
1442 1443
};

1444
const struct file_operations urandom_fops = {
1445
	.read_iter = urandom_read_iter,
1446
	.write_iter = random_write_iter,
1447 1448 1449 1450
	.unlocked_ioctl = random_ioctl,
	.compat_ioctl = compat_ptr_ioctl,
	.fasync = random_fasync,
	.llseek = noop_llseek,
1451 1452
	.splice_read = generic_file_splice_read,
	.splice_write = iter_file_splice_write,
1453 1454
};

1455

L
Linus Torvalds 已提交
1456 1457
/********************************************************************
 *
1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475
 * Sysctl interface.
 *
 * These are partly unused legacy knobs with dummy values to not break
 * userspace and partly still useful things. They are usually accessible
 * in /proc/sys/kernel/random/ and are as follows:
 *
 * - boot_id - a UUID representing the current boot.
 *
 * - uuid - a random UUID, different each time the file is read.
 *
 * - poolsize - the number of bits of entropy that the input pool can
 *   hold, tied to the POOL_BITS constant.
 *
 * - entropy_avail - the number of bits of entropy currently in the
 *   input pool. Always <= poolsize.
 *
 * - write_wakeup_threshold - the amount of entropy in the input pool
 *   below which write polls to /dev/random will unblock, requesting
1476
 *   more entropy, tied to the POOL_READY_BITS constant. It is writable
1477 1478 1479
 *   to avoid breaking old userspaces, but writing to it does not
 *   change any behavior of the RNG.
 *
1480
 * - urandom_min_reseed_secs - fixed to the value CRNG_RESEED_INTERVAL.
1481 1482
 *   It is writable to avoid breaking old userspaces, but writing
 *   to it does not change any behavior of the RNG.
L
Linus Torvalds 已提交
1483 1484 1485 1486 1487 1488 1489
 *
 ********************************************************************/

#ifdef CONFIG_SYSCTL

#include <linux/sysctl.h>

1490
static int sysctl_random_min_urandom_seed = CRNG_RESEED_INTERVAL / HZ;
1491
static int sysctl_random_write_wakeup_bits = POOL_READY_BITS;
1492
static int sysctl_poolsize = POOL_BITS;
1493
static u8 sysctl_bootid[UUID_SIZE];
L
Linus Torvalds 已提交
1494 1495

/*
G
Greg Price 已提交
1496
 * This function is used to return both the bootid UUID, and random
1497
 * UUID. The difference is in whether table->data is NULL; if it is,
L
Linus Torvalds 已提交
1498 1499
 * then a new UUID is generated and returned to the user.
 */
1500
static int proc_do_uuid(struct ctl_table *table, int write, void *buf,
1501
			size_t *lenp, loff_t *ppos)
L
Linus Torvalds 已提交
1502
{
1503 1504 1505 1506 1507 1508 1509 1510 1511
	u8 tmp_uuid[UUID_SIZE], *uuid;
	char uuid_string[UUID_STRING_LEN + 1];
	struct ctl_table fake_table = {
		.data = uuid_string,
		.maxlen = UUID_STRING_LEN
	};

	if (write)
		return -EPERM;
L
Linus Torvalds 已提交
1512 1513 1514 1515 1516

	uuid = table->data;
	if (!uuid) {
		uuid = tmp_uuid;
		generate_random_uuid(uuid);
1517 1518 1519 1520 1521 1522 1523 1524
	} else {
		static DEFINE_SPINLOCK(bootid_spinlock);

		spin_lock(&bootid_spinlock);
		if (!uuid[8])
			generate_random_uuid(uuid);
		spin_unlock(&bootid_spinlock);
	}
L
Linus Torvalds 已提交
1525

1526
	snprintf(uuid_string, sizeof(uuid_string), "%pU", uuid);
1527
	return proc_dostring(&fake_table, 0, buf, lenp, ppos);
L
Linus Torvalds 已提交
1528 1529
}

1530
/* The same as proc_dointvec, but writes don't change anything. */
1531
static int proc_do_rointvec(struct ctl_table *table, int write, void *buf,
1532 1533
			    size_t *lenp, loff_t *ppos)
{
1534
	return write ? 0 : proc_dointvec(table, 0, buf, lenp, ppos);
1535 1536
}

1537
static struct ctl_table random_table[] = {
L
Linus Torvalds 已提交
1538 1539 1540 1541 1542
	{
		.procname	= "poolsize",
		.data		= &sysctl_poolsize,
		.maxlen		= sizeof(int),
		.mode		= 0444,
1543
		.proc_handler	= proc_dointvec,
L
Linus Torvalds 已提交
1544 1545 1546
	},
	{
		.procname	= "entropy_avail",
1547
		.data		= &input_pool.init_bits,
L
Linus Torvalds 已提交
1548 1549
		.maxlen		= sizeof(int),
		.mode		= 0444,
1550
		.proc_handler	= proc_dointvec,
L
Linus Torvalds 已提交
1551 1552 1553
	},
	{
		.procname	= "write_wakeup_threshold",
1554
		.data		= &sysctl_random_write_wakeup_bits,
L
Linus Torvalds 已提交
1555 1556
		.maxlen		= sizeof(int),
		.mode		= 0644,
1557
		.proc_handler	= proc_do_rointvec,
L
Linus Torvalds 已提交
1558
	},
1559 1560
	{
		.procname	= "urandom_min_reseed_secs",
1561
		.data		= &sysctl_random_min_urandom_seed,
1562 1563
		.maxlen		= sizeof(int),
		.mode		= 0644,
1564
		.proc_handler	= proc_do_rointvec,
1565
	},
L
Linus Torvalds 已提交
1566 1567 1568 1569
	{
		.procname	= "boot_id",
		.data		= &sysctl_bootid,
		.mode		= 0444,
1570
		.proc_handler	= proc_do_uuid,
L
Linus Torvalds 已提交
1571 1572 1573 1574
	},
	{
		.procname	= "uuid",
		.mode		= 0444,
1575
		.proc_handler	= proc_do_uuid,
L
Linus Torvalds 已提交
1576
	},
1577
	{ }
L
Linus Torvalds 已提交
1578
};
1579 1580

/*
1581 1582
 * random_init() is called before sysctl_init(),
 * so we cannot call register_sysctl_init() in random_init()
1583 1584 1585 1586 1587 1588 1589
 */
static int __init random_sysctls_init(void)
{
	register_sysctl_init("kernel/random", random_table);
	return 0;
}
device_initcall(random_sysctls_init);
1590
#endif