random.c 63.9 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3
/*
 * random.c -- A strong random number generator
 *
4 5 6
 * Copyright (C) 2017 Jason A. Donenfeld <Jason@zx2c4.com>. All
 * Rights Reserved.
 *
7
 * Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005
L
Linus Torvalds 已提交
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
 *
 * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  All
 * rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, and the entire permission notice in its entirety,
 *    including the disclaimer of warranties.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote
 *    products derived from this software without specific prior
 *    written permission.
 *
 * ALTERNATIVELY, this product may be distributed under the terms of
 * the GNU General Public License, in which case the provisions of the GPL are
 * required INSTEAD OF the above restrictions.  (This clause is
 * necessary due to a potential bad interaction between the GPL and
 * the restrictions contained in a BSD-style copyright.)
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
 * WHICH ARE HEREBY DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
 * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 */

/*
 * (now, with legal B.S. out of the way.....)
 *
 * This routine gathers environmental noise from device drivers, etc.,
 * and returns good random numbers, suitable for cryptographic use.
 * Besides the obvious cryptographic uses, these numbers are also good
 * for seeding TCP sequence numbers, and other places where it is
 * desirable to have numbers which are not only random, but hard to
 * predict by an attacker.
 *
 * Theory of operation
 * ===================
 *
 * Computers are very predictable devices.  Hence it is extremely hard
 * to produce truly random numbers on a computer --- as opposed to
 * pseudo-random numbers, which can easily generated by using a
 * algorithm.  Unfortunately, it is very easy for attackers to guess
 * the sequence of pseudo-random number generators, and for some
 * applications this is not acceptable.  So instead, we must try to
 * gather "environmental noise" from the computer's environment, which
 * must be hard for outside attackers to observe, and use that to
 * generate random numbers.  In a Unix environment, this is best done
 * from inside the kernel.
 *
 * Sources of randomness from the environment include inter-keyboard
 * timings, inter-interrupt timings from some interrupts, and other
 * events which are both (a) non-deterministic and (b) hard for an
 * outside observer to measure.  Randomness from these sources are
 * added to an "entropy pool", which is mixed using a CRC-like function.
 * This is not cryptographically strong, but it is adequate assuming
 * the randomness is not chosen maliciously, and it is fast enough that
 * the overhead of doing it on every interrupt is very reasonable.
 * As random bytes are mixed into the entropy pool, the routines keep
 * an *estimate* of how many bits of randomness have been stored into
 * the random number generator's internal state.
 *
 * When random bytes are desired, they are obtained by taking the SHA
 * hash of the contents of the "entropy pool".  The SHA hash avoids
 * exposing the internal state of the entropy pool.  It is believed to
 * be computationally infeasible to derive any useful information
 * about the input of SHA from its output.  Even if it is possible to
 * analyze SHA in some clever way, as long as the amount of data
 * returned from the generator is less than the inherent entropy in
 * the pool, the output data is totally unpredictable.  For this
 * reason, the routine decreases its internal estimate of how many
 * bits of "true randomness" are contained in the entropy pool as it
 * outputs random numbers.
 *
 * If this estimate goes to zero, the routine can still generate
 * random numbers; however, an attacker may (at least in theory) be
 * able to infer the future output of the generator from prior
 * outputs.  This requires successful cryptanalysis of SHA, which is
 * not believed to be feasible, but there is a remote possibility.
 * Nonetheless, these numbers should be useful for the vast majority
 * of purposes.
 *
 * Exported interfaces ---- output
 * ===============================
 *
 * There are three exported interfaces; the first is one designed to
 * be used from within the kernel:
 *
 * 	void get_random_bytes(void *buf, int nbytes);
 *
 * This interface will return the requested number of random bytes,
 * and place it in the requested buffer.
 *
 * The two other interfaces are two character devices /dev/random and
 * /dev/urandom.  /dev/random is suitable for use when very high
 * quality randomness is desired (for example, for key generation or
 * one-time pads), as it will only return a maximum of the number of
 * bits of randomness (as estimated by the random number generator)
 * contained in the entropy pool.
 *
 * The /dev/urandom device does not have this limit, and will return
 * as many bytes as are requested.  As more and more random bytes are
 * requested without giving time for the entropy pool to recharge,
 * this will result in random numbers that are merely cryptographically
 * strong.  For many applications, however, this is acceptable.
 *
 * Exported interfaces ---- input
 * ==============================
 *
 * The current exported interfaces for gathering environmental noise
 * from the devices are:
 *
131
 *	void add_device_randomness(const void *buf, unsigned int size);
L
Linus Torvalds 已提交
132 133
 * 	void add_input_randomness(unsigned int type, unsigned int code,
 *                                unsigned int value);
134
 *	void add_interrupt_randomness(int irq, int irq_flags);
135
 * 	void add_disk_randomness(struct gendisk *disk);
L
Linus Torvalds 已提交
136
 *
137 138 139 140 141 142 143 144
 * add_device_randomness() is for adding data to the random 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* add 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).
 *
L
Linus Torvalds 已提交
145 146 147
 * add_input_randomness() uses the input layer interrupt timing, as well as
 * the event type information from the hardware.
 *
148 149 150
 * 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 randomness roughly once a second.
151 152 153 154 155 156
 *
 * 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.
L
Linus Torvalds 已提交
157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253
 *
 * All of these routines try to estimate how many bits of randomness a
 * particular randomness source.  They do this by keeping track of the
 * first and second order deltas of the event timings.
 *
 * Ensuring unpredictability at system startup
 * ============================================
 *
 * When any operating system starts up, it will go through a sequence
 * of actions that are fairly predictable by an adversary, especially
 * if the start-up does not involve interaction with a human operator.
 * This reduces the actual number of bits of unpredictability in the
 * entropy pool below the value in entropy_count.  In order to
 * counteract this effect, it helps to carry information in the
 * entropy pool across shut-downs and start-ups.  To do this, put the
 * following lines an appropriate script which is run during the boot
 * sequence:
 *
 *	echo "Initializing random number generator..."
 *	random_seed=/var/run/random-seed
 *	# Carry a random seed from start-up to start-up
 *	# Load and then save the whole entropy pool
 *	if [ -f $random_seed ]; then
 *		cat $random_seed >/dev/urandom
 *	else
 *		touch $random_seed
 *	fi
 *	chmod 600 $random_seed
 *	dd if=/dev/urandom of=$random_seed count=1 bs=512
 *
 * and the following lines in an appropriate script which is run as
 * the system is shutdown:
 *
 *	# Carry a random seed from shut-down to start-up
 *	# Save the whole entropy pool
 *	echo "Saving random seed..."
 *	random_seed=/var/run/random-seed
 *	touch $random_seed
 *	chmod 600 $random_seed
 *	dd if=/dev/urandom of=$random_seed count=1 bs=512
 *
 * For example, on most modern systems using the System V init
 * scripts, such code fragments would be found in
 * /etc/rc.d/init.d/random.  On older Linux systems, the correct script
 * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0.
 *
 * Effectively, these commands cause the contents of the entropy pool
 * to be saved at shut-down time and reloaded into the entropy pool at
 * start-up.  (The 'dd' in the addition to the bootup script is to
 * make sure that /etc/random-seed is different for every start-up,
 * even if the system crashes without executing rc.0.)  Even with
 * complete knowledge of the start-up activities, predicting the state
 * of the entropy pool requires knowledge of the previous history of
 * the system.
 *
 * Configuring the /dev/random driver under Linux
 * ==============================================
 *
 * The /dev/random driver under Linux uses minor numbers 8 and 9 of
 * the /dev/mem major number (#1).  So if your system does not have
 * /dev/random and /dev/urandom created already, they can be created
 * by using the commands:
 *
 * 	mknod /dev/random c 1 8
 * 	mknod /dev/urandom c 1 9
 *
 * Acknowledgements:
 * =================
 *
 * Ideas for constructing this random number generator were derived
 * from Pretty Good Privacy's random number generator, and from private
 * discussions with Phil Karn.  Colin Plumb provided a faster random
 * number generator, which speed up the mixing function of the entropy
 * pool, taken from PGPfone.  Dale Worley has also contributed many
 * useful ideas and suggestions to improve this driver.
 *
 * Any flaws in the design are solely my responsibility, and should
 * not be attributed to the Phil, Colin, or any of authors of PGP.
 *
 * Further background information on this topic may be obtained from
 * RFC 1750, "Randomness Recommendations for Security", by Donald
 * Eastlake, Steve Crocker, and Jeff Schiller.
 */

#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>
#include <linux/genhd.h>
#include <linux/interrupt.h>
254
#include <linux/mm.h>
255
#include <linux/nodemask.h>
L
Linus Torvalds 已提交
256
#include <linux/spinlock.h>
257
#include <linux/kthread.h>
L
Linus Torvalds 已提交
258 259
#include <linux/percpu.h>
#include <linux/cryptohash.h>
260
#include <linux/fips.h>
261
#include <linux/ptrace.h>
262
#include <linux/kmemcheck.h>
263
#include <linux/workqueue.h>
264
#include <linux/irq.h>
265 266
#include <linux/syscalls.h>
#include <linux/completion.h>
267
#include <linux/uuid.h>
268
#include <crypto/chacha20.h>
269

L
Linus Torvalds 已提交
270
#include <asm/processor.h>
271
#include <linux/uaccess.h>
L
Linus Torvalds 已提交
272
#include <asm/irq.h>
273
#include <asm/irq_regs.h>
L
Linus Torvalds 已提交
274 275
#include <asm/io.h>

276 277 278
#define CREATE_TRACE_POINTS
#include <trace/events/random.h>

279 280
/* #define ADD_INTERRUPT_BENCH */

L
Linus Torvalds 已提交
281 282 283
/*
 * Configuration information
 */
284 285 286 287 288 289
#define INPUT_POOL_SHIFT	12
#define INPUT_POOL_WORDS	(1 << (INPUT_POOL_SHIFT-5))
#define OUTPUT_POOL_SHIFT	10
#define OUTPUT_POOL_WORDS	(1 << (OUTPUT_POOL_SHIFT-5))
#define SEC_XFER_SIZE		512
#define EXTRACT_SIZE		10
L
Linus Torvalds 已提交
290 291


292 293
#define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))

294
/*
T
Theodore Ts'o 已提交
295 296
 * To allow fractional bits to be tracked, the entropy_count field is
 * denominated in units of 1/8th bits.
297 298 299
 *
 * 2*(ENTROPY_SHIFT + log2(poolbits)) must <= 31, or the multiply in
 * credit_entropy_bits() needs to be 64 bits wide.
300 301 302 303
 */
