Root/
1 | /* |
2 | * random.c -- A strong random number generator |
3 | * |
4 | * Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005 |
5 | * |
6 | * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All |
7 | * rights reserved. |
8 | * |
9 | * Redistribution and use in source and binary forms, with or without |
10 | * modification, are permitted provided that the following conditions |
11 | * are met: |
12 | * 1. Redistributions of source code must retain the above copyright |
13 | * notice, and the entire permission notice in its entirety, |
14 | * including the disclaimer of warranties. |
15 | * 2. Redistributions in binary form must reproduce the above copyright |
16 | * notice, this list of conditions and the following disclaimer in the |
17 | * documentation and/or other materials provided with the distribution. |
18 | * 3. The name of the author may not be used to endorse or promote |
19 | * products derived from this software without specific prior |
20 | * written permission. |
21 | * |
22 | * ALTERNATIVELY, this product may be distributed under the terms of |
23 | * the GNU General Public License, in which case the provisions of the GPL are |
24 | * required INSTEAD OF the above restrictions. (This clause is |
25 | * necessary due to a potential bad interaction between the GPL and |
26 | * the restrictions contained in a BSD-style copyright.) |
27 | * |
28 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED |
29 | * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
30 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF |
31 | * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE |
32 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
33 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT |
34 | * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR |
35 | * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
36 | * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
37 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE |
38 | * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH |
39 | * DAMAGE. |
40 | */ |
41 | |
42 | /* |
43 | * (now, with legal B.S. out of the way.....) |
44 | * |
45 | * This routine gathers environmental noise from device drivers, etc., |
46 | * and returns good random numbers, suitable for cryptographic use. |
47 | * Besides the obvious cryptographic uses, these numbers are also good |
48 | * for seeding TCP sequence numbers, and other places where it is |
49 | * desirable to have numbers which are not only random, but hard to |
50 | * predict by an attacker. |
51 | * |
52 | * Theory of operation |
53 | * =================== |
54 | * |
55 | * Computers are very predictable devices. Hence it is extremely hard |
56 | * to produce truly random numbers on a computer --- as opposed to |
57 | * pseudo-random numbers, which can easily generated by using a |
58 | * algorithm. Unfortunately, it is very easy for attackers to guess |
59 | * the sequence of pseudo-random number generators, and for some |
60 | * applications this is not acceptable. So instead, we must try to |
61 | * gather "environmental noise" from the computer's environment, which |
62 | * must be hard for outside attackers to observe, and use that to |
63 | * generate random numbers. In a Unix environment, this is best done |
64 | * from inside the kernel. |
65 | * |
66 | * Sources of randomness from the environment include inter-keyboard |
67 | * timings, inter-interrupt timings from some interrupts, and other |
68 | * events which are both (a) non-deterministic and (b) hard for an |
69 | * outside observer to measure. Randomness from these sources are |
70 | * added to an "entropy pool", which is mixed using a CRC-like function. |
71 | * This is not cryptographically strong, but it is adequate assuming |
72 | * the randomness is not chosen maliciously, and it is fast enough that |
73 | * the overhead of doing it on every interrupt is very reasonable. |
74 | * As random bytes are mixed into the entropy pool, the routines keep |
75 | * an *estimate* of how many bits of randomness have been stored into |
76 | * the random number generator's internal state. |
77 | * |
78 | * When random bytes are desired, they are obtained by taking the SHA |
79 | * hash of the contents of the "entropy pool". The SHA hash avoids |
80 | * exposing the internal state of the entropy pool. It is believed to |
81 | * be computationally infeasible to derive any useful information |
82 | * about the input of SHA from its output. Even if it is possible to |
83 | * analyze SHA in some clever way, as long as the amount of data |
84 | * returned from the generator is less than the inherent entropy in |
85 | * the pool, the output data is totally unpredictable. For this |
86 | * reason, the routine decreases its internal estimate of how many |
87 | * bits of "true randomness" are contained in the entropy pool as it |
88 | * outputs random numbers. |
89 | * |
90 | * If this estimate goes to zero, the routine can still generate |
91 | * random numbers; however, an attacker may (at least in theory) be |
92 | * able to infer the future output of the generator from prior |
93 | * outputs. This requires successful cryptanalysis of SHA, which is |
94 | * not believed to be feasible, but there is a remote possibility. |
95 | * Nonetheless, these numbers should be useful for the vast majority |
96 | * of purposes. |
97 | * |
98 | * Exported interfaces ---- output |
99 | * =============================== |
100 | * |
101 | * There are three exported interfaces; the first is one designed to |
102 | * be used from within the kernel: |
103 | * |
104 | * void get_random_bytes(void *buf, int nbytes); |
105 | * |
106 | * This interface will return the requested number of random bytes, |
107 | * and place it in the requested buffer. |
108 | * |
109 | * The two other interfaces are two character devices /dev/random and |
110 | * /dev/urandom. /dev/random is suitable for use when very high |
111 | * quality randomness is desired (for example, for key generation or |
112 | * one-time pads), as it will only return a maximum of the number of |
113 | * bits of randomness (as estimated by the random number generator) |
114 | * contained in the entropy pool. |
115 | * |
116 | * The /dev/urandom device does not have this limit, and will return |
117 | * as many bytes as are requested. As more and more random bytes are |
118 | * requested without giving time for the entropy pool to recharge, |
119 | * this will result in random numbers that are merely cryptographically |
120 | * strong. For many applications, however, this is acceptable. |
121 | * |
122 | * Exported interfaces ---- input |
123 | * ============================== |
124 | * |
125 | * The current exported interfaces for gathering environmental noise |
126 | * from the devices are: |
127 | * |
128 | * void add_device_randomness(const void *buf, unsigned int size); |
129 | * void add_input_randomness(unsigned int type, unsigned int code, |
130 | * unsigned int value); |
131 | * void add_interrupt_randomness(int irq, int irq_flags); |
132 | * void add_disk_randomness(struct gendisk *disk); |
133 | * |
134 | * add_device_randomness() is for adding data to the random pool that |
135 | * is likely to differ between two devices (or possibly even per boot). |
136 | * This would be things like MAC addresses or serial numbers, or the |
137 | * read-out of the RTC. This does *not* add any actual entropy to the |
138 | * pool, but it initializes the pool to different values for devices |
139 | * that might otherwise be identical and have very little entropy |
140 | * available to them (particularly common in the embedded world). |
141 | * |
142 | * add_input_randomness() uses the input layer interrupt timing, as well as |
143 | * the event type information from the hardware. |
144 | * |
145 | * add_interrupt_randomness() uses the interrupt timing as random |
146 | * inputs to the entropy pool. Using the cycle counters and the irq source |
147 | * as inputs, it feeds the randomness roughly once a second. |
148 | * |
149 | * add_disk_randomness() uses what amounts to the seek time of block |
150 | * layer request events, on a per-disk_devt basis, as input to the |
151 | * entropy pool. Note that high-speed solid state drives with very low |
152 | * seek times do not make for good sources of entropy, as their seek |
153 | * times are usually fairly consistent. |
154 | * |
155 | * All of these routines try to estimate how many bits of randomness a |
156 | * particular randomness source. They do this by keeping track of the |
157 | * first and second order deltas of the event timings. |
158 | * |
159 | * Ensuring unpredictability at system startup |
160 | * ============================================ |
161 | * |
162 | * When any operating system starts up, it will go through a sequence |
163 | * of actions that are fairly predictable by an adversary, especially |
164 | * if the start-up does not involve interaction with a human operator. |
165 | * This reduces the actual number of bits of unpredictability in the |
166 | * entropy pool below the value in entropy_count. In order to |
167 | * counteract this effect, it helps to carry information in the |
168 | * entropy pool across shut-downs and start-ups. To do this, put the |
169 | * following lines an appropriate script which is run during the boot |
170 | * sequence: |
171 | * |
172 | * echo "Initializing random number generator..." |
173 | * random_seed=/var/run/random-seed |
174 | * # Carry a random seed from start-up to start-up |
175 | * # Load and then save the whole entropy pool |
176 | * if [ -f $random_seed ]; then |
177 | * cat $random_seed >/dev/urandom |
178 | * else |
179 | * touch $random_seed |
180 | * fi |
181 | * chmod 600 $random_seed |
182 | * dd if=/dev/urandom of=$random_seed count=1 bs=512 |
183 | * |
184 | * and the following lines in an appropriate script which is run as |
185 | * the system is shutdown: |
186 | * |
187 | * # Carry a random seed from shut-down to start-up |
188 | * # Save the whole entropy pool |
189 | * echo "Saving random seed..." |
190 | * random_seed=/var/run/random-seed |
191 | * touch $random_seed |
192 | * chmod 600 $random_seed |
193 | * dd if=/dev/urandom of=$random_seed count=1 bs=512 |
194 | * |
195 | * For example, on most modern systems using the System V init |
196 | * scripts, such code fragments would be found in |
197 | * /etc/rc.d/init.d/random. On older Linux systems, the correct script |
198 | * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0. |
199 | * |
200 | * Effectively, these commands cause the contents of the entropy pool |
201 | * to be saved at shut-down time and reloaded into the entropy pool at |
202 | * start-up. (The 'dd' in the addition to the bootup script is to |
203 | * make sure that /etc/random-seed is different for every start-up, |
204 | * even if the system crashes without executing rc.0.) Even with |
205 | * complete knowledge of the start-up activities, predicting the state |
206 | * of the entropy pool requires knowledge of the previous history of |
207 | * the system. |
208 | * |
209 | * Configuring the /dev/random driver under Linux |
210 | * ============================================== |
211 | * |
212 | * The /dev/random driver under Linux uses minor numbers 8 and 9 of |
213 | * the /dev/mem major number (#1). So if your system does not have |
214 | * /dev/random and /dev/urandom created already, they can be created |
215 | * by using the commands: |
216 | * |
217 | * mknod /dev/random c 1 8 |
218 | * mknod /dev/urandom c 1 9 |
219 | * |
220 | * Acknowledgements: |
221 | * ================= |
222 | * |
223 | * Ideas for constructing this random number generator were derived |
224 | * from Pretty Good Privacy's random number generator, and from private |
225 | * discussions with Phil Karn. Colin Plumb provided a faster random |
226 | * number generator, which speed up the mixing function of the entropy |
227 | * pool, taken from PGPfone. Dale Worley has also contributed many |
228 | * useful ideas and suggestions to improve this driver. |
229 | * |
230 | * Any flaws in the design are solely my responsibility, and should |
231 | * not be attributed to the Phil, Colin, or any of authors of PGP. |
232 | * |
233 | * Further background information on this topic may be obtained from |
234 | * RFC 1750, "Randomness Recommendations for Security", by Donald |
235 | * Eastlake, Steve Crocker, and Jeff Schiller. |
236 | */ |
237 | |
238 | #include <linux/utsname.h> |
239 | #include <linux/module.h> |
240 | #include <linux/kernel.h> |
241 | #include <linux/major.h> |
242 | #include <linux/string.h> |
243 | #include <linux/fcntl.h> |
244 | #include <linux/slab.h> |
245 | #include <linux/random.h> |
246 | #include <linux/poll.h> |
247 | #include <linux/init.h> |
248 | #include <linux/fs.h> |
249 | #include <linux/genhd.h> |
250 | #include <linux/interrupt.h> |
251 | #include <linux/mm.h> |
252 | #include <linux/spinlock.h> |
253 | #include <linux/percpu.h> |
254 | #include <linux/cryptohash.h> |
255 | #include <linux/fips.h> |
256 | #include <linux/ptrace.h> |
257 | #include <linux/kmemcheck.h> |
258 | |
259 | #ifdef CONFIG_GENERIC_HARDIRQS |
260 | # include <linux/irq.h> |
261 | #endif |
262 | |
263 | #include <asm/processor.h> |
264 | #include <asm/uaccess.h> |
265 | #include <asm/irq.h> |
266 | #include <asm/irq_regs.h> |
267 | #include <asm/io.h> |
268 | |
269 | #define CREATE_TRACE_POINTS |
270 | #include <trace/events/random.h> |
271 | |
272 | /* |
273 | * Configuration information |
274 | */ |
275 | #define INPUT_POOL_WORDS 128 |
276 | #define OUTPUT_POOL_WORDS 32 |
277 | #define SEC_XFER_SIZE 512 |
278 | #define EXTRACT_SIZE 10 |
279 | |
280 | #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long)) |
281 | |
282 | /* |
283 | * The minimum number of bits of entropy before we wake up a read on |
284 | * /dev/random. Should be enough to do a significant reseed. |
285 | */ |
286 | static int random_read_wakeup_thresh = 64; |
287 | |
288 | /* |
289 | * If the entropy count falls under this number of bits, then we |
290 | * should wake up processes which are selecting or polling on write |
291 | * access to /dev/random. |
292 | */ |
293 | static int random_write_wakeup_thresh = 128; |
294 | |
295 | /* |
296 | * When the input pool goes over trickle_thresh, start dropping most |
297 | * samples to avoid wasting CPU time and reduce lock contention. |
298 | */ |
299 | |
300 | static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28; |
301 | |
302 | static DEFINE_PER_CPU(int, trickle_count); |
303 | |
304 | /* |
305 | * A pool of size .poolwords is stirred with a primitive polynomial |
306 | * of degree .poolwords over GF(2). The taps for various sizes are |
307 | * defined below. They are chosen to be evenly spaced (minimum RMS |
308 | * distance from evenly spaced; the numbers in the comments are a |
309 | * scaled squared error sum) except for the last tap, which is 1 to |
310 | * get the twisting happening as fast as possible. |
311 | */ |
312 | static struct poolinfo { |
313 | int poolwords; |
314 | int tap1, tap2, tap3, tap4, tap5; |
315 | } poolinfo_table[] = { |
316 | /* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */ |
317 | { 128, 103, 76, 51, 25, 1 }, |
318 | /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */ |
319 | { 32, 26, 20, 14, 7, 1 }, |
320 | #if 0 |
321 | /* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */ |
322 | { 2048, 1638, 1231, 819, 411, 1 }, |
323 | |
324 | /* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */ |
325 | { 1024, 817, 615, 412, 204, 1 }, |
326 | |
327 | /* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */ |
328 | { 1024, 819, 616, 410, 207, 2 }, |
329 | |
330 | /* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */ |
331 | { 512, 411, 308, 208, 104, 1 }, |
332 | |
333 | /* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */ |
334 | { 512, 409, 307, 206, 102, 2 }, |
335 | /* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */ |
336 | { 512, 409, 309, 205, 103, 2 }, |
337 | |
338 | /* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */ |
339 | { 256, 205, 155, 101, 52, 1 }, |
340 | |
341 | /* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */ |
342 | { 128, 103, 78, 51, 27, 2 }, |
343 | |
344 | /* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */ |
345 | { 64, 52, 39, 26, 14, 1 }, |
346 | #endif |
347 | }; |
348 | |
349 | #define POOLBITS poolwords*32 |
350 | #define POOLBYTES poolwords*4 |
351 | |
352 | /* |
353 | * For the purposes of better mixing, we use the CRC-32 polynomial as |
354 | * well to make a twisted Generalized Feedback Shift Reigster |
355 | * |
356 | * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM |
357 | * Transactions on Modeling and Computer Simulation 2(3):179-194. |
358 | * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators |
359 | * II. ACM Transactions on Mdeling and Computer Simulation 4:254-266) |
360 | * |
361 | * Thanks to Colin Plumb for suggesting this. |
362 | * |
363 | * We have not analyzed the resultant polynomial to prove it primitive; |
364 | * in fact it almost certainly isn't. Nonetheless, the irreducible factors |
365 | * of a random large-degree polynomial over GF(2) are more than large enough |
366 | * that periodicity is not a concern. |
367 | * |
368 | * The input hash is much less sensitive than the output hash. All |
369 | * that we want of it is that it be a good non-cryptographic hash; |
370 | * i.e. it not produce collisions when fed "random" data of the sort |
371 | * we expect to see. As long as the pool state differs for different |
372 | * inputs, we have preserved the input entropy and done a good job. |
373 | * The fact that an intelligent attacker can construct inputs that |
374 | * will produce controlled alterations to the pool's state is not |
375 | * important because we don't consider such inputs to contribute any |
376 | * randomness. The only property we need with respect to them is that |
377 | * the attacker can't increase his/her knowledge of the pool's state. |
378 | * Since all additions are reversible (knowing the final state and the |
379 | * input, you can reconstruct the initial state), if an attacker has |
380 | * any uncertainty about the initial state, he/she can only shuffle |
381 | * that uncertainty about, but never cause any collisions (which would |
382 | * decrease the uncertainty). |
383 | * |
384 | * The chosen system lets the state of the pool be (essentially) the input |
385 | * modulo the generator polymnomial. Now, for random primitive polynomials, |
386 | * this is a universal class of hash functions, meaning that the chance |
387 | * of a collision is limited by the attacker's knowledge of the generator |
388 | * polynomail, so if it is chosen at random, an attacker can never force |
389 | * a collision. Here, we use a fixed polynomial, but we *can* assume that |
390 | * ###--> it is unknown to the processes generating the input entropy. <-### |
391 | * Because of this important property, this is a good, collision-resistant |
392 | * hash; hash collisions will occur no more often than chance. |
393 | */ |
394 | |
395 | /* |
396 | * Static global variables |
397 | */ |
398 | static DECLARE_WAIT_QUEUE_HEAD(random_read_wait); |
399 | static DECLARE_WAIT_QUEUE_HEAD(random_write_wait); |
400 | static struct fasync_struct *fasync; |
401 | |
402 | static bool debug; |
403 | module_param(debug, bool, 0644); |
404 | #define DEBUG_ENT(fmt, arg...) do { \ |
405 | if (debug) \ |
406 | printk(KERN_DEBUG "random %04d %04d %04d: " \ |
407 | fmt,\ |
408 | input_pool.entropy_count,\ |
409 | blocking_pool.entropy_count,\ |
410 | nonblocking_pool.entropy_count,\ |
411 | ## arg); } while (0) |
412 | |
413 | /********************************************************************** |
414 | * |
415 | * OS independent entropy store. Here are the functions which handle |
416 | * storing entropy in an entropy pool. |
417 | * |
418 | **********************************************************************/ |
419 | |
420 | struct entropy_store; |
421 | struct entropy_store { |
422 | /* read-only data: */ |
423 | struct poolinfo *poolinfo; |
424 | __u32 *pool; |
425 | const char *name; |
426 | struct entropy_store *pull; |
427 | int limit; |
428 | |
429 | /* read-write data: */ |
430 | spinlock_t lock; |
431 | unsigned add_ptr; |
432 | unsigned input_rotate; |
433 | int entropy_count; |
434 | int entropy_total; |
435 | unsigned int initialized:1; |
436 | bool last_data_init; |
437 | __u8 last_data[EXTRACT_SIZE]; |
438 | }; |
439 | |
440 | static __u32 input_pool_data[INPUT_POOL_WORDS]; |
441 | static __u32 blocking_pool_data[OUTPUT_POOL_WORDS]; |
442 | static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS]; |
443 | |
444 | static struct entropy_store input_pool = { |
445 | .poolinfo = &poolinfo_table[0], |
446 | .name = "input", |
447 | .limit = 1, |
448 | .lock = __SPIN_LOCK_UNLOCKED(input_pool.lock), |
449 | .pool = input_pool_data |
450 | }; |
451 | |
452 | static struct entropy_store blocking_pool = { |
453 | .poolinfo = &poolinfo_table[1], |
454 | .name = "blocking", |
455 | .limit = 1, |
456 | .pull = &input_pool, |
457 | .lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock), |
458 | .pool = blocking_pool_data |
459 | }; |
460 | |
461 | static struct entropy_store nonblocking_pool = { |
462 | .poolinfo = &poolinfo_table[1], |
463 | .name = "nonblocking", |
464 | .pull = &input_pool, |
465 | .lock = __SPIN_LOCK_UNLOCKED(nonblocking_pool.lock), |
466 | .pool = nonblocking_pool_data |
467 | }; |
468 | |
469 | static __u32 const twist_table[8] = { |
470 | 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, |
471 | 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 }; |
472 | |
473 | /* |
474 | * This function adds bytes into the entropy "pool". It does not |
475 | * update the entropy estimate. The caller should call |
476 | * credit_entropy_bits if this is appropriate. |
477 | * |
478 | * The pool is stirred with a primitive polynomial of the appropriate |
479 | * degree, and then twisted. We twist by three bits at a time because |
480 | * it's cheap to do so and helps slightly in the expected case where |
481 | * the entropy is concentrated in the low-order bits. |
482 | */ |
483 | static void _mix_pool_bytes(struct entropy_store *r, const void *in, |
484 | int nbytes, __u8 out[64]) |
485 | { |
486 | unsigned long i, j, tap1, tap2, tap3, tap4, tap5; |
487 | int input_rotate; |
488 | int wordmask = r->poolinfo->poolwords - 1; |
489 | const char *bytes = in; |
490 | __u32 w; |
491 | |
492 | tap1 = r->poolinfo->tap1; |
493 | tap2 = r->poolinfo->tap2; |
494 | tap3 = r->poolinfo->tap3; |
495 | tap4 = r->poolinfo->tap4; |
496 | tap5 = r->poolinfo->tap5; |
497 | |
498 | smp_rmb(); |
499 | input_rotate = ACCESS_ONCE(r->input_rotate); |
500 | i = ACCESS_ONCE(r->add_ptr); |
501 | |
502 | /* mix one byte at a time to simplify size handling and churn faster */ |
503 | while (nbytes--) { |
504 | w = rol32(*bytes++, input_rotate & 31); |
505 | i = (i - 1) & wordmask; |
506 | |
507 | /* XOR in the various taps */ |
508 | w ^= r->pool[i]; |
509 | w ^= r->pool[(i + tap1) & wordmask]; |
510 | w ^= r->pool[(i + tap2) & wordmask]; |
511 | w ^= r->pool[(i + tap3) & wordmask]; |
512 | w ^= r->pool[(i + tap4) & wordmask]; |
513 | w ^= r->pool[(i + tap5) & wordmask]; |
514 | |
515 | /* Mix the result back in with a twist */ |
516 | r->pool[i] = (w >> 3) ^ twist_table[w & 7]; |
517 | |
518 | /* |
519 | * Normally, we add 7 bits of rotation to the pool. |
520 | * At the beginning of the pool, add an extra 7 bits |
521 | * rotation, so that successive passes spread the |
522 | * input bits across the pool evenly. |
523 | */ |
524 | input_rotate += i ? 7 : 14; |
525 | } |
526 | |
527 | ACCESS_ONCE(r->input_rotate) = input_rotate; |
528 | ACCESS_ONCE(r->add_ptr) = i; |
529 | smp_wmb(); |
530 | |
531 | if (out) |
532 | for (j = 0; j < 16; j++) |
533 | ((__u32 *)out)[j] = r->pool[(i - j) & wordmask]; |
534 | } |
535 | |
536 | static void __mix_pool_bytes(struct entropy_store *r, const void *in, |
537 | int nbytes, __u8 out[64]) |
538 | { |
539 | trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_); |
540 | _mix_pool_bytes(r, in, nbytes, out); |
541 | } |
542 | |
543 | static void mix_pool_bytes(struct entropy_store *r, const void *in, |
544 | int nbytes, __u8 out[64]) |
545 | { |
546 | unsigned long flags; |
547 | |
548 | trace_mix_pool_bytes(r->name, nbytes, _RET_IP_); |
549 | spin_lock_irqsave(&r->lock, flags); |
550 | _mix_pool_bytes(r, in, nbytes, out); |
551 | spin_unlock_irqrestore(&r->lock, flags); |
552 | } |
553 | |
554 | struct fast_pool { |
555 | __u32 pool[4]; |
556 | unsigned long last; |
557 | unsigned short count; |
558 | unsigned char rotate; |
559 | unsigned char last_timer_intr; |
560 | }; |
561 | |
562 | /* |
563 | * This is a fast mixing routine used by the interrupt randomness |
564 | * collector. It's hardcoded for an 128 bit pool and assumes that any |
565 | * locks that might be needed are taken by the caller. |
566 | */ |
567 | static void fast_mix(struct fast_pool *f, const void *in, int nbytes) |
568 | { |
569 | const char *bytes = in; |
570 | __u32 w; |
571 | unsigned i = f->count; |
572 | unsigned input_rotate = f->rotate; |
573 | |
574 | while (nbytes--) { |
575 | w = rol32(*bytes++, input_rotate & 31) ^ f->pool[i & 3] ^ |
576 | f->pool[(i + 1) & 3]; |
577 | f->pool[i & 3] = (w >> 3) ^ twist_table[w & 7]; |
578 | input_rotate += (i++ & 3) ? 7 : 14; |
579 | } |
580 | f->count = i; |
581 | f->rotate = input_rotate; |
582 | } |
583 | |
584 | /* |
585 | * Credit (or debit) the entropy store with n bits of entropy |
586 | */ |
587 | static void credit_entropy_bits(struct entropy_store *r, int nbits) |
588 | { |
589 | int entropy_count, orig; |
590 | |
591 | if (!nbits) |
592 | return; |
593 | |
594 | DEBUG_ENT("added %d entropy credits to %s\n", nbits, r->name); |
595 | retry: |
596 | entropy_count = orig = ACCESS_ONCE(r->entropy_count); |
597 | entropy_count += nbits; |
598 | |
599 | if (entropy_count < 0) { |
600 | DEBUG_ENT("negative entropy/overflow\n"); |
601 | entropy_count = 0; |
602 | } else if (entropy_count > r->poolinfo->POOLBITS) |
603 | entropy_count = r->poolinfo->POOLBITS; |
604 | if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) |
605 | goto retry; |
606 | |
607 | if (!r->initialized && nbits > 0) { |
608 | r->entropy_total += nbits; |
609 | if (r->entropy_total > 128) |
610 | r->initialized = 1; |
611 | } |
612 | |
613 | trace_credit_entropy_bits(r->name, nbits, entropy_count, |
614 | r->entropy_total, _RET_IP_); |
615 | |
616 | /* should we wake readers? */ |
617 | if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) { |
618 | wake_up_interruptible(&random_read_wait); |
619 | kill_fasync(&fasync, SIGIO, POLL_IN); |
620 | } |
621 | } |
622 | |
623 | /********************************************************************* |
624 | * |
625 | * Entropy input management |
626 | * |
627 | *********************************************************************/ |
628 | |
629 | /* There is one of these per entropy source */ |
630 | struct timer_rand_state { |
631 | cycles_t last_time; |
632 | long last_delta, last_delta2; |
633 | unsigned dont_count_entropy:1; |
634 | }; |
635 | |
636 | /* |
637 | * Add device- or boot-specific data to the input and nonblocking |
638 | * pools to help initialize them to unique values. |
639 | * |
640 | * None of this adds any entropy, it is meant to avoid the |
641 | * problem of the nonblocking pool having similar initial state |
642 | * across largely identical devices. |
643 | */ |
644 | void add_device_randomness(const void *buf, unsigned int size) |
645 | { |
646 | unsigned long time = get_cycles() ^ jiffies; |
647 | |
648 | mix_pool_bytes(&input_pool, buf, size, NULL); |
649 | mix_pool_bytes(&input_pool, &time, sizeof(time), NULL); |
650 | mix_pool_bytes(&nonblocking_pool, buf, size, NULL); |
651 | mix_pool_bytes(&nonblocking_pool, &time, sizeof(time), NULL); |
652 | } |
653 | EXPORT_SYMBOL(add_device_randomness); |
654 | |
655 | static struct timer_rand_state input_timer_state; |
656 | |
657 | /* |
658 | * This function adds entropy to the entropy "pool" by using timing |
659 | * delays. It uses the timer_rand_state structure to make an estimate |
660 | * of how many bits of entropy this call has added to the pool. |
661 | * |
662 | * The number "num" is also added to the pool - it should somehow describe |
663 | * the type of event which just happened. This is currently 0-255 for |
664 | * keyboard scan codes, and 256 upwards for interrupts. |
665 | * |
666 | */ |
667 | static void add_timer_randomness(struct timer_rand_state *state, unsigned num) |
668 | { |
669 | struct { |
670 | long jiffies; |
671 | unsigned cycles; |
672 | unsigned num; |
673 | } sample; |
674 | long delta, delta2, delta3; |
675 | |
676 | preempt_disable(); |
677 | /* if over the trickle threshold, use only 1 in 4096 samples */ |
678 | if (input_pool.entropy_count > trickle_thresh && |
679 | ((__this_cpu_inc_return(trickle_count) - 1) & 0xfff)) |
680 | goto out; |
681 | |
682 | sample.jiffies = jiffies; |
683 | sample.cycles = get_cycles(); |
684 | sample.num = num; |
685 | mix_pool_bytes(&input_pool, &sample, sizeof(sample), NULL); |
686 | |
687 | /* |
688 | * Calculate number of bits of randomness we probably added. |
689 | * We take into account the first, second and third-order deltas |
690 | * in order to make our estimate. |
691 | */ |
692 | |
693 | if (!state->dont_count_entropy) { |
694 | delta = sample.jiffies - state->last_time; |
695 | state->last_time = sample.jiffies; |
696 | |
697 | delta2 = delta - state->last_delta; |
698 | state->last_delta = delta; |
699 | |
700 | delta3 = delta2 - state->last_delta2; |
701 | state->last_delta2 = delta2; |
702 | |
703 | if (delta < 0) |
704 | delta = -delta; |
705 | if (delta2 < 0) |
706 | delta2 = -delta2; |
707 | if (delta3 < 0) |
708 | delta3 = -delta3; |
709 | if (delta > delta2) |
710 | delta = delta2; |
711 | if (delta > delta3) |
712 | delta = delta3; |
713 | |
714 | /* |
715 | * delta is now minimum absolute delta. |
716 | * Round down by 1 bit on general principles, |
717 | * and limit entropy entimate to 12 bits. |
718 | */ |
719 | credit_entropy_bits(&input_pool, |
720 | min_t(int, fls(delta>>1), 11)); |
721 | } |
722 | out: |
723 | preempt_enable(); |
724 | } |
725 | |
726 | void add_input_randomness(unsigned int type, unsigned int code, |
727 | unsigned int value) |
728 | { |
729 | static unsigned char last_value; |
730 | |
731 | /* ignore autorepeat and the like */ |
732 | if (value == last_value) |
733 | return; |
734 | |
735 | DEBUG_ENT("input event\n"); |
736 | last_value = value; |
737 | add_timer_randomness(&input_timer_state, |
738 | (type << 4) ^ code ^ (code >> 4) ^ value); |
739 | } |
740 | EXPORT_SYMBOL_GPL(add_input_randomness); |
741 | |
742 | static DEFINE_PER_CPU(struct fast_pool, irq_randomness); |
743 | |
744 | void add_interrupt_randomness(int irq, int irq_flags) |
745 | { |
746 | struct entropy_store *r; |
747 | struct fast_pool *fast_pool = &__get_cpu_var(irq_randomness); |
748 | struct pt_regs *regs = get_irq_regs(); |
749 | unsigned long now = jiffies; |
750 | __u32 input[4], cycles = get_cycles(); |
751 | |
752 | input[0] = cycles ^ jiffies; |
753 | input[1] = irq; |
754 | if (regs) { |
755 | __u64 ip = instruction_pointer(regs); |
756 | input[2] = ip; |
757 | input[3] = ip >> 32; |
758 | } |
759 | |
760 | fast_mix(fast_pool, input, sizeof(input)); |
761 | |
762 | if ((fast_pool->count & 1023) && |
763 | !time_after(now, fast_pool->last + HZ)) |
764 | return; |
765 | |
766 | fast_pool->last = now; |
767 | |
768 | r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool; |
769 | __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool), NULL); |
770 | /* |
771 | * If we don't have a valid cycle counter, and we see |
772 | * back-to-back timer interrupts, then skip giving credit for |
773 | * any entropy. |
774 | */ |
775 | if (cycles == 0) { |
776 | if (irq_flags & __IRQF_TIMER) { |
777 | if (fast_pool->last_timer_intr) |
778 | return; |
779 | fast_pool->last_timer_intr = 1; |
780 | } else |
781 | fast_pool->last_timer_intr = 0; |
782 | } |
783 | credit_entropy_bits(r, 1); |
784 | } |
785 | |
786 | #ifdef CONFIG_BLOCK |
787 | void add_disk_randomness(struct gendisk *disk) |
788 | { |
789 | if (!disk || !disk->random) |
790 | return; |
791 | /* first major is 1, so we get >= 0x200 here */ |
792 | DEBUG_ENT("disk event %d:%d\n", |
793 | MAJOR(disk_devt(disk)), MINOR(disk_devt(disk))); |
794 | |
795 | add_timer_randomness(disk->random, 0x100 + disk_devt(disk)); |
796 | } |
797 | #endif |
798 | |
799 | /********************************************************************* |
800 | * |
801 | * Entropy extraction routines |
802 | * |
803 | *********************************************************************/ |
804 | |
805 | static ssize_t extract_entropy(struct entropy_store *r, void *buf, |
806 | size_t nbytes, int min, int rsvd); |
807 | |
808 | /* |
809 | * This utility inline function is responsible for transferring entropy |
810 | * from the primary pool to the secondary extraction pool. We make |
811 | * sure we pull enough for a 'catastrophic reseed'. |
812 | */ |
813 | static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) |
814 | { |
815 | __u32 tmp[OUTPUT_POOL_WORDS]; |
816 | |
817 | if (r->pull && r->entropy_count < nbytes * 8 && |
818 | r->entropy_count < r->poolinfo->POOLBITS) { |
819 | /* If we're limited, always leave two wakeup worth's BITS */ |
820 | int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4; |
821 | int bytes = nbytes; |
822 | |
823 | /* pull at least as many as BYTES as wakeup BITS */ |
824 | bytes = max_t(int, bytes, random_read_wakeup_thresh / 8); |
825 | /* but never more than the buffer size */ |
826 | bytes = min_t(int, bytes, sizeof(tmp)); |
827 | |
828 | DEBUG_ENT("going to reseed %s with %d bits " |
829 | "(%zu of %d requested)\n", |
830 | r->name, bytes * 8, nbytes * 8, r->entropy_count); |
831 | |
832 | bytes = extract_entropy(r->pull, tmp, bytes, |
833 | random_read_wakeup_thresh / 8, rsvd); |
834 | mix_pool_bytes(r, tmp, bytes, NULL); |
835 | credit_entropy_bits(r, bytes*8); |
836 | } |
837 | } |
838 | |
839 | /* |
840 | * These functions extracts randomness from the "entropy pool", and |
841 | * returns it in a buffer. |
842 | * |
843 | * The min parameter specifies the minimum amount we can pull before |
844 | * failing to avoid races that defeat catastrophic reseeding while the |
845 | * reserved parameter indicates how much entropy we must leave in the |
846 | * pool after each pull to avoid starving other readers. |
847 | * |
848 | * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words. |
849 | */ |
850 | |
851 | static size_t account(struct entropy_store *r, size_t nbytes, int min, |
852 | int reserved) |
853 | { |
854 | unsigned long flags; |
855 | int wakeup_write = 0; |
856 | |
857 | /* Hold lock while accounting */ |
858 | spin_lock_irqsave(&r->lock, flags); |
859 | |
860 | BUG_ON(r->entropy_count > r->poolinfo->POOLBITS); |
861 | DEBUG_ENT("trying to extract %zu bits from %s\n", |
862 | nbytes * 8, r->name); |
863 | |
864 | /* Can we pull enough? */ |
865 | if (r->entropy_count / 8 < min + reserved) { |
866 | nbytes = 0; |
867 | } else { |
868 | /* If limited, never pull more than available */ |
869 | if (r->limit && nbytes + reserved >= r->entropy_count / 8) |
870 | nbytes = r->entropy_count/8 - reserved; |
871 | |
872 | if (r->entropy_count / 8 >= nbytes + reserved) |
873 | r->entropy_count -= nbytes*8; |
874 | else |
875 | r->entropy_count = reserved; |
876 | |
877 | if (r->entropy_count < random_write_wakeup_thresh) |
878 | wakeup_write = 1; |
879 | } |
880 | |
881 | DEBUG_ENT("debiting %zu entropy credits from %s%s\n", |
882 | nbytes * 8, r->name, r->limit ? "" : " (unlimited)"); |
883 | |
884 | spin_unlock_irqrestore(&r->lock, flags); |
885 | |
886 | if (wakeup_write) { |
887 | wake_up_interruptible(&random_write_wait); |
888 | kill_fasync(&fasync, SIGIO, POLL_OUT); |
889 | } |
890 | |
891 | return nbytes; |
892 | } |
893 | |
894 | static void extract_buf(struct entropy_store *r, __u8 *out) |
895 | { |
896 | int i; |
897 | union { |
898 | __u32 w[5]; |
899 | unsigned long l[LONGS(EXTRACT_SIZE)]; |
900 | } hash; |
901 | __u32 workspace[SHA_WORKSPACE_WORDS]; |
902 | __u8 extract[64]; |
903 | unsigned long flags; |
904 | |
905 | /* Generate a hash across the pool, 16 words (512 bits) at a time */ |
906 | sha_init(hash.w); |
907 | spin_lock_irqsave(&r->lock, flags); |
908 | for (i = 0; i < r->poolinfo->poolwords; i += 16) |
909 | sha_transform(hash.w, (__u8 *)(r->pool + i), workspace); |
910 | |
911 | /* |
912 | * We mix the hash back into the pool to prevent backtracking |
913 | * attacks (where the attacker knows the state of the pool |
914 | * plus the current outputs, and attempts to find previous |
915 | * ouputs), unless the hash function can be inverted. By |
916 | * mixing at least a SHA1 worth of hash data back, we make |
917 | * brute-forcing the feedback as hard as brute-forcing the |
918 | * hash. |
919 | */ |
920 | __mix_pool_bytes(r, hash.w, sizeof(hash.w), extract); |
921 | spin_unlock_irqrestore(&r->lock, flags); |
922 | |
923 | /* |
924 | * To avoid duplicates, we atomically extract a portion of the |
925 | * pool while mixing, and hash one final time. |
926 | */ |
927 | sha_transform(hash.w, extract, workspace); |
928 | memset(extract, 0, sizeof(extract)); |
929 | memset(workspace, 0, sizeof(workspace)); |
930 | |
931 | /* |
932 | * In case the hash function has some recognizable output |
933 | * pattern, we fold it in half. Thus, we always feed back |
934 | * twice as much data as we output. |
935 | */ |
936 | hash.w[0] ^= hash.w[3]; |
937 | hash.w[1] ^= hash.w[4]; |
938 | hash.w[2] ^= rol32(hash.w[2], 16); |
939 | |
940 | /* |
941 | * If we have a architectural hardware random number |
942 | * generator, mix that in, too. |
943 | */ |
944 | for (i = 0; i < LONGS(EXTRACT_SIZE); i++) { |
945 | unsigned long v; |
946 | if (!arch_get_random_long(&v)) |
947 | break; |
948 | hash.l[i] ^= v; |
949 | } |
950 | |
951 | memcpy(out, &hash, EXTRACT_SIZE); |
952 | memset(&hash, 0, sizeof(hash)); |
953 | } |
954 | |
955 | static ssize_t extract_entropy(struct entropy_store *r, void *buf, |
956 | size_t nbytes, int min, int reserved) |
957 | { |
958 | ssize_t ret = 0, i; |
959 | __u8 tmp[EXTRACT_SIZE]; |
960 | |
961 | /* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */ |
962 | if (fips_enabled && !r->last_data_init) |
963 | nbytes += EXTRACT_SIZE; |
964 | |
965 | trace_extract_entropy(r->name, nbytes, r->entropy_count, _RET_IP_); |
966 | xfer_secondary_pool(r, nbytes); |
967 | nbytes = account(r, nbytes, min, reserved); |
968 | |
969 | while (nbytes) { |
970 | extract_buf(r, tmp); |
971 | |
972 | if (fips_enabled) { |
973 | unsigned long flags; |
974 | |
975 | |
976 | /* prime last_data value if need be, per fips 140-2 */ |
977 | if (!r->last_data_init) { |
978 | spin_lock_irqsave(&r->lock, flags); |
979 | memcpy(r->last_data, tmp, EXTRACT_SIZE); |
980 | r->last_data_init = true; |
981 | nbytes -= EXTRACT_SIZE; |
982 | spin_unlock_irqrestore(&r->lock, flags); |
983 | extract_buf(r, tmp); |
984 | } |
985 | |
986 | spin_lock_irqsave(&r->lock, flags); |
987 | if (!memcmp(tmp, r->last_data, EXTRACT_SIZE)) |
988 | panic("Hardware RNG duplicated output!\n"); |
989 | memcpy(r->last_data, tmp, EXTRACT_SIZE); |
990 | spin_unlock_irqrestore(&r->lock, flags); |
991 | } |
992 | i = min_t(int, nbytes, EXTRACT_SIZE); |
993 | memcpy(buf, tmp, i); |
994 | nbytes -= i; |
995 | buf += i; |
996 | ret += i; |
997 | } |
998 | |
999 | /* Wipe data just returned from memory */ |
1000 | memset(tmp, 0, sizeof(tmp)); |
1001 | |
1002 | return ret; |
1003 | } |
1004 | |
1005 | static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf, |
1006 | size_t nbytes) |
1007 | { |
1008 | ssize_t ret = 0, i; |
1009 | __u8 tmp[EXTRACT_SIZE]; |
1010 | |
1011 | trace_extract_entropy_user(r->name, nbytes, r->entropy_count, _RET_IP_); |
1012 | xfer_secondary_pool(r, nbytes); |
1013 | nbytes = account(r, nbytes, 0, 0); |
1014 | |
1015 | while (nbytes) { |
1016 | if (need_resched()) { |
1017 | if (signal_pending(current)) { |
1018 | if (ret == 0) |
1019 | ret = -ERESTARTSYS; |
1020 | break; |
1021 | } |
1022 | schedule(); |
1023 | } |
1024 | |
1025 | extract_buf(r, tmp); |
1026 | i = min_t(int, nbytes, EXTRACT_SIZE); |
1027 | if (copy_to_user(buf, tmp, i)) { |
1028 | ret = -EFAULT; |
1029 | break; |
1030 | } |
1031 | |
1032 | nbytes -= i; |
1033 | buf += i; |
1034 | ret += i; |
1035 | } |
1036 | |
1037 | /* Wipe data just returned from memory */ |
1038 | memset(tmp, 0, sizeof(tmp)); |
1039 | |
1040 | return ret; |
1041 | } |
1042 | |
1043 | /* |
1044 | * This function is the exported kernel interface. It returns some |
1045 | * number of good random numbers, suitable for key generation, seeding |
1046 | * TCP sequence numbers, etc. It does not use the hw random number |
1047 | * generator, if available; use get_random_bytes_arch() for that. |
1048 | */ |
1049 | void get_random_bytes(void *buf, int nbytes) |
1050 | { |
1051 | extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0); |
1052 | } |
1053 | EXPORT_SYMBOL(get_random_bytes); |
1054 | |
1055 | /* |
1056 | * This function will use the architecture-specific hardware random |
1057 | * number generator if it is available. The arch-specific hw RNG will |
1058 | * almost certainly be faster than what we can do in software, but it |
1059 | * is impossible to verify that it is implemented securely (as |
1060 | * opposed, to, say, the AES encryption of a sequence number using a |
1061 | * key known by the NSA). So it's useful if we need the speed, but |
1062 | * only if we're willing to trust the hardware manufacturer not to |
1063 | * have put in a back door. |
1064 | */ |
1065 | void get_random_bytes_arch(void *buf, int nbytes) |
1066 | { |
1067 | char *p = buf; |
1068 | |
1069 | trace_get_random_bytes(nbytes, _RET_IP_); |
1070 | while (nbytes) { |
1071 | unsigned long v; |
1072 | int chunk = min(nbytes, (int)sizeof(unsigned long)); |
1073 | |
1074 | if (!arch_get_random_long(&v)) |
1075 | break; |
1076 | |
1077 | memcpy(p, &v, chunk); |
1078 | p += chunk; |
1079 | nbytes -= chunk; |
1080 | } |
1081 | |
1082 | if (nbytes) |
1083 | extract_entropy(&nonblocking_pool, p, nbytes, 0, 0); |
1084 | } |
1085 | EXPORT_SYMBOL(get_random_bytes_arch); |
1086 | |
1087 | |
1088 | /* |
1089 | * init_std_data - initialize pool with system data |
1090 | * |
1091 | * @r: pool to initialize |
1092 | * |
1093 | * This function clears the pool's entropy count and mixes some system |
1094 | * data into the pool to prepare it for use. The pool is not cleared |
1095 | * as that can only decrease the entropy in the pool. |
1096 | */ |
1097 | static void init_std_data(struct entropy_store *r) |
1098 | { |
1099 | int i; |
1100 | ktime_t now = ktime_get_real(); |
1101 | unsigned long rv; |
1102 | |
1103 | r->entropy_count = 0; |
1104 | r->entropy_total = 0; |
1105 | r->last_data_init = false; |
1106 | mix_pool_bytes(r, &now, sizeof(now), NULL); |
1107 | for (i = r->poolinfo->POOLBYTES; i > 0; i -= sizeof(rv)) { |
1108 | if (!arch_get_random_long(&rv)) |
1109 | break; |
1110 | mix_pool_bytes(r, &rv, sizeof(rv), NULL); |
1111 | } |
1112 | mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL); |
1113 | } |
1114 | |
1115 | /* |
1116 | * Note that setup_arch() may call add_device_randomness() |
1117 | * long before we get here. This allows seeding of the pools |
1118 | * with some platform dependent data very early in the boot |
1119 | * process. But it limits our options here. We must use |
1120 | * statically allocated structures that already have all |
1121 | * initializations complete at compile time. We should also |
1122 | * take care not to overwrite the precious per platform data |
1123 | * we were given. |
1124 | */ |
1125 | static int rand_initialize(void) |
1126 | { |
1127 | init_std_data(&input_pool); |
1128 | init_std_data(&blocking_pool); |
1129 | init_std_data(&nonblocking_pool); |
1130 | return 0; |
1131 | } |
1132 | module_init(rand_initialize); |
1133 | |
1134 | #ifdef CONFIG_BLOCK |
1135 | void rand_initialize_disk(struct gendisk *disk) |
1136 | { |
1137 | struct timer_rand_state *state; |
1138 | |
1139 | /* |
1140 | * If kzalloc returns null, we just won't use that entropy |
1141 | * source. |
1142 | */ |
1143 | state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL); |
1144 | if (state) |
1145 | disk->random = state; |
1146 | } |
1147 | #endif |
1148 | |
1149 | static ssize_t |
1150 | random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) |
1151 | { |
1152 | ssize_t n, retval = 0, count = 0; |
1153 | |
1154 | if (nbytes == 0) |
1155 | return 0; |
1156 | |
1157 | while (nbytes > 0) { |
1158 | n = nbytes; |
1159 | if (n > SEC_XFER_SIZE) |
1160 | n = SEC_XFER_SIZE; |
1161 | |
1162 | DEBUG_ENT("reading %zu bits\n", n*8); |
1163 | |
1164 | n = extract_entropy_user(&blocking_pool, buf, n); |
1165 | |
1166 | if (n < 0) { |
1167 | retval = n; |
1168 | break; |
1169 | } |
1170 | |
1171 | DEBUG_ENT("read got %zd bits (%zd still needed)\n", |
1172 | n*8, (nbytes-n)*8); |
1173 | |
1174 | if (n == 0) { |
1175 | if (file->f_flags & O_NONBLOCK) { |
1176 | retval = -EAGAIN; |
1177 | break; |
1178 | } |
1179 | |
1180 | DEBUG_ENT("sleeping?\n"); |
1181 | |
1182 | wait_event_interruptible(random_read_wait, |
1183 | input_pool.entropy_count >= |
1184 | random_read_wakeup_thresh); |
1185 | |
1186 | DEBUG_ENT("awake\n"); |
1187 | |
1188 | if (signal_pending(current)) { |
1189 | retval = -ERESTARTSYS; |
1190 | break; |
1191 | } |
1192 | |
1193 | continue; |
1194 | } |
1195 | |
1196 | count += n; |
1197 | buf += n; |
1198 | nbytes -= n; |
1199 | break; /* This break makes the device work */ |
1200 | /* like a named pipe */ |
1201 | } |
1202 | |
1203 | return (count ? count : retval); |
1204 | } |
1205 | |
1206 | static ssize_t |
1207 | urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) |
1208 | { |
1209 | return extract_entropy_user(&nonblocking_pool, buf, nbytes); |
1210 | } |
1211 | |
1212 | static unsigned int |
1213 | random_poll(struct file *file, poll_table * wait) |
1214 | { |
1215 | unsigned int mask; |
1216 | |
1217 | poll_wait(file, &random_read_wait, wait); |
1218 | poll_wait(file, &random_write_wait, wait); |
1219 | mask = 0; |
1220 | if (input_pool.entropy_count >= random_read_wakeup_thresh) |
1221 | mask |= POLLIN | POLLRDNORM; |
1222 | if (input_pool.entropy_count < random_write_wakeup_thresh) |
1223 | mask |= POLLOUT | POLLWRNORM; |
1224 | return mask; |
1225 | } |
1226 | |
1227 | static int |
1228 | write_pool(struct entropy_store *r, const char __user *buffer, size_t count) |
1229 | { |
1230 | size_t bytes; |
1231 | __u32 buf[16]; |
1232 | const char __user *p = buffer; |
1233 | |
1234 | while (count > 0) { |
1235 | bytes = min(count, sizeof(buf)); |
1236 | if (copy_from_user(&buf, p, bytes)) |
1237 | return -EFAULT; |
1238 | |
1239 | count -= bytes; |
1240 | p += bytes; |
1241 | |
1242 | mix_pool_bytes(r, buf, bytes, NULL); |
1243 | cond_resched(); |
1244 | } |
1245 | |
1246 | return 0; |
1247 | } |
1248 | |
1249 | static ssize_t random_write(struct file *file, const char __user *buffer, |
1250 | size_t count, loff_t *ppos) |
1251 | { |
1252 | size_t ret; |
1253 | |
1254 | ret = write_pool(&blocking_pool, buffer, count); |
1255 | if (ret) |
1256 | return ret; |
1257 | ret = write_pool(&nonblocking_pool, buffer, count); |
1258 | if (ret) |
1259 | return ret; |
1260 | |
1261 | return (ssize_t)count; |
1262 | } |
1263 | |
1264 | static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) |
1265 | { |
1266 | int size, ent_count; |
1267 | int __user *p = (int __user *)arg; |
1268 | int retval; |
1269 | |
1270 | switch (cmd) { |
1271 | case RNDGETENTCNT: |
1272 | /* inherently racy, no point locking */ |
1273 | if (put_user(input_pool.entropy_count, p)) |
1274 | return -EFAULT; |
1275 | return 0; |
1276 | case RNDADDTOENTCNT: |
1277 | if (!capable(CAP_SYS_ADMIN)) |
1278 | return -EPERM; |
1279 | if (get_user(ent_count, p)) |
1280 | return -EFAULT; |
1281 | credit_entropy_bits(&input_pool, ent_count); |
1282 | return 0; |
1283 | case RNDADDENTROPY: |
1284 | if (!capable(CAP_SYS_ADMIN)) |
1285 | return -EPERM; |
1286 | if (get_user(ent_count, p++)) |
1287 | return -EFAULT; |
1288 | if (ent_count < 0) |
1289 | return -EINVAL; |
1290 | if (get_user(size, p++)) |
1291 | return -EFAULT; |
1292 | retval = write_pool(&input_pool, (const char __user *)p, |
1293 | size); |
1294 | if (retval < 0) |
1295 | return retval; |
1296 | credit_entropy_bits(&input_pool, ent_count); |
1297 | return 0; |
1298 | case RNDZAPENTCNT: |
1299 | case RNDCLEARPOOL: |
1300 | /* Clear the entropy pool counters. */ |
1301 | if (!capable(CAP_SYS_ADMIN)) |
1302 | return -EPERM; |
1303 | rand_initialize(); |
1304 | return 0; |
1305 | default: |
1306 | return -EINVAL; |
1307 | } |
1308 | } |
1309 | |
1310 | static int random_fasync(int fd, struct file *filp, int on) |
1311 | { |
1312 | return fasync_helper(fd, filp, on, &fasync); |
1313 | } |
1314 | |
1315 | const struct file_operations random_fops = { |
1316 | .read = random_read, |
1317 | .write = random_write, |
1318 | .poll = random_poll, |
1319 | .unlocked_ioctl = random_ioctl, |
1320 | .fasync = random_fasync, |
1321 | .llseek = noop_llseek, |
1322 | }; |
1323 | |
1324 | const struct file_operations urandom_fops = { |
1325 | .read = urandom_read, |
1326 | .write = random_write, |
1327 | .unlocked_ioctl = random_ioctl, |
1328 | .fasync = random_fasync, |
1329 | .llseek = noop_llseek, |
1330 | }; |
1331 | |
1332 | /*************************************************************** |
1333 | * Random UUID interface |
1334 | * |
1335 | * Used here for a Boot ID, but can be useful for other kernel |
1336 | * drivers. |
1337 | ***************************************************************/ |
1338 | |
1339 | /* |
1340 | * Generate random UUID |
1341 | */ |
1342 | void generate_random_uuid(unsigned char uuid_out[16]) |
1343 | { |
1344 | get_random_bytes(uuid_out, 16); |
1345 | /* Set UUID version to 4 --- truly random generation */ |
1346 | uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40; |
1347 | /* Set the UUID variant to DCE */ |
1348 | uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80; |
1349 | } |
1350 | EXPORT_SYMBOL(generate_random_uuid); |
1351 | |
1352 | /******************************************************************** |
1353 | * |
1354 | * Sysctl interface |
1355 | * |
1356 | ********************************************************************/ |
1357 | |
1358 | #ifdef CONFIG_SYSCTL |
1359 | |
1360 | #include <linux/sysctl.h> |
1361 | |
1362 | static int min_read_thresh = 8, min_write_thresh; |
1363 | static int max_read_thresh = INPUT_POOL_WORDS * 32; |
1364 | static int max_write_thresh = INPUT_POOL_WORDS * 32; |
1365 | static char sysctl_bootid[16]; |
1366 | |
1367 | /* |
1368 | * These functions is used to return both the bootid UUID, and random |
1369 | * UUID. The difference is in whether table->data is NULL; if it is, |
1370 | * then a new UUID is generated and returned to the user. |
1371 | * |
1372 | * If the user accesses this via the proc interface, it will be returned |
1373 | * as an ASCII string in the standard UUID format. If accesses via the |
1374 | * sysctl system call, it is returned as 16 bytes of binary data. |
1375 | */ |
1376 | static int proc_do_uuid(ctl_table *table, int write, |
1377 | void __user *buffer, size_t *lenp, loff_t *ppos) |
1378 | { |
1379 | ctl_table fake_table; |
1380 | unsigned char buf[64], tmp_uuid[16], *uuid; |
1381 | |
1382 | uuid = table->data; |
1383 | if (!uuid) { |
1384 | uuid = tmp_uuid; |
1385 | generate_random_uuid(uuid); |
1386 | } else { |
1387 | static DEFINE_SPINLOCK(bootid_spinlock); |
1388 | |
1389 | spin_lock(&bootid_spinlock); |
1390 | if (!uuid[8]) |
1391 | generate_random_uuid(uuid); |
1392 | spin_unlock(&bootid_spinlock); |
1393 | } |
1394 | |
1395 | sprintf(buf, "%pU", uuid); |
1396 | |
1397 | fake_table.data = buf; |
1398 | fake_table.maxlen = sizeof(buf); |
1399 | |
1400 | return proc_dostring(&fake_table, write, buffer, lenp, ppos); |
1401 | } |
1402 | |
1403 | static int sysctl_poolsize = INPUT_POOL_WORDS * 32; |
1404 | extern ctl_table random_table[]; |
1405 | ctl_table random_table[] = { |
1406 | { |
1407 | .procname = "poolsize", |
1408 | .data = &sysctl_poolsize, |
1409 | .maxlen = sizeof(int), |
1410 | .mode = 0444, |
1411 | .proc_handler = proc_dointvec, |
1412 | }, |
1413 | { |
1414 | .procname = "entropy_avail", |
1415 | .maxlen = sizeof(int), |
1416 | .mode = 0444, |
1417 | .proc_handler = proc_dointvec, |
1418 | .data = &input_pool.entropy_count, |
1419 | }, |
1420 | { |
1421 | .procname = "read_wakeup_threshold", |
1422 | .data = &random_read_wakeup_thresh, |
1423 | .maxlen = sizeof(int), |
1424 | .mode = 0644, |
1425 | .proc_handler = proc_dointvec_minmax, |
1426 | .extra1 = &min_read_thresh, |
1427 | .extra2 = &max_read_thresh, |
1428 | }, |
1429 | { |
1430 | .procname = "write_wakeup_threshold", |
1431 | .data = &random_write_wakeup_thresh, |
1432 | .maxlen = sizeof(int), |
1433 | .mode = 0644, |
1434 | .proc_handler = proc_dointvec_minmax, |
1435 | .extra1 = &min_write_thresh, |
1436 | .extra2 = &max_write_thresh, |
1437 | }, |
1438 | { |
1439 | .procname = "boot_id", |
1440 | .data = &sysctl_bootid, |
1441 | .maxlen = 16, |
1442 | .mode = 0444, |
1443 | .proc_handler = proc_do_uuid, |
1444 | }, |
1445 | { |
1446 | .procname = "uuid", |
1447 | .maxlen = 16, |
1448 | .mode = 0444, |
1449 | .proc_handler = proc_do_uuid, |
1450 | }, |
1451 | { } |
1452 | }; |
1453 | #endif /* CONFIG_SYSCTL */ |
1454 | |
1455 | static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned; |
1456 | |
1457 | static int __init random_int_secret_init(void) |
1458 | { |
1459 | get_random_bytes(random_int_secret, sizeof(random_int_secret)); |
1460 | return 0; |
1461 | } |
1462 | late_initcall(random_int_secret_init); |
1463 | |
1464 | /* |
1465 | * Get a random word for internal kernel use only. Similar to urandom but |
1466 | * with the goal of minimal entropy pool depletion. As a result, the random |
1467 | * value is not cryptographically secure but for several uses the cost of |
1468 | * depleting entropy is too high |
1469 | */ |
1470 | static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash); |
1471 | unsigned int get_random_int(void) |
1472 | { |
1473 | __u32 *hash; |
1474 | unsigned int ret; |
1475 | |
1476 | if (arch_get_random_int(&ret)) |
1477 | return ret; |
1478 | |
1479 | hash = get_cpu_var(get_random_int_hash); |
1480 | |
1481 | hash[0] += current->pid + jiffies + get_cycles(); |
1482 | md5_transform(hash, random_int_secret); |
1483 | ret = hash[0]; |
1484 | put_cpu_var(get_random_int_hash); |
1485 | |
1486 | return ret; |
1487 | } |
1488 | |
1489 | /* |
1490 | * randomize_range() returns a start address such that |
1491 | * |
1492 | * [...... <range> .....] |
1493 | * start end |
1494 | * |
1495 | * a <range> with size "len" starting at the return value is inside in the |
1496 | * area defined by [start, end], but is otherwise randomized. |
1497 | */ |
1498 | unsigned long |
1499 | randomize_range(unsigned long start, unsigned long end, unsigned long len) |
1500 | { |
1501 | unsigned long range = end - len - start; |
1502 | |
1503 | if (end <= start + len) |
1504 | return 0; |
1505 | return PAGE_ALIGN(get_random_int() % range + start); |
1506 | } |
1507 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9