random.c 49 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673
  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. * (now, with legal B.S. out of the way.....)
  43. *
  44. * This routine gathers environmental noise from device drivers, etc.,
  45. * and returns good random numbers, suitable for cryptographic use.
  46. * Besides the obvious cryptographic uses, these numbers are also good
  47. * for seeding TCP sequence numbers, and other places where it is
  48. * desirable to have numbers which are not only random, but hard to
  49. * predict by an attacker.
  50. *
  51. * Theory of operation
  52. * ===================
  53. *
  54. * Computers are very predictable devices. Hence it is extremely hard
  55. * to produce truly random numbers on a computer --- as opposed to
  56. * pseudo-random numbers, which can easily generated by using a
  57. * algorithm. Unfortunately, it is very easy for attackers to guess
  58. * the sequence of pseudo-random number generators, and for some
  59. * applications this is not acceptable. So instead, we must try to
  60. * gather "environmental noise" from the computer's environment, which
  61. * must be hard for outside attackers to observe, and use that to
  62. * generate random numbers. In a Unix environment, this is best done
  63. * from inside the kernel.
  64. *
  65. * Sources of randomness from the environment include inter-keyboard
  66. * timings, inter-interrupt timings from some interrupts, and other
  67. * events which are both (a) non-deterministic and (b) hard for an
  68. * outside observer to measure. Randomness from these sources are
  69. * added to an "entropy pool", which is mixed using a CRC-like function.
  70. * This is not cryptographically strong, but it is adequate assuming
  71. * the randomness is not chosen maliciously, and it is fast enough that
  72. * the overhead of doing it on every interrupt is very reasonable.
  73. * As random bytes are mixed into the entropy pool, the routines keep
  74. * an *estimate* of how many bits of randomness have been stored into
  75. * the random number generator's internal state.
  76. *
  77. * When random bytes are desired, they are obtained by taking the SHA
  78. * hash of the contents of the "entropy pool". The SHA hash avoids
  79. * exposing the internal state of the entropy pool. It is believed to
  80. * be computationally infeasible to derive any useful information
  81. * about the input of SHA from its output. Even if it is possible to
  82. * analyze SHA in some clever way, as long as the amount of data
  83. * returned from the generator is less than the inherent entropy in
  84. * the pool, the output data is totally unpredictable. For this
  85. * reason, the routine decreases its internal estimate of how many
  86. * bits of "true randomness" are contained in the entropy pool as it
  87. * outputs random numbers.
  88. *
  89. * If this estimate goes to zero, the routine can still generate
  90. * random numbers; however, an attacker may (at least in theory) be
  91. * able to infer the future output of the generator from prior
  92. * outputs. This requires successful cryptanalysis of SHA, which is
  93. * not believed to be feasible, but there is a remote possibility.
  94. * Nonetheless, these numbers should be useful for the vast majority
  95. * of purposes.
  96. *
  97. * Exported interfaces ---- output
  98. * ===============================
  99. *
  100. * There are three exported interfaces; the first is one designed to
  101. * be used from within the kernel:
  102. *
  103. * void get_random_bytes(void *buf, int nbytes);
  104. *
  105. * This interface will return the requested number of random bytes,
  106. * and place it in the requested buffer.
  107. *
  108. * The two other interfaces are two character devices /dev/random and
  109. * /dev/urandom. /dev/random is suitable for use when very high
  110. * quality randomness is desired (for example, for key generation or
  111. * one-time pads), as it will only return a maximum of the number of
  112. * bits of randomness (as estimated by the random number generator)
  113. * contained in the entropy pool.
  114. *
  115. * The /dev/urandom device does not have this limit, and will return
  116. * as many bytes as are requested. As more and more random bytes are
  117. * requested without giving time for the entropy pool to recharge,
  118. * this will result in random numbers that are merely cryptographically
  119. * strong. For many applications, however, this is acceptable.
  120. *
  121. * Exported interfaces ---- input
  122. * ==============================
  123. *
  124. * The current exported interfaces for gathering environmental noise
  125. * from the devices are:
  126. *
  127. * void add_input_randomness(unsigned int type, unsigned int code,
  128. * unsigned int value);
  129. * void add_interrupt_randomness(int irq);
  130. *
  131. * add_input_randomness() uses the input layer interrupt timing, as well as
  132. * the event type information from the hardware.
  133. *
  134. * add_interrupt_randomness() uses the inter-interrupt timing as random
  135. * inputs to the entropy pool. Note that not all interrupts are good
  136. * sources of randomness! For example, the timer interrupts is not a
  137. * good choice, because the periodicity of the interrupts is too
  138. * regular, and hence predictable to an attacker. Disk interrupts are
  139. * a better measure, since the timing of the disk interrupts are more
  140. * unpredictable.
  141. *
  142. * All of these routines try to estimate how many bits of randomness a
  143. * particular randomness source. They do this by keeping track of the
  144. * first and second order deltas of the event timings.
  145. *
  146. * Ensuring unpredictability at system startup
  147. * ============================================
  148. *
  149. * When any operating system starts up, it will go through a sequence
  150. * of actions that are fairly predictable by an adversary, especially
  151. * if the start-up does not involve interaction with a human operator.
  152. * This reduces the actual number of bits of unpredictability in the
  153. * entropy pool below the value in entropy_count. In order to
  154. * counteract this effect, it helps to carry information in the
  155. * entropy pool across shut-downs and start-ups. To do this, put the
  156. * following lines an appropriate script which is run during the boot
  157. * sequence:
  158. *
  159. * echo "Initializing random number generator..."
  160. * random_seed=/var/run/random-seed
  161. * # Carry a random seed from start-up to start-up
  162. * # Load and then save the whole entropy pool
  163. * if [ -f $random_seed ]; then
  164. * cat $random_seed >/dev/urandom
  165. * else
  166. * touch $random_seed
  167. * fi
  168. * chmod 600 $random_seed
  169. * dd if=/dev/urandom of=$random_seed count=1 bs=512
  170. *
  171. * and the following lines in an appropriate script which is run as
  172. * the system is shutdown:
  173. *
  174. * # Carry a random seed from shut-down to start-up
  175. * # Save the whole entropy pool
  176. * echo "Saving random seed..."
  177. * random_seed=/var/run/random-seed
  178. * touch $random_seed
  179. * chmod 600 $random_seed
  180. * dd if=/dev/urandom of=$random_seed count=1 bs=512
  181. *
  182. * For example, on most modern systems using the System V init
  183. * scripts, such code fragments would be found in
  184. * /etc/rc.d/init.d/random. On older Linux systems, the correct script
  185. * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0.
  186. *
  187. * Effectively, these commands cause the contents of the entropy pool
  188. * to be saved at shut-down time and reloaded into the entropy pool at
  189. * start-up. (The 'dd' in the addition to the bootup script is to
  190. * make sure that /etc/random-seed is different for every start-up,
  191. * even if the system crashes without executing rc.0.) Even with
  192. * complete knowledge of the start-up activities, predicting the state
  193. * of the entropy pool requires knowledge of the previous history of
  194. * the system.
  195. *
  196. * Configuring the /dev/random driver under Linux
  197. * ==============================================
  198. *
  199. * The /dev/random driver under Linux uses minor numbers 8 and 9 of
  200. * the /dev/mem major number (#1). So if your system does not have
  201. * /dev/random and /dev/urandom created already, they can be created
  202. * by using the commands:
  203. *
  204. * mknod /dev/random c 1 8
  205. * mknod /dev/urandom c 1 9
  206. *
  207. * Acknowledgements:
  208. * =================
  209. *
  210. * Ideas for constructing this random number generator were derived
  211. * from Pretty Good Privacy's random number generator, and from private
  212. * discussions with Phil Karn. Colin Plumb provided a faster random
  213. * number generator, which speed up the mixing function of the entropy
  214. * pool, taken from PGPfone. Dale Worley has also contributed many
  215. * useful ideas and suggestions to improve this driver.
  216. *
  217. * Any flaws in the design are solely my responsibility, and should
  218. * not be attributed to the Phil, Colin, or any of authors of PGP.
  219. *
  220. * Further background information on this topic may be obtained from
  221. * RFC 1750, "Randomness Recommendations for Security", by Donald
  222. * Eastlake, Steve Crocker, and Jeff Schiller.
  223. */
  224. #include <linux/utsname.h>
  225. #include <linux/module.h>
  226. #include <linux/kernel.h>
  227. #include <linux/major.h>
  228. #include <linux/string.h>
  229. #include <linux/fcntl.h>
  230. #include <linux/slab.h>
  231. #include <linux/random.h>
  232. #include <linux/poll.h>
  233. #include <linux/init.h>
  234. #include <linux/fs.h>
  235. #include <linux/genhd.h>
  236. #include <linux/interrupt.h>
  237. #include <linux/spinlock.h>
  238. #include <linux/percpu.h>
  239. #include <linux/cryptohash.h>
  240. #include <asm/processor.h>
  241. #include <asm/uaccess.h>
  242. #include <asm/irq.h>
  243. #include <asm/io.h>
  244. /*
  245. * Configuration information
  246. */
  247. #define INPUT_POOL_WORDS 128
  248. #define OUTPUT_POOL_WORDS 32
  249. #define SEC_XFER_SIZE 512
  250. /*
  251. * The minimum number of bits of entropy before we wake up a read on
  252. * /dev/random. Should be enough to do a significant reseed.
  253. */
  254. static int random_read_wakeup_thresh = 64;
  255. /*
  256. * If the entropy count falls under this number of bits, then we
  257. * should wake up processes which are selecting or polling on write
  258. * access to /dev/random.
  259. */
  260. static int random_write_wakeup_thresh = 128;
  261. /*
  262. * When the input pool goes over trickle_thresh, start dropping most
  263. * samples to avoid wasting CPU time and reduce lock contention.
  264. */
  265. static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;
  266. static DEFINE_PER_CPU(int, trickle_count) = 0;
  267. /*
  268. * A pool of size .poolwords is stirred with a primitive polynomial
  269. * of degree .poolwords over GF(2). The taps for various sizes are
  270. * defined below. They are chosen to be evenly spaced (minimum RMS
  271. * distance from evenly spaced; the numbers in the comments are a
  272. * scaled squared error sum) except for the last tap, which is 1 to
  273. * get the twisting happening as fast as possible.
  274. */
  275. static struct poolinfo {
  276. int poolwords;
  277. int tap1, tap2, tap3, tap4, tap5;
  278. } poolinfo_table[] = {
  279. /* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
  280. { 128, 103, 76, 51, 25, 1 },
  281. /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
  282. { 32, 26, 20, 14, 7, 1 },
  283. #if 0
  284. /* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */
  285. { 2048, 1638, 1231, 819, 411, 1 },
  286. /* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
  287. { 1024, 817, 615, 412, 204, 1 },
  288. /* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
  289. { 1024, 819, 616, 410, 207, 2 },
  290. /* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
  291. { 512, 411, 308, 208, 104, 1 },
  292. /* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
  293. { 512, 409, 307, 206, 102, 2 },
  294. /* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */
  295. { 512, 409, 309, 205, 103, 2 },
  296. /* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
  297. { 256, 205, 155, 101, 52, 1 },
  298. /* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
  299. { 128, 103, 78, 51, 27, 2 },
  300. /* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */
  301. { 64, 52, 39, 26, 14, 1 },
  302. #endif
  303. };
  304. #define POOLBITS poolwords*32
  305. #define POOLBYTES poolwords*4
  306. /*
  307. * For the purposes of better mixing, we use the CRC-32 polynomial as
  308. * well to make a twisted Generalized Feedback Shift Reigster
  309. *
  310. * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM
  311. * Transactions on Modeling and Computer Simulation 2(3):179-194.
  312. * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators
  313. * II. ACM Transactions on Mdeling and Computer Simulation 4:254-266)
  314. *
  315. * Thanks to Colin Plumb for suggesting this.
  316. *
  317. * We have not analyzed the resultant polynomial to prove it primitive;
  318. * in fact it almost certainly isn't. Nonetheless, the irreducible factors
  319. * of a random large-degree polynomial over GF(2) are more than large enough
  320. * that periodicity is not a concern.
  321. *
  322. * The input hash is much less sensitive than the output hash. All
  323. * that we want of it is that it be a good non-cryptographic hash;
  324. * i.e. it not produce collisions when fed "random" data of the sort
  325. * we expect to see. As long as the pool state differs for different
  326. * inputs, we have preserved the input entropy and done a good job.
  327. * The fact that an intelligent attacker can construct inputs that
  328. * will produce controlled alterations to the pool's state is not
  329. * important because we don't consider such inputs to contribute any
  330. * randomness. The only property we need with respect to them is that
  331. * the attacker can't increase his/her knowledge of the pool's state.
  332. * Since all additions are reversible (knowing the final state and the
  333. * input, you can reconstruct the initial state), if an attacker has
  334. * any uncertainty about the initial state, he/she can only shuffle
  335. * that uncertainty about, but never cause any collisions (which would
  336. * decrease the uncertainty).
  337. *
  338. * The chosen system lets the state of the pool be (essentially) the input
  339. * modulo the generator polymnomial. Now, for random primitive polynomials,
  340. * this is a universal class of hash functions, meaning that the chance
  341. * of a collision is limited by the attacker's knowledge of the generator
  342. * polynomail, so if it is chosen at random, an attacker can never force
  343. * a collision. Here, we use a fixed polynomial, but we *can* assume that
  344. * ###--> it is unknown to the processes generating the input entropy. <-###
  345. * Because of this important property, this is a good, collision-resistant
  346. * hash; hash collisions will occur no more often than chance.
  347. */
  348. /*
  349. * Static global variables
  350. */
  351. static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
  352. static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
  353. #if 0
  354. static int debug = 0;
  355. module_param(debug, bool, 0644);
  356. #define DEBUG_ENT(fmt, arg...) do { if (debug) \
  357. printk(KERN_DEBUG "random %04d %04d %04d: " \
  358. fmt,\
  359. input_pool.entropy_count,\
  360. blocking_pool.entropy_count,\
  361. nonblocking_pool.entropy_count,\
  362. ## arg); } while (0)
  363. #else
  364. #define DEBUG_ENT(fmt, arg...) do {} while (0)
  365. #endif
  366. /**********************************************************************
  367. *
  368. * OS independent entropy store. Here are the functions which handle
  369. * storing entropy in an entropy pool.
  370. *
  371. **********************************************************************/
  372. struct entropy_store;
  373. struct entropy_store {
  374. /* mostly-read data: */
  375. struct poolinfo *poolinfo;
  376. __u32 *pool;
  377. const char *name;
  378. int limit;
  379. struct entropy_store *pull;
  380. /* read-write data: */
  381. spinlock_t lock ____cacheline_aligned_in_smp;
  382. unsigned add_ptr;
  383. int entropy_count;
  384. int input_rotate;
  385. };
  386. static __u32 input_pool_data[INPUT_POOL_WORDS];
  387. static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
  388. static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
  389. static struct entropy_store input_pool = {
  390. .poolinfo = &poolinfo_table[0],
  391. .name = "input",
  392. .limit = 1,
  393. .lock = __SPIN_LOCK_UNLOCKED(&input_pool.lock),
  394. .pool = input_pool_data
  395. };
  396. static struct entropy_store blocking_pool = {
  397. .poolinfo = &poolinfo_table[1],
  398. .name = "blocking",
  399. .limit = 1,
  400. .pull = &input_pool,
  401. .lock = __SPIN_LOCK_UNLOCKED(&blocking_pool.lock),
  402. .pool = blocking_pool_data
  403. };
  404. static struct entropy_store nonblocking_pool = {
  405. .poolinfo = &poolinfo_table[1],
  406. .name = "nonblocking",
  407. .pull = &input_pool,
  408. .lock = __SPIN_LOCK_UNLOCKED(&nonblocking_pool.lock),
  409. .pool = nonblocking_pool_data
  410. };
  411. /*
  412. * This function adds a byte into the entropy "pool". It does not
  413. * update the entropy estimate. The caller should call
  414. * credit_entropy_store if this is appropriate.
  415. *
  416. * The pool is stirred with a primitive polynomial of the appropriate
  417. * degree, and then twisted. We twist by three bits at a time because
  418. * it's cheap to do so and helps slightly in the expected case where
  419. * the entropy is concentrated in the low-order bits.
  420. */
  421. static void __add_entropy_words(struct entropy_store *r, const __u32 *in,
  422. int nwords, __u32 out[16])
  423. {
  424. static __u32 const twist_table[8] = {
  425. 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
  426. 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
  427. unsigned long i, add_ptr, tap1, tap2, tap3, tap4, tap5;
  428. int new_rotate, input_rotate;
  429. int wordmask = r->poolinfo->poolwords - 1;
  430. __u32 w, next_w;
  431. unsigned long flags;
  432. /* Taps are constant, so we can load them without holding r->lock. */
  433. tap1 = r->poolinfo->tap1;
  434. tap2 = r->poolinfo->tap2;
  435. tap3 = r->poolinfo->tap3;
  436. tap4 = r->poolinfo->tap4;
  437. tap5 = r->poolinfo->tap5;
  438. next_w = *in++;
  439. spin_lock_irqsave(&r->lock, flags);
  440. prefetch_range(r->pool, wordmask);
  441. input_rotate = r->input_rotate;
  442. add_ptr = r->add_ptr;
  443. while (nwords--) {
  444. w = rol32(next_w, input_rotate);
  445. if (nwords > 0)
  446. next_w = *in++;
  447. i = add_ptr = (add_ptr - 1) & wordmask;
  448. /*
  449. * Normally, we add 7 bits of rotation to the pool.
  450. * At the beginning of the pool, add an extra 7 bits
  451. * rotation, so that successive passes spread the
  452. * input bits across the pool evenly.
  453. */
  454. new_rotate = input_rotate + 14;
  455. if (i)
  456. new_rotate = input_rotate + 7;
  457. input_rotate = new_rotate & 31;
  458. /* XOR in the various taps */
  459. w ^= r->pool[(i + tap1) & wordmask];
  460. w ^= r->pool[(i + tap2) & wordmask];
  461. w ^= r->pool[(i + tap3) & wordmask];
  462. w ^= r->pool[(i + tap4) & wordmask];
  463. w ^= r->pool[(i + tap5) & wordmask];
  464. w ^= r->pool[i];
  465. r->pool[i] = (w >> 3) ^ twist_table[w & 7];
  466. }
  467. r->input_rotate = input_rotate;
  468. r->add_ptr = add_ptr;
  469. if (out) {
  470. for (i = 0; i < 16; i++) {
  471. out[i] = r->pool[add_ptr];
  472. add_ptr = (add_ptr - 1) & wordmask;
  473. }
  474. }
  475. spin_unlock_irqrestore(&r->lock, flags);
  476. }
  477. static inline void add_entropy_words(struct entropy_store *r, const __u32 *in,
  478. int nwords)
  479. {
  480. __add_entropy_words(r, in, nwords, NULL);
  481. }
  482. /*
  483. * Credit (or debit) the entropy store with n bits of entropy
  484. */
  485. static void credit_entropy_store(struct entropy_store *r, int nbits)
  486. {
  487. unsigned long flags;
  488. spin_lock_irqsave(&r->lock, flags);
  489. if (r->entropy_count + nbits < 0) {
  490. DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
  491. r->entropy_count, nbits);
  492. r->entropy_count = 0;
  493. } else if (r->entropy_count + nbits > r->poolinfo->POOLBITS) {
  494. r->entropy_count = r->poolinfo->POOLBITS;
  495. } else {
  496. r->entropy_count += nbits;
  497. if (nbits)
  498. DEBUG_ENT("added %d entropy credits to %s\n",
  499. nbits, r->name);
  500. }
  501. spin_unlock_irqrestore(&r->lock, flags);
  502. }
  503. /*********************************************************************
  504. *
  505. * Entropy input management
  506. *
  507. *********************************************************************/
  508. /* There is one of these per entropy source */
  509. struct timer_rand_state {
  510. cycles_t last_time;
  511. long last_delta,last_delta2;
  512. unsigned dont_count_entropy:1;
  513. };
  514. static struct timer_rand_state input_timer_state;
  515. static struct timer_rand_state *irq_timer_state[NR_IRQS];
  516. /*
  517. * This function adds entropy to the entropy "pool" by using timing
  518. * delays. It uses the timer_rand_state structure to make an estimate
  519. * of how many bits of entropy this call has added to the pool.
  520. *
  521. * The number "num" is also added to the pool - it should somehow describe
  522. * the type of event which just happened. This is currently 0-255 for
  523. * keyboard scan codes, and 256 upwards for interrupts.
  524. *
  525. */
  526. static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
  527. {
  528. struct {
  529. cycles_t cycles;
  530. long jiffies;
  531. unsigned num;
  532. } sample;
  533. long delta, delta2, delta3;
  534. preempt_disable();
  535. /* if over the trickle threshold, use only 1 in 4096 samples */
  536. if (input_pool.entropy_count > trickle_thresh &&
  537. (__get_cpu_var(trickle_count)++ & 0xfff))
  538. goto out;
  539. sample.jiffies = jiffies;
  540. sample.cycles = get_cycles();
  541. sample.num = num;
  542. add_entropy_words(&input_pool, (u32 *)&sample, sizeof(sample)/4);
  543. /*
  544. * Calculate number of bits of randomness we probably added.
  545. * We take into account the first, second and third-order deltas
  546. * in order to make our estimate.
  547. */
  548. if (!state->dont_count_entropy) {
  549. delta = sample.jiffies - state->last_time;
  550. state->last_time = sample.jiffies;
  551. delta2 = delta - state->last_delta;
  552. state->last_delta = delta;
  553. delta3 = delta2 - state->last_delta2;
  554. state->last_delta2 = delta2;
  555. if (delta < 0)
  556. delta = -delta;
  557. if (delta2 < 0)
  558. delta2 = -delta2;
  559. if (delta3 < 0)
  560. delta3 = -delta3;
  561. if (delta > delta2)
  562. delta = delta2;
  563. if (delta > delta3)
  564. delta = delta3;
  565. /*
  566. * delta is now minimum absolute delta.
  567. * Round down by 1 bit on general principles,
  568. * and limit entropy entimate to 12 bits.
  569. */
  570. credit_entropy_store(&input_pool,
  571. min_t(int, fls(delta>>1), 11));
  572. }
  573. if(input_pool.entropy_count >= random_read_wakeup_thresh)
  574. wake_up_interruptible(&random_read_wait);
  575. out:
  576. preempt_enable();
  577. }
  578. void add_input_randomness(unsigned int type, unsigned int code,
  579. unsigned int value)
  580. {
  581. static unsigned char last_value;
  582. /* ignore autorepeat and the like */
  583. if (value == last_value)
  584. return;
  585. DEBUG_ENT("input event\n");
  586. last_value = value;
  587. add_timer_randomness(&input_timer_state,
  588. (type << 4) ^ code ^ (code >> 4) ^ value);
  589. }
  590. EXPORT_SYMBOL_GPL(add_input_randomness);
  591. void add_interrupt_randomness(int irq)
  592. {
  593. if (irq >= NR_IRQS || irq_timer_state[irq] == 0)
  594. return;
  595. DEBUG_ENT("irq event %d\n", irq);
  596. add_timer_randomness(irq_timer_state[irq], 0x100 + irq);
  597. }
  598. #ifdef CONFIG_BLOCK
  599. void add_disk_randomness(struct gendisk *disk)
  600. {
  601. if (!disk || !disk->random)
  602. return;
  603. /* first major is 1, so we get >= 0x200 here */
  604. DEBUG_ENT("disk event %d:%d\n", disk->major, disk->first_minor);
  605. add_timer_randomness(disk->random,
  606. 0x100 + MKDEV(disk->major, disk->first_minor));
  607. }
  608. EXPORT_SYMBOL(add_disk_randomness);
  609. #endif
  610. #define EXTRACT_SIZE 10
  611. /*********************************************************************
  612. *
  613. * Entropy extraction routines
  614. *
  615. *********************************************************************/
  616. static ssize_t extract_entropy(struct entropy_store *r, void * buf,
  617. size_t nbytes, int min, int rsvd);
  618. /*
  619. * This utility inline function is responsible for transfering entropy
  620. * from the primary pool to the secondary extraction pool. We make
  621. * sure we pull enough for a 'catastrophic reseed'.
  622. */
  623. static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
  624. {
  625. __u32 tmp[OUTPUT_POOL_WORDS];
  626. if (r->pull && r->entropy_count < nbytes * 8 &&
  627. r->entropy_count < r->poolinfo->POOLBITS) {
  628. int bytes = max_t(int, random_read_wakeup_thresh / 8,
  629. min_t(int, nbytes, sizeof(tmp)));
  630. int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
  631. DEBUG_ENT("going to reseed %s with %d bits "
  632. "(%d of %d requested)\n",
  633. r->name, bytes * 8, nbytes * 8, r->entropy_count);
  634. bytes=extract_entropy(r->pull, tmp, bytes,
  635. random_read_wakeup_thresh / 8, rsvd);
  636. add_entropy_words(r, tmp, (bytes + 3) / 4);
  637. credit_entropy_store(r, bytes*8);
  638. }
  639. }
  640. /*
  641. * These functions extracts randomness from the "entropy pool", and
  642. * returns it in a buffer.
  643. *
  644. * The min parameter specifies the minimum amount we can pull before
  645. * failing to avoid races that defeat catastrophic reseeding while the
  646. * reserved parameter indicates how much entropy we must leave in the
  647. * pool after each pull to avoid starving other readers.
  648. *
  649. * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
  650. */
  651. static size_t account(struct entropy_store *r, size_t nbytes, int min,
  652. int reserved)
  653. {
  654. unsigned long flags;
  655. BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
  656. /* Hold lock while accounting */
  657. spin_lock_irqsave(&r->lock, flags);
  658. DEBUG_ENT("trying to extract %d bits from %s\n",
  659. nbytes * 8, r->name);
  660. /* Can we pull enough? */
  661. if (r->entropy_count / 8 < min + reserved) {
  662. nbytes = 0;
  663. } else {
  664. /* If limited, never pull more than available */
  665. if (r->limit && nbytes + reserved >= r->entropy_count / 8)
  666. nbytes = r->entropy_count/8 - reserved;
  667. if(r->entropy_count / 8 >= nbytes + reserved)
  668. r->entropy_count -= nbytes*8;
  669. else
  670. r->entropy_count = reserved;
  671. if (r->entropy_count < random_write_wakeup_thresh)
  672. wake_up_interruptible(&random_write_wait);
  673. }
  674. DEBUG_ENT("debiting %d entropy credits from %s%s\n",
  675. nbytes * 8, r->name, r->limit ? "" : " (unlimited)");
  676. spin_unlock_irqrestore(&r->lock, flags);
  677. return nbytes;
  678. }
  679. static void extract_buf(struct entropy_store *r, __u8 *out)
  680. {
  681. int i;
  682. __u32 data[16], buf[5 + SHA_WORKSPACE_WORDS];
  683. sha_init(buf);
  684. /*
  685. * As we hash the pool, we mix intermediate values of
  686. * the hash back into the pool. This eliminates
  687. * backtracking attacks (where the attacker knows
  688. * the state of the pool plus the current outputs, and
  689. * attempts to find previous ouputs), unless the hash
  690. * function can be inverted.
  691. */
  692. for (i = 0; i < r->poolinfo->poolwords; i += 16) {
  693. /* hash blocks of 16 words = 512 bits */
  694. sha_transform(buf, (__u8 *)(r->pool + i), buf + 5);
  695. /* feed back portion of the resulting hash */
  696. add_entropy_words(r, &buf[i % 5], 1);
  697. }
  698. /*
  699. * To avoid duplicates, we atomically extract a
  700. * portion of the pool while mixing, and hash one
  701. * final time.
  702. */
  703. __add_entropy_words(r, &buf[i % 5], 1, data);
  704. sha_transform(buf, (__u8 *)data, buf + 5);
  705. /*
  706. * In case the hash function has some recognizable
  707. * output pattern, we fold it in half.
  708. */
  709. buf[0] ^= buf[3];
  710. buf[1] ^= buf[4];
  711. buf[0] ^= rol32(buf[3], 16);
  712. memcpy(out, buf, EXTRACT_SIZE);
  713. memset(buf, 0, sizeof(buf));
  714. }
  715. static ssize_t extract_entropy(struct entropy_store *r, void * buf,
  716. size_t nbytes, int min, int reserved)
  717. {
  718. ssize_t ret = 0, i;
  719. __u8 tmp[EXTRACT_SIZE];
  720. xfer_secondary_pool(r, nbytes);
  721. nbytes = account(r, nbytes, min, reserved);
  722. while (nbytes) {
  723. extract_buf(r, tmp);
  724. i = min_t(int, nbytes, EXTRACT_SIZE);
  725. memcpy(buf, tmp, i);
  726. nbytes -= i;
  727. buf += i;
  728. ret += i;
  729. }
  730. /* Wipe data just returned from memory */
  731. memset(tmp, 0, sizeof(tmp));
  732. return ret;
  733. }
  734. static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
  735. size_t nbytes)
  736. {
  737. ssize_t ret = 0, i;
  738. __u8 tmp[EXTRACT_SIZE];
  739. xfer_secondary_pool(r, nbytes);
  740. nbytes = account(r, nbytes, 0, 0);
  741. while (nbytes) {
  742. if (need_resched()) {
  743. if (signal_pending(current)) {
  744. if (ret == 0)
  745. ret = -ERESTARTSYS;
  746. break;
  747. }
  748. schedule();
  749. }
  750. extract_buf(r, tmp);
  751. i = min_t(int, nbytes, EXTRACT_SIZE);
  752. if (copy_to_user(buf, tmp, i)) {
  753. ret = -EFAULT;
  754. break;
  755. }
  756. nbytes -= i;
  757. buf += i;
  758. ret += i;
  759. }
  760. /* Wipe data just returned from memory */
  761. memset(tmp, 0, sizeof(tmp));
  762. return ret;
  763. }
  764. /*
  765. * This function is the exported kernel interface. It returns some
  766. * number of good random numbers, suitable for seeding TCP sequence
  767. * numbers, etc.
  768. */
  769. void get_random_bytes(void *buf, int nbytes)
  770. {
  771. extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0);
  772. }
  773. EXPORT_SYMBOL(get_random_bytes);
  774. /*
  775. * init_std_data - initialize pool with system data
  776. *
  777. * @r: pool to initialize
  778. *
  779. * This function clears the pool's entropy count and mixes some system
  780. * data into the pool to prepare it for use. The pool is not cleared
  781. * as that can only decrease the entropy in the pool.
  782. */
  783. static void init_std_data(struct entropy_store *r)
  784. {
  785. struct timeval tv;
  786. unsigned long flags;
  787. spin_lock_irqsave(&r->lock, flags);
  788. r->entropy_count = 0;
  789. spin_unlock_irqrestore(&r->lock, flags);
  790. do_gettimeofday(&tv);
  791. add_entropy_words(r, (__u32 *)&tv, sizeof(tv)/4);
  792. add_entropy_words(r, (__u32 *)utsname(),
  793. sizeof(*(utsname()))/4);
  794. }
  795. static int __init rand_initialize(void)
  796. {
  797. init_std_data(&input_pool);
  798. init_std_data(&blocking_pool);
  799. init_std_data(&nonblocking_pool);
  800. return 0;
  801. }
  802. module_init(rand_initialize);
  803. void rand_initialize_irq(int irq)
  804. {
  805. struct timer_rand_state *state;
  806. if (irq >= NR_IRQS || irq_timer_state[irq])
  807. return;
  808. /*
  809. * If kmalloc returns null, we just won't use that entropy
  810. * source.
  811. */
  812. state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
  813. if (state) {
  814. memset(state, 0, sizeof(struct timer_rand_state));
  815. irq_timer_state[irq] = state;
  816. }
  817. }
  818. #ifdef CONFIG_BLOCK
  819. void rand_initialize_disk(struct gendisk *disk)
  820. {
  821. struct timer_rand_state *state;
  822. /*
  823. * If kmalloc returns null, we just won't use that entropy
  824. * source.
  825. */
  826. state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
  827. if (state) {
  828. memset(state, 0, sizeof(struct timer_rand_state));
  829. disk->random = state;
  830. }
  831. }
  832. #endif
  833. static ssize_t
  834. random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos)
  835. {
  836. ssize_t n, retval = 0, count = 0;
  837. if (nbytes == 0)
  838. return 0;
  839. while (nbytes > 0) {
  840. n = nbytes;
  841. if (n > SEC_XFER_SIZE)
  842. n = SEC_XFER_SIZE;
  843. DEBUG_ENT("reading %d bits\n", n*8);
  844. n = extract_entropy_user(&blocking_pool, buf, n);
  845. DEBUG_ENT("read got %d bits (%d still needed)\n",
  846. n*8, (nbytes-n)*8);
  847. if (n == 0) {
  848. if (file->f_flags & O_NONBLOCK) {
  849. retval = -EAGAIN;
  850. break;
  851. }
  852. DEBUG_ENT("sleeping?\n");
  853. wait_event_interruptible(random_read_wait,
  854. input_pool.entropy_count >=
  855. random_read_wakeup_thresh);
  856. DEBUG_ENT("awake\n");
  857. if (signal_pending(current)) {
  858. retval = -ERESTARTSYS;
  859. break;
  860. }
  861. continue;
  862. }
  863. if (n < 0) {
  864. retval = n;
  865. break;
  866. }
  867. count += n;
  868. buf += n;
  869. nbytes -= n;
  870. break; /* This break makes the device work */
  871. /* like a named pipe */
  872. }
  873. /*
  874. * If we gave the user some bytes, update the access time.
  875. */
  876. if (count)
  877. file_accessed(file);
  878. return (count ? count : retval);
  879. }
  880. static ssize_t
  881. urandom_read(struct file * file, char __user * buf,
  882. size_t nbytes, loff_t *ppos)
  883. {
  884. return extract_entropy_user(&nonblocking_pool, buf, nbytes);
  885. }
  886. static unsigned int
  887. random_poll(struct file *file, poll_table * wait)
  888. {
  889. unsigned int mask;
  890. poll_wait(file, &random_read_wait, wait);
  891. poll_wait(file, &random_write_wait, wait);
  892. mask = 0;
  893. if (input_pool.entropy_count >= random_read_wakeup_thresh)
  894. mask |= POLLIN | POLLRDNORM;
  895. if (input_pool.entropy_count < random_write_wakeup_thresh)
  896. mask |= POLLOUT | POLLWRNORM;
  897. return mask;
  898. }
  899. static int
  900. write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
  901. {
  902. size_t bytes;
  903. __u32 buf[16];
  904. const char __user *p = buffer;
  905. while (count > 0) {
  906. bytes = min(count, sizeof(buf));
  907. if (copy_from_user(&buf, p, bytes))
  908. return -EFAULT;
  909. count -= bytes;
  910. p += bytes;
  911. add_entropy_words(r, buf, (bytes + 3) / 4);
  912. }
  913. return 0;
  914. }
  915. static ssize_t
  916. random_write(struct file * file, const char __user * buffer,
  917. size_t count, loff_t *ppos)
  918. {
  919. size_t ret;
  920. struct inode *inode = file->f_path.dentry->d_inode;
  921. ret = write_pool(&blocking_pool, buffer, count);
  922. if (ret)
  923. return ret;
  924. ret = write_pool(&nonblocking_pool, buffer, count);
  925. if (ret)
  926. return ret;
  927. inode->i_mtime = current_fs_time(inode->i_sb);
  928. mark_inode_dirty(inode);
  929. return (ssize_t)count;
  930. }
  931. static int
  932. random_ioctl(struct inode * inode, struct file * file,
  933. unsigned int cmd, unsigned long arg)
  934. {
  935. int size, ent_count;
  936. int __user *p = (int __user *)arg;
  937. int retval;
  938. switch (cmd) {
  939. case RNDGETENTCNT:
  940. ent_count = input_pool.entropy_count;
  941. if (put_user(ent_count, p))
  942. return -EFAULT;
  943. return 0;
  944. case RNDADDTOENTCNT:
  945. if (!capable(CAP_SYS_ADMIN))
  946. return -EPERM;
  947. if (get_user(ent_count, p))
  948. return -EFAULT;
  949. credit_entropy_store(&input_pool, ent_count);
  950. /*
  951. * Wake up waiting processes if we have enough
  952. * entropy.
  953. */
  954. if (input_pool.entropy_count >= random_read_wakeup_thresh)
  955. wake_up_interruptible(&random_read_wait);
  956. return 0;
  957. case RNDADDENTROPY:
  958. if (!capable(CAP_SYS_ADMIN))
  959. return -EPERM;
  960. if (get_user(ent_count, p++))
  961. return -EFAULT;
  962. if (ent_count < 0)
  963. return -EINVAL;
  964. if (get_user(size, p++))
  965. return -EFAULT;
  966. retval = write_pool(&input_pool, (const char __user *)p,
  967. size);
  968. if (retval < 0)
  969. return retval;
  970. credit_entropy_store(&input_pool, ent_count);
  971. /*
  972. * Wake up waiting processes if we have enough
  973. * entropy.
  974. */
  975. if (input_pool.entropy_count >= random_read_wakeup_thresh)
  976. wake_up_interruptible(&random_read_wait);
  977. return 0;
  978. case RNDZAPENTCNT:
  979. case RNDCLEARPOOL:
  980. /* Clear the entropy pool counters. */
  981. if (!capable(CAP_SYS_ADMIN))
  982. return -EPERM;
  983. init_std_data(&input_pool);
  984. init_std_data(&blocking_pool);
  985. init_std_data(&nonblocking_pool);
  986. return 0;
  987. default:
  988. return -EINVAL;
  989. }
  990. }
  991. const struct file_operations random_fops = {
  992. .read = random_read,
  993. .write = random_write,
  994. .poll = random_poll,
  995. .ioctl = random_ioctl,
  996. };
  997. const struct file_operations urandom_fops = {
  998. .read = urandom_read,
  999. .write = random_write,
  1000. .ioctl = random_ioctl,
  1001. };
  1002. /***************************************************************
  1003. * Random UUID interface
  1004. *
  1005. * Used here for a Boot ID, but can be useful for other kernel
  1006. * drivers.
  1007. ***************************************************************/
  1008. /*
  1009. * Generate random UUID
  1010. */
  1011. void generate_random_uuid(unsigned char uuid_out[16])
  1012. {
  1013. get_random_bytes(uuid_out, 16);
  1014. /* Set UUID version to 4 --- truely random generation */
  1015. uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
  1016. /* Set the UUID variant to DCE */
  1017. uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
  1018. }
  1019. EXPORT_SYMBOL(generate_random_uuid);
  1020. /********************************************************************
  1021. *
  1022. * Sysctl interface
  1023. *
  1024. ********************************************************************/
  1025. #ifdef CONFIG_SYSCTL
  1026. #include <linux/sysctl.h>
  1027. static int min_read_thresh = 8, min_write_thresh;
  1028. static int max_read_thresh = INPUT_POOL_WORDS * 32;
  1029. static int max_write_thresh = INPUT_POOL_WORDS * 32;
  1030. static char sysctl_bootid[16];
  1031. /*
  1032. * These functions is used to return both the bootid UUID, and random
  1033. * UUID. The difference is in whether table->data is NULL; if it is,
  1034. * then a new UUID is generated and returned to the user.
  1035. *
  1036. * If the user accesses this via the proc interface, it will be returned
  1037. * as an ASCII string in the standard UUID format. If accesses via the
  1038. * sysctl system call, it is returned as 16 bytes of binary data.
  1039. */
  1040. static int proc_do_uuid(ctl_table *table, int write, struct file *filp,
  1041. void __user *buffer, size_t *lenp, loff_t *ppos)
  1042. {
  1043. ctl_table fake_table;
  1044. unsigned char buf[64], tmp_uuid[16], *uuid;
  1045. uuid = table->data;
  1046. if (!uuid) {
  1047. uuid = tmp_uuid;
  1048. uuid[8] = 0;
  1049. }
  1050. if (uuid[8] == 0)
  1051. generate_random_uuid(uuid);
  1052. sprintf(buf, "%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-"
  1053. "%02x%02x%02x%02x%02x%02x",
  1054. uuid[0], uuid[1], uuid[2], uuid[3],
  1055. uuid[4], uuid[5], uuid[6], uuid[7],
  1056. uuid[8], uuid[9], uuid[10], uuid[11],
  1057. uuid[12], uuid[13], uuid[14], uuid[15]);
  1058. fake_table.data = buf;
  1059. fake_table.maxlen = sizeof(buf);
  1060. return proc_dostring(&fake_table, write, filp, buffer, lenp, ppos);
  1061. }
  1062. static int uuid_strategy(ctl_table *table, int __user *name, int nlen,
  1063. void __user *oldval, size_t __user *oldlenp,
  1064. void __user *newval, size_t newlen)
  1065. {
  1066. unsigned char tmp_uuid[16], *uuid;
  1067. unsigned int len;
  1068. if (!oldval || !oldlenp)
  1069. return 1;
  1070. uuid = table->data;
  1071. if (!uuid) {
  1072. uuid = tmp_uuid;
  1073. uuid[8] = 0;
  1074. }
  1075. if (uuid[8] == 0)
  1076. generate_random_uuid(uuid);
  1077. if (get_user(len, oldlenp))
  1078. return -EFAULT;
  1079. if (len) {
  1080. if (len > 16)
  1081. len = 16;
  1082. if (copy_to_user(oldval, uuid, len) ||
  1083. put_user(len, oldlenp))
  1084. return -EFAULT;
  1085. }
  1086. return 1;
  1087. }
  1088. static int sysctl_poolsize = INPUT_POOL_WORDS * 32;
  1089. ctl_table random_table[] = {
  1090. {
  1091. .ctl_name = RANDOM_POOLSIZE,
  1092. .procname = "poolsize",
  1093. .data = &sysctl_poolsize,
  1094. .maxlen = sizeof(int),
  1095. .mode = 0444,
  1096. .proc_handler = &proc_dointvec,
  1097. },
  1098. {
  1099. .ctl_name = RANDOM_ENTROPY_COUNT,
  1100. .procname = "entropy_avail",
  1101. .maxlen = sizeof(int),
  1102. .mode = 0444,
  1103. .proc_handler = &proc_dointvec,
  1104. .data = &input_pool.entropy_count,
  1105. },
  1106. {
  1107. .ctl_name = RANDOM_READ_THRESH,
  1108. .procname = "read_wakeup_threshold",
  1109. .data = &random_read_wakeup_thresh,
  1110. .maxlen = sizeof(int),
  1111. .mode = 0644,
  1112. .proc_handler = &proc_dointvec_minmax,
  1113. .strategy = &sysctl_intvec,
  1114. .extra1 = &min_read_thresh,
  1115. .extra2 = &max_read_thresh,
  1116. },
  1117. {
  1118. .ctl_name = RANDOM_WRITE_THRESH,
  1119. .procname = "write_wakeup_threshold",
  1120. .data = &random_write_wakeup_thresh,
  1121. .maxlen = sizeof(int),
  1122. .mode = 0644,
  1123. .proc_handler = &proc_dointvec_minmax,
  1124. .strategy = &sysctl_intvec,
  1125. .extra1 = &min_write_thresh,
  1126. .extra2 = &max_write_thresh,
  1127. },
  1128. {
  1129. .ctl_name = RANDOM_BOOT_ID,
  1130. .procname = "boot_id",
  1131. .data = &sysctl_bootid,
  1132. .maxlen = 16,
  1133. .mode = 0444,
  1134. .proc_handler = &proc_do_uuid,
  1135. .strategy = &uuid_strategy,
  1136. },
  1137. {
  1138. .ctl_name = RANDOM_UUID,
  1139. .procname = "uuid",
  1140. .maxlen = 16,
  1141. .mode = 0444,
  1142. .proc_handler = &proc_do_uuid,
  1143. .strategy = &uuid_strategy,
  1144. },
  1145. { .ctl_name = 0 }
  1146. };
  1147. #endif /* CONFIG_SYSCTL */
  1148. /********************************************************************
  1149. *
  1150. * Random funtions for networking
  1151. *
  1152. ********************************************************************/
  1153. /*
  1154. * TCP initial sequence number picking. This uses the random number
  1155. * generator to pick an initial secret value. This value is hashed
  1156. * along with the TCP endpoint information to provide a unique
  1157. * starting point for each pair of TCP endpoints. This defeats
  1158. * attacks which rely on guessing the initial TCP sequence number.
  1159. * This algorithm was suggested by Steve Bellovin.
  1160. *
  1161. * Using a very strong hash was taking an appreciable amount of the total
  1162. * TCP connection establishment time, so this is a weaker hash,
  1163. * compensated for by changing the secret periodically.
  1164. */
  1165. /* F, G and H are basic MD4 functions: selection, majority, parity */
  1166. #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
  1167. #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
  1168. #define H(x, y, z) ((x) ^ (y) ^ (z))
  1169. /*
  1170. * The generic round function. The application is so specific that
  1171. * we don't bother protecting all the arguments with parens, as is generally
  1172. * good macro practice, in favor of extra legibility.
  1173. * Rotation is separate from addition to prevent recomputation
  1174. */
  1175. #define ROUND(f, a, b, c, d, x, s) \
  1176. (a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s)))
  1177. #define K1 0
  1178. #define K2 013240474631UL
  1179. #define K3 015666365641UL
  1180. #if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
  1181. static __u32 twothirdsMD4Transform (__u32 const buf[4], __u32 const in[12])
  1182. {
  1183. __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
  1184. /* Round 1 */
  1185. ROUND(F, a, b, c, d, in[ 0] + K1, 3);
  1186. ROUND(F, d, a, b, c, in[ 1] + K1, 7);
  1187. ROUND(F, c, d, a, b, in[ 2] + K1, 11);
  1188. ROUND(F, b, c, d, a, in[ 3] + K1, 19);
  1189. ROUND(F, a, b, c, d, in[ 4] + K1, 3);
  1190. ROUND(F, d, a, b, c, in[ 5] + K1, 7);
  1191. ROUND(F, c, d, a, b, in[ 6] + K1, 11);
  1192. ROUND(F, b, c, d, a, in[ 7] + K1, 19);
  1193. ROUND(F, a, b, c, d, in[ 8] + K1, 3);
  1194. ROUND(F, d, a, b, c, in[ 9] + K1, 7);
  1195. ROUND(F, c, d, a, b, in[10] + K1, 11);
  1196. ROUND(F, b, c, d, a, in[11] + K1, 19);
  1197. /* Round 2 */
  1198. ROUND(G, a, b, c, d, in[ 1] + K2, 3);
  1199. ROUND(G, d, a, b, c, in[ 3] + K2, 5);
  1200. ROUND(G, c, d, a, b, in[ 5] + K2, 9);
  1201. ROUND(G, b, c, d, a, in[ 7] + K2, 13);
  1202. ROUND(G, a, b, c, d, in[ 9] + K2, 3);
  1203. ROUND(G, d, a, b, c, in[11] + K2, 5);
  1204. ROUND(G, c, d, a, b, in[ 0] + K2, 9);
  1205. ROUND(G, b, c, d, a, in[ 2] + K2, 13);
  1206. ROUND(G, a, b, c, d, in[ 4] + K2, 3);
  1207. ROUND(G, d, a, b, c, in[ 6] + K2, 5);
  1208. ROUND(G, c, d, a, b, in[ 8] + K2, 9);
  1209. ROUND(G, b, c, d, a, in[10] + K2, 13);
  1210. /* Round 3 */
  1211. ROUND(H, a, b, c, d, in[ 3] + K3, 3);
  1212. ROUND(H, d, a, b, c, in[ 7] + K3, 9);
  1213. ROUND(H, c, d, a, b, in[11] + K3, 11);
  1214. ROUND(H, b, c, d, a, in[ 2] + K3, 15);
  1215. ROUND(H, a, b, c, d, in[ 6] + K3, 3);
  1216. ROUND(H, d, a, b, c, in[10] + K3, 9);
  1217. ROUND(H, c, d, a, b, in[ 1] + K3, 11);
  1218. ROUND(H, b, c, d, a, in[ 5] + K3, 15);
  1219. ROUND(H, a, b, c, d, in[ 9] + K3, 3);
  1220. ROUND(H, d, a, b, c, in[ 0] + K3, 9);
  1221. ROUND(H, c, d, a, b, in[ 4] + K3, 11);
  1222. ROUND(H, b, c, d, a, in[ 8] + K3, 15);
  1223. return buf[1] + b; /* "most hashed" word */
  1224. /* Alternative: return sum of all words? */
  1225. }
  1226. #endif
  1227. #undef ROUND
  1228. #undef F
  1229. #undef G
  1230. #undef H
  1231. #undef K1
  1232. #undef K2
  1233. #undef K3
  1234. /* This should not be decreased so low that ISNs wrap too fast. */
  1235. #define REKEY_INTERVAL (300 * HZ)
  1236. /*
  1237. * Bit layout of the tcp sequence numbers (before adding current time):
  1238. * bit 24-31: increased after every key exchange
  1239. * bit 0-23: hash(source,dest)
  1240. *
  1241. * The implementation is similar to the algorithm described
  1242. * in the Appendix of RFC 1185, except that
  1243. * - it uses a 1 MHz clock instead of a 250 kHz clock
  1244. * - it performs a rekey every 5 minutes, which is equivalent
  1245. * to a (source,dest) tulple dependent forward jump of the
  1246. * clock by 0..2^(HASH_BITS+1)
  1247. *
  1248. * Thus the average ISN wraparound time is 68 minutes instead of
  1249. * 4.55 hours.
  1250. *
  1251. * SMP cleanup and lock avoidance with poor man's RCU.
  1252. * Manfred Spraul <manfred@colorfullife.com>
  1253. *
  1254. */
  1255. #define COUNT_BITS 8
  1256. #define COUNT_MASK ((1 << COUNT_BITS) - 1)
  1257. #define HASH_BITS 24
  1258. #define HASH_MASK ((1 << HASH_BITS) - 1)
  1259. static struct keydata {
  1260. __u32 count; /* already shifted to the final position */
  1261. __u32 secret[12];
  1262. } ____cacheline_aligned ip_keydata[2];
  1263. static unsigned int ip_cnt;
  1264. static void rekey_seq_generator(struct work_struct *work);
  1265. static DECLARE_DELAYED_WORK(rekey_work, rekey_seq_generator);
  1266. /*
  1267. * Lock avoidance:
  1268. * The ISN generation runs lockless - it's just a hash over random data.
  1269. * State changes happen every 5 minutes when the random key is replaced.
  1270. * Synchronization is performed by having two copies of the hash function
  1271. * state and rekey_seq_generator always updates the inactive copy.
  1272. * The copy is then activated by updating ip_cnt.
  1273. * The implementation breaks down if someone blocks the thread
  1274. * that processes SYN requests for more than 5 minutes. Should never
  1275. * happen, and even if that happens only a not perfectly compliant
  1276. * ISN is generated, nothing fatal.
  1277. */
  1278. static void rekey_seq_generator(struct work_struct *work)
  1279. {
  1280. struct keydata *keyptr = &ip_keydata[1 ^ (ip_cnt & 1)];
  1281. get_random_bytes(keyptr->secret, sizeof(keyptr->secret));
  1282. keyptr->count = (ip_cnt & COUNT_MASK) << HASH_BITS;
  1283. smp_wmb();
  1284. ip_cnt++;
  1285. schedule_delayed_work(&rekey_work, REKEY_INTERVAL);
  1286. }
  1287. static inline struct keydata *get_keyptr(void)
  1288. {
  1289. struct keydata *keyptr = &ip_keydata[ip_cnt & 1];
  1290. smp_rmb();
  1291. return keyptr;
  1292. }
  1293. static __init int seqgen_init(void)
  1294. {
  1295. rekey_seq_generator(NULL);
  1296. return 0;
  1297. }
  1298. late_initcall(seqgen_init);
  1299. #if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
  1300. __u32 secure_tcpv6_sequence_number(__be32 *saddr, __be32 *daddr,
  1301. __be16 sport, __be16 dport)
  1302. {
  1303. struct timeval tv;
  1304. __u32 seq;
  1305. __u32 hash[12];
  1306. struct keydata *keyptr = get_keyptr();
  1307. /* The procedure is the same as for IPv4, but addresses are longer.
  1308. * Thus we must use twothirdsMD4Transform.
  1309. */
  1310. memcpy(hash, saddr, 16);
  1311. hash[4]=((__force u16)sport << 16) + (__force u16)dport;
  1312. memcpy(&hash[5],keyptr->secret,sizeof(__u32) * 7);
  1313. seq = twothirdsMD4Transform((const __u32 *)daddr, hash) & HASH_MASK;
  1314. seq += keyptr->count;
  1315. do_gettimeofday(&tv);
  1316. seq += tv.tv_usec + tv.tv_sec * 1000000;
  1317. return seq;
  1318. }
  1319. EXPORT_SYMBOL(secure_tcpv6_sequence_number);
  1320. #endif
  1321. /* The code below is shamelessly stolen from secure_tcp_sequence_number().
  1322. * All blames to Andrey V. Savochkin <saw@msu.ru>.
  1323. */
  1324. __u32 secure_ip_id(__be32 daddr)
  1325. {
  1326. struct keydata *keyptr;
  1327. __u32 hash[4];
  1328. keyptr = get_keyptr();
  1329. /*
  1330. * Pick a unique starting offset for each IP destination.
  1331. * The dest ip address is placed in the starting vector,
  1332. * which is then hashed with random data.
  1333. */
  1334. hash[0] = (__force __u32)daddr;
  1335. hash[1] = keyptr->secret[9];
  1336. hash[2] = keyptr->secret[10];
  1337. hash[3] = keyptr->secret[11];
  1338. return half_md4_transform(hash, keyptr->secret);
  1339. }
  1340. #ifdef CONFIG_INET
  1341. __u32 secure_tcp_sequence_number(__be32 saddr, __be32 daddr,
  1342. __be16 sport, __be16 dport)
  1343. {
  1344. struct timeval tv;
  1345. __u32 seq;
  1346. __u32 hash[4];
  1347. struct keydata *keyptr = get_keyptr();
  1348. /*
  1349. * Pick a unique starting offset for each TCP connection endpoints
  1350. * (saddr, daddr, sport, dport).
  1351. * Note that the words are placed into the starting vector, which is
  1352. * then mixed with a partial MD4 over random data.
  1353. */
  1354. hash[0]=(__force u32)saddr;
  1355. hash[1]=(__force u32)daddr;
  1356. hash[2]=((__force u16)sport << 16) + (__force u16)dport;
  1357. hash[3]=keyptr->secret[11];
  1358. seq = half_md4_transform(hash, keyptr->secret) & HASH_MASK;
  1359. seq += keyptr->count;
  1360. /*
  1361. * As close as possible to RFC 793, which
  1362. * suggests using a 250 kHz clock.
  1363. * Further reading shows this assumes 2 Mb/s networks.
  1364. * For 10 Mb/s Ethernet, a 1 MHz clock is appropriate.
  1365. * That's funny, Linux has one built in! Use it!
  1366. * (Networks are faster now - should this be increased?)
  1367. */
  1368. do_gettimeofday(&tv);
  1369. seq += tv.tv_usec + tv.tv_sec * 1000000;
  1370. #if 0
  1371. printk("init_seq(%lx, %lx, %d, %d) = %d\n",
  1372. saddr, daddr, sport, dport, seq);
  1373. #endif
  1374. return seq;
  1375. }
  1376. EXPORT_SYMBOL(secure_tcp_sequence_number);
  1377. /* Generate secure starting point for ephemeral IPV4 transport port search */
  1378. u32 secure_ipv4_port_ephemeral(__be32 saddr, __be32 daddr, __be16 dport)
  1379. {
  1380. struct keydata *keyptr = get_keyptr();
  1381. u32 hash[4];
  1382. /*
  1383. * Pick a unique starting offset for each ephemeral port search
  1384. * (saddr, daddr, dport) and 48bits of random data.
  1385. */
  1386. hash[0] = (__force u32)saddr;
  1387. hash[1] = (__force u32)daddr;
  1388. hash[2] = (__force u32)dport ^ keyptr->secret[10];
  1389. hash[3] = keyptr->secret[11];
  1390. return half_md4_transform(hash, keyptr->secret);
  1391. }
  1392. #if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
  1393. u32 secure_ipv6_port_ephemeral(const __be32 *saddr, const __be32 *daddr, __be16 dport)
  1394. {
  1395. struct keydata *keyptr = get_keyptr();
  1396. u32 hash[12];
  1397. memcpy(hash, saddr, 16);
  1398. hash[4] = (__force u32)dport;
  1399. memcpy(&hash[5],keyptr->secret,sizeof(__u32) * 7);
  1400. return twothirdsMD4Transform((const __u32 *)daddr, hash);
  1401. }
  1402. #endif
  1403. #if defined(CONFIG_IP_DCCP) || defined(CONFIG_IP_DCCP_MODULE)
  1404. /* Similar to secure_tcp_sequence_number but generate a 48 bit value
  1405. * bit's 32-47 increase every key exchange
  1406. * 0-31 hash(source, dest)
  1407. */
  1408. u64 secure_dccp_sequence_number(__be32 saddr, __be32 daddr,
  1409. __be16 sport, __be16 dport)
  1410. {
  1411. struct timeval tv;
  1412. u64 seq;
  1413. __u32 hash[4];
  1414. struct keydata *keyptr = get_keyptr();
  1415. hash[0] = (__force u32)saddr;
  1416. hash[1] = (__force u32)daddr;
  1417. hash[2] = ((__force u16)sport << 16) + (__force u16)dport;
  1418. hash[3] = keyptr->secret[11];
  1419. seq = half_md4_transform(hash, keyptr->secret);
  1420. seq |= ((u64)keyptr->count) << (32 - HASH_BITS);
  1421. do_gettimeofday(&tv);
  1422. seq += tv.tv_usec + tv.tv_sec * 1000000;
  1423. seq &= (1ull << 48) - 1;
  1424. #if 0
  1425. printk("dccp init_seq(%lx, %lx, %d, %d) = %d\n",
  1426. saddr, daddr, sport, dport, seq);
  1427. #endif
  1428. return seq;
  1429. }
  1430. EXPORT_SYMBOL(secure_dccp_sequence_number);
  1431. #endif
  1432. #endif /* CONFIG_INET */
  1433. /*
  1434. * Get a random word for internal kernel use only. Similar to urandom but
  1435. * with the goal of minimal entropy pool depletion. As a result, the random
  1436. * value is not cryptographically secure but for several uses the cost of
  1437. * depleting entropy is too high
  1438. */
  1439. unsigned int get_random_int(void)
  1440. {
  1441. /*
  1442. * Use IP's RNG. It suits our purpose perfectly: it re-keys itself
  1443. * every second, from the entropy pool (and thus creates a limited
  1444. * drain on it), and uses halfMD4Transform within the second. We
  1445. * also mix it with jiffies and the PID:
  1446. */
  1447. return secure_ip_id((__force __be32)(current->pid + jiffies));
  1448. }
  1449. /*
  1450. * randomize_range() returns a start address such that
  1451. *
  1452. * [...... <range> .....]
  1453. * start end
  1454. *
  1455. * a <range> with size "len" starting at the return value is inside in the
  1456. * area defined by [start, end], but is otherwise randomized.
  1457. */
  1458. unsigned long
  1459. randomize_range(unsigned long start, unsigned long end, unsigned long len)
  1460. {
  1461. unsigned long range = end - len - start;
  1462. if (end <= start + len)
  1463. return 0;
  1464. return PAGE_ALIGN(get_random_int() % range + start);
  1465. }