#define ENTROPY_SHIFT 3
#define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)

L
Linus Torvalds 已提交
304 305 306 307
/*
 * The minimum number of bits of entropy before we wake up a read on
 * /dev/random.  Should be enough to do a significant reseed.
 */
308
static int random_read_wakeup_bits = 64;
L
Linus Torvalds 已提交
309 310 311 312 313 314

/*
 * If the entropy count falls under this number of bits, then we
 * should wake up processes which are selecting or polling on write
 * access to /dev/random.
 */
315
static int random_write_wakeup_bits = 28 * OUTPUT_POOL_WORDS;
L
Linus Torvalds 已提交
316 317

/*
318 319 320 321 322 323 324 325 326 327
 * Originally, we used a primitive polynomial of degree .poolwords
 * over GF(2).  The taps for various sizes are defined below.  They
 * were chosen to be evenly spaced except for the last tap, which is 1
 * to get the twisting happening as fast as possible.
 *
 * For the purposes of better mixing, we use the CRC-32 polynomial as
 * well to make a (modified) twisted Generalized Feedback Shift
 * Register.  (See M. Matsumoto & Y. Kurita, 1992.  Twisted GFSR
 * generators.  ACM Transactions on Modeling and Computer Simulation
 * 2(3):179-194.  Also see M. Matsumoto & Y. Kurita, 1994.  Twisted
328
 * GFSR generators II.  ACM Transactions on Modeling and Computer
329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
 * Simulation 4:254-266)
 *
 * Thanks to Colin Plumb for suggesting this.
 *
 * The mixing operation is much less sensitive than the output hash,
 * where we use SHA-1.  All that we want of mixing operation is that
 * it be a good non-cryptographic hash; i.e. it not produce collisions
 * when fed "random" data of the sort we expect to see.  As long as
 * the pool state differs for different inputs, we have preserved the
 * input entropy and done a good job.  The fact that an intelligent
 * attacker can construct inputs that will produce controlled
 * alterations to the pool's state is not important because we don't
 * consider such inputs to contribute any randomness.  The only
 * property we need with respect to them is that the attacker can't
 * increase his/her knowledge of the pool's state.  Since all
 * additions are reversible (knowing the final state and the input,
 * you can reconstruct the initial state), if an attacker has any
 * uncertainty about the initial state, he/she can only shuffle that
 * uncertainty about, but never cause any collisions (which would
 * decrease the uncertainty).
 *
 * Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
 * Videau in their paper, "The Linux Pseudorandom Number Generator
 * Revisited" (see: http://eprint.iacr.org/2012/251.pdf).  In their
 * paper, they point out that we are not using a true Twisted GFSR,
 * since Matsumoto & Kurita used a trinomial feedback polynomial (that
 * is, with only three taps, instead of the six that we are using).
 * As a result, the resulting polynomial is neither primitive nor
 * irreducible, and hence does not have a maximal period over
 * GF(2**32).  They suggest a slight change to the generator
 * polynomial which improves the resulting TGFSR polynomial to be
 * irreducible, which we have made here.
L
Linus Torvalds 已提交
361 362
 */
static struct poolinfo {
363 364
	int poolbitshift, poolwords, poolbytes, poolbits, poolfracbits;
#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32, (x) << (ENTROPY_SHIFT+5)
L
Linus Torvalds 已提交
365 366
	int tap1, tap2, tap3, tap4, tap5;
} poolinfo_table[] = {
367 368 369 370 371 372
	/* was: x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 */
	/* x^128 + x^104 + x^76 + x^51 +x^25 + x + 1 */
	{ S(128),	104,	76,	51,	25,	1 },
	/* was: x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 */
	/* x^32 + x^26 + x^19 + x^14 + x^7 + x + 1 */
	{ S(32),	26,	19,	14,	7,	1 },
L
Linus Torvalds 已提交
373 374
#if 0
	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
375
	{ S(2048),	1638,	1231,	819,	411,	1 },
L
Linus Torvalds 已提交
376 377

	/* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
378
	{ S(1024),	817,	615,	412,	204,	1 },
L
Linus Torvalds 已提交
379 380

	/* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
381
	{ S(1024),	819,	616,	410,	207,	2 },
L
Linus Torvalds 已提交
382 383

	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
384
	{ S(512),	411,	308,	208,	104,	1 },
L
Linus Torvalds 已提交
385 386

	/* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
387
	{ S(512),	409,	307,	206,	102,	2 },
L
Linus Torvalds 已提交
388
	/* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */
389
	{ S(512),	409,	309,	205,	103,	2 },
L
Linus Torvalds 已提交
390 391

	/* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
392
	{ S(256),	205,	155,	101,	52,	1 },
L
Linus Torvalds 已提交
393 394

	/* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
395
	{ S(128),	103,	78,	51,	27,	2 },
L
Linus Torvalds 已提交
396 397

	/* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */
398
	{ S(64),	52,	39,	26,	14,	1 },
L
Linus Torvalds 已提交
399 400 401 402 403 404 405 406
#endif
};

/*
 * Static global variables
 */
static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
407
static struct fasync_struct *fasync;
L
Linus Torvalds 已提交
408

409 410 411
static DEFINE_SPINLOCK(random_ready_list_lock);
static LIST_HEAD(random_ready_list);

412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
struct crng_state {
	__u32		state[16];
	unsigned long	init_time;
	spinlock_t	lock;
};

struct crng_state primary_crng = {
	.lock = __SPIN_LOCK_UNLOCKED(primary_crng.lock),
};

/*
 * crng_init =  0 --> Uninitialized
 *		1 --> Initialized
 *		2 --> Initialized from input_pool
 *
 * crng_init is protected by primary_crng->lock, and only increases
 * its value (from 0->1->2).
 */
static int crng_init = 0;
#define crng_ready() (likely(crng_init > 0))
static int crng_init_cnt = 0;
#define CRNG_INIT_CNT_THRESH (2*CHACHA20_KEY_SIZE)
434 435
static void _extract_crng(struct crng_state *crng,
			  __u8 out[CHACHA20_BLOCK_SIZE]);
436 437
static void _crng_backtrack_protect(struct crng_state *crng,
				    __u8 tmp[CHACHA20_BLOCK_SIZE], int used);
438
static void process_random_ready_list(void);
439
static void _get_random_bytes(void *buf, int nbytes);
440

L
Linus Torvalds 已提交
441 442 443 444 445 446 447 448 449
/**********************************************************************
 *
 * OS independent entropy store.   Here are the functions which handle
 * storing entropy in an entropy pool.
 *
 **********************************************************************/

struct entropy_store;
struct entropy_store {
450
	/* read-only data: */
451
	const struct poolinfo *poolinfo;
L
Linus Torvalds 已提交
452 453 454
	__u32 *pool;
	const char *name;
	struct entropy_store *pull;
455
	struct work_struct push_work;
L
Linus Torvalds 已提交
456 457

	/* read-write data: */
458
	unsigned long last_pulled;
459
	spinlock_t lock;
460 461
	unsigned short add_ptr;
	unsigned short input_rotate;
462
	int entropy_count;
463 464
	int entropy_total;
	unsigned int initialized:1;
465
	unsigned int last_data_init:1;
M
Matt Mackall 已提交
466
	__u8 last_data[EXTRACT_SIZE];
L
Linus Torvalds 已提交
467 468
};

469 470 471 472 473 474
static ssize_t extract_entropy(struct entropy_store *r, void *buf,
			       size_t nbytes, int min, int rsvd);
static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
				size_t nbytes, int fips);

static void crng_reseed(struct crng_state *crng, struct entropy_store *r);
475
static void push_to_pool(struct work_struct *work);
476 477
static __u32 input_pool_data[INPUT_POOL_WORDS] __latent_entropy;
static __u32 blocking_pool_data[OUTPUT_POOL_WORDS] __latent_entropy;
L
Linus Torvalds 已提交
478 479 480 481

static struct entropy_store input_pool = {
	.poolinfo = &poolinfo_table[0],
	.name = "input",
482
	.lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
L
Linus Torvalds 已提交
483 484 485 486 487 488 489
	.pool = input_pool_data
};

static struct entropy_store blocking_pool = {
	.poolinfo = &poolinfo_table[1],
	.name = "blocking",
	.pull = &input_pool,
490
	.lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock),
491 492 493
	.pool = blocking_pool_data,
	.push_work = __WORK_INITIALIZER(blocking_pool.push_work,
					push_to_pool),
L
Linus Torvalds 已提交
494 495
};

496 497 498 499
static __u32 const twist_table[8] = {
	0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
	0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };

L
Linus Torvalds 已提交
500
/*
501
 * This function adds bytes into the entropy "pool".  It does not
L
Linus Torvalds 已提交
502
 * update the entropy estimate.  The caller should call
503
 * credit_entropy_bits if this is appropriate.
L
Linus Torvalds 已提交
504 505 506 507 508 509
 *
 * The pool is stirred with a primitive polynomial of the appropriate
 * degree, and then twisted.  We twist by three bits at a time because
 * it's cheap to do so and helps slightly in the expected case where
 * the entropy is concentrated in the low-order bits.
 */
510
static void _mix_pool_bytes(struct entropy_store *r, const void *in,
511
			    int nbytes)
L
Linus Torvalds 已提交
512
{
513
	unsigned long i, tap1, tap2, tap3, tap4, tap5;
514
	int input_rotate;
L
Linus Torvalds 已提交
515
	int wordmask = r->poolinfo->poolwords - 1;
516
	const char *bytes = in;
517
	__u32 w;
L
Linus Torvalds 已提交
518 519 520 521 522 523 524

	tap1 = r->poolinfo->tap1;
	tap2 = r->poolinfo->tap2;
	tap3 = r->poolinfo->tap3;
	tap4 = r->poolinfo->tap4;
	tap5 = r->poolinfo->tap5;

525 526
	input_rotate = r->input_rotate;
	i = r->add_ptr;
L
Linus Torvalds 已提交
527

528 529
	/* mix one byte at a time to simplify size handling and churn faster */
	while (nbytes--) {
530
		w = rol32(*bytes++, input_rotate);
M
Matt Mackall 已提交
531
		i = (i - 1) & wordmask;
L
Linus Torvalds 已提交
532 533

		/* XOR in the various taps */
M
Matt Mackall 已提交
534
		w ^= r->pool[i];
L
Linus Torvalds 已提交
535 536 537 538 539
		w ^= r->pool[(i + tap1) & wordmask];
		w ^= r->pool[(i + tap2) & wordmask];
		w ^= r->pool[(i + tap3) & wordmask];
		w ^= r->pool[(i + tap4) & wordmask];
		w ^= r->pool[(i + tap5) & wordmask];
M
Matt Mackall 已提交
540 541

		/* Mix the result back in with a twist */
L
Linus Torvalds 已提交
542
		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
543 544 545 546 547 548 549

		/*
		 * Normally, we add 7 bits of rotation to the pool.
		 * At the beginning of the pool, add an extra 7 bits
		 * rotation, so that successive passes spread the
		 * input bits across the pool evenly.
		 */
550
		input_rotate = (input_rotate + (i ? 7 : 14)) & 31;
L
Linus Torvalds 已提交
551 552
	}

553 554
	r->input_rotate = input_rotate;
	r->add_ptr = i;
L
Linus Torvalds 已提交
555 556
}

