/* * random.c -- A strong random number generator * * Copyright (C) 2017 Jason A. Donenfeld <Jason@zx2c4.com>. All * Rights Reserved. * * Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005 * * 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 four exported interfaces; two for use within the kernel, * and two or use from userspace. * * Exported interfaces ---- userspace output * ----------------------------------------- * * The userspace 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 ---- kernel output * -------------------------------------- * * The primary kernel interface is * * 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. This is equivalent to a * read from /dev/urandom. * * For less critical applications, there are the functions: * * u32 get_random_u32() * u64 get_random_u64() * unsigned int get_random_int() * unsigned long get_random_long() * * These are produced by a cryptographic RNG seeded from get_random_bytes, * and so do not deplete the entropy pool as much. These are recommended * for most in-kernel operations *if the result is going to be stored in * the kernel*. * * Specifically, the get_random_int() family do not attempt to do * "anti-backtracking". If you capture the state of the kernel (e.g. * by snapshotting the VM), you can figure out previous get_random_int() * return values. But if the value is stored in the kernel anyway, * this is not a problem. * * It *is* safe to expose get_random_int() output to attackers (e.g. as * network cookies); given outputs 1..n, it's not feasible to predict * outputs 0 or n+1. The only concern is an attacker who breaks into * the kernel later; the get_random_int() engine is not reseeded as * often as the get_random_bytes() one. * * get_random_bytes() is needed for keys that need to stay secret after * they are erased from the kernel. For example, any key that will * be wrapped and stored encrypted. And session encryption keys: we'd * like to know that after the session is closed and the keys erased, * the plaintext is unrecoverable to someone who recorded the ciphertext. * * But for network ports/cookies, stack canaries, PRNG seeds, address * space layout randomization, session *authentication* keys, or other * applications where the sensitive data is stored in the kernel in * plaintext for as long as it's sensitive, the get_random_int() family * is just fine. * * Consider ASLR. We want to keep the address space secret from an * outside attacker while the process is running, but once the address * space is torn down, it's of no use to an attacker any more. And it's * stored in kernel data structures as long as it's alive, so worrying * about an attacker's ability to extrapolate it from the get_random_int() * CRNG is silly. * * Even some cryptographic keys are safe to generate with get_random_int(). * In particular, keys for SipHash are generally fine. Here, knowledge * of the key authorizes you to do something to a kernel object (inject * packets to a network connection, or flood a hash table), and the * key is stored with the object being protected. Once it goes away, * we no longer care if anyone knows the key. * * prandom_u32() * ------------- * * For even weaker applications, see the pseudorandom generator * prandom_u32(), prandom_max(), and prandom_bytes(). If the random * numbers aren't security-critical at all, these are *far* cheaper. * Useful for self-tests, random error simulation, randomized backoffs, * and any other application where you trust that nobody is trying to * maliciously mess with you by guessing the "random" numbers. * * Exported interfaces ---- input * ============================== * * The current exported interfaces for gathering environmental noise * from the devices are: * * void add_device_randomness(const void *buf, unsigned int size); * void add_input_randomness(unsigned int type, unsigned int code, * unsigned int value); * void add_interrupt_randomness(int irq, int irq_flags); * void add_disk_randomness(struct gendisk *disk); * * 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). * * add_input_randomness() uses the input layer interrupt timing, as well as * the event type information from the hardware. * * 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. * * 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. * * 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. */ #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt #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>#include <linux/mm.h>#include <linux/nodemask.h>#include <linux/spinlock.h>#include <linux/kthread.h>#include <linux/percpu.h>#include <linux/fips.h>#include <linux/ptrace.h>#include <linux/workqueue.h>#include <linux/irq.h>#include <linux/ratelimit.h>#include <linux/syscalls.h>#include <linux/completion.h>#include <linux/uuid.h>#include <crypto/chacha.h>#include <crypto/sha1.h> #include <asm/processor.h>#include <linux/uaccess.h>#include <asm/irq.h>#include <asm/irq_regs.h>#include <asm/io.h> #define CREATE_TRACE_POINTS#include <trace/events/random.h> /* #define ADD_INTERRUPT_BENCH */ /* * Configuration information */#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 EXTRACT_SIZE 10 #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long)) /* * To allow fractional bits to be tracked, the entropy_count field is * denominated in units of 1/8th bits. * * 2*(ENTROPY_SHIFT + poolbitshift) must <= 31, or the multiply in * credit_entropy_bits() needs to be 64 bits wide. */#define ENTROPY_SHIFT 3#define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT) /* * 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. */static int random_write_wakeup_bits = 28 * OUTPUT_POOL_WORDS; /* * 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 * GFSR generators II. ACM Transactions on Modeling and Computer * 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. */static const struct poolinfo { int poolbitshift, poolwords, poolbytes, poolfracbits;#define S(x) ilog2(x)+5, (x), (x)*4, (x) << (ENTROPY_SHIFT+5) int tap1, tap2, tap3, tap4, tap5;} poolinfo_table[] = { /* 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 },}; /* * Static global variables */static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);static struct fasync_struct *fasync; static DEFINE_SPINLOCK(random_ready_list_lock);static LIST_HEAD(random_ready_list); struct crng_state { __u32 state[16]; unsigned long init_time; spinlock_t lock;}; static 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 > 1))static int crng_init_cnt = 0;static unsigned long crng_global_init_time = 0;#define CRNG_INIT_CNT_THRESH (2*CHACHA_KEY_SIZE)static void _extract_crng(struct crng_state *crng, __u8 out[CHACHA_BLOCK_SIZE]);static void _crng_backtrack_protect(struct crng_state *crng, __u8 tmp[CHACHA_BLOCK_SIZE], int used);static void process_random_ready_list(void);static void _get_random_bytes(void *buf, int nbytes); static struct ratelimit_state unseeded_warning = RATELIMIT_STATE_INIT("warn_unseeded_randomness", HZ, 3);static struct ratelimit_state urandom_warning = RATELIMIT_STATE_INIT("warn_urandom_randomness", HZ, 3); static int ratelimit_disable __read_mostly; module_param_named(ratelimit_disable, ratelimit_disable, int, 0644);MODULE_PARM_DESC(ratelimit_disable, "Disable random ratelimit suppression"); /********************************************************************** * * OS independent entropy store. Here are the functions which handle * storing entropy in an entropy pool. * **********************************************************************/ struct entropy_store;struct entropy_store { /* read-only data: */ const struct poolinfo *poolinfo; __u32 *pool; const char *name; /* read-write data: */ spinlock_t lock; unsigned short add_ptr;Lines 1–500 of 2305. Load more
/* * random.c -- A strong random number generator * * Copyright (C) 2017 Jason A. Donenfeld <Jason@zx2c4.com>. All * Rights Reserved. * * Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005 * * 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 four exported interfaces; two for use within the kernel, * and two or use from userspace. * * Exported interfaces ---- userspace output * ----------------------------------------- * * The userspace 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 ---- kernel output * -------------------------------------- * * The primary kernel interface is * * 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. This is equivalent to a * read from /dev/urandom. * * For less critical applications, there are the functions: * * u32 get_random_u32() * u64 get_random_u64() * unsigned int get_random_int() * unsigned long get_random_long() * * These are produced by a cryptographic RNG seeded from get_random_bytes, * and so do not deplete the entropy pool as much. These are recommended * for most in-kernel operations *if the result is going to be stored in * the kernel*. * * Specifically, the get_random_int() family do not attempt to do * "anti-backtracking". If you capture the state of the kernel (e.g. * by snapshotting the VM), you can figure out previous get_random_int() * return values. But if the value is stored in the kernel anyway, * this is not a problem. * * It *is* safe to expose get_random_int() output to attackers (e.g. as * network cookies); given outputs 1..n, it's not feasible to predict * outputs 0 or n+1. The only concern is an attacker who breaks into * the kernel later; the get_random_int() engine is not reseeded as * often as the get_random_bytes() one. * * get_random_bytes() is needed for keys that need to stay secret after * they are erased from the kernel. For example, any key that will * be wrapped and stored encrypted. And session encryption keys: we'd * like to know that after the session is closed and the keys erased, * the plaintext is unrecoverable to someone who recorded the ciphertext. * * But for network ports/cookies, stack canaries, PRNG seeds, address * space layout randomization, session *authentication* keys, or other * applications where the sensitive data is stored in the kernel in * plaintext for as long as it's sensitive, the get_random_int() family * is just fine. * * Consider ASLR. We want to keep the address space secret from an * outside attacker while the process is running, but once the address * space is torn down, it's of no use to an attacker any more. And it's * stored in kernel data structures as long as it's alive, so worrying * about an attacker's ability to extrapolate it from the get_random_int() * CRNG is silly. * * Even some cryptographic keys are safe to generate with get_random_int(). * In particular, keys for SipHash are generally fine. Here, knowledge * of the key authorizes you to do something to a kernel object (inject * packets to a network connection, or flood a hash table), and the * key is stored with the object being protected. Once it goes away, * we no longer care if anyone knows the key. * * prandom_u32() * ------------- * * For even weaker applications, see the pseudorandom generator * prandom_u32(), prandom_max(), and prandom_bytes(). If the random * numbers aren't security-critical at all, these are *far* cheaper. * Useful for self-tests, random error simulation, randomized backoffs, * and any other application where you trust that nobody is trying to * maliciously mess with you by guessing the "random" numbers. * * Exported interfaces ---- input * ============================== * * The current exported interfaces for gathering environmental noise * from the devices are: * * void add_device_randomness(const void *buf, unsigned int size); * void add_input_randomness(unsigned int type, unsigned int code, * unsigned int value); * void add_interrupt_randomness(int irq, int irq_flags); * void add_disk_randomness(struct gendisk *disk); * * 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). * * add_input_randomness() uses the input layer interrupt timing, as well as * the event type information from the hardware. * * 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. * * 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. * * 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. */ #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt #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> #include <linux/mm.h> #include <linux/nodemask.h> #include <linux/spinlock.h> #include <linux/kthread.h> #include <linux/percpu.h> #include <linux/fips.h> #include <linux/ptrace.h> #include <linux/workqueue.h> #include <linux/irq.h> #include <linux/ratelimit.h> #include <linux/syscalls.h> #include <linux/completion.h> #include <linux/uuid.h> #include <crypto/chacha.h> #include <crypto/sha1.h> #include <asm/processor.h> #include <linux/uaccess.h> #include <asm/irq.h> #include <asm/irq_regs.h> #include <asm/io.h> #define CREATE_TRACE_POINTS #include <trace/events/random.h> /* #define ADD_INTERRUPT_BENCH */ /* * Configuration information */ #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 EXTRACT_SIZE 10 #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long)) /* * To allow fractional bits to be tracked, the entropy_count field is * denominated in units of 1/8th bits. * * 2*(ENTROPY_SHIFT + poolbitshift) must <= 31, or the multiply in * credit_entropy_bits() needs to be 64 bits wide. */ #define ENTROPY_SHIFT 3 #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT) /* * 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. */ static int random_write_wakeup_bits = 28 * OUTPUT_POOL_WORDS; /* * 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 * GFSR generators II. ACM Transactions on Modeling and Computer * 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. */ static const struct poolinfo { int poolbitshift, poolwords, poolbytes, poolfracbits; #define S(x) ilog2(x)+5, (x), (x)*4, (x) << (ENTROPY_SHIFT+5) int tap1, tap2, tap3, tap4, tap5; } poolinfo_table[] = { /* 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 }, }; /* * Static global variables */ static DECLARE_WAIT_QUEUE_HEAD(random_write_wait); static struct fasync_struct *fasync; static DEFINE_SPINLOCK(random_ready_list_lock); static LIST_HEAD(random_ready_list); struct crng_state { __u32 state[16]; unsigned long init_time; spinlock_t lock; }; static 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 > 1)) static int crng_init_cnt = 0; static unsigned long crng_global_init_time = 0; #define CRNG_INIT_CNT_THRESH (2*CHACHA_KEY_SIZE) static void _extract_crng(struct crng_state *crng, __u8 out[CHACHA_BLOCK_SIZE]); static void _crng_backtrack_protect(struct crng_state *crng, __u8 tmp[CHACHA_BLOCK_SIZE], int used); static void process_random_ready_list(void); static void _get_random_bytes(void *buf, int nbytes); static struct ratelimit_state unseeded_warning = RATELIMIT_STATE_INIT("warn_unseeded_randomness", HZ, 3); static struct ratelimit_state urandom_warning = RATELIMIT_STATE_INIT("warn_urandom_randomness", HZ, 3); static int ratelimit_disable __read_mostly; module_param_named(ratelimit_disable, ratelimit_disable, int, 0644); MODULE_PARM_DESC(ratelimit_disable, "Disable random ratelimit suppression"); /********************************************************************** * * OS independent entropy store. Here are the functions which handle * storing entropy in an entropy pool. * **********************************************************************/ struct entropy_store; struct entropy_store { /* read-only data: */ const struct poolinfo *poolinfo; __u32 *pool; const char *name; /* read-write data: */ spinlock_t lock; unsigned short add_ptr;