| Author | Tokens | Token Proportion | Commits | Commit Proportion |
|---|---|---|---|---|
| Theodore Y. Ts'o | 3643 | 43.95% | 52 | 22.03% |
| Linus Torvalds (pre-git) | 1135 | 13.69% | 19 | 8.05% |
| Matt Mackall | 544 | 6.56% | 37 | 15.68% |
| H. Peter Anvin | 437 | 5.27% | 7 | 2.97% |
| Linus Torvalds | 341 | 4.11% | 12 | 5.08% |
| Jason A. Donenfeld | 324 | 3.91% | 9 | 3.81% |
| Herbert Xu | 271 | 3.27% | 2 | 0.85% |
| Mark Rutland | 202 | 2.44% | 4 | 1.69% |
| Andrew Lutomirski | 172 | 2.08% | 3 | 1.27% |
| Andrew Morton | 105 | 1.27% | 6 | 2.54% |
| Sebastian Andrzej Siewior | 91 | 1.10% | 1 | 0.42% |
| Dave Jones | 83 | 1.00% | 2 | 0.85% |
| Jason Cooper | 80 | 0.97% | 1 | 0.42% |
| Jarod Wilson | 80 | 0.97% | 2 | 0.85% |
| Torsten Duwe | 63 | 0.76% | 1 | 0.42% |
| Eric Biggers | 58 | 0.70% | 4 | 1.69% |
| Kees Cook | 52 | 0.63% | 3 | 1.27% |
| Jeff Dike | 51 | 0.62% | 1 | 0.42% |
| Al Viro | 46 | 0.55% | 3 | 1.27% |
| Hsin-Yi, Wang | 46 | 0.55% | 1 | 0.42% |
| Hannes Frederic Sowa | 42 | 0.51% | 1 | 0.42% |
| Neil Horman | 34 | 0.41% | 1 | 0.42% |
| Greg Price | 31 | 0.37% | 7 | 2.97% |
| Yangtao Li | 26 | 0.31% | 5 | 2.12% |
| Mathieu Desnoyers | 25 | 0.30% | 1 | 0.42% |
| Daniel Cashman | 22 | 0.27% | 1 | 0.42% |
| Qian Cai | 21 | 0.25% | 1 | 0.42% |
| Tobin C Harding | 19 | 0.23% | 1 | 0.42% |
| Willy Tarreau | 16 | 0.19% | 1 | 0.42% |
| Arnd Bergmann | 15 | 0.18% | 2 | 0.85% |
| Jiri Kosina | 14 | 0.17% | 1 | 0.42% |
| Art Haas | 14 | 0.17% | 1 | 0.42% |
| Yinghai Lu | 13 | 0.16% | 2 | 0.85% |
| Jon DeVree | 13 | 0.16% | 1 | 0.42% |
| Michael Schmitz | 13 | 0.16% | 1 | 0.42% |
| David Howells | 10 | 0.12% | 1 | 0.42% |
| Stephan Mueller | 10 | 0.12% | 2 | 0.85% |
| Arjan van de Ven | 9 | 0.11% | 2 | 0.85% |
| George Spelvin | 9 | 0.11% | 2 | 0.85% |
| Tejun Heo | 8 | 0.10% | 1 | 0.42% |
| Serge E. Hallyn | 7 | 0.08% | 1 | 0.42% |
| Andy Shevchenko | 7 | 0.08% | 2 | 0.85% |
| Joe Perches | 7 | 0.08% | 3 | 1.27% |
| Olof Johansson | 6 | 0.07% | 1 | 0.42% |
| Eric Dumazet | 6 | 0.07% | 1 | 0.42% |
| Fabio Estevam | 6 | 0.07% | 1 | 0.42% |
| Ingo Molnar | 6 | 0.07% | 1 | 0.42% |
| David S. Miller | 6 | 0.07% | 1 | 0.42% |
| Brian Gerst | 5 | 0.06% | 1 | 0.42% |
| Dmitry Torokhov | 5 | 0.06% | 1 | 0.42% |
| Arnaldo Carvalho de Melo | 5 | 0.06% | 2 | 0.85% |
| Christoph Hellwig | 5 | 0.06% | 1 | 0.42% |
| Sergey Senozhatsky | 4 | 0.05% | 1 | 0.42% |
| Rasmus Villemoes | 4 | 0.05% | 3 | 1.27% |
| Anton Blanchard | 4 | 0.05% | 1 | 0.42% |
| Bálint Márton | 3 | 0.04% | 1 | 0.42% |
| Michael Ellerman | 3 | 0.04% | 1 | 0.42% |
| Andrea Righi | 3 | 0.04% | 1 | 0.42% |
| Tony Luck | 2 | 0.02% | 2 | 0.85% |
| Daniel Borkmann | 2 | 0.02% | 1 | 0.42% |
| Christoph Lameter | 2 | 0.02% | 1 | 0.42% |
| Manfred Spraul | 1 | 0.01% | 1 | 0.42% |
| Eric W. Biedermann | 1 | 0.01% | 1 | 0.42% |
| Emese Revfy | 1 | 0.01% | 1 | 0.42% |
| Total | 8289 | 236 |
/* * 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/sha.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; unsigned short input_rotate; int entropy_count; unsigned int initialized:1; unsigned int last_data_init:1; __u8 last_data[EXTRACT_SIZE]; }; 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); static __u32 input_pool_data[INPUT_POOL_WORDS] __latent_entropy; static struct entropy_store input_pool = { .poolinfo = &poolinfo_table[0], .name = "input", .lock = __SPIN_LOCK_UNLOCKED(input_pool.lock), .pool = input_pool_data }; static __u32 const twist_table[8] = { 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 }; /* * This function adds bytes into the entropy "pool". It does not * update the entropy estimate. The caller should call * credit_entropy_bits if this is appropriate. * * 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. */ static void _mix_pool_bytes(struct entropy_store *r, const void *in, int nbytes) { unsigned long i, tap1, tap2, tap3, tap4, tap5; int input_rotate; int wordmask = r->poolinfo->poolwords - 1; const char *bytes = in; __u32 w; tap1 = r->poolinfo->tap1; tap2 = r->poolinfo->tap2; tap3 = r->poolinfo->tap3; tap4 = r->poolinfo->tap4; tap5 = r->poolinfo->tap5; input_rotate = r->input_rotate; i = r->add_ptr; /* mix one byte at a time to simplify size handling and churn faster */ while (nbytes--) { w = rol32(*bytes++, input_rotate); i = (i - 1) & wordmask; /* XOR in the various taps */ w ^= r->pool[i]; 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]; /* Mix the result back in with a twist */ r->pool[i] = (w >> 3) ^ twist_table[w & 7]; /* * 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. */ input_rotate = (input_rotate + (i ? 7 : 14)) & 31; } r->input_rotate = input_rotate; r->add_ptr = i; } static void __mix_pool_bytes(struct entropy_store *r, const void *in, int nbytes) { trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_); _mix_pool_bytes(r, in, nbytes); } static void mix_pool_bytes(struct entropy_store *r, const void *in, int nbytes) { unsigned long flags; trace_mix_pool_bytes(r->name, nbytes, _RET_IP_); spin_lock_irqsave(&r->lock, flags); _mix_pool_bytes(r, in, nbytes); spin_unlock_irqrestore(&r->lock, flags); } struct fast_pool { __u32 pool[4]; unsigned long last; unsigned short reg_idx; unsigned char count; }; /* * 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. */ static void fast_mix(struct fast_pool *f) { __u32 a = f->pool[0], b = f->pool[1]; __u32 c = f->pool[2], d = f->pool[3]; a += b; c += d; b = rol32(b, 6); d = rol32(d, 27); d ^= a; b ^= c; a += b; c += d; b = rol32(b, 16); d = rol32(d, 14); d ^= a; b ^= c; a += b; c += d; b = rol32(b, 6); d = rol32(d, 27); d ^= a; b ^= c; a += b; c += d; b = rol32(b, 16); d = rol32(d, 14); d ^= a; b ^= c; f->pool[0] = a; f->pool[1] = b; f->pool[2] = c; f->pool[3] = d; f->count++; } 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); } /* * 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. */ static void credit_entropy_bits(struct entropy_store *r, int nbits) { int entropy_count, orig, has_initialized = 0; const int pool_size = r->poolinfo->poolfracbits; int nfrac = nbits << ENTROPY_SHIFT; if (!nbits) return; retry: entropy_count = orig = READ_ONCE(r->entropy_count); 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)); } if (WARN_ON(entropy_count < 0)) { pr_warn("negative entropy/overflow: pool %s count %d\n", r->name, entropy_count); entropy_count = 0; } else if (entropy_count > pool_size) entropy_count = pool_size; if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) goto retry; if (has_initialized) { r->initialized = 1; kill_fasync(&fasync, SIGIO, POLL_IN); } trace_credit_entropy_bits(r->name, nbits, entropy_count >> ENTROPY_SHIFT, _RET_IP_); if (r == &input_pool) { int entropy_bits = entropy_count >> ENTROPY_SHIFT; if (crng_init < 2) { if (entropy_bits < 128) return; crng_reseed(&primary_crng, r); entropy_bits = ENTROPY_BITS(r); } } } static int credit_entropy_bits_safe(struct entropy_store *r, int nbits) { const int nbits_max = r->poolinfo->poolwords * 32; if (nbits < 0) return -EINVAL; /* Cap the value to avoid overflows */ nbits = min(nbits, nbits_max); credit_entropy_bits(r, nbits); return 0; } /********************************************************************* * * CRNG using CHACHA20 * *********************************************************************/ #define CRNG_RESEED_INTERVAL (300*HZ) static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait); #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 static void invalidate_batched_entropy(void); static void numa_crng_init(void); static bool trust_cpu __ro_after_init = IS_ENABLED(CONFIG_RANDOM_TRUST_CPU); static int __init parse_trust_cpu(char *arg) { return kstrtobool(arg, &trust_cpu); } early_param("random.trust_cpu", parse_trust_cpu); static bool crng_init_try_arch(struct crng_state *crng) { int i; bool arch_init = true; unsigned long rv; for (i = 4; i < 16; i++) { if (!arch_get_random_seed_long(&rv) && !arch_get_random_long(&rv)) { rv = random_get_entropy(); arch_init = false; } crng->state[i] ^= rv; } return arch_init; } static bool __init crng_init_try_arch_early(struct crng_state *crng) { int i; bool arch_init = true; unsigned long rv; for (i = 4; i < 16; i++) { if (!arch_get_random_seed_long_early(&rv) && !arch_get_random_long_early(&rv)) { rv = random_get_entropy(); arch_init = false; } crng->state[i] ^= rv; } return arch_init; } static void __maybe_unused crng_initialize_secondary(struct crng_state *crng) { memcpy(&crng->state[0], "expand 32-byte k", 16); _get_random_bytes(&crng->state[4], sizeof(__u32) * 12); crng_init_try_arch(crng); crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1; } static void __init crng_initialize_primary(struct crng_state *crng) { memcpy(&crng->state[0], "expand 32-byte k", 16); _extract_entropy(&input_pool, &crng->state[4], sizeof(__u32) * 12, 0); if (crng_init_try_arch_early(crng) && trust_cpu) { invalidate_batched_entropy(); numa_crng_init(); crng_init = 2; pr_notice("crng done (trusting CPU's manufacturer)\n"); } crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1; } #ifdef CONFIG_NUMA static void do_numa_crng_init(struct work_struct *work) { int i; struct crng_state *crng; struct crng_state **pool; pool = kcalloc(nr_node_ids, sizeof(*pool), GFP_KERNEL|__GFP_NOFAIL); for_each_online_node(i) { crng = kmalloc_node(sizeof(struct crng_state), GFP_KERNEL | __GFP_NOFAIL, i); spin_lock_init(&crng->lock); crng_initialize_secondary(crng); pool[i] = crng; } mb(); if (cmpxchg(&crng_node_pool, NULL, pool)) { for_each_node(i) kfree(pool[i]); kfree(pool); } } static DECLARE_WORK(numa_crng_init_work, do_numa_crng_init); static void numa_crng_init(void) { schedule_work(&numa_crng_init_work); } #else static void numa_crng_init(void) {} #endif /* * crng_fast_load() can be called by code in the interrupt service * path. So we can't afford to dilly-dally. */ 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_init != 0) { 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 % CHACHA_KEY_SIZE] ^= *cp; cp++; crng_init_cnt++; len--; } spin_unlock_irqrestore(&primary_crng.lock, flags); if (crng_init_cnt >= CRNG_INIT_CNT_THRESH) { invalidate_batched_entropy(); crng_init = 1; pr_notice("fast init done\n"); } return 1; } /* * crng_slow_load() is called by add_device_randomness, which has two * attributes. (1) We can't trust the buffer passed to it is * guaranteed to be unpredictable (so it might not have any entropy at * all), and (2) it doesn't have the performance constraints of * crng_fast_load(). * * So we do something more comprehensive which is guaranteed to touch * all of the primary_crng's state, and which uses a LFSR with a * period of 255 as part of the mixing algorithm. Finally, we do * *not* advance crng_init_cnt since buffer we may get may be something * like a fixed DMI table (for example), which might very well be * unique to the machine, but is otherwise unvarying. */ static int crng_slow_load(const char *cp, size_t len) { unsigned long flags; static unsigned char lfsr = 1; unsigned char tmp; unsigned i, max = CHACHA_KEY_SIZE; const char * src_buf = cp; char * dest_buf = (char *) &primary_crng.state[4]; if (!spin_trylock_irqsave(&primary_crng.lock, flags)) return 0; if (crng_init != 0) { spin_unlock_irqrestore(&primary_crng.lock, flags); return 0; } if (len > max) max = len; for (i = 0; i < max ; i++) { tmp = lfsr; lfsr >>= 1; if (tmp & 1) lfsr ^= 0xE1; tmp = dest_buf[i % CHACHA_KEY_SIZE]; dest_buf[i % CHACHA_KEY_SIZE] ^= src_buf[i % len] ^ lfsr; lfsr += (tmp << 3) | (tmp >> 5); } spin_unlock_irqrestore(&primary_crng.lock, flags); return 1; } static void crng_reseed(struct crng_state *crng, struct entropy_store *r) { unsigned long flags; int i, num; union { __u8 block[CHACHA_BLOCK_SIZE]; __u32 key[8]; } buf; if (r) { num = extract_entropy(r, &buf, 32, 16, 0); if (num == 0) return; } else { _extract_crng(&primary_crng, buf.block); _crng_backtrack_protect(&primary_crng, buf.block, CHACHA_KEY_SIZE); } spin_lock_irqsave(&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; spin_unlock_irqrestore(&crng->lock, flags); if (crng == &primary_crng && crng_init < 2) { invalidate_batched_entropy(); numa_crng_init(); crng_init = 2; process_random_ready_list(); wake_up_interruptible(&crng_init_wait); kill_fasync(&fasync, SIGIO, POLL_IN); pr_notice("crng init done\n"); if (unseeded_warning.missed) { pr_notice("%d get_random_xx warning(s) missed due to ratelimiting\n", unseeded_warning.missed); unseeded_warning.missed = 0; } if (urandom_warning.missed) { pr_notice("%d urandom warning(s) missed due to ratelimiting\n", urandom_warning.missed); urandom_warning.missed = 0; } } } static void _extract_crng(struct crng_state *crng, __u8 out[CHACHA_BLOCK_SIZE]) { unsigned long v, flags; if (crng_ready() && (time_after(crng_global_init_time, crng->init_time) || time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL))) crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL); 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); } static void extract_crng(__u8 out[CHACHA_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); } /* * 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[CHACHA_BLOCK_SIZE], int used) { unsigned long flags; __u32 *s, *d; int i; used = round_up(used, sizeof(__u32)); if (used + CHACHA_KEY_SIZE > CHACHA_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[CHACHA_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); } static ssize_t extract_crng_user(void __user *buf, size_t nbytes) { ssize_t ret = 0, i = CHACHA_BLOCK_SIZE; __u8 tmp[CHACHA_BLOCK_SIZE] __aligned(4); 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, CHACHA_BLOCK_SIZE); if (copy_to_user(buf, tmp, i)) { ret = -EFAULT; break; } nbytes -= i; buf += i; ret += i; } crng_backtrack_protect(tmp, i); /* Wipe data just written to memory */ memzero_explicit(tmp, sizeof(tmp)); return ret; } /********************************************************************* * * Entropy input management * *********************************************************************/ /* There is one of these per entropy source */ struct timer_rand_state { cycles_t last_time; long last_delta, last_delta2; }; #define INIT_TIMER_RAND_STATE { INITIAL_JIFFIES, }; /* * Add device- or boot-specific data to the input pool to help * initialize it. * * 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. */ void add_device_randomness(const void *buf, unsigned int size) { unsigned long time = random_get_entropy() ^ jiffies; unsigned long flags; if (!crng_ready() && size) crng_slow_load(buf, size); trace_add_device_randomness(size, _RET_IP_); spin_lock_irqsave(&input_pool.lock, flags); _mix_pool_bytes(&input_pool, buf, size); _mix_pool_bytes(&input_pool, &time, sizeof(time)); spin_unlock_irqrestore(&input_pool.lock, flags); } EXPORT_SYMBOL(add_device_randomness); static struct timer_rand_state input_timer_state = INIT_TIMER_RAND_STATE; /* * 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) { struct entropy_store *r; struct { long jiffies; unsigned cycles; unsigned num; } sample; long delta, delta2, delta3; sample.jiffies = jiffies; sample.cycles = random_get_entropy(); sample.num = num; r = &input_pool; mix_pool_bytes(r, &sample, sizeof(sample)); /* * Calculate number of bits of randomness we probably added. * We take into account the first, second and third-order deltas * in order to make our estimate. */ delta = sample.jiffies - READ_ONCE(state->last_time); WRITE_ONCE(state->last_time, sample.jiffies); delta2 = delta - READ_ONCE(state->last_delta); WRITE_ONCE(state->last_delta, delta); delta3 = delta2 - READ_ONCE(state->last_delta2); WRITE_ONCE(state->last_delta2, delta2); if (delta < 0) delta = -delta; if (delta2 < 0) delta2 = -delta2; if (delta3 < 0) delta3 = -delta3; if (delta > delta2) delta = delta2; if (delta > delta3) delta = delta3; /* * delta is now minimum absolute delta. * Round down by 1 bit on general principles, * and limit entropy estimate to 12 bits. */ credit_entropy_bits(r, min_t(int, fls(delta>>1), 11)); } void add_input_randomness(unsigned int type, unsigned int code, 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); trace_add_input_randomness(ENTROPY_BITS(&input_pool)); } EXPORT_SYMBOL_GPL(add_input_randomness); static DEFINE_PER_CPU(struct fast_pool, irq_randomness); #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 static __u32 get_reg(struct fast_pool *f, struct pt_regs *regs) { __u32 *ptr = (__u32 *) regs; unsigned int idx; if (regs == NULL) return 0; idx = READ_ONCE(f->reg_idx); if (idx >= sizeof(struct pt_regs) / sizeof(__u32)) idx = 0; ptr += idx++; WRITE_ONCE(f->reg_idx, idx); return *ptr; } void add_interrupt_randomness(int irq, int irq_flags) { struct entropy_store *r; struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness); struct pt_regs *regs = get_irq_regs(); unsigned long now = jiffies; cycles_t cycles = random_get_entropy(); __u32 c_high, j_high; __u64 ip; unsigned long seed; int credit = 0; if (cycles == 0) cycles = get_reg(fast_pool, regs); c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0; j_high = (sizeof(now) > 4) ? now >> 32 : 0; fast_pool->pool[0] ^= cycles ^ j_high ^ irq; fast_pool->pool[1] ^= now ^ c_high; ip = regs ? instruction_pointer(regs) : _RET_IP_; fast_pool->pool[2] ^= ip; fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 : get_reg(fast_pool, regs); fast_mix(fast_pool); add_interrupt_bench(cycles); this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]); if (unlikely(crng_init == 0)) { 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; } if ((fast_pool->count < 64) && !time_after(now, fast_pool->last + HZ)) return; r = &input_pool; if (!spin_trylock(&r->lock)) return; fast_pool->last = now; __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); /* * If we have architectural seed generator, produce a seed and * add it to the pool. For the sake of paranoia don't let the * architectural seed generator dominate the input from the * interrupt noise. */ if (arch_get_random_seed_long(&seed)) { __mix_pool_bytes(r, &seed, sizeof(seed)); credit = 1; } spin_unlock(&r->lock); fast_pool->count = 0; /* award one bit for the contents of the fast pool */ credit_entropy_bits(r, credit + 1); } EXPORT_SYMBOL_GPL(add_interrupt_randomness); #ifdef CONFIG_BLOCK void add_disk_randomness(struct gendisk *disk) { if (!disk || !disk->random) return; /* first major is 1, so we get >= 0x200 here */ add_timer_randomness(disk->random, 0x100 + disk_devt(disk)); trace_add_disk_randomness(disk_devt(disk), ENTROPY_BITS(&input_pool)); } EXPORT_SYMBOL_GPL(add_disk_randomness); #endif /********************************************************************* * * Entropy extraction routines * *********************************************************************/ /* * This function decides how many bytes to actually take from the * given pool, and also debits the entropy count accordingly. */ static size_t account(struct entropy_store *r, size_t nbytes, int min, int reserved) { int entropy_count, orig, have_bytes; size_t ibytes, nfrac; BUG_ON(r->entropy_count > r->poolinfo->poolfracbits); /* Can we pull enough? */ retry: entropy_count = orig = READ_ONCE(r->entropy_count); ibytes = nbytes; /* never pull more than available */ have_bytes = entropy_count >> (ENTROPY_SHIFT + 3); if ((have_bytes -= reserved) < 0) have_bytes = 0; ibytes = min_t(size_t, ibytes, have_bytes); if (ibytes < min) ibytes = 0; if (WARN_ON(entropy_count < 0)) { pr_warn("negative entropy count: pool %s count %d\n", r->name, entropy_count); entropy_count = 0; } nfrac = ibytes << (ENTROPY_SHIFT + 3); if ((size_t) entropy_count > nfrac) entropy_count -= nfrac; else entropy_count = 0; if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) goto retry; trace_debit_entropy(r->name, 8 * ibytes); if (ibytes && ENTROPY_BITS(r) < random_write_wakeup_bits) { wake_up_interruptible(&random_write_wait); kill_fasync(&fasync, SIGIO, POLL_OUT); } return ibytes; } /* * This function does the actual extraction for extract_entropy and * extract_entropy_user. * * Note: we assume that .poolwords is a multiple of 16 words. */ static void extract_buf(struct entropy_store *r, __u8 *out) { int i; union { __u32 w[5]; unsigned long l[LONGS(20)]; } hash; __u32 workspace[SHA1_WORKSPACE_WORDS]; unsigned long flags; /* * If we have an architectural hardware random number * generator, use it for SHA's initial vector */ sha1_init(hash.w); for (i = 0; i < LONGS(20); i++) { unsigned long v; if (!arch_get_random_long(&v)) break; hash.l[i] = v; } /* 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) sha1_transform(hash.w, (__u8 *)(r->pool + i), workspace); /* * 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. */ __mix_pool_bytes(r, hash.w, sizeof(hash.w)); spin_unlock_irqrestore(&r->lock, flags); memzero_explicit(workspace, sizeof(workspace)); /* * 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. */ 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); memzero_explicit(&hash, sizeof(hash)); } 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; } /* * 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. */ static ssize_t extract_entropy(struct entropy_store *r, void *buf, size_t nbytes, int min, int reserved) { __u8 tmp[EXTRACT_SIZE]; unsigned long flags; /* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */ if (fips_enabled) { spin_lock_irqsave(&r->lock, flags); if (!r->last_data_init) { r->last_data_init = 1; spin_unlock_irqrestore(&r->lock, flags); trace_extract_entropy(r->name, EXTRACT_SIZE, ENTROPY_BITS(r), _RET_IP_); extract_buf(r, tmp); spin_lock_irqsave(&r->lock, flags); memcpy(r->last_data, tmp, EXTRACT_SIZE); } spin_unlock_irqrestore(&r->lock, flags); } trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_); nbytes = account(r, nbytes, min, reserved); return _extract_entropy(r, buf, nbytes, fips_enabled); } #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 if (__ratelimit(&unseeded_warning)) printk_deferred(KERN_NOTICE "random: %s called from %pS " "with crng_init=%d\n", func_name, caller, crng_init); } /* * This function is the exported kernel interface. It returns some * number of good random numbers, suitable for key generation, seeding * TCP sequence numbers, etc. It does not rely on the hardware random * number generator. For random bytes direct from the hardware RNG * (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. */ static void _get_random_bytes(void *buf, int nbytes) { __u8 tmp[CHACHA_BLOCK_SIZE] __aligned(4); trace_get_random_bytes(nbytes, _RET_IP_); while (nbytes >= CHACHA_BLOCK_SIZE) { extract_crng(buf); buf += CHACHA_BLOCK_SIZE; nbytes -= CHACHA_BLOCK_SIZE; } if (nbytes > 0) { extract_crng(tmp); memcpy(buf, tmp, nbytes); crng_backtrack_protect(tmp, nbytes); } else crng_backtrack_protect(tmp, CHACHA_BLOCK_SIZE); memzero_explicit(tmp, sizeof(tmp)); } void get_random_bytes(void *buf, int nbytes) { static void *previous; warn_unseeded_randomness(&previous); _get_random_bytes(buf, nbytes); } EXPORT_SYMBOL(get_random_bytes); /* * Each time the timer fires, we expect that we got an unpredictable * jump in the cycle counter. Even if the timer is running on another * CPU, the timer activity will be touching the stack of the CPU that is * generating entropy.. * * Note that we don't re-arm the timer in the timer itself - we are * happy to be scheduled away, since that just makes the load more * complex, but we do not want the timer to keep ticking unless the * entropy loop is running. * * So the re-arming always happens in the entropy loop itself. */ static void entropy_timer(struct timer_list *t) { credit_entropy_bits(&input_pool, 1); } /* * If we have an actual cycle counter, see if we can * generate enough entropy with timing noise */ static void try_to_generate_entropy(void) { struct { unsigned long now; struct timer_list timer; } stack; stack.now = random_get_entropy(); /* Slow counter - or none. Don't even bother */ if (stack.now == random_get_entropy()) return; timer_setup_on_stack(&stack.timer, entropy_timer, 0); while (!crng_ready()) { if (!timer_pending(&stack.timer)) mod_timer(&stack.timer, jiffies+1); mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now)); schedule(); stack.now = random_get_entropy(); } del_timer_sync(&stack.timer); destroy_timer_on_stack(&stack.timer); mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now)); } /* * 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; do { int ret; ret = wait_event_interruptible_timeout(crng_init_wait, crng_ready(), HZ); if (ret) return ret > 0 ? 0 : ret; try_to_generate_entropy(); } while (!crng_ready()); return 0; } EXPORT_SYMBOL(wait_for_random_bytes); /* * Returns whether or not the urandom pool has been 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. * * Returns: true if the urandom pool has been seeded. * false if the urandom pool has not been seeded. */ bool rng_is_initialized(void) { return crng_ready(); } EXPORT_SYMBOL(rng_is_initialized); /* * 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; if (crng_ready()) return err; owner = rdy->owner; if (!try_module_get(owner)) return -ENOENT; spin_lock_irqsave(&random_ready_list_lock, flags); if (crng_ready()) 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); /* * 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. * * Return number of bytes filled in. */ int __must_check get_random_bytes_arch(void *buf, int nbytes) { int left = nbytes; char *p = buf; trace_get_random_bytes_arch(left, _RET_IP_); while (left) { unsigned long v; int chunk = min_t(int, left, sizeof(unsigned long)); if (!arch_get_random_long(&v)) break; memcpy(p, &v, chunk); p += chunk; left -= chunk; } return nbytes - left; } EXPORT_SYMBOL(get_random_bytes_arch); /* * 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 init_std_data(struct entropy_store *r) { int i; ktime_t now = ktime_get_real(); unsigned long rv; mix_pool_bytes(r, &now, sizeof(now)); for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) { if (!arch_get_random_seed_long(&rv) && !arch_get_random_long(&rv)) rv = random_get_entropy(); mix_pool_bytes(r, &rv, sizeof(rv)); } mix_pool_bytes(r, utsname(), sizeof(*(utsname()))); } /* * 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. */ int __init rand_initialize(void) { init_std_data(&input_pool); crng_initialize_primary(&primary_crng); crng_global_init_time = jiffies; if (ratelimit_disable) { urandom_warning.interval = 0; unseeded_warning.interval = 0; } return 0; } #ifdef CONFIG_BLOCK void rand_initialize_disk(struct gendisk *disk) { struct timer_rand_state *state; /* * If kzalloc returns null, we just won't use that entropy * source. */ state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL); if (state) { state->last_time = INITIAL_JIFFIES; disk->random = state; } } #endif static ssize_t urandom_read_nowarn(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) { int ret; nbytes = min_t(size_t, nbytes, INT_MAX >> (ENTROPY_SHIFT + 3)); ret = extract_crng_user(buf, nbytes); trace_urandom_read(8 * nbytes, 0, ENTROPY_BITS(&input_pool)); return ret; } static ssize_t urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) { unsigned long flags; static int maxwarn = 10; if (!crng_ready() && maxwarn > 0) { maxwarn--; if (__ratelimit(&urandom_warning)) pr_notice("%s: uninitialized urandom read (%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); } return urandom_read_nowarn(file, buf, nbytes, ppos); } static ssize_t random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) { int ret; ret = wait_for_random_bytes(); if (ret != 0) return ret; return urandom_read_nowarn(file, buf, nbytes, ppos); } static __poll_t random_poll(struct file *file, poll_table * wait) { __poll_t mask; poll_wait(file, &crng_init_wait, wait); poll_wait(file, &random_write_wait, wait); mask = 0; if (crng_ready()) mask |= EPOLLIN | EPOLLRDNORM; if (ENTROPY_BITS(&input_pool) < random_write_wakeup_bits) mask |= EPOLLOUT | EPOLLWRNORM; return mask; } static int write_pool(struct entropy_store *r, const char __user *buffer, size_t count) { size_t bytes; __u32 t, buf[16]; const char __user *p = buffer; while (count > 0) { int b, i = 0; bytes = min(count, sizeof(buf)); if (copy_from_user(&buf, p, bytes)) return -EFAULT; for (b = bytes ; b > 0 ; b -= sizeof(__u32), i++) { if (!arch_get_random_int(&t)) break; buf[i] ^= t; } count -= bytes; p += bytes; mix_pool_bytes(r, buf, bytes); cond_resched(); } return 0; } static ssize_t random_write(struct file *file, const char __user *buffer, size_t count, loff_t *ppos) { size_t ret; ret = write_pool(&input_pool, buffer, count); if (ret) return ret; return (ssize_t)count; } static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) { int size, ent_count; int __user *p = (int __user *)arg; int retval; switch (cmd) { case RNDGETENTCNT: /* inherently racy, no point locking */ ent_count = ENTROPY_BITS(&input_pool); if (put_user(ent_count, p)) return -EFAULT; return 0; case RNDADDTOENTCNT: if (!capable(CAP_SYS_ADMIN)) return -EPERM; if (get_user(ent_count, p)) return -EFAULT; return credit_entropy_bits_safe(&input_pool, ent_count); 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; retval = write_pool(&input_pool, (const char __user *)p, size); if (retval < 0) return retval; return credit_entropy_bits_safe(&input_pool, ent_count); case RNDZAPENTCNT: case RNDCLEARPOOL: /* * Clear the entropy pool counters. We no longer clear * the entropy pool, as that's silly. */ if (!capable(CAP_SYS_ADMIN)) return -EPERM; input_pool.entropy_count = 0; return 0; case RNDRESEEDCRNG: if (!capable(CAP_SYS_ADMIN)) return -EPERM; if (crng_init < 2) return -ENODATA; crng_reseed(&primary_crng, NULL); crng_global_init_time = jiffies - 1; return 0; default: return -EINVAL; } } static int random_fasync(int fd, struct file *filp, int on) { return fasync_helper(fd, filp, on, &fasync); } const struct file_operations random_fops = { .read = random_read, .write = random_write, .poll = random_poll, .unlocked_ioctl = random_ioctl, .compat_ioctl = compat_ptr_ioctl, .fasync = random_fasync, .llseek = noop_llseek, }; const struct file_operations urandom_fops = { .read = urandom_read, .write = random_write, .unlocked_ioctl = random_ioctl, .compat_ioctl = compat_ptr_ioctl, .fasync = random_fasync, .llseek = noop_llseek, }; SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count, unsigned int, flags) { int ret; if (flags & ~(GRND_NONBLOCK|GRND_RANDOM|GRND_INSECURE)) return -EINVAL; /* * Requesting insecure and blocking randomness at the same time makes * no sense. */ if ((flags & (GRND_INSECURE|GRND_RANDOM)) == (GRND_INSECURE|GRND_RANDOM)) return -EINVAL; if (count > INT_MAX) count = INT_MAX; if (!(flags & GRND_INSECURE) && !crng_ready()) { if (flags & GRND_NONBLOCK) return -EAGAIN; ret = wait_for_random_bytes(); if (unlikely(ret)) return ret; } return urandom_read_nowarn(NULL, buf, count, NULL); } /******************************************************************** * * Sysctl interface * ********************************************************************/ #ifdef CONFIG_SYSCTL #include <linux/sysctl.h> static int min_write_thresh; static int max_write_thresh = INPUT_POOL_WORDS * 32; static int random_min_urandom_seed = 60; static char sysctl_bootid[16]; /* * This function is used to return both the bootid UUID, and random * UUID. The difference is in whether table->data is NULL; if it is, * then a new UUID is generated and returned to the user. * * 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. */ static int proc_do_uuid(struct ctl_table *table, int write, void *buffer, size_t *lenp, loff_t *ppos) { struct ctl_table fake_table; unsigned char buf[64], tmp_uuid[16], *uuid; uuid = table->data; if (!uuid) { uuid = tmp_uuid; generate_random_uuid(uuid); } else { static DEFINE_SPINLOCK(bootid_spinlock); spin_lock(&bootid_spinlock); if (!uuid[8]) generate_random_uuid(uuid); spin_unlock(&bootid_spinlock); } sprintf(buf, "%pU", uuid); fake_table.data = buf; fake_table.maxlen = sizeof(buf); return proc_dostring(&fake_table, write, buffer, lenp, ppos); } /* * Return entropy available scaled to integral bits */ static int proc_do_entropy(struct ctl_table *table, int write, void *buffer, size_t *lenp, loff_t *ppos) { struct ctl_table fake_table; 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); } static int sysctl_poolsize = INPUT_POOL_WORDS * 32; extern struct ctl_table random_table[]; struct ctl_table random_table[] = { { .procname = "poolsize", .data = &sysctl_poolsize, .maxlen = sizeof(int), .mode = 0444, .proc_handler = proc_dointvec, }, { .procname = "entropy_avail", .maxlen = sizeof(int), .mode = 0444, .proc_handler = proc_do_entropy, .data = &input_pool.entropy_count, }, { .procname = "write_wakeup_threshold", .data = &random_write_wakeup_bits, .maxlen = sizeof(int), .mode = 0644, .proc_handler = proc_dointvec_minmax, .extra1 = &min_write_thresh, .extra2 = &max_write_thresh, }, { .procname = "urandom_min_reseed_secs", .data = &random_min_urandom_seed, .maxlen = sizeof(int), .mode = 0644, .proc_handler = proc_dointvec, }, { .procname = "boot_id", .data = &sysctl_bootid, .maxlen = 16, .mode = 0444, .proc_handler = proc_do_uuid, }, { .procname = "uuid", .maxlen = 16, .mode = 0444, .proc_handler = proc_do_uuid, }, #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 { } }; #endif /* CONFIG_SYSCTL */ struct batched_entropy { union { u64 entropy_u64[CHACHA_BLOCK_SIZE / sizeof(u64)]; u32 entropy_u32[CHACHA_BLOCK_SIZE / sizeof(u32)]; }; unsigned int position; spinlock_t batch_lock; }; /* * Get a random word for internal kernel use only. The quality of the random * number is good as /dev/urandom, but there is no backtrack protection, with * the 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. */ static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u64) = { .batch_lock = __SPIN_LOCK_UNLOCKED(batched_entropy_u64.lock), }; u64 get_random_u64(void) { u64 ret; unsigned long flags; struct batched_entropy *batch; static void *previous; warn_unseeded_randomness(&previous); batch = raw_cpu_ptr(&batched_entropy_u64); spin_lock_irqsave(&batch->batch_lock, flags); if (batch->position % ARRAY_SIZE(batch->entropy_u64) == 0) { extract_crng((u8 *)batch->entropy_u64); batch->position = 0; } ret = batch->entropy_u64[batch->position++]; spin_unlock_irqrestore(&batch->batch_lock, flags); return ret; } EXPORT_SYMBOL(get_random_u64); static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u32) = { .batch_lock = __SPIN_LOCK_UNLOCKED(batched_entropy_u32.lock), }; u32 get_random_u32(void) { u32 ret; unsigned long flags; struct batched_entropy *batch; static void *previous; warn_unseeded_randomness(&previous); batch = raw_cpu_ptr(&batched_entropy_u32); spin_lock_irqsave(&batch->batch_lock, flags); if (batch->position % ARRAY_SIZE(batch->entropy_u32) == 0) { extract_crng((u8 *)batch->entropy_u32); batch->position = 0; } ret = batch->entropy_u32[batch->position++]; spin_unlock_irqrestore(&batch->batch_lock, flags); return ret; } EXPORT_SYMBOL(get_random_u32); /* 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; for_each_possible_cpu (cpu) { struct batched_entropy *batched_entropy; batched_entropy = per_cpu_ptr(&batched_entropy_u32, cpu); spin_lock_irqsave(&batched_entropy->batch_lock, flags); batched_entropy->position = 0; spin_unlock(&batched_entropy->batch_lock); batched_entropy = per_cpu_ptr(&batched_entropy_u64, cpu); spin_lock(&batched_entropy->batch_lock); batched_entropy->position = 0; spin_unlock_irqrestore(&batched_entropy->batch_lock, flags); } } /** * 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); } /* 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; if (unlikely(crng_init == 0)) { crng_fast_load(buffer, count); return; } /* 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); mix_pool_bytes(poolp, buffer, count); credit_entropy_bits(poolp, entropy); } EXPORT_SYMBOL_GPL(add_hwgenerator_randomness); /* Handle random seed passed by bootloader. * If the seed is trustworthy, it would be regarded as hardware RNGs. Otherwise * it would be regarded as device data. * The decision is controlled by CONFIG_RANDOM_TRUST_BOOTLOADER. */ void add_bootloader_randomness(const void *buf, unsigned int size) { if (IS_ENABLED(CONFIG_RANDOM_TRUST_BOOTLOADER)) add_hwgenerator_randomness(buf, size, size * 8); else add_device_randomness(buf, size); } EXPORT_SYMBOL_GPL(add_bootloader_randomness);
Information contained on this website is for historical information purposes only and does not indicate or represent copyright ownership.
Created with Cregit http://github.com/cregit/cregit
Version 2.0-RC1