557
static void __mix_pool_bytes(struct entropy_store *r, const void *in,
558
			     int nbytes)
559 560
{
	trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_);
561
	_mix_pool_bytes(r, in, nbytes);
562 563 564
}

static void mix_pool_bytes(struct entropy_store *r, const void *in,
565
			   int nbytes)
L
Linus Torvalds 已提交
566
{
567 568
	unsigned long flags;

569
	trace_mix_pool_bytes(r->name, nbytes, _RET_IP_);
570
	spin_lock_irqsave(&r->lock, flags);
571
	_mix_pool_bytes(r, in, nbytes);
572
	spin_unlock_irqrestore(&r->lock, flags);
L
Linus Torvalds 已提交
573 574
}

575 576 577
struct fast_pool {
	__u32		pool[4];
	unsigned long	last;
578
	unsigned short	reg_idx;
579
	unsigned char	count;
580 581 582 583 584 585 586
};

/*
 * This is a fast mixing routine used by the interrupt randomness
 * collector.  It's hardcoded for an 128 bit pool and assumes that any
 * locks that might be needed are taken by the caller.
 */
587
static void fast_mix(struct fast_pool *f)
588
{
589 590 591 592
	__u32 a = f->pool[0],	b = f->pool[1];
	__u32 c = f->pool[2],	d = f->pool[3];

	a += b;			c += d;
G
George Spelvin 已提交
593
	b = rol32(b, 6);	d = rol32(d, 27);
594 595 596
	d ^= a;			b ^= c;

	a += b;			c += d;
G
George Spelvin 已提交
597
	b = rol32(b, 16);	d = rol32(d, 14);
598 599 600
	d ^= a;			b ^= c;

	a += b;			c += d;
G
George Spelvin 已提交
601
	b = rol32(b, 6);	d = rol32(d, 27);
602 603 604
	d ^= a;			b ^= c;

	a += b;			c += d;
G
George Spelvin 已提交
605
	b = rol32(b, 16);	d = rol32(d, 14);
606 607 608 609
	d ^= a;			b ^= c;

	f->pool[0] = a;  f->pool[1] = b;
	f->pool[2] = c;  f->pool[3] = d;
610
	f->count++;
611 612
}

613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628
static void process_random_ready_list(void)
{
	unsigned long flags;
	struct random_ready_callback *rdy, *tmp;

	spin_lock_irqsave(&random_ready_list_lock, flags);
	list_for_each_entry_safe(rdy, tmp, &random_ready_list, list) {
		struct module *owner = rdy->owner;

		list_del_init(&rdy->list);
		rdy->func(rdy);
		module_put(owner);
	}
	spin_unlock_irqrestore(&random_ready_list_lock, flags);
}

L
Linus Torvalds 已提交
629
/*
630 631 632
 * Credit (or debit) the entropy store with n bits of entropy.
 * Use credit_entropy_bits_safe() if the value comes from userspace
 * or otherwise should be checked for extreme values.
L
Linus Torvalds 已提交
633
 */
634
static void credit_entropy_bits(struct entropy_store *r, int nbits)
L
Linus Torvalds 已提交
635
{
636
	int entropy_count, orig;
637 638
	const int pool_size = r->poolinfo->poolfracbits;
	int nfrac = nbits << ENTROPY_SHIFT;
L
Linus Torvalds 已提交
639

640 641 642
	if (!nbits)
		return;

643 644
retry:
	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682
	if (nfrac < 0) {
		/* Debit */
		entropy_count += nfrac;
	} else {
		/*
		 * Credit: we have to account for the possibility of
		 * overwriting already present entropy.	 Even in the
		 * ideal case of pure Shannon entropy, new contributions
		 * approach the full value asymptotically:
		 *
		 * entropy <- entropy + (pool_size - entropy) *
		 *	(1 - exp(-add_entropy/pool_size))
		 *
		 * For add_entropy <= pool_size/2 then
		 * (1 - exp(-add_entropy/pool_size)) >=
		 *    (add_entropy/pool_size)*0.7869...
		 * so we can approximate the exponential with
		 * 3/4*add_entropy/pool_size and still be on the
		 * safe side by adding at most pool_size/2 at a time.
		 *
		 * The use of pool_size-2 in the while statement is to
		 * prevent rounding artifacts from making the loop
		 * arbitrarily long; this limits the loop to log2(pool_size)*2
		 * turns no matter how large nbits is.
		 */
		int pnfrac = nfrac;
		const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
		/* The +2 corresponds to the /4 in the denominator */

		do {
			unsigned int anfrac = min(pnfrac, pool_size/2);
			unsigned int add =
				((pool_size - entropy_count)*anfrac*3) >> s;

			entropy_count += add;
			pnfrac -= anfrac;
		} while (unlikely(entropy_count < pool_size-2 && pnfrac));
	}
683

684
	if (unlikely(entropy_count < 0)) {
685 686 687
		pr_warn("random: negative entropy/overflow: pool %s count %d\n",
			r->name, entropy_count);
		WARN_ON(1);
688
		entropy_count = 0;
689 690
	} else if (entropy_count > pool_size)
		entropy_count = pool_size;
691 692
	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
		goto retry;
L
Linus Torvalds 已提交
693

694
	r->entropy_total += nbits;
695 696 697
	if (!r->initialized && r->entropy_total > 128) {
		r->initialized = 1;
		r->entropy_total = 0;
698 699
	}

700 701
	trace_credit_entropy_bits(r->name, nbits,
				  entropy_count >> ENTROPY_SHIFT,
702 703
				  r->entropy_total, _RET_IP_);

704
	if (r == &input_pool) {
705
		int entropy_bits = entropy_count >> ENTROPY_SHIFT;
706

707 708 709 710 711
		if (crng_init < 2 && entropy_bits >= 128) {
			crng_reseed(&primary_crng, r);
			entropy_bits = r->entropy_count >> ENTROPY_SHIFT;
		}

712
		/* should we wake readers? */
713
		if (entropy_bits >= random_read_wakeup_bits) {
714 715 716 717
			wake_up_interruptible(&random_read_wait);
			kill_fasync(&fasync, SIGIO, POLL_IN);
		}
		/* If the input pool is getting full, send some
718
		 * entropy to the blocking pool until it is 75% full.
719
		 */
720
		if (entropy_bits > random_write_wakeup_bits &&
721
		    r->initialized &&
722
		    r->entropy_total >= 2*random_read_wakeup_bits) {
723 724 725
			struct entropy_store *other = &blocking_pool;

			if (other->entropy_count <=
726 727
			    3 * other->poolinfo->poolfracbits / 4) {
				schedule_work(&other->push_work);
728 729 730
				r->entropy_total = 0;
			}
		}
731
	}
L
Linus Torvalds 已提交
732 733
}

734
static int credit_entropy_bits_safe(struct entropy_store *r, int nbits)
735 736 737
{
	const int nbits_max = (int)(~0U >> (ENTROPY_SHIFT + 1));

738 739 740
	if (nbits < 0)
		return -EINVAL;

741 742 743 744
	/* Cap the value to avoid overflows */
	nbits = min(nbits,  nbits_max);

	credit_entropy_bits(r, nbits);
745
	return 0;
746 747
}

748 749 750 751 752 753 754 755 756 757
/*********************************************************************
 *
 * CRNG using CHACHA20
 *
 *********************************************************************/

#define CRNG_RESEED_INTERVAL (300*HZ)

static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait);

758 759 760 761 762 763 764 765 766 767
#ifdef CONFIG_NUMA
/*
 * Hack to deal with crazy userspace progams when they are all trying
 * to access /dev/urandom in parallel.  The programs are almost
 * certainly doing something terribly wrong, but we'll work around
 * their brain damage.
 */
static struct crng_state **crng_node_pool __read_mostly;
#endif

768 769
static void invalidate_batched_entropy(void);

770 771 772 773 774 775 776 777 778 779
static void crng_initialize(struct crng_state *crng)
{
	int		i;
	unsigned long	rv;

	memcpy(&crng->state[0], "expand 32-byte k", 16);
	if (crng == &primary_crng)
		_extract_entropy(&input_pool, &crng->state[4],
				 sizeof(__u32) * 12, 0);
	else
780
		_get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805
	for (i = 4; i < 16; i++) {
		if (!arch_get_random_seed_long(&rv) &&
		    !arch_get_random_long(&rv))
			rv = random_get_entropy();
		crng->state[i] ^= rv;
	}
	crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
}

static int crng_fast_load(const char *cp, size_t len)
{
	unsigned long flags;
	char *p;

	if (!spin_trylock_irqsave(&primary_crng.lock, flags))
		return 0;
	if (crng_ready()) {
		spin_unlock_irqrestore(&primary_crng.lock, flags);
		return 0;
	}
	p = (unsigned char *) &primary_crng.state[4];
	while (len > 0 && crng_init_cnt < CRNG_INIT_CNT_THRESH) {
		p[crng_init_cnt % CHACHA20_KEY_SIZE] ^= *cp;
		cp++; crng_init_cnt++; len--;
	}
806
	spin_unlock_irqrestore(&primary_crng.lock, flags);
807
	if (crng_init_cnt >= CRNG_INIT_CNT_THRESH) {
808
		invalidate_batched_entropy();
809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828
		crng_init = 1;
		wake_up_interruptible(&crng_init_wait);
		pr_notice("random: fast init done\n");
	}
	return 1;
}

static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
{
	unsigned long	flags;
	int		i, num;
	union {
		__u8	block[CHACHA20_BLOCK_SIZE];
		__u32	key[8];
	} buf;

	if (r) {
		num = extract_entropy(r, &buf, 32, 16, 0);
		if (num == 0)
			return;
829
	} else {
830
		_extract_crng(&primary_crng, buf.block);
831 832 833
		_crng_backtrack_protect(&primary_crng, buf.block,
					CHACHA20_KEY_SIZE);
	}
834 835 836 837 838 839 840 841 842 843
	spin_lock_irqsave(&primary_crng.lock, flags);
	for (i = 0; i < 8; i++) {
		unsigned long	rv;
		if (!arch_get_random_seed_long(&rv) &&
		    !arch_get_random_long(&rv))
			rv = random_get_entropy();
		crng->state[i+4] ^= buf.key[i] ^ rv;
	}
	memzero_explicit(&buf, sizeof(buf));
	crng->init_time = jiffies;
844
	spin_unlock_irqrestore(&primary_crng.lock, flags);
845
	if (crng == &primary_crng && crng_init < 2) {
846
		invalidate_batched_entropy();
847 848 849 850 851 852 853
		crng_init = 2;
		process_random_ready_list();
		wake_up_interruptible(&crng_init_wait);
		pr_notice("random: crng init done\n");
	}
}

854 855
static void _extract_crng(struct crng_state *crng,
			  __u8 out[CHACHA20_BLOCK_SIZE])
856 857 858 859 860
{
	unsigned long v, flags;

	if (crng_init > 1 &&
	    time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL))
861
		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
862 863 864 865 866 867 868 869 870
	spin_lock_irqsave(&crng->lock, flags);
	if (arch_get_random_long(&v))
		crng->state[14] ^= v;
	chacha20_block(&crng->state[0], out);
	if (crng->state[12] == 0)
		crng->state[13]++;
	spin_unlock_irqrestore(&crng->lock, flags);
}

871 872 873 874 875 876 877 878 879 880 881 882 883
static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE])
{
	struct crng_state *crng = NULL;

#ifdef CONFIG_NUMA
	if (crng_node_pool)
		crng = crng_node_pool[numa_node_id()];
	if (crng == NULL)
#endif
		crng = &primary_crng;
	_extract_crng(crng, out);
}

884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920
/*
 * Use the leftover bytes from the CRNG block output (if there is
 * enough) to mutate the CRNG key to provide backtracking protection.
 */
static void _crng_backtrack_protect(struct crng_state *crng,
				    __u8 tmp[CHACHA20_BLOCK_SIZE], int used)
{
	unsigned long	flags;
	__u32		*s, *d;
	int		i;

	used = round_up(used, sizeof(__u32));
	if (used + CHACHA20_KEY_SIZE > CHACHA20_BLOCK_SIZE) {
		extract_crng(tmp);
		used = 0;
	}
	spin_lock_irqsave(&crng->lock, flags);
	s = (__u32 *) &tmp[used];
	d = &crng->state[4];
	for (i=0; i < 8; i++)
		*d++ ^= *s++;
	spin_unlock_irqrestore(&crng->lock, flags);
}

static void crng_backtrack_protect(__u8 tmp[CHACHA20_BLOCK_SIZE], int used)
{
	struct crng_state *crng = NULL;

#ifdef CONFIG_NUMA
	if (crng_node_pool)
		crng = crng_node_pool[numa_node_id()];
	if (crng == NULL)
#endif
		crng = &primary_crng;
	_crng_backtrack_protect(crng, tmp, used);
}

921 922
static ssize_t extract_crng_user(void __user *buf, size_t nbytes)
{
923
	ssize_t ret = 0, i = CHACHA20_BLOCK_SIZE;
924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947
	__u8 tmp[CHACHA20_BLOCK_SIZE];
	int large_request = (nbytes > 256);

	while (nbytes) {
		if (large_request && need_resched()) {
			if (signal_pending(current)) {
				if (ret == 0)
					ret = -ERESTARTSYS;
				break;
			}
			schedule();
		}

		extract_crng(tmp);
		i = min_t(int, nbytes, CHACHA20_BLOCK_SIZE);
		if (copy_to_user(buf, tmp, i)) {
			ret = -EFAULT;
			break;
		}

		nbytes -= i;
		buf += i;
		ret += i;
	}
948
	crng_backtrack_protect(tmp, i);
949 950 951 952 953 954 955 956

	/* Wipe data just written to memory */
	memzero_explicit(tmp, sizeof(tmp));

	return ret;
}


L
Linus Torvalds 已提交
957 958 959 960 961 962 963 964 965
/*********************************************************************
 *
 * Entropy input management
 *
 *********************************************************************/

/* There is one of these per entropy source */
struct timer_rand_state {
	cycles_t last_time;
966
	long last_delta, last_delta2;
L
Linus Torvalds 已提交
967 968 969
	unsigned dont_count_entropy:1;
};

970 971
#define INIT_TIMER_RAND_STATE { INITIAL_JIFFIES, };

972
/*
973 974
 * Add device- or boot-specific data to the input pool to help
 * initialize it.
975
 *
976 977 978
 * 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.
979 980 981
 */
void add_device_randomness(const void *buf, unsigned int size)
{
982
	unsigned long time = random_get_entropy() ^ jiffies;
983
	unsigned long flags;
984

985 986 987 988 989
	if (!crng_ready()) {
		crng_fast_load(buf, size);
		return;
	}

990
	trace_add_device_randomness(size, _RET_IP_);
991
	spin_lock_irqsave(&input_pool.lock, flags);
992 993
	_mix_pool_bytes(&input_pool, buf, size);
	_mix_pool_bytes(&input_pool, &time, sizeof(time));
994
	spin_unlock_irqrestore(&input_pool.lock, flags);
995 996 997
}
EXPORT_SYMBOL(add_device_randomness);

998
static struct timer_rand_state input_timer_state = INIT_TIMER_RAND_STATE;
999

L
Linus Torvalds 已提交
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011
/*
 * This function adds entropy to the entropy "pool" by using timing
 * 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 number "num" is also added to the pool - it should somehow describe
 * the type of event which just happened.  This is currently 0-255 for
 * keyboard scan codes, and 256 upwards for interrupts.
 *
 */
static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
{
1012
	struct entropy_store	*r;
L
Linus Torvalds 已提交
1013 1014
	struct {
		long jiffies;
1015
		unsigned cycles;
L
Linus Torvalds 已提交
1016 1017 1018 1019 1020 1021 1022
		unsigned num;
	} sample;
	long delta, delta2, delta3;

	preempt_disable();

	sample.jiffies = jiffies;
1023
	sample.cycles = random_get_entropy();
L
Linus Torvalds 已提交
1024
	sample.num = num;
1025
	r = &input_pool;
1026
	mix_pool_bytes(r, &sample, sizeof(sample));
L
Linus Torvalds 已提交
1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059

	/*
	 * 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.
	 */

	if (!state->dont_count_entropy) {
		delta = sample.jiffies - state->last_time;
		state->last_time = sample.jiffies;

		delta2 = delta - state->last_delta;
		state->last_delta = delta;

		delta3 = delta2 - state->last_delta2;
		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;

		/*
		 * delta is now minimum absolute delta.
		 * Round down by 1 bit on general principles,
		 * and limit entropy entimate to 12 bits.
		 */
1060
		credit_entropy_bits(r, min_t(int, fls(delta>>1), 11));
L
Linus Torvalds 已提交
1061 1062 1063 1064
	}
	preempt_enable();
}

1065
void add_input_randomness(unsigned int type, unsigned int code,
L
Linus Torvalds 已提交
1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076
				 unsigned int value)
{
	static unsigned char last_value;

	/* 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);
1077
	trace_add_input_randomness(ENTROPY_BITS(&input_pool));
L
Linus Torvalds 已提交
1078
}
1079
EXPORT_SYMBOL_GPL(add_input_randomness);
L
Linus Torvalds 已提交
1080

1081 1082
static DEFINE_PER_CPU(struct fast_pool, irq_randomness);

1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103
#ifdef ADD_INTERRUPT_BENCH
static unsigned long avg_cycles, avg_deviation;

#define AVG_SHIFT 8     /* Exponential average factor k=1/256 */
#define FIXED_1_2 (1 << (AVG_SHIFT-1))

static void add_interrupt_bench(cycles_t start)
{
        long delta = random_get_entropy() - start;

        /* Use a weighted moving average */
        delta = delta - ((avg_cycles + FIXED_1_2) >> AVG_SHIFT);
        avg_cycles += delta;
        /* And average deviation */
        delta = abs(delta) - ((avg_deviation + FIXED_1_2) >> AVG_SHIFT);
        avg_deviation += delta;
}
#else
#define add_interrupt_bench(x)
#endif

1104 1105 1106
static __u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
{
	__u32 *ptr = (__u32 *) regs;
1107
	unsigned int idx;
1108 1109 1110

	if (regs == NULL)
		return 0;
1111 1112 1113 1114 1115
	idx = READ_ONCE(f->reg_idx);
	if (idx >= sizeof(struct pt_regs) / sizeof(__u32))
		idx = 0;
	ptr += idx++;
	WRITE_ONCE(f->reg_idx, idx);
1116
	return *ptr;
1117 1118
}

1119
void add_interrupt_randomness(int irq, int irq_flags)
L
Linus Torvalds 已提交
1120
{
1121
	struct entropy_store	*r;
1122
	struct fast_pool	*fast_pool = this_cpu_ptr(&irq_randomness);
1123 1124
	struct pt_regs		*regs = get_irq_regs();
	unsigned long		now = jiffies;
1125
	cycles_t		cycles = random_get_entropy();
1126
	__u32			c_high, j_high;
1127
	__u64			ip;
1128
	unsigned long		seed;
1129
	int			credit = 0;
1130

1131 1132
	if (cycles == 0)
		cycles = get_reg(fast_pool, regs);
1133 1134
	c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
	j_high = (sizeof(now) > 4) ? now >> 32 : 0;
1135 1136
	fast_pool->pool[0] ^= cycles ^ j_high ^ irq;
	fast_pool->pool[1] ^= now ^ c_high;
1137
	ip = regs ? instruction_pointer(regs) : _RET_IP_;
1138
	fast_pool->pool[2] ^= ip;
1139 1140
	fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 :
		get_reg(fast_pool, regs);
1141

1142 1143
	fast_mix(fast_pool);
	add_interrupt_bench(cycles);
1144

1145 1146 1147 1148 1149 1150 1151 1152 1153 1154
	if (!crng_ready()) {
		if ((fast_pool->count >= 64) &&
		    crng_fast_load((char *) fast_pool->pool,
				   sizeof(fast_pool->pool))) {
			fast_pool->count = 0;
			fast_pool->last = now;
		}
		return;
	}

1155 1156
	if ((fast_pool->count < 64) &&
	    !time_after(now, fast_pool->last + HZ))
L
Linus Torvalds 已提交
1157 1158
		return;

1159
	r = &input_pool;
1160
	if (!spin_trylock(&r->lock))
1161
		return;
1162

1163
	fast_pool->last = now;
1164
	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
1165 1166 1167

	/*
	 * If we have architectural seed generator, produce a seed and
1168 1169 1170
	 * add it to the pool.  For the sake of paranoia don't let the
	 * architectural seed generator dominate the input from the
	 * interrupt noise.
1171 1172
	 */
	if (arch_get_random_seed_long(&seed)) {
1173
		__mix_pool_bytes(r, &seed, sizeof(seed));
1174
		credit = 1;
1175
	}
1176
	spin_unlock(&r->lock);
1177

1178
	fast_pool->count = 0;
1179

1180 1181
	/* award one bit for the contents of the fast pool */
	credit_entropy_bits(r, credit + 1);
L
Linus Torvalds 已提交
1182
}
1183
EXPORT_SYMBOL_GPL(add_interrupt_randomness);
L
Linus Torvalds 已提交
1184

1185
#ifdef CONFIG_BLOCK
L
Linus Torvalds 已提交
1186 1187 1188 1189 1190
void add_disk_randomness(struct gendisk *disk)
{
	if (!disk || !disk->random)
		return;
	/* first major is 1, so we get >= 0x200 here */
1191
	add_timer_randomness(disk->random, 0x100 + disk_devt(disk));
1192
	trace_add_disk_randomness(disk_devt(disk), ENTROPY_BITS(&input_pool));
L
Linus Torvalds 已提交
1193
}
1194
EXPORT_SYMBOL_GPL(add_disk_randomness);
1195
#endif
L
Linus Torvalds 已提交
1196 1197 1198 1199 1200 1201 1202 1203

/*********************************************************************
 *
 * Entropy extraction routines
 *
 *********************************************************************/

/*
L
Lucas De Marchi 已提交
1204
 * This utility inline function is responsible for transferring entropy
L
Linus Torvalds 已提交
1205 1206 1207
 * from the primary pool to the secondary extraction pool. We make
 * sure we pull enough for a 'catastrophic reseed'.
 */
1208
static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes);
L
Linus Torvalds 已提交
1209 1210
static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
{
1211 1212 1213 1214 1215 1216
	if (!r->pull ||
	    r->entropy_count >= (nbytes << (ENTROPY_SHIFT + 3)) ||
	    r->entropy_count > r->poolinfo->poolfracbits)
		return;

	_xfer_secondary_pool(r, nbytes);
1217 1218 1219 1220 1221 1222 1223 1224
}

static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
{
	__u32	tmp[OUTPUT_POOL_WORDS];

	int bytes = nbytes;

1225 1226
	/* pull at least as much as a wakeup */
	bytes = max_t(int, bytes, random_read_wakeup_bits / 8);
1227 1228 1229
	/* but never more than the buffer size */
	bytes = min_t(int, bytes, sizeof(tmp));

1230 1231
	trace_xfer_secondary_pool(r->name, bytes * 8, nbytes * 8,
				  ENTROPY_BITS(r), ENTROPY_BITS(r->pull));
1232
	bytes = extract_entropy(r->pull, tmp, bytes,
S
Stephan Müller 已提交
1233
				random_read_wakeup_bits / 8, 0);
1234
	mix_pool_bytes(r, tmp, bytes);
1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248
	credit_entropy_bits(r, bytes*8);
}

/*
 * Used as a workqueue function so that when the input pool is getting
 * full, we can "spill over" some entropy to the output pools.  That
 * way the output pools can store some of the excess entropy instead
 * of letting it go to waste.
 */
static void push_to_pool(struct work_struct *work)
{
	struct entropy_store *r = container_of(work, struct entropy_store,
					      push_work);
	BUG_ON(!r);
1249
	_xfer_secondary_pool(r, random_read_wakeup_bits/8);
1250 1251
	trace_push_to_pool(r->name, r->entropy_count >> ENTROPY_SHIFT,
			   r->pull->entropy_count >> ENTROPY_SHIFT);
L
Linus Torvalds 已提交
1252 1253 1254
}

/*
G
Greg Price 已提交
1255 1256
 * This function decides how many bytes to actually take from the
 * given pool, and also debits the entropy count accordingly.
L
Linus Torvalds 已提交
1257 1258 1259 1260
 */
static size_t account(struct entropy_store *r, size_t nbytes, int min,
		      int reserved)
{
S
Stephan Müller 已提交
1261
	int entropy_count, orig, have_bytes;
1262
	size_t ibytes, nfrac;
L
Linus Torvalds 已提交
1263

1264
	BUG_ON(r->entropy_count > r->poolinfo->poolfracbits);
L
Linus Torvalds 已提交
1265 1266

	/* Can we pull enough? */
1267
retry:
1268 1269
	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
	ibytes = nbytes;
S
Stephan Müller 已提交
1270 1271
	/* never pull more than available */
	have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
1272

S
Stephan Müller 已提交
1273 1274 1275
	if ((have_bytes -= reserved) < 0)
		have_bytes = 0;
	ibytes = min_t(size_t, ibytes, have_bytes);
G
Greg Price 已提交
1276
	if (ibytes < min)
1277
		ibytes = 0;
1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288

	if (unlikely(entropy_count < 0)) {
		pr_warn("random: negative entropy count: pool %s count %d\n",
			r->name, entropy_count);
		WARN_ON(1);
		entropy_count = 0;
	}
	nfrac = ibytes << (ENTROPY_SHIFT + 3);
	if ((size_t) entropy_count > nfrac)
		entropy_count -= nfrac;
	else
1289
		entropy_count = 0;
1290

G
Greg Price 已提交
1291 1292
	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
		goto retry;
L
Linus Torvalds 已提交
1293

1294
	trace_debit_entropy(r->name, 8 * ibytes);
G
Greg Price 已提交
1295
	if (ibytes &&
1296
	    (r->entropy_count >> ENTROPY_SHIFT) < random_write_wakeup_bits) {
1297 1298 1299 1300
		wake_up_interruptible(&random_write_wait);
		kill_fasync(&fasync, SIGIO, POLL_OUT);
	}

1301
	return ibytes;
L
Linus Torvalds 已提交
1302 1303
}

G
Greg Price 已提交
1304 1305 1306 1307 1308 1309
/*
 * This function does the actual extraction for extract_entropy and
 * extract_entropy_user.
 *
 * Note: we assume that .poolwords is a multiple of 16 words.
 */
L
Linus Torvalds 已提交
1310 1311
static void extract_buf(struct entropy_store *r, __u8 *out)
{
1312
	int i;
1313 1314
	union {
		__u32 w[5];
1315
		unsigned long l[LONGS(20)];
1316 1317
	} hash;
	__u32 workspace[SHA_WORKSPACE_WORDS];
1318
	unsigned long flags;
L
Linus Torvalds 已提交
1319

1320
	/*
1321
	 * If we have an architectural hardware random number
1322
	 * generator, use it for SHA's initial vector
1323
	 */
1324
	sha_init(hash.w);
1325 1326 1327 1328
	for (i = 0; i < LONGS(20); i++) {
		unsigned long v;
		if (!arch_get_random_long(&v))
			break;
1329
		hash.l[i] = v;
1330 1331
	}

1332 1333 1334 1335 1336
	/* Generate a hash across the pool, 16 words (512 bits) at a time */
	spin_lock_irqsave(&r->lock, flags);
	for (i = 0; i < r->poolinfo->poolwords; i += 16)
		sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);

L
Linus Torvalds 已提交
1337
	/*
1338 1339 1340 1341 1342 1343 1344
	 * We mix the hash back into the pool to prevent backtracking
	 * attacks (where the attacker knows the state of the pool
	 * plus the current outputs, and attempts to find previous
	 * ouputs), unless the hash function can be inverted. By
	 * mixing at least a SHA1 worth of hash data back, we make
	 * brute-forcing the feedback as hard as brute-forcing the
	 * hash.
L
Linus Torvalds 已提交
1345
	 */
1346
	__mix_pool_bytes(r, hash.w, sizeof(hash.w));
1347
	spin_unlock_irqrestore(&r->lock, flags);
L
Linus Torvalds 已提交
1348

1349
	memzero_explicit(workspace, sizeof(workspace));
L
Linus Torvalds 已提交
1350 1351

	/*
1352 1353 1354
	 * In case the hash function has some recognizable output
	 * pattern, we fold it in half. Thus, we always feed back
	 * twice as much data as we output.
L
Linus Torvalds 已提交
1355
	 */
1356 1357 1358 1359 1360
	hash.w[0] ^= hash.w[3];
	hash.w[1] ^= hash.w[4];
	hash.w[2] ^= rol32(hash.w[2], 16);

	memcpy(out, &hash, EXTRACT_SIZE);
1361
	memzero_explicit(&hash, sizeof(hash));
L
Linus Torvalds 已提交
1362 1363
}

1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393
static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
				size_t nbytes, int fips)
{
	ssize_t ret = 0, i;
	__u8 tmp[EXTRACT_SIZE];
	unsigned long flags;

	while (nbytes) {
		extract_buf(r, tmp);

		if (fips) {
			spin_lock_irqsave(&r->lock, flags);
			if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
				panic("Hardware RNG duplicated output!\n");
			memcpy(r->last_data, tmp, EXTRACT_SIZE);
			spin_unlock_irqrestore(&r->lock, flags);
		}
		i = min_t(int, nbytes, EXTRACT_SIZE);
		memcpy(buf, tmp, i);
		nbytes -= i;
		buf += i;
		ret += i;
	}

	/* Wipe data just returned from memory */
	memzero_explicit(tmp, sizeof(tmp));

	return ret;
}

G
Greg Price 已提交
1394 1395 1396 1397 1398 1399 1400 1401 1402
/*
 * This function extracts randomness from the "entropy pool", and
 * returns it in a buffer.
 *
 * The min parameter specifies the minimum amount we can pull before
 * failing to avoid races that defeat catastrophic reseeding while the
 * reserved parameter indicates how much entropy we must leave in the
 * pool after each pull to avoid starving other readers.
 */
1403
static ssize_t extract_entropy(struct entropy_store *r, void *buf,
1404
				 size_t nbytes, int min, int reserved)
L
Linus Torvalds 已提交
1405 1406
{
	__u8 tmp[EXTRACT_SIZE];
1407
	unsigned long flags;
L
Linus Torvalds 已提交
1408

1409
	/* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */
1410 1411 1412
	if (fips_enabled) {
		spin_lock_irqsave(&r->lock, flags);
		if (!r->last_data_init) {
1413
			r->last_data_init = 1;
1414 1415
			spin_unlock_irqrestore(&r->lock, flags);
			trace_extract_entropy(r->name, EXTRACT_SIZE,
1416
					      ENTROPY_BITS(r), _RET_IP_);
1417 1418 1419 1420 1421 1422 1423
			xfer_secondary_pool(r, EXTRACT_SIZE);
			extract_buf(r, tmp);
			spin_lock_irqsave(&r->lock, flags);
			memcpy(r->last_data, tmp, EXTRACT_SIZE);
		}
		spin_unlock_irqrestore(&r->lock, flags);
	}
1424

1425
	trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
L
Linus Torvalds 已提交
1426 1427 1428
	xfer_secondary_pool(r, nbytes);
	nbytes = account(r, nbytes, min, reserved);

1429
	return _extract_entropy(r, buf, nbytes, fips_enabled);
L
Linus Torvalds 已提交
1430 1431
}

G
Greg Price 已提交
1432 1433 1434 1435
/*
 * This function extracts randomness from the "entropy pool", and
 * returns it in a userspace buffer.
 */
L
Linus Torvalds 已提交
1436 1437 1438 1439 1440
static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
				    size_t nbytes)
{
	ssize_t ret = 0, i;
	__u8 tmp[EXTRACT_SIZE];
1441
	int large_request = (nbytes > 256);
L
Linus Torvalds 已提交
1442

1443
	trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
L
Linus Torvalds 已提交
1444 1445 1446 1447
	xfer_secondary_pool(r, nbytes);
	nbytes = account(r, nbytes, 0, 0);

	while (nbytes) {
1448
		if (large_request && need_resched()) {
L
Linus Torvalds 已提交
1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469
			if (signal_pending(current)) {
				if (ret == 0)
					ret = -ERESTARTSYS;
				break;
			}
			schedule();
		}

		extract_buf(r, tmp);
		i = min_t(int, nbytes, EXTRACT_SIZE);
		if (copy_to_user(buf, tmp, i)) {
			ret = -EFAULT;
			break;
		}

		nbytes -= i;
		buf += i;
		ret += i;
	}

	/* Wipe data just returned from memory */
1470
	memzero_explicit(tmp, sizeof(tmp));
L
Linus Torvalds 已提交
1471 1472 1473 1474

	return ret;
}

1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494
#define warn_unseeded_randomness(previous) \
	_warn_unseeded_randomness(__func__, (void *) _RET_IP_, (previous))

static void _warn_unseeded_randomness(const char *func_name, void *caller,
				      void **previous)
{
#ifdef CONFIG_WARN_ALL_UNSEEDED_RANDOM
	const bool print_once = false;
#else
	static bool print_once __read_mostly;
#endif

	if (print_once ||
	    crng_ready() ||
	    (previous && (caller == READ_ONCE(*previous))))
		return;
	WRITE_ONCE(*previous, caller);
#ifndef CONFIG_WARN_ALL_UNSEEDED_RANDOM
	print_once = true;
#endif
1495
	pr_notice("random: %s called from %pS with crng_init=%d\n",
1496 1497 1498
		  func_name, caller, crng_init);
}

L
Linus Torvalds 已提交
1499 1500
/*
 * This function is the exported kernel interface.  It returns some
1501
 * number of good random numbers, suitable for key generation, seeding
1502 1503
 * TCP sequence numbers, etc.  It does not rely on the hardware random
 * number generator.  For random bytes direct from the hardware RNG
1504 1505 1506 1507
 * (when available), use get_random_bytes_arch(). 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.
L
Linus Torvalds 已提交
1508
 */
1509
static void _get_random_bytes(void *buf, int nbytes)
1510
{
1511 1512
	__u8 tmp[CHACHA20_BLOCK_SIZE];

1513
	trace_get_random_bytes(nbytes, _RET_IP_);
1514 1515 1516 1517 1518 1519 1520 1521 1522 1523

	while (nbytes >= CHACHA20_BLOCK_SIZE) {
		extract_crng(buf);
		buf += CHACHA20_BLOCK_SIZE;
		nbytes -= CHACHA20_BLOCK_SIZE;
	}

	if (nbytes > 0) {
		extract_crng(tmp);
		memcpy(buf, tmp, nbytes);
1524 1525 1526 1527
		crng_backtrack_protect(tmp, nbytes);
	} else
		crng_backtrack_protect(tmp, CHACHA20_BLOCK_SIZE);
	memzero_explicit(tmp, sizeof(tmp));
1528
}
1529 1530 1531 1532 1533 1534 1535 1536

void get_random_bytes(void *buf, int nbytes)
{
	static void *previous;

	warn_unseeded_randomness(&previous);
	_get_random_bytes(buf, nbytes);
}
1537 1538
EXPORT_SYMBOL(get_random_bytes);

1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556
/*
 * Wait for the urandom pool to be seeded and thus guaranteed 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. Using any of these functions without first calling
 * this function forfeits the guarantee of security.
 *
 * Returns: 0 if the urandom pool has been seeded.
 *          -ERESTARTSYS if the function was interrupted by a signal.
 */
int wait_for_random_bytes(void)
{
	if (likely(crng_ready()))
		return 0;
	return wait_event_interruptible(crng_init_wait, crng_ready());
}
EXPORT_SYMBOL(wait_for_random_bytes);

1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570
/*
 * Add a callback function that will be invoked when the nonblocking
 * pool is initialised.
 *
 * returns: 0 if callback is successfully added
 *	    -EALREADY if pool is already initialised (callback not called)
 *	    -ENOENT if module for callback is not alive
 */
int add_random_ready_callback(struct random_ready_callback *rdy)
{
	struct module *owner;
	unsigned long flags;
	int err = -EALREADY;

1571
	if (crng_ready())
1572 1573 1574 1575 1576 1577 1578
		return err;

	owner = rdy->owner;
	if (!try_module_get(owner))
		return -ENOENT;

	spin_lock_irqsave(&random_ready_list_lock, flags);
1579
	if (crng_ready())
1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614
		goto out;

	owner = NULL;

	list_add(&rdy->list, &random_ready_list);
	err = 0;

out:
	spin_unlock_irqrestore(&random_ready_list_lock, flags);

	module_put(owner);

	return err;
}
EXPORT_SYMBOL(add_random_ready_callback);

/*
 * Delete a previously registered readiness callback function.
 */
void del_random_ready_callback(struct random_ready_callback *rdy)
{
	unsigned long flags;
	struct module *owner = NULL;

	spin_lock_irqsave(&random_ready_list_lock, flags);
	if (!list_empty(&rdy->list)) {
		list_del_init(&rdy->list);
		owner = rdy->owner;
	}
	spin_unlock_irqrestore(&random_ready_list_lock, flags);

	module_put(owner);
}
EXPORT_SYMBOL(del_random_ready_callback);

1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625
/*
 * This function will use the architecture-specific hardware random
 * number generator if it is available.  The arch-specific hw RNG will
 * almost certainly be faster than what we can do in software, but it
 * is impossible to verify that it is implemented securely (as
 * opposed, to, say, the AES encryption of a sequence number using a
 * key known by the NSA).  So it's useful if we need the speed, but
 * only if we're willing to trust the hardware manufacturer not to
 * have put in a back door.
 */
void get_random_bytes_arch(void *buf, int nbytes)
L
Linus Torvalds 已提交
1626
{
1627 1628
	char *p = buf;

1629
	trace_get_random_bytes_arch(nbytes, _RET_IP_);
1630 1631 1632
	while (nbytes) {
		unsigned long v;
		int chunk = min(nbytes, (int)sizeof(unsigned long));
1633

1634 1635 1636
		if (!arch_get_random_long(&v))
			break;
		
L
Luck, Tony 已提交
1637
		memcpy(p, &v, chunk);
1638 1639 1640 1641
		p += chunk;
		nbytes -= chunk;
	}

1642
	if (nbytes)
1643
		get_random_bytes(p, nbytes);
L
Linus Torvalds 已提交
1644
}
1645 1646
EXPORT_SYMBOL(get_random_bytes_arch);

L
Linus Torvalds 已提交
1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658

/*
 * init_std_data - initialize pool with system data
 *
 * @r: pool to initialize
 *
 * This function clears the pool's entropy count and mixes some system
 * data into the pool to prepare it for use. The pool is not cleared
 * as that can only decrease the entropy in the pool.
 */
static void init_std_data(struct entropy_store *r)
{
1659
	int i;
1660 1661
	ktime_t now = ktime_get_real();
	unsigned long rv;
L
Linus Torvalds 已提交
1662

1663
	r->last_pulled = jiffies;
1664
	mix_pool_bytes(r, &now, sizeof(now));
1665
	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
1666 1667
		if (!arch_get_random_seed_long(&rv) &&
		    !arch_get_random_long(&rv))
1668
			rv = random_get_entropy();
1669
		mix_pool_bytes(r, &rv, sizeof(rv));
1670
	}
1671
	mix_pool_bytes(r, utsname(), sizeof(*(utsname())));
L
Linus Torvalds 已提交
1672 1673
}

1674 1675 1676 1677 1678 1679 1680 1681 1682 1683
/*
 * Note that setup_arch() may call add_device_randomness()
 * long before we get here. This allows seeding of the pools
 * with some platform dependent data very early in the boot
 * process. But it limits our options here. We must use
 * statically allocated structures that already have all
 * initializations complete at compile time. We should also
 * take care not to overwrite the precious per platform data
 * we were given.
 */
M
Matt Mackall 已提交
1684
static int rand_initialize(void)
L
Linus Torvalds 已提交
1685
{
1686 1687 1688 1689 1690 1691
#ifdef CONFIG_NUMA
	int i;
	struct crng_state *crng;
	struct crng_state **pool;
#endif

L
Linus Torvalds 已提交
1692 1693
	init_std_data(&input_pool);
	init_std_data(&blocking_pool);
1694
	crng_initialize(&primary_crng);
1695 1696

#ifdef CONFIG_NUMA
1697
	pool = kcalloc(nr_node_ids, sizeof(*pool), GFP_KERNEL|__GFP_NOFAIL);
1698
	for_each_online_node(i) {
1699 1700 1701 1702 1703 1704 1705 1706 1707
		crng = kmalloc_node(sizeof(struct crng_state),
				    GFP_KERNEL | __GFP_NOFAIL, i);
		spin_lock_init(&crng->lock);
		crng_initialize(crng);
		pool[i] = crng;
	}
	mb();
	crng_node_pool = pool;
#endif
L
Linus Torvalds 已提交
1708 1709
	return 0;
}
1710
early_initcall(rand_initialize);
L
Linus Torvalds 已提交
1711

1712
#ifdef CONFIG_BLOCK
L
Linus Torvalds 已提交
1713 1714 1715 1716 1717
void rand_initialize_disk(struct gendisk *disk)
{
	struct timer_rand_state *state;

	/*
1718
	 * If kzalloc returns null, we just won't use that entropy
L
Linus Torvalds 已提交
1719 1720
	 * source.
	 */
1721
	state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
1722 1723
	if (state) {
		state->last_time = INITIAL_JIFFIES;
L
Linus Torvalds 已提交
1724
		disk->random = state;
1725
	}
L
Linus Torvalds 已提交
1726
}
1727
#endif
L
Linus Torvalds 已提交
1728 1729

static ssize_t
1730
_random_read(int nonblock, char __user *buf, size_t nbytes)
L
Linus Torvalds 已提交
1731
{
1732
	ssize_t n;
L
Linus Torvalds 已提交
1733 1734 1735 1736

	if (nbytes == 0)
		return 0;

1737 1738 1739 1740 1741
	nbytes = min_t(size_t, nbytes, SEC_XFER_SIZE);
	while (1) {
		n = extract_entropy_user(&blocking_pool, buf, nbytes);
		if (n < 0)
			return n;
1742 1743 1744
		trace_random_read(n*8, (nbytes-n)*8,
				  ENTROPY_BITS(&blocking_pool),
				  ENTROPY_BITS(&input_pool));
1745 1746
		if (n > 0)
			return n;
1747

1748
		/* Pool is (near) empty.  Maybe wait and retry. */
1749
		if (nonblock)
1750 1751 1752 1753
			return -EAGAIN;

		wait_event_interruptible(random_read_wait,
			ENTROPY_BITS(&input_pool) >=
1754
			random_read_wakeup_bits);
1755 1756
		if (signal_pending(current))
			return -ERESTARTSYS;
L
Linus Torvalds 已提交
1757 1758 1759
	}
}

1760 1761 1762 1763 1764 1765
static ssize_t
random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
{
	return _random_read(file->f_flags & O_NONBLOCK, buf, nbytes);
}

L
Linus Torvalds 已提交
1766
static ssize_t
1767
urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
L
Linus Torvalds 已提交
1768
{
1769
	unsigned long flags;
1770
	static int maxwarn = 10;
1771 1772
	int ret;

1773
	if (!crng_ready() && maxwarn > 0) {
1774 1775
		maxwarn--;
		printk(KERN_NOTICE "random: %s: uninitialized urandom read "
1776 1777 1778 1779 1780
		       "(%zd bytes read)\n",
		       current->comm, nbytes);
		spin_lock_irqsave(&primary_crng.lock, flags);
		crng_init_cnt = 0;
		spin_unlock_irqrestore(&primary_crng.lock, flags);
1781
	}
1782
	nbytes = min_t(size_t, nbytes, INT_MAX >> (ENTROPY_SHIFT + 3));
1783 1784
	ret = extract_crng_user(buf, nbytes);
	trace_urandom_read(8 * nbytes, 0, ENTROPY_BITS(&input_pool));
1785
	return ret;
L
Linus Torvalds 已提交
1786 1787 1788 1789 1790 1791 1792 1793 1794 1795
}

static unsigned int
random_poll(struct file *file, poll_table * wait)
{
	unsigned int mask;

	poll_wait(file, &random_read_wait, wait);
	poll_wait(file, &random_write_wait, wait);
	mask = 0;
1796
	if (ENTROPY_BITS(&input_pool) >= random_read_wakeup_bits)
L
Linus Torvalds 已提交
1797
		mask |= POLLIN | POLLRDNORM;
1798
	if (ENTROPY_BITS(&input_pool) < random_write_wakeup_bits)
L
Linus Torvalds 已提交
1799 1800 1801 1802
		mask |= POLLOUT | POLLWRNORM;
	return mask;
}

1803 1804
static int
write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
L
Linus Torvalds 已提交
1805 1806 1807 1808 1809
{
	size_t bytes;
	__u32 buf[16];
	const char __user *p = buffer;

1810 1811 1812 1813
	while (count > 0) {
		bytes = min(count, sizeof(buf));
		if (copy_from_user(&buf, p, bytes))
			return -EFAULT;
L
Linus Torvalds 已提交
1814

1815
		count -= bytes;
L
Linus Torvalds 已提交
1816 1817
		p += bytes;

1818
		mix_pool_bytes(r, buf, bytes);
1819
		cond_resched();
L
Linus Torvalds 已提交
1820
	}
1821 1822 1823 1824

	return 0;
}

1825 1826
static ssize_t random_write(struct file *file, const char __user *buffer,
			    size_t count, loff_t *ppos)
1827 1828 1829
{
	size_t ret;

1830
	ret = write_pool(&input_pool, buffer, count);
1831 1832 1833 1834
	if (ret)
		return ret;

	return (ssize_t)count;
L
Linus Torvalds 已提交
1835 1836
}

M
Matt Mackall 已提交
1837
static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
L
Linus Torvalds 已提交
1838 1839 1840 1841 1842 1843 1844
{
	int size, ent_count;
	int __user *p = (int __user *)arg;
	int retval;

	switch (cmd) {
	case RNDGETENTCNT:
M
Matt Mackall 已提交
1845
		/* inherently racy, no point locking */
1846 1847
		ent_count = ENTROPY_BITS(&input_pool);
		if (put_user(ent_count, p))
L
Linus Torvalds 已提交
1848 1849 1850 1851 1852 1853 1854
			return -EFAULT;
		return 0;
	case RNDADDTOENTCNT:
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
		if (get_user(ent_count, p))
			return -EFAULT;
1855
		return credit_entropy_bits_safe(&input_pool, ent_count);
L
Linus Torvalds 已提交
1856 1857 1858 1859 1860 1861 1862 1863 1864
	case RNDADDENTROPY:
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
		if (get_user(ent_count, p++))
			return -EFAULT;
		if (ent_count < 0)
			return -EINVAL;
		if (get_user(size, p++))
			return -EFAULT;
1865 1866
		retval = write_pool(&input_pool, (const char __user *)p,
				    size);
L
Linus Torvalds 已提交
1867 1868
		if (retval < 0)
			return retval;
1869
		return credit_entropy_bits_safe(&input_pool, ent_count);
L
Linus Torvalds 已提交
1870 1871
	case RNDZAPENTCNT:
	case RNDCLEARPOOL:
1872 1873 1874 1875
		/*
		 * Clear the entropy pool counters. We no longer clear
		 * the entropy pool, as that's silly.
		 */
L
Linus Torvalds 已提交
1876 1877
		if (!capable(CAP_SYS_ADMIN))
			return -EPERM;
1878 1879
		input_pool.entropy_count = 0;
		blocking_pool.entropy_count = 0;
L
Linus Torvalds 已提交
1880 1881 1882 1883 1884 1885
		return 0;
	default:
		return -EINVAL;
	}
}

1886 1887 1888 1889 1890
static int random_fasync(int fd, struct file *filp, int on)
{
	return fasync_helper(fd, filp, on, &fasync);
}

1891
const struct file_operations random_fops = {
L
Linus Torvalds 已提交
1892 1893 1894
	.read  = random_read,
	.write = random_write,
	.poll  = random_poll,
M
Matt Mackall 已提交
1895
	.unlocked_ioctl = random_ioctl,
1896
	.fasync = random_fasync,
1897
	.llseek = noop_llseek,
L
Linus Torvalds 已提交
1898 1899
};

1900
const struct file_operations urandom_fops = {
L
Linus Torvalds 已提交
1901 1902
	.read  = urandom_read,
	.write = random_write,
M
Matt Mackall 已提交
1903
	.unlocked_ioctl = random_ioctl,
1904
	.fasync = random_fasync,
1905
	.llseek = noop_llseek,
L
Linus Torvalds 已提交
1906 1907
};

1908 1909 1910
SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
		unsigned int, flags)
{
1911 1912
	int ret;

1913 1914 1915 1916 1917 1918 1919 1920 1921
	if (flags & ~(GRND_NONBLOCK|GRND_RANDOM))
		return -EINVAL;

	if (count > INT_MAX)
		count = INT_MAX;

	if (flags & GRND_RANDOM)
		return _random_read(flags & GRND_NONBLOCK, buf, count);

1922
	if (!crng_ready()) {
1923 1924
		if (flags & GRND_NONBLOCK)
			return -EAGAIN;
1925 1926 1927
		ret = wait_for_random_bytes();
		if (unlikely(ret))
			return ret;
1928 1929 1930 1931
	}
	return urandom_read(NULL, buf, count, NULL);
}

L
Linus Torvalds 已提交
1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942
/********************************************************************
 *
 * Sysctl interface
 *
 ********************************************************************/

#ifdef CONFIG_SYSCTL

#include <linux/sysctl.h>

static int min_read_thresh = 8, min_write_thresh;
1943
static int max_read_thresh = OUTPUT_POOL_WORDS * 32;
L
Linus Torvalds 已提交
1944
static int max_write_thresh = INPUT_POOL_WORDS * 32;
1945
static int random_min_urandom_seed = 60;
L
Linus Torvalds 已提交
1946 1947 1948
static char sysctl_bootid[16];

/*
G
Greg Price 已提交
1949
 * This function is used to return both the bootid UUID, and random
L
Linus Torvalds 已提交
1950 1951 1952
 * UUID.  The difference is in whether table->data is NULL; if it is,
 * then a new UUID is generated and returned to the user.
 *
G
Greg Price 已提交
1953 1954 1955
 * If the user accesses this via the proc interface, the UUID will be
 * returned as an ASCII string in the standard UUID format; if via the
 * sysctl system call, as 16 bytes of binary data.
L
Linus Torvalds 已提交
1956
 */
1957
static int proc_do_uuid(struct ctl_table *table, int write,
L
Linus Torvalds 已提交
1958 1959
			void __user *buffer, size_t *lenp, loff_t *ppos)
{
1960
	struct ctl_table fake_table;
L
Linus Torvalds 已提交
1961 1962 1963 1964 1965 1966
	unsigned char buf[64], tmp_uuid[16], *uuid;

	uuid = table->data;
	if (!uuid) {
		uuid = tmp_uuid;
		generate_random_uuid(uuid);
1967 1968 1969 1970 1971 1972 1973 1974
	} else {
		static DEFINE_SPINLOCK(bootid_spinlock);

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

J
Joe Perches 已提交
1976 1977
	sprintf(buf, "%pU", uuid);

L
Linus Torvalds 已提交
1978 1979 1980
	fake_table.data = buf;
	fake_table.maxlen = sizeof(buf);

1981
	return proc_dostring(&fake_table, write, buffer, lenp, ppos);
L
Linus Torvalds 已提交
1982 1983
}

1984 1985 1986
/*
 * Return entropy available scaled to integral bits
 */
1987
static int proc_do_entropy(struct ctl_table *table, int write,
1988 1989
			   void __user *buffer, size_t *lenp, loff_t *ppos)
{
1990
	struct ctl_table fake_table;
1991 1992 1993 1994 1995 1996 1997 1998 1999 2000
	int entropy_count;

	entropy_count = *(int *)table->data >> ENTROPY_SHIFT;

	fake_table.data = &entropy_count;
	fake_table.maxlen = sizeof(entropy_count);

	return proc_dointvec(&fake_table, write, buffer, lenp, ppos);
}

L
Linus Torvalds 已提交
2001
static int sysctl_poolsize = INPUT_POOL_WORDS * 32;
2002 2003
extern struct ctl_table random_table[];
struct ctl_table random_table[] = {
L
Linus Torvalds 已提交
2004 2005 2006 2007 2008
	{
		.procname	= "poolsize",
		.data		= &sysctl_poolsize,
		.maxlen		= sizeof(int),
		.mode		= 0444,
2009
		.proc_handler	= proc_dointvec,
L
Linus Torvalds 已提交
2010 2011 2012 2013 2014
	},
	{
		.procname	= "entropy_avail",
		.maxlen		= sizeof(int),
		.mode		= 0444,
2015
		.proc_handler	= proc_do_entropy,
L
Linus Torvalds 已提交
2016 2017 2018 2019
		.data		= &input_pool.entropy_count,
	},
	{
		.procname	= "read_wakeup_threshold",
2020
		.data		= &random_read_wakeup_bits,
L
Linus Torvalds 已提交
2021 2022
		.maxlen		= sizeof(int),
		.mode		= 0644,
2023
		.proc_handler	= proc_dointvec_minmax,
L
Linus Torvalds 已提交
2024 2025 2026 2027 2028
		.extra1		= &min_read_thresh,
		.extra2		= &max_read_thresh,
	},
	{
		.procname	= "write_wakeup_threshold",
2029
		.data		= &random_write_wakeup_bits,
L
Linus Torvalds 已提交
2030 2031
		.maxlen		= sizeof(int),
		.mode		= 0644,
2032
		.proc_handler	= proc_dointvec_minmax,
L
Linus Torvalds 已提交
2033 2034 2035
		.extra1		= &min_write_thresh,
		.extra2		= &max_write_thresh,
	},
2036 2037 2038 2039 2040 2041 2042
	{
		.procname	= "urandom_min_reseed_secs",
		.data		= &random_min_urandom_seed,
		.maxlen		= sizeof(int),
		.mode		= 0644,
		.proc_handler	= proc_dointvec,
	},
L
Linus Torvalds 已提交
2043 2044 2045 2046 2047
	{
		.procname	= "boot_id",
		.data		= &sysctl_bootid,
		.maxlen		= 16,
		.mode		= 0444,
2048
		.proc_handler	= proc_do_uuid,
L
Linus Torvalds 已提交
2049 2050 2051 2052 2053
	},
	{
		.procname	= "uuid",
		.maxlen		= 16,
		.mode		= 0444,
2054
		.proc_handler	= proc_do_uuid,
L
Linus Torvalds 已提交
2055
	},
2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071
#ifdef ADD_INTERRUPT_BENCH
	{
		.procname	= "add_interrupt_avg_cycles",
		.data		= &avg_cycles,
		.maxlen		= sizeof(avg_cycles),
		.mode		= 0444,
		.proc_handler	= proc_doulongvec_minmax,
	},
	{
		.procname	= "add_interrupt_avg_deviation",
		.data		= &avg_deviation,
		.maxlen		= sizeof(avg_deviation),
		.mode		= 0444,
		.proc_handler	= proc_doulongvec_minmax,
	},
#endif
2072
	{ }
L
Linus Torvalds 已提交
2073 2074 2075
};
#endif 	/* CONFIG_SYSCTL */

2076 2077
struct batched_entropy {
	union {
2078 2079
		u64 entropy_u64[CHACHA20_BLOCK_SIZE / sizeof(u64)];
		u32 entropy_u32[CHACHA20_BLOCK_SIZE / sizeof(u32)];
2080 2081 2082
	};
	unsigned int position;
};
2083
static rwlock_t batched_entropy_reset_lock = __RW_LOCK_UNLOCKED(batched_entropy_reset_lock);
2084

L
Linus Torvalds 已提交
2085
/*
2086 2087
 * Get a random word for internal kernel use only. The quality of the random
 * number is either as good as RDRAND or as good as /dev/urandom, with the
2088 2089 2090 2091
 * goal of being quite fast and not depleting entropy. 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.
L
Linus Torvalds 已提交
2092
 */
2093 2094
static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u64);
u64 get_random_u64(void)
L
Linus Torvalds 已提交
2095
{
2096
	u64 ret;
2097
	bool use_lock;
2098
	unsigned long flags = 0;
2099
	struct batched_entropy *batch;
2100
	static void *previous;
2101

2102 2103
#if BITS_PER_LONG == 64
	if (arch_get_random_long((unsigned long *)&ret))
2104
		return ret;
2105 2106 2107 2108 2109
#else
	if (arch_get_random_long((unsigned long *)&ret) &&
	    arch_get_random_long((unsigned long *)&ret + 1))
	    return ret;
#endif
2110

2111
	warn_unseeded_randomness(&previous);
2112

2113
	use_lock = READ_ONCE(crng_init) < 2;
2114
	batch = &get_cpu_var(batched_entropy_u64);
2115 2116
	if (use_lock)
		read_lock_irqsave(&batched_entropy_reset_lock, flags);
2117 2118
	if (batch->position % ARRAY_SIZE(batch->entropy_u64) == 0) {
		extract_crng((u8 *)batch->entropy_u64);
2119 2120
		batch->position = 0;
	}
2121
	ret = batch->entropy_u64[batch->position++];
2122 2123
	if (use_lock)
		read_unlock_irqrestore(&batched_entropy_reset_lock, flags);
2124
	put_cpu_var(batched_entropy_u64);
2125
	return ret;
L
Linus Torvalds 已提交
2126
}
2127
EXPORT_SYMBOL(get_random_u64);
L
Linus Torvalds 已提交
2128

2129 2130
static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u32);
u32 get_random_u32(void)
2131
{
2132
	u32 ret;
2133
	bool use_lock;
2134
	unsigned long flags = 0;
2135
	struct batched_entropy *batch;
2136
	static void *previous;
2137

2138
	if (arch_get_random_int(&ret))
2139 2140
		return ret;

2141
	warn_unseeded_randomness(&previous);
2142

2143
	use_lock = READ_ONCE(crng_init) < 2;
2144
	batch = &get_cpu_var(batched_entropy_u32);
2145 2146
	if (use_lock)
		read_lock_irqsave(&batched_entropy_reset_lock, flags);
2147 2148
	if (batch->position % ARRAY_SIZE(batch->entropy_u32) == 0) {
		extract_crng((u8 *)batch->entropy_u32);
2149 2150
		batch->position = 0;
	}
2151
	ret = batch->entropy_u32[batch->position++];
2152 2153
	if (use_lock)
		read_unlock_irqrestore(&batched_entropy_reset_lock, flags);
2154
	put_cpu_var(batched_entropy_u32);
2155 2156
	return ret;
}
2157
EXPORT_SYMBOL(get_random_u32);
2158

2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175
/* It's important to invalidate all potential batched entropy that might
 * be stored before the crng is initialized, which we can do lazily by
 * simply resetting the counter to zero so that it's re-extracted on the
 * next usage. */
static void invalidate_batched_entropy(void)
{
	int cpu;
	unsigned long flags;

	write_lock_irqsave(&batched_entropy_reset_lock, flags);
	for_each_possible_cpu (cpu) {
		per_cpu_ptr(&batched_entropy_u32, cpu)->position = 0;
		per_cpu_ptr(&batched_entropy_u64, cpu)->position = 0;
	}
	write_unlock_irqrestore(&batched_entropy_reset_lock, flags);
}

2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208
/**
 * randomize_page - Generate a random, page aligned address
 * @start:	The smallest acceptable address the caller will take.
 * @range:	The size of the area, starting at @start, within which the
 *		random address must fall.
 *
 * If @start + @range would overflow, @range is capped.
 *
 * NOTE: Historical use of randomize_range, which this replaces, presumed that
 * @start was already page aligned.  We now align it regardless.
 *
 * Return: A page aligned address within [start, start + range).  On error,
 * @start is returned.
 */
unsigned long
randomize_page(unsigned long start, unsigned long range)
{
	if (!PAGE_ALIGNED(start)) {
		range -= PAGE_ALIGN(start) - start;
		start = PAGE_ALIGN(start);
	}

	if (start > ULONG_MAX - range)
		range = ULONG_MAX - start;

	range >>= PAGE_SHIFT;

	if (range == 0)
		return start;

	return start + (get_random_long() % range << PAGE_SHIFT);
}

2209 2210 2211 2212 2213 2214 2215 2216 2217
/* 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.
 */
void add_hwgenerator_randomness(const char *buffer, size_t count,
				size_t entropy)
{
	struct entropy_store *poolp = &input_pool;

2218 2219 2220
	if (!crng_ready()) {
		crng_fast_load(buffer, count);
		return;
2221
	}
2222 2223 2224 2225 2226 2227 2228

	/* Suspend writing if we're above the trickle threshold.
	 * We'll be woken up again once below random_write_wakeup_thresh,
	 * or when the calling thread is about to terminate.
	 */
	wait_event_interruptible(random_write_wait, kthread_should_stop() ||
			ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits);
2229 2230 2231 2232
	mix_pool_bytes(poolp, buffer, count);
	credit_entropy_bits(poolp, entropy);
}
EXPORT_SYMBOL_GPL(add_hwgenerator_randomness);