random.c 69 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358
  1. /*
  2. * random.c -- A strong random number generator
  3. *
  4. * Copyright (C) 2017 Jason A. Donenfeld <Jason@zx2c4.com>. All
  5. * Rights Reserved.
  6. *
  7. * Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005
  8. *
  9. * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All
  10. * rights reserved.
  11. *
  12. * Redistribution and use in source and binary forms, with or without
  13. * modification, are permitted provided that the following conditions
  14. * are met:
  15. * 1. Redistributions of source code must retain the above copyright
  16. * notice, and the entire permission notice in its entirety,
  17. * including the disclaimer of warranties.
  18. * 2. Redistributions in binary form must reproduce the above copyright
  19. * notice, this list of conditions and the following disclaimer in the
  20. * documentation and/or other materials provided with the distribution.
  21. * 3. The name of the author may not be used to endorse or promote
  22. * products derived from this software without specific prior
  23. * written permission.
  24. *
  25. * ALTERNATIVELY, this product may be distributed under the terms of
  26. * the GNU General Public License, in which case the provisions of the GPL are
  27. * required INSTEAD OF the above restrictions. (This clause is
  28. * necessary due to a potential bad interaction between the GPL and
  29. * the restrictions contained in a BSD-style copyright.)
  30. *
  31. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
  32. * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  33. * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
  34. * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
  35. * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  36. * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
  37. * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  38. * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  39. * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  40. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
  41. * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
  42. * DAMAGE.
  43. */
  44. /*
  45. * (now, with legal B.S. out of the way.....)
  46. *
  47. * This routine gathers environmental noise from device drivers, etc.,
  48. * and returns good random numbers, suitable for cryptographic use.
  49. * Besides the obvious cryptographic uses, these numbers are also good
  50. * for seeding TCP sequence numbers, and other places where it is
  51. * desirable to have numbers which are not only random, but hard to
  52. * predict by an attacker.
  53. *
  54. * Theory of operation
  55. * ===================
  56. *
  57. * Computers are very predictable devices. Hence it is extremely hard
  58. * to produce truly random numbers on a computer --- as opposed to
  59. * pseudo-random numbers, which can easily generated by using a
  60. * algorithm. Unfortunately, it is very easy for attackers to guess
  61. * the sequence of pseudo-random number generators, and for some
  62. * applications this is not acceptable. So instead, we must try to
  63. * gather "environmental noise" from the computer's environment, which
  64. * must be hard for outside attackers to observe, and use that to
  65. * generate random numbers. In a Unix environment, this is best done
  66. * from inside the kernel.
  67. *
  68. * Sources of randomness from the environment include inter-keyboard
  69. * timings, inter-interrupt timings from some interrupts, and other
  70. * events which are both (a) non-deterministic and (b) hard for an
  71. * outside observer to measure. Randomness from these sources are
  72. * added to an "entropy pool", which is mixed using a CRC-like function.
  73. * This is not cryptographically strong, but it is adequate assuming
  74. * the randomness is not chosen maliciously, and it is fast enough that
  75. * the overhead of doing it on every interrupt is very reasonable.
  76. * As random bytes are mixed into the entropy pool, the routines keep
  77. * an *estimate* of how many bits of randomness have been stored into
  78. * the random number generator's internal state.
  79. *
  80. * When random bytes are desired, they are obtained by taking the SHA
  81. * hash of the contents of the "entropy pool". The SHA hash avoids
  82. * exposing the internal state of the entropy pool. It is believed to
  83. * be computationally infeasible to derive any useful information
  84. * about the input of SHA from its output. Even if it is possible to
  85. * analyze SHA in some clever way, as long as the amount of data
  86. * returned from the generator is less than the inherent entropy in
  87. * the pool, the output data is totally unpredictable. For this
  88. * reason, the routine decreases its internal estimate of how many
  89. * bits of "true randomness" are contained in the entropy pool as it
  90. * outputs random numbers.
  91. *
  92. * If this estimate goes to zero, the routine can still generate
  93. * random numbers; however, an attacker may (at least in theory) be
  94. * able to infer the future output of the generator from prior
  95. * outputs. This requires successful cryptanalysis of SHA, which is
  96. * not believed to be feasible, but there is a remote possibility.
  97. * Nonetheless, these numbers should be useful for the vast majority
  98. * of purposes.
  99. *
  100. * Exported interfaces ---- output
  101. * ===============================
  102. *
  103. * There are four exported interfaces; two for use within the kernel,
  104. * and two or use from userspace.
  105. *
  106. * Exported interfaces ---- userspace output
  107. * -----------------------------------------
  108. *
  109. * The userspace 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 ---- kernel output
  123. * --------------------------------------
  124. *
  125. * The primary kernel interface is
  126. *
  127. * void get_random_bytes(void *buf, int nbytes);
  128. *
  129. * This interface will return the requested number of random bytes,
  130. * and place it in the requested buffer. This is equivalent to a
  131. * read from /dev/urandom.
  132. *
  133. * For less critical applications, there are the functions:
  134. *
  135. * u32 get_random_u32()
  136. * u64 get_random_u64()
  137. * unsigned int get_random_int()
  138. * unsigned long get_random_long()
  139. *
  140. * These are produced by a cryptographic RNG seeded from get_random_bytes,
  141. * and so do not deplete the entropy pool as much. These are recommended
  142. * for most in-kernel operations *if the result is going to be stored in
  143. * the kernel*.
  144. *
  145. * Specifically, the get_random_int() family do not attempt to do
  146. * "anti-backtracking". If you capture the state of the kernel (e.g.
  147. * by snapshotting the VM), you can figure out previous get_random_int()
  148. * return values. But if the value is stored in the kernel anyway,
  149. * this is not a problem.
  150. *
  151. * It *is* safe to expose get_random_int() output to attackers (e.g. as
  152. * network cookies); given outputs 1..n, it's not feasible to predict
  153. * outputs 0 or n+1. The only concern is an attacker who breaks into
  154. * the kernel later; the get_random_int() engine is not reseeded as
  155. * often as the get_random_bytes() one.
  156. *
  157. * get_random_bytes() is needed for keys that need to stay secret after
  158. * they are erased from the kernel. For example, any key that will
  159. * be wrapped and stored encrypted. And session encryption keys: we'd
  160. * like to know that after the session is closed and the keys erased,
  161. * the plaintext is unrecoverable to someone who recorded the ciphertext.
  162. *
  163. * But for network ports/cookies, stack canaries, PRNG seeds, address
  164. * space layout randomization, session *authentication* keys, or other
  165. * applications where the sensitive data is stored in the kernel in
  166. * plaintext for as long as it's sensitive, the get_random_int() family
  167. * is just fine.
  168. *
  169. * Consider ASLR. We want to keep the address space secret from an
  170. * outside attacker while the process is running, but once the address
  171. * space is torn down, it's of no use to an attacker any more. And it's
  172. * stored in kernel data structures as long as it's alive, so worrying
  173. * about an attacker's ability to extrapolate it from the get_random_int()
  174. * CRNG is silly.
  175. *
  176. * Even some cryptographic keys are safe to generate with get_random_int().
  177. * In particular, keys for SipHash are generally fine. Here, knowledge
  178. * of the key authorizes you to do something to a kernel object (inject
  179. * packets to a network connection, or flood a hash table), and the
  180. * key is stored with the object being protected. Once it goes away,
  181. * we no longer care if anyone knows the key.
  182. *
  183. * prandom_u32()
  184. * -------------
  185. *
  186. * For even weaker applications, see the pseudorandom generator
  187. * prandom_u32(), prandom_max(), and prandom_bytes(). If the random
  188. * numbers aren't security-critical at all, these are *far* cheaper.
  189. * Useful for self-tests, random error simulation, randomized backoffs,
  190. * and any other application where you trust that nobody is trying to
  191. * maliciously mess with you by guessing the "random" numbers.
  192. *
  193. * Exported interfaces ---- input
  194. * ==============================
  195. *
  196. * The current exported interfaces for gathering environmental noise
  197. * from the devices are:
  198. *
  199. * void add_device_randomness(const void *buf, unsigned int size);
  200. * void add_input_randomness(unsigned int type, unsigned int code,
  201. * unsigned int value);
  202. * void add_interrupt_randomness(int irq, int irq_flags);
  203. * void add_disk_randomness(struct gendisk *disk);
  204. *
  205. * add_device_randomness() is for adding data to the random pool that
  206. * is likely to differ between two devices (or possibly even per boot).
  207. * This would be things like MAC addresses or serial numbers, or the
  208. * read-out of the RTC. This does *not* add any actual entropy to the
  209. * pool, but it initializes the pool to different values for devices
  210. * that might otherwise be identical and have very little entropy
  211. * available to them (particularly common in the embedded world).
  212. *
  213. * add_input_randomness() uses the input layer interrupt timing, as well as
  214. * the event type information from the hardware.
  215. *
  216. * add_interrupt_randomness() uses the interrupt timing as random
  217. * inputs to the entropy pool. Using the cycle counters and the irq source
  218. * as inputs, it feeds the randomness roughly once a second.
  219. *
  220. * add_disk_randomness() uses what amounts to the seek time of block
  221. * layer request events, on a per-disk_devt basis, as input to the
  222. * entropy pool. Note that high-speed solid state drives with very low
  223. * seek times do not make for good sources of entropy, as their seek
  224. * times are usually fairly consistent.
  225. *
  226. * All of these routines try to estimate how many bits of randomness a
  227. * particular randomness source. They do this by keeping track of the
  228. * first and second order deltas of the event timings.
  229. *
  230. * Ensuring unpredictability at system startup
  231. * ============================================
  232. *
  233. * When any operating system starts up, it will go through a sequence
  234. * of actions that are fairly predictable by an adversary, especially
  235. * if the start-up does not involve interaction with a human operator.
  236. * This reduces the actual number of bits of unpredictability in the
  237. * entropy pool below the value in entropy_count. In order to
  238. * counteract this effect, it helps to carry information in the
  239. * entropy pool across shut-downs and start-ups. To do this, put the
  240. * following lines an appropriate script which is run during the boot
  241. * sequence:
  242. *
  243. * echo "Initializing random number generator..."
  244. * random_seed=/var/run/random-seed
  245. * # Carry a random seed from start-up to start-up
  246. * # Load and then save the whole entropy pool
  247. * if [ -f $random_seed ]; then
  248. * cat $random_seed >/dev/urandom
  249. * else
  250. * touch $random_seed
  251. * fi
  252. * chmod 600 $random_seed
  253. * dd if=/dev/urandom of=$random_seed count=1 bs=512
  254. *
  255. * and the following lines in an appropriate script which is run as
  256. * the system is shutdown:
  257. *
  258. * # Carry a random seed from shut-down to start-up
  259. * # Save the whole entropy pool
  260. * echo "Saving random seed..."
  261. * random_seed=/var/run/random-seed
  262. * touch $random_seed
  263. * chmod 600 $random_seed
  264. * dd if=/dev/urandom of=$random_seed count=1 bs=512
  265. *
  266. * For example, on most modern systems using the System V init
  267. * scripts, such code fragments would be found in
  268. * /etc/rc.d/init.d/random. On older Linux systems, the correct script
  269. * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0.
  270. *
  271. * Effectively, these commands cause the contents of the entropy pool
  272. * to be saved at shut-down time and reloaded into the entropy pool at
  273. * start-up. (The 'dd' in the addition to the bootup script is to
  274. * make sure that /etc/random-seed is different for every start-up,
  275. * even if the system crashes without executing rc.0.) Even with
  276. * complete knowledge of the start-up activities, predicting the state
  277. * of the entropy pool requires knowledge of the previous history of
  278. * the system.
  279. *
  280. * Configuring the /dev/random driver under Linux
  281. * ==============================================
  282. *
  283. * The /dev/random driver under Linux uses minor numbers 8 and 9 of
  284. * the /dev/mem major number (#1). So if your system does not have
  285. * /dev/random and /dev/urandom created already, they can be created
  286. * by using the commands:
  287. *
  288. * mknod /dev/random c 1 8
  289. * mknod /dev/urandom c 1 9
  290. *
  291. * Acknowledgements:
  292. * =================
  293. *
  294. * Ideas for constructing this random number generator were derived
  295. * from Pretty Good Privacy's random number generator, and from private
  296. * discussions with Phil Karn. Colin Plumb provided a faster random
  297. * number generator, which speed up the mixing function of the entropy
  298. * pool, taken from PGPfone. Dale Worley has also contributed many
  299. * useful ideas and suggestions to improve this driver.
  300. *
  301. * Any flaws in the design are solely my responsibility, and should
  302. * not be attributed to the Phil, Colin, or any of authors of PGP.
  303. *
  304. * Further background information on this topic may be obtained from
  305. * RFC 1750, "Randomness Recommendations for Security", by Donald
  306. * Eastlake, Steve Crocker, and Jeff Schiller.
  307. */
  308. #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
  309. #include <linux/utsname.h>
  310. #include <linux/module.h>
  311. #include <linux/kernel.h>
  312. #include <linux/major.h>
  313. #include <linux/string.h>
  314. #include <linux/fcntl.h>
  315. #include <linux/slab.h>
  316. #include <linux/random.h>
  317. #include <linux/poll.h>
  318. #include <linux/init.h>
  319. #include <linux/fs.h>
  320. #include <linux/genhd.h>
  321. #include <linux/interrupt.h>
  322. #include <linux/mm.h>
  323. #include <linux/nodemask.h>
  324. #include <linux/spinlock.h>
  325. #include <linux/kthread.h>
  326. #include <linux/percpu.h>
  327. #include <linux/fips.h>
  328. #include <linux/ptrace.h>
  329. #include <linux/workqueue.h>
  330. #include <linux/irq.h>
  331. #include <linux/ratelimit.h>
  332. #include <linux/syscalls.h>
  333. #include <linux/completion.h>
  334. #include <linux/uuid.h>
  335. #include <crypto/chacha.h>
  336. #include <crypto/sha.h>
  337. #include <asm/processor.h>
  338. #include <linux/uaccess.h>
  339. #include <asm/irq.h>
  340. #include <asm/irq_regs.h>
  341. #include <asm/io.h>
  342. #define CREATE_TRACE_POINTS
  343. #include <trace/events/random.h>
  344. /* #define ADD_INTERRUPT_BENCH */
  345. /*
  346. * Configuration information
  347. */
  348. #define INPUT_POOL_SHIFT 12
  349. #define INPUT_POOL_WORDS (1 << (INPUT_POOL_SHIFT-5))
  350. #define OUTPUT_POOL_SHIFT 10
  351. #define OUTPUT_POOL_WORDS (1 << (OUTPUT_POOL_SHIFT-5))
  352. #define EXTRACT_SIZE 10
  353. #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
  354. /*
  355. * To allow fractional bits to be tracked, the entropy_count field is
  356. * denominated in units of 1/8th bits.
  357. *
  358. * 2*(ENTROPY_SHIFT + poolbitshift) must <= 31, or the multiply in
  359. * credit_entropy_bits() needs to be 64 bits wide.
  360. */
  361. #define ENTROPY_SHIFT 3
  362. #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
  363. /*
  364. * If the entropy count falls under this number of bits, then we
  365. * should wake up processes which are selecting or polling on write
  366. * access to /dev/random.
  367. */
  368. static int random_write_wakeup_bits = 28 * OUTPUT_POOL_WORDS;
  369. /*
  370. * Originally, we used a primitive polynomial of degree .poolwords
  371. * over GF(2). The taps for various sizes are defined below. They
  372. * were chosen to be evenly spaced except for the last tap, which is 1
  373. * to get the twisting happening as fast as possible.
  374. *
  375. * For the purposes of better mixing, we use the CRC-32 polynomial as
  376. * well to make a (modified) twisted Generalized Feedback Shift
  377. * Register. (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR
  378. * generators. ACM Transactions on Modeling and Computer Simulation
  379. * 2(3):179-194. Also see M. Matsumoto & Y. Kurita, 1994. Twisted
  380. * GFSR generators II. ACM Transactions on Modeling and Computer
  381. * Simulation 4:254-266)
  382. *
  383. * Thanks to Colin Plumb for suggesting this.
  384. *
  385. * The mixing operation is much less sensitive than the output hash,
  386. * where we use SHA-1. All that we want of mixing operation is that
  387. * it be a good non-cryptographic hash; i.e. it not produce collisions
  388. * when fed "random" data of the sort we expect to see. As long as
  389. * the pool state differs for different inputs, we have preserved the
  390. * input entropy and done a good job. The fact that an intelligent
  391. * attacker can construct inputs that will produce controlled
  392. * alterations to the pool's state is not important because we don't
  393. * consider such inputs to contribute any randomness. The only
  394. * property we need with respect to them is that the attacker can't
  395. * increase his/her knowledge of the pool's state. Since all
  396. * additions are reversible (knowing the final state and the input,
  397. * you can reconstruct the initial state), if an attacker has any
  398. * uncertainty about the initial state, he/she can only shuffle that
  399. * uncertainty about, but never cause any collisions (which would
  400. * decrease the uncertainty).
  401. *
  402. * Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
  403. * Videau in their paper, "The Linux Pseudorandom Number Generator
  404. * Revisited" (see: http://eprint.iacr.org/2012/251.pdf). In their
  405. * paper, they point out that we are not using a true Twisted GFSR,
  406. * since Matsumoto & Kurita used a trinomial feedback polynomial (that
  407. * is, with only three taps, instead of the six that we are using).
  408. * As a result, the resulting polynomial is neither primitive nor
  409. * irreducible, and hence does not have a maximal period over
  410. * GF(2**32). They suggest a slight change to the generator
  411. * polynomial which improves the resulting TGFSR polynomial to be
  412. * irreducible, which we have made here.
  413. */
  414. static const struct poolinfo {
  415. int poolbitshift, poolwords, poolbytes, poolfracbits;
  416. #define S(x) ilog2(x)+5, (x), (x)*4, (x) << (ENTROPY_SHIFT+5)
  417. int tap1, tap2, tap3, tap4, tap5;
  418. } poolinfo_table[] = {
  419. /* was: x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 */
  420. /* x^128 + x^104 + x^76 + x^51 +x^25 + x + 1 */
  421. { S(128), 104, 76, 51, 25, 1 },
  422. };
  423. /*
  424. * Static global variables
  425. */
  426. static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
  427. static struct fasync_struct *fasync;
  428. static DEFINE_SPINLOCK(random_ready_list_lock);
  429. static LIST_HEAD(random_ready_list);
  430. struct crng_state {
  431. __u32 state[16];
  432. unsigned long init_time;
  433. spinlock_t lock;
  434. };
  435. static struct crng_state primary_crng = {
  436. .lock = __SPIN_LOCK_UNLOCKED(primary_crng.lock),
  437. };
  438. /*
  439. * crng_init = 0 --> Uninitialized
  440. * 1 --> Initialized
  441. * 2 --> Initialized from input_pool
  442. *
  443. * crng_init is protected by primary_crng->lock, and only increases
  444. * its value (from 0->1->2).
  445. */
  446. static int crng_init = 0;
  447. static bool crng_need_final_init = false;
  448. #define crng_ready() (likely(crng_init > 1))
  449. static int crng_init_cnt = 0;
  450. static unsigned long crng_global_init_time = 0;
  451. #define CRNG_INIT_CNT_THRESH (2*CHACHA_KEY_SIZE)
  452. static void _extract_crng(struct crng_state *crng, __u8 out[CHACHA_BLOCK_SIZE]);
  453. static void _crng_backtrack_protect(struct crng_state *crng,
  454. __u8 tmp[CHACHA_BLOCK_SIZE], int used);
  455. static void process_random_ready_list(void);
  456. static void _get_random_bytes(void *buf, int nbytes);
  457. static struct ratelimit_state unseeded_warning =
  458. RATELIMIT_STATE_INIT("warn_unseeded_randomness", HZ, 3);
  459. static struct ratelimit_state urandom_warning =
  460. RATELIMIT_STATE_INIT("warn_urandom_randomness", HZ, 3);
  461. static int ratelimit_disable __read_mostly;
  462. module_param_named(ratelimit_disable, ratelimit_disable, int, 0644);
  463. MODULE_PARM_DESC(ratelimit_disable, "Disable random ratelimit suppression");
  464. /**********************************************************************
  465. *
  466. * OS independent entropy store. Here are the functions which handle
  467. * storing entropy in an entropy pool.
  468. *
  469. **********************************************************************/
  470. struct entropy_store;
  471. struct entropy_store {
  472. /* read-only data: */
  473. const struct poolinfo *poolinfo;
  474. __u32 *pool;
  475. const char *name;
  476. /* read-write data: */
  477. spinlock_t lock;
  478. unsigned short add_ptr;
  479. unsigned short input_rotate;
  480. int entropy_count;
  481. unsigned int initialized:1;
  482. unsigned int last_data_init:1;
  483. __u8 last_data[EXTRACT_SIZE];
  484. };
  485. static ssize_t extract_entropy(struct entropy_store *r, void *buf,
  486. size_t nbytes, int min, int rsvd);
  487. static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
  488. size_t nbytes, int fips);
  489. static void crng_reseed(struct crng_state *crng, struct entropy_store *r);
  490. static __u32 input_pool_data[INPUT_POOL_WORDS] __latent_entropy;
  491. static struct entropy_store input_pool = {
  492. .poolinfo = &poolinfo_table[0],
  493. .name = "input",
  494. .lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
  495. .pool = input_pool_data
  496. };
  497. static __u32 const twist_table[8] = {
  498. 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
  499. 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
  500. /*
  501. * This function adds bytes into the entropy "pool". It does not
  502. * update the entropy estimate. The caller should call
  503. * credit_entropy_bits if this is appropriate.
  504. *
  505. * The pool is stirred with a primitive polynomial of the appropriate
  506. * degree, and then twisted. We twist by three bits at a time because
  507. * it's cheap to do so and helps slightly in the expected case where
  508. * the entropy is concentrated in the low-order bits.
  509. */
  510. static void _mix_pool_bytes(struct entropy_store *r, const void *in,
  511. int nbytes)
  512. {
  513. unsigned long i, tap1, tap2, tap3, tap4, tap5;
  514. int input_rotate;
  515. int wordmask = r->poolinfo->poolwords - 1;
  516. const char *bytes = in;
  517. __u32 w;
  518. tap1 = r->poolinfo->tap1;
  519. tap2 = r->poolinfo->tap2;
  520. tap3 = r->poolinfo->tap3;
  521. tap4 = r->poolinfo->tap4;
  522. tap5 = r->poolinfo->tap5;
  523. input_rotate = r->input_rotate;
  524. i = r->add_ptr;
  525. /* mix one byte at a time to simplify size handling and churn faster */
  526. while (nbytes--) {
  527. w = rol32(*bytes++, input_rotate);
  528. i = (i - 1) & wordmask;
  529. /* XOR in the various taps */
  530. w ^= r->pool[i];
  531. w ^= r->pool[(i + tap1) & wordmask];
  532. w ^= r->pool[(i + tap2) & wordmask];
  533. w ^= r->pool[(i + tap3) & wordmask];
  534. w ^= r->pool[(i + tap4) & wordmask];
  535. w ^= r->pool[(i + tap5) & wordmask];
  536. /* Mix the result back in with a twist */
  537. r->pool[i] = (w >> 3) ^ twist_table[w & 7];
  538. /*
  539. * Normally, we add 7 bits of rotation to the pool.
  540. * At the beginning of the pool, add an extra 7 bits
  541. * rotation, so that successive passes spread the
  542. * input bits across the pool evenly.
  543. */
  544. input_rotate = (input_rotate + (i ? 7 : 14)) & 31;
  545. }
  546. r->input_rotate = input_rotate;
  547. r->add_ptr = i;
  548. }
  549. static void __mix_pool_bytes(struct entropy_store *r, const void *in,
  550. int nbytes)
  551. {
  552. trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_);
  553. _mix_pool_bytes(r, in, nbytes);
  554. }
  555. static void mix_pool_bytes(struct entropy_store *r, const void *in,
  556. int nbytes)
  557. {
  558. unsigned long flags;
  559. trace_mix_pool_bytes(r->name, nbytes, _RET_IP_);
  560. spin_lock_irqsave(&r->lock, flags);
  561. _mix_pool_bytes(r, in, nbytes);
  562. spin_unlock_irqrestore(&r->lock, flags);
  563. }
  564. struct fast_pool {
  565. __u32 pool[4];
  566. unsigned long last;
  567. unsigned short reg_idx;
  568. unsigned char count;
  569. };
  570. /*
  571. * This is a fast mixing routine used by the interrupt randomness
  572. * collector. It's hardcoded for an 128 bit pool and assumes that any
  573. * locks that might be needed are taken by the caller.
  574. */
  575. static void fast_mix(struct fast_pool *f)
  576. {
  577. __u32 a = f->pool[0], b = f->pool[1];
  578. __u32 c = f->pool[2], d = f->pool[3];
  579. a += b; c += d;
  580. b = rol32(b, 6); d = rol32(d, 27);
  581. d ^= a; b ^= c;
  582. a += b; c += d;
  583. b = rol32(b, 16); d = rol32(d, 14);
  584. d ^= a; b ^= c;
  585. a += b; c += d;
  586. b = rol32(b, 6); d = rol32(d, 27);
  587. d ^= a; b ^= c;
  588. a += b; c += d;
  589. b = rol32(b, 16); d = rol32(d, 14);
  590. d ^= a; b ^= c;
  591. f->pool[0] = a; f->pool[1] = b;
  592. f->pool[2] = c; f->pool[3] = d;
  593. f->count++;
  594. }
  595. static void process_random_ready_list(void)
  596. {
  597. unsigned long flags;
  598. struct random_ready_callback *rdy, *tmp;
  599. spin_lock_irqsave(&random_ready_list_lock, flags);
  600. list_for_each_entry_safe(rdy, tmp, &random_ready_list, list) {
  601. struct module *owner = rdy->owner;
  602. list_del_init(&rdy->list);
  603. rdy->func(rdy);
  604. module_put(owner);
  605. }
  606. spin_unlock_irqrestore(&random_ready_list_lock, flags);
  607. }
  608. /*
  609. * Credit (or debit) the entropy store with n bits of entropy.
  610. * Use credit_entropy_bits_safe() if the value comes from userspace
  611. * or otherwise should be checked for extreme values.
  612. */
  613. static void credit_entropy_bits(struct entropy_store *r, int nbits)
  614. {
  615. int entropy_count, orig, has_initialized = 0;
  616. const int pool_size = r->poolinfo->poolfracbits;
  617. int nfrac = nbits << ENTROPY_SHIFT;
  618. if (!nbits)
  619. return;
  620. retry:
  621. entropy_count = orig = READ_ONCE(r->entropy_count);
  622. if (nfrac < 0) {
  623. /* Debit */
  624. entropy_count += nfrac;
  625. } else {
  626. /*
  627. * Credit: we have to account for the possibility of
  628. * overwriting already present entropy. Even in the
  629. * ideal case of pure Shannon entropy, new contributions
  630. * approach the full value asymptotically:
  631. *
  632. * entropy <- entropy + (pool_size - entropy) *
  633. * (1 - exp(-add_entropy/pool_size))
  634. *
  635. * For add_entropy <= pool_size/2 then
  636. * (1 - exp(-add_entropy/pool_size)) >=
  637. * (add_entropy/pool_size)*0.7869...
  638. * so we can approximate the exponential with
  639. * 3/4*add_entropy/pool_size and still be on the
  640. * safe side by adding at most pool_size/2 at a time.
  641. *
  642. * The use of pool_size-2 in the while statement is to
  643. * prevent rounding artifacts from making the loop
  644. * arbitrarily long; this limits the loop to log2(pool_size)*2
  645. * turns no matter how large nbits is.
  646. */
  647. int pnfrac = nfrac;
  648. const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
  649. /* The +2 corresponds to the /4 in the denominator */
  650. do {
  651. unsigned int anfrac = min(pnfrac, pool_size/2);
  652. unsigned int add =
  653. ((pool_size - entropy_count)*anfrac*3) >> s;
  654. entropy_count += add;
  655. pnfrac -= anfrac;
  656. } while (unlikely(entropy_count < pool_size-2 && pnfrac));
  657. }
  658. if (WARN_ON(entropy_count < 0)) {
  659. pr_warn("negative entropy/overflow: pool %s count %d\n",
  660. r->name, entropy_count);
  661. entropy_count = 0;
  662. } else if (entropy_count > pool_size)
  663. entropy_count = pool_size;
  664. if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
  665. goto retry;
  666. if (has_initialized) {
  667. r->initialized = 1;
  668. kill_fasync(&fasync, SIGIO, POLL_IN);
  669. }
  670. trace_credit_entropy_bits(r->name, nbits,
  671. entropy_count >> ENTROPY_SHIFT, _RET_IP_);
  672. if (r == &input_pool) {
  673. int entropy_bits = entropy_count >> ENTROPY_SHIFT;
  674. if (crng_init < 2) {
  675. if (entropy_bits < 128)
  676. return;
  677. crng_reseed(&primary_crng, r);
  678. entropy_bits = ENTROPY_BITS(r);
  679. }
  680. }
  681. }
  682. static int credit_entropy_bits_safe(struct entropy_store *r, int nbits)
  683. {
  684. const int nbits_max = r->poolinfo->poolwords * 32;
  685. if (nbits < 0)
  686. return -EINVAL;
  687. /* Cap the value to avoid overflows */
  688. nbits = min(nbits, nbits_max);
  689. credit_entropy_bits(r, nbits);
  690. return 0;
  691. }
  692. /*********************************************************************
  693. *
  694. * CRNG using CHACHA20
  695. *
  696. *********************************************************************/
  697. #define CRNG_RESEED_INTERVAL (300*HZ)
  698. static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait);
  699. #ifdef CONFIG_NUMA
  700. /*
  701. * Hack to deal with crazy userspace progams when they are all trying
  702. * to access /dev/urandom in parallel. The programs are almost
  703. * certainly doing something terribly wrong, but we'll work around
  704. * their brain damage.
  705. */
  706. static struct crng_state **crng_node_pool __read_mostly;
  707. #endif
  708. static void invalidate_batched_entropy(void);
  709. static void numa_crng_init(void);
  710. static bool trust_cpu __ro_after_init = IS_ENABLED(CONFIG_RANDOM_TRUST_CPU);
  711. static int __init parse_trust_cpu(char *arg)
  712. {
  713. return kstrtobool(arg, &trust_cpu);
  714. }
  715. early_param("random.trust_cpu", parse_trust_cpu);
  716. static bool crng_init_try_arch(struct crng_state *crng)
  717. {
  718. int i;
  719. bool arch_init = true;
  720. unsigned long rv;
  721. for (i = 4; i < 16; i++) {
  722. if (!arch_get_random_seed_long(&rv) &&
  723. !arch_get_random_long(&rv)) {
  724. rv = random_get_entropy();
  725. arch_init = false;
  726. }
  727. crng->state[i] ^= rv;
  728. }
  729. return arch_init;
  730. }
  731. static bool __init crng_init_try_arch_early(struct crng_state *crng)
  732. {
  733. int i;
  734. bool arch_init = true;
  735. unsigned long rv;
  736. for (i = 4; i < 16; i++) {
  737. if (!arch_get_random_seed_long_early(&rv) &&
  738. !arch_get_random_long_early(&rv)) {
  739. rv = random_get_entropy();
  740. arch_init = false;
  741. }
  742. crng->state[i] ^= rv;
  743. }
  744. return arch_init;
  745. }
  746. static void __maybe_unused crng_initialize_secondary(struct crng_state *crng)
  747. {
  748. chacha_init_consts(crng->state);
  749. _get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
  750. crng_init_try_arch(crng);
  751. crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
  752. }
  753. static void __init crng_initialize_primary(struct crng_state *crng)
  754. {
  755. chacha_init_consts(crng->state);
  756. _extract_entropy(&input_pool, &crng->state[4], sizeof(__u32) * 12, 0);
  757. if (crng_init_try_arch_early(crng) && trust_cpu) {
  758. invalidate_batched_entropy();
  759. numa_crng_init();
  760. crng_init = 2;
  761. pr_notice("crng done (trusting CPU's manufacturer)\n");
  762. }
  763. crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
  764. }
  765. static void crng_finalize_init(struct crng_state *crng)
  766. {
  767. if (crng != &primary_crng || crng_init >= 2)
  768. return;
  769. if (!system_wq) {
  770. /* We can't call numa_crng_init until we have workqueues,
  771. * so mark this for processing later. */
  772. crng_need_final_init = true;
  773. return;
  774. }
  775. invalidate_batched_entropy();
  776. numa_crng_init();
  777. crng_init = 2;
  778. process_random_ready_list();
  779. wake_up_interruptible(&crng_init_wait);
  780. kill_fasync(&fasync, SIGIO, POLL_IN);
  781. pr_notice("crng init done\n");
  782. if (unseeded_warning.missed) {
  783. pr_notice("%d get_random_xx warning(s) missed due to ratelimiting\n",
  784. unseeded_warning.missed);
  785. unseeded_warning.missed = 0;
  786. }
  787. if (urandom_warning.missed) {
  788. pr_notice("%d urandom warning(s) missed due to ratelimiting\n",
  789. urandom_warning.missed);
  790. urandom_warning.missed = 0;
  791. }
  792. }
  793. #ifdef CONFIG_NUMA
  794. static void do_numa_crng_init(struct work_struct *work)
  795. {
  796. int i;
  797. struct crng_state *crng;
  798. struct crng_state **pool;
  799. pool = kcalloc(nr_node_ids, sizeof(*pool), GFP_KERNEL|__GFP_NOFAIL);
  800. for_each_online_node(i) {
  801. crng = kmalloc_node(sizeof(struct crng_state),
  802. GFP_KERNEL | __GFP_NOFAIL, i);
  803. spin_lock_init(&crng->lock);
  804. crng_initialize_secondary(crng);
  805. pool[i] = crng;
  806. }
  807. /* pairs with READ_ONCE() in select_crng() */
  808. if (cmpxchg_release(&crng_node_pool, NULL, pool) != NULL) {
  809. for_each_node(i)
  810. kfree(pool[i]);
  811. kfree(pool);
  812. }
  813. }
  814. static DECLARE_WORK(numa_crng_init_work, do_numa_crng_init);
  815. static void numa_crng_init(void)
  816. {
  817. schedule_work(&numa_crng_init_work);
  818. }
  819. static struct crng_state *select_crng(void)
  820. {
  821. struct crng_state **pool;
  822. int nid = numa_node_id();
  823. /* pairs with cmpxchg_release() in do_numa_crng_init() */
  824. pool = READ_ONCE(crng_node_pool);
  825. if (pool && pool[nid])
  826. return pool[nid];
  827. return &primary_crng;
  828. }
  829. #else
  830. static void numa_crng_init(void) {}
  831. static struct crng_state *select_crng(void)
  832. {
  833. return &primary_crng;
  834. }
  835. #endif
  836. /*
  837. * crng_fast_load() can be called by code in the interrupt service
  838. * path. So we can't afford to dilly-dally. Returns the number of
  839. * bytes processed from cp.
  840. */
  841. static size_t crng_fast_load(const char *cp, size_t len)
  842. {
  843. unsigned long flags;
  844. char *p;
  845. size_t ret = 0;
  846. if (!spin_trylock_irqsave(&primary_crng.lock, flags))
  847. return 0;
  848. if (crng_init != 0) {
  849. spin_unlock_irqrestore(&primary_crng.lock, flags);
  850. return 0;
  851. }
  852. p = (unsigned char *) &primary_crng.state[4];
  853. while (len > 0 && crng_init_cnt < CRNG_INIT_CNT_THRESH) {
  854. p[crng_init_cnt % CHACHA_KEY_SIZE] ^= *cp;
  855. cp++; crng_init_cnt++; len--; ret++;
  856. }
  857. spin_unlock_irqrestore(&primary_crng.lock, flags);
  858. if (crng_init_cnt >= CRNG_INIT_CNT_THRESH) {
  859. invalidate_batched_entropy();
  860. crng_init = 1;
  861. pr_notice("fast init done\n");
  862. }
  863. return ret;
  864. }
  865. /*
  866. * crng_slow_load() is called by add_device_randomness, which has two
  867. * attributes. (1) We can't trust the buffer passed to it is
  868. * guaranteed to be unpredictable (so it might not have any entropy at
  869. * all), and (2) it doesn't have the performance constraints of
  870. * crng_fast_load().
  871. *
  872. * So we do something more comprehensive which is guaranteed to touch
  873. * all of the primary_crng's state, and which uses a LFSR with a
  874. * period of 255 as part of the mixing algorithm. Finally, we do
  875. * *not* advance crng_init_cnt since buffer we may get may be something
  876. * like a fixed DMI table (for example), which might very well be
  877. * unique to the machine, but is otherwise unvarying.
  878. */
  879. static int crng_slow_load(const char *cp, size_t len)
  880. {
  881. unsigned long flags;
  882. static unsigned char lfsr = 1;
  883. unsigned char tmp;
  884. unsigned i, max = CHACHA_KEY_SIZE;
  885. const char * src_buf = cp;
  886. char * dest_buf = (char *) &primary_crng.state[4];
  887. if (!spin_trylock_irqsave(&primary_crng.lock, flags))
  888. return 0;
  889. if (crng_init != 0) {
  890. spin_unlock_irqrestore(&primary_crng.lock, flags);
  891. return 0;
  892. }
  893. if (len > max)
  894. max = len;
  895. for (i = 0; i < max ; i++) {
  896. tmp = lfsr;
  897. lfsr >>= 1;
  898. if (tmp & 1)
  899. lfsr ^= 0xE1;
  900. tmp = dest_buf[i % CHACHA_KEY_SIZE];
  901. dest_buf[i % CHACHA_KEY_SIZE] ^= src_buf[i % len] ^ lfsr;
  902. lfsr += (tmp << 3) | (tmp >> 5);
  903. }
  904. spin_unlock_irqrestore(&primary_crng.lock, flags);
  905. return 1;
  906. }
  907. static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
  908. {
  909. unsigned long flags;
  910. int i, num;
  911. union {
  912. __u8 block[CHACHA_BLOCK_SIZE];
  913. __u32 key[8];
  914. } buf;
  915. if (r) {
  916. num = extract_entropy(r, &buf, 32, 16, 0);
  917. if (num == 0)
  918. return;
  919. } else {
  920. _extract_crng(&primary_crng, buf.block);
  921. _crng_backtrack_protect(&primary_crng, buf.block,
  922. CHACHA_KEY_SIZE);
  923. }
  924. spin_lock_irqsave(&crng->lock, flags);
  925. for (i = 0; i < 8; i++) {
  926. unsigned long rv;
  927. if (!arch_get_random_seed_long(&rv) &&
  928. !arch_get_random_long(&rv))
  929. rv = random_get_entropy();
  930. crng->state[i+4] ^= buf.key[i] ^ rv;
  931. }
  932. memzero_explicit(&buf, sizeof(buf));
  933. WRITE_ONCE(crng->init_time, jiffies);
  934. spin_unlock_irqrestore(&crng->lock, flags);
  935. crng_finalize_init(crng);
  936. }
  937. static void _extract_crng(struct crng_state *crng,
  938. __u8 out[CHACHA_BLOCK_SIZE])
  939. {
  940. unsigned long v, flags, init_time;
  941. if (crng_ready()) {
  942. init_time = READ_ONCE(crng->init_time);
  943. if (time_after(READ_ONCE(crng_global_init_time), init_time) ||
  944. time_after(jiffies, init_time + CRNG_RESEED_INTERVAL))
  945. crng_reseed(crng, crng == &primary_crng ?
  946. &input_pool : NULL);
  947. }
  948. spin_lock_irqsave(&crng->lock, flags);
  949. if (arch_get_random_long(&v))
  950. crng->state[14] ^= v;
  951. chacha20_block(&crng->state[0], out);
  952. if (crng->state[12] == 0)
  953. crng->state[13]++;
  954. spin_unlock_irqrestore(&crng->lock, flags);
  955. }
  956. static void extract_crng(__u8 out[CHACHA_BLOCK_SIZE])
  957. {
  958. _extract_crng(select_crng(), out);
  959. }
  960. /*
  961. * Use the leftover bytes from the CRNG block output (if there is
  962. * enough) to mutate the CRNG key to provide backtracking protection.
  963. */
  964. static void _crng_backtrack_protect(struct crng_state *crng,
  965. __u8 tmp[CHACHA_BLOCK_SIZE], int used)
  966. {
  967. unsigned long flags;
  968. __u32 *s, *d;
  969. int i;
  970. used = round_up(used, sizeof(__u32));
  971. if (used + CHACHA_KEY_SIZE > CHACHA_BLOCK_SIZE) {
  972. extract_crng(tmp);
  973. used = 0;
  974. }
  975. spin_lock_irqsave(&crng->lock, flags);
  976. s = (__u32 *) &tmp[used];
  977. d = &crng->state[4];
  978. for (i=0; i < 8; i++)
  979. *d++ ^= *s++;
  980. spin_unlock_irqrestore(&crng->lock, flags);
  981. }
  982. static void crng_backtrack_protect(__u8 tmp[CHACHA_BLOCK_SIZE], int used)
  983. {
  984. _crng_backtrack_protect(select_crng(), tmp, used);
  985. }
  986. static ssize_t extract_crng_user(void __user *buf, size_t nbytes)
  987. {
  988. ssize_t ret = 0, i = CHACHA_BLOCK_SIZE;
  989. __u8 tmp[CHACHA_BLOCK_SIZE] __aligned(4);
  990. int large_request = (nbytes > 256);
  991. while (nbytes) {
  992. if (large_request && need_resched()) {
  993. if (signal_pending(current)) {
  994. if (ret == 0)
  995. ret = -ERESTARTSYS;
  996. break;
  997. }
  998. schedule();
  999. }
  1000. extract_crng(tmp);
  1001. i = min_t(int, nbytes, CHACHA_BLOCK_SIZE);
  1002. if (copy_to_user(buf, tmp, i)) {
  1003. ret = -EFAULT;
  1004. break;
  1005. }
  1006. nbytes -= i;
  1007. buf += i;
  1008. ret += i;
  1009. }
  1010. crng_backtrack_protect(tmp, i);
  1011. /* Wipe data just written to memory */
  1012. memzero_explicit(tmp, sizeof(tmp));
  1013. return ret;
  1014. }
  1015. /*********************************************************************
  1016. *
  1017. * Entropy input management
  1018. *
  1019. *********************************************************************/
  1020. /* There is one of these per entropy source */
  1021. struct timer_rand_state {
  1022. cycles_t last_time;
  1023. long last_delta, last_delta2;
  1024. };
  1025. #define INIT_TIMER_RAND_STATE { INITIAL_JIFFIES, };
  1026. /*
  1027. * Add device- or boot-specific data to the input pool to help
  1028. * initialize it.
  1029. *
  1030. * None of this adds any entropy; it is meant to avoid the problem of
  1031. * the entropy pool having similar initial state across largely
  1032. * identical devices.
  1033. */
  1034. void add_device_randomness(const void *buf, unsigned int size)
  1035. {
  1036. unsigned long time = random_get_entropy() ^ jiffies;
  1037. unsigned long flags;
  1038. if (!crng_ready() && size)
  1039. crng_slow_load(buf, size);
  1040. trace_add_device_randomness(size, _RET_IP_);
  1041. spin_lock_irqsave(&input_pool.lock, flags);
  1042. _mix_pool_bytes(&input_pool, buf, size);
  1043. _mix_pool_bytes(&input_pool, &time, sizeof(time));
  1044. spin_unlock_irqrestore(&input_pool.lock, flags);
  1045. }
  1046. EXPORT_SYMBOL(add_device_randomness);
  1047. static struct timer_rand_state input_timer_state = INIT_TIMER_RAND_STATE;
  1048. /*
  1049. * This function adds entropy to the entropy "pool" by using timing
  1050. * delays. It uses the timer_rand_state structure to make an estimate
  1051. * of how many bits of entropy this call has added to the pool.
  1052. *
  1053. * The number "num" is also added to the pool - it should somehow describe
  1054. * the type of event which just happened. This is currently 0-255 for
  1055. * keyboard scan codes, and 256 upwards for interrupts.
  1056. *
  1057. */
  1058. static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
  1059. {
  1060. struct entropy_store *r;
  1061. struct {
  1062. long jiffies;
  1063. unsigned cycles;
  1064. unsigned num;
  1065. } sample;
  1066. long delta, delta2, delta3;
  1067. sample.jiffies = jiffies;
  1068. sample.cycles = random_get_entropy();
  1069. sample.num = num;
  1070. r = &input_pool;
  1071. mix_pool_bytes(r, &sample, sizeof(sample));
  1072. /*
  1073. * Calculate number of bits of randomness we probably added.
  1074. * We take into account the first, second and third-order deltas
  1075. * in order to make our estimate.
  1076. */
  1077. delta = sample.jiffies - READ_ONCE(state->last_time);
  1078. WRITE_ONCE(state->last_time, sample.jiffies);
  1079. delta2 = delta - READ_ONCE(state->last_delta);
  1080. WRITE_ONCE(state->last_delta, delta);
  1081. delta3 = delta2 - READ_ONCE(state->last_delta2);
  1082. WRITE_ONCE(state->last_delta2, delta2);
  1083. if (delta < 0)
  1084. delta = -delta;
  1085. if (delta2 < 0)
  1086. delta2 = -delta2;
  1087. if (delta3 < 0)
  1088. delta3 = -delta3;
  1089. if (delta > delta2)
  1090. delta = delta2;
  1091. if (delta > delta3)
  1092. delta = delta3;
  1093. /*
  1094. * delta is now minimum absolute delta.
  1095. * Round down by 1 bit on general principles,
  1096. * and limit entropy estimate to 12 bits.
  1097. */
  1098. credit_entropy_bits(r, min_t(int, fls(delta>>1), 11));
  1099. }
  1100. void add_input_randomness(unsigned int type, unsigned int code,
  1101. unsigned int value)
  1102. {
  1103. static unsigned char last_value;
  1104. /* ignore autorepeat and the like */
  1105. if (value == last_value)
  1106. return;
  1107. last_value = value;
  1108. add_timer_randomness(&input_timer_state,
  1109. (type << 4) ^ code ^ (code >> 4) ^ value);
  1110. trace_add_input_randomness(ENTROPY_BITS(&input_pool));
  1111. }
  1112. EXPORT_SYMBOL_GPL(add_input_randomness);
  1113. static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
  1114. #ifdef ADD_INTERRUPT_BENCH
  1115. static unsigned long avg_cycles, avg_deviation;
  1116. #define AVG_SHIFT 8 /* Exponential average factor k=1/256 */
  1117. #define FIXED_1_2 (1 << (AVG_SHIFT-1))
  1118. static void add_interrupt_bench(cycles_t start)
  1119. {
  1120. long delta = random_get_entropy() - start;
  1121. /* Use a weighted moving average */
  1122. delta = delta - ((avg_cycles + FIXED_1_2) >> AVG_SHIFT);
  1123. avg_cycles += delta;
  1124. /* And average deviation */
  1125. delta = abs(delta) - ((avg_deviation + FIXED_1_2) >> AVG_SHIFT);
  1126. avg_deviation += delta;
  1127. }
  1128. #else
  1129. #define add_interrupt_bench(x)
  1130. #endif
  1131. static __u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
  1132. {
  1133. __u32 *ptr = (__u32 *) regs;
  1134. unsigned int idx;
  1135. if (regs == NULL)
  1136. return 0;
  1137. idx = READ_ONCE(f->reg_idx);
  1138. if (idx >= sizeof(struct pt_regs) / sizeof(__u32))
  1139. idx = 0;
  1140. ptr += idx++;
  1141. WRITE_ONCE(f->reg_idx, idx);
  1142. return *ptr;
  1143. }
  1144. void add_interrupt_randomness(int irq, int irq_flags)
  1145. {
  1146. struct entropy_store *r;
  1147. struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness);
  1148. struct pt_regs *regs = get_irq_regs();
  1149. unsigned long now = jiffies;
  1150. cycles_t cycles = random_get_entropy();
  1151. __u32 c_high, j_high;
  1152. __u64 ip;
  1153. unsigned long seed;
  1154. int credit = 0;
  1155. if (cycles == 0)
  1156. cycles = get_reg(fast_pool, regs);
  1157. c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
  1158. j_high = (sizeof(now) > 4) ? now >> 32 : 0;
  1159. fast_pool->pool[0] ^= cycles ^ j_high ^ irq;
  1160. fast_pool->pool[1] ^= now ^ c_high;
  1161. ip = regs ? instruction_pointer(regs) : _RET_IP_;
  1162. fast_pool->pool[2] ^= ip;
  1163. fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 :
  1164. get_reg(fast_pool, regs);
  1165. fast_mix(fast_pool);
  1166. add_interrupt_bench(cycles);
  1167. if (unlikely(crng_init == 0)) {
  1168. if ((fast_pool->count >= 64) &&
  1169. crng_fast_load((char *) fast_pool->pool,
  1170. sizeof(fast_pool->pool)) > 0) {
  1171. fast_pool->count = 0;
  1172. fast_pool->last = now;
  1173. }
  1174. return;
  1175. }
  1176. if ((fast_pool->count < 64) &&
  1177. !time_after(now, fast_pool->last + HZ))
  1178. return;
  1179. r = &input_pool;
  1180. if (!spin_trylock(&r->lock))
  1181. return;
  1182. fast_pool->last = now;
  1183. __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
  1184. /*
  1185. * If we have architectural seed generator, produce a seed and
  1186. * add it to the pool. For the sake of paranoia don't let the
  1187. * architectural seed generator dominate the input from the
  1188. * interrupt noise.
  1189. */
  1190. if (arch_get_random_seed_long(&seed)) {
  1191. __mix_pool_bytes(r, &seed, sizeof(seed));
  1192. credit = 1;
  1193. }
  1194. spin_unlock(&r->lock);
  1195. fast_pool->count = 0;
  1196. /* award one bit for the contents of the fast pool */
  1197. credit_entropy_bits(r, credit + 1);
  1198. }
  1199. EXPORT_SYMBOL_GPL(add_interrupt_randomness);
  1200. #ifdef CONFIG_BLOCK
  1201. void add_disk_randomness(struct gendisk *disk)
  1202. {
  1203. if (!disk || !disk->random)
  1204. return;
  1205. /* first major is 1, so we get >= 0x200 here */
  1206. add_timer_randomness(disk->random, 0x100 + disk_devt(disk));
  1207. trace_add_disk_randomness(disk_devt(disk), ENTROPY_BITS(&input_pool));
  1208. }
  1209. EXPORT_SYMBOL_GPL(add_disk_randomness);
  1210. #endif
  1211. /*********************************************************************
  1212. *
  1213. * Entropy extraction routines
  1214. *
  1215. *********************************************************************/
  1216. /*
  1217. * This function decides how many bytes to actually take from the
  1218. * given pool, and also debits the entropy count accordingly.
  1219. */
  1220. static size_t account(struct entropy_store *r, size_t nbytes, int min,
  1221. int reserved)
  1222. {
  1223. int entropy_count, orig, have_bytes;
  1224. size_t ibytes, nfrac;
  1225. BUG_ON(r->entropy_count > r->poolinfo->poolfracbits);
  1226. /* Can we pull enough? */
  1227. retry:
  1228. entropy_count = orig = READ_ONCE(r->entropy_count);
  1229. ibytes = nbytes;
  1230. /* never pull more than available */
  1231. have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
  1232. if ((have_bytes -= reserved) < 0)
  1233. have_bytes = 0;
  1234. ibytes = min_t(size_t, ibytes, have_bytes);
  1235. if (ibytes < min)
  1236. ibytes = 0;
  1237. if (WARN_ON(entropy_count < 0)) {
  1238. pr_warn("negative entropy count: pool %s count %d\n",
  1239. r->name, entropy_count);
  1240. entropy_count = 0;
  1241. }
  1242. nfrac = ibytes << (ENTROPY_SHIFT + 3);
  1243. if ((size_t) entropy_count > nfrac)
  1244. entropy_count -= nfrac;
  1245. else
  1246. entropy_count = 0;
  1247. if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
  1248. goto retry;
  1249. trace_debit_entropy(r->name, 8 * ibytes);
  1250. if (ibytes && ENTROPY_BITS(r) < random_write_wakeup_bits) {
  1251. wake_up_interruptible(&random_write_wait);
  1252. kill_fasync(&fasync, SIGIO, POLL_OUT);
  1253. }
  1254. return ibytes;
  1255. }
  1256. /*
  1257. * This function does the actual extraction for extract_entropy and
  1258. * extract_entropy_user.
  1259. *
  1260. * Note: we assume that .poolwords is a multiple of 16 words.
  1261. */
  1262. static void extract_buf(struct entropy_store *r, __u8 *out)
  1263. {
  1264. int i;
  1265. union {
  1266. __u32 w[5];
  1267. unsigned long l[LONGS(20)];
  1268. } hash;
  1269. __u32 workspace[SHA1_WORKSPACE_WORDS];
  1270. unsigned long flags;
  1271. /*
  1272. * If we have an architectural hardware random number
  1273. * generator, use it for SHA's initial vector
  1274. */
  1275. sha1_init(hash.w);
  1276. for (i = 0; i < LONGS(20); i++) {
  1277. unsigned long v;
  1278. if (!arch_get_random_long(&v))
  1279. break;
  1280. hash.l[i] = v;
  1281. }
  1282. /* Generate a hash across the pool, 16 words (512 bits) at a time */
  1283. spin_lock_irqsave(&r->lock, flags);
  1284. for (i = 0; i < r->poolinfo->poolwords; i += 16)
  1285. sha1_transform(hash.w, (__u8 *)(r->pool + i), workspace);
  1286. /*
  1287. * We mix the hash back into the pool to prevent backtracking
  1288. * attacks (where the attacker knows the state of the pool
  1289. * plus the current outputs, and attempts to find previous
  1290. * ouputs), unless the hash function can be inverted. By
  1291. * mixing at least a SHA1 worth of hash data back, we make
  1292. * brute-forcing the feedback as hard as brute-forcing the
  1293. * hash.
  1294. */
  1295. __mix_pool_bytes(r, hash.w, sizeof(hash.w));
  1296. spin_unlock_irqrestore(&r->lock, flags);
  1297. memzero_explicit(workspace, sizeof(workspace));
  1298. /*
  1299. * In case the hash function has some recognizable output
  1300. * pattern, we fold it in half. Thus, we always feed back
  1301. * twice as much data as we output.
  1302. */
  1303. hash.w[0] ^= hash.w[3];
  1304. hash.w[1] ^= hash.w[4];
  1305. hash.w[2] ^= rol32(hash.w[2], 16);
  1306. memcpy(out, &hash, EXTRACT_SIZE);
  1307. memzero_explicit(&hash, sizeof(hash));
  1308. }
  1309. static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
  1310. size_t nbytes, int fips)
  1311. {
  1312. ssize_t ret = 0, i;
  1313. __u8 tmp[EXTRACT_SIZE];
  1314. unsigned long flags;
  1315. while (nbytes) {
  1316. extract_buf(r, tmp);
  1317. if (fips) {
  1318. spin_lock_irqsave(&r->lock, flags);
  1319. if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
  1320. panic("Hardware RNG duplicated output!\n");
  1321. memcpy(r->last_data, tmp, EXTRACT_SIZE);
  1322. spin_unlock_irqrestore(&r->lock, flags);
  1323. }
  1324. i = min_t(int, nbytes, EXTRACT_SIZE);
  1325. memcpy(buf, tmp, i);
  1326. nbytes -= i;
  1327. buf += i;
  1328. ret += i;
  1329. }
  1330. /* Wipe data just returned from memory */
  1331. memzero_explicit(tmp, sizeof(tmp));
  1332. return ret;
  1333. }
  1334. /*
  1335. * This function extracts randomness from the "entropy pool", and
  1336. * returns it in a buffer.
  1337. *
  1338. * The min parameter specifies the minimum amount we can pull before
  1339. * failing to avoid races that defeat catastrophic reseeding while the
  1340. * reserved parameter indicates how much entropy we must leave in the
  1341. * pool after each pull to avoid starving other readers.
  1342. */
  1343. static ssize_t extract_entropy(struct entropy_store *r, void *buf,
  1344. size_t nbytes, int min, int reserved)
  1345. {
  1346. __u8 tmp[EXTRACT_SIZE];
  1347. unsigned long flags;
  1348. /* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */
  1349. if (fips_enabled) {
  1350. spin_lock_irqsave(&r->lock, flags);
  1351. if (!r->last_data_init) {
  1352. r->last_data_init = 1;
  1353. spin_unlock_irqrestore(&r->lock, flags);
  1354. trace_extract_entropy(r->name, EXTRACT_SIZE,
  1355. ENTROPY_BITS(r), _RET_IP_);
  1356. extract_buf(r, tmp);
  1357. spin_lock_irqsave(&r->lock, flags);
  1358. memcpy(r->last_data, tmp, EXTRACT_SIZE);
  1359. }
  1360. spin_unlock_irqrestore(&r->lock, flags);
  1361. }
  1362. trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
  1363. nbytes = account(r, nbytes, min, reserved);
  1364. return _extract_entropy(r, buf, nbytes, fips_enabled);
  1365. }
  1366. #define warn_unseeded_randomness(previous) \
  1367. _warn_unseeded_randomness(__func__, (void *) _RET_IP_, (previous))
  1368. static void _warn_unseeded_randomness(const char *func_name, void *caller,
  1369. void **previous)
  1370. {
  1371. #ifdef CONFIG_WARN_ALL_UNSEEDED_RANDOM
  1372. const bool print_once = false;
  1373. #else
  1374. static bool print_once __read_mostly;
  1375. #endif
  1376. if (print_once ||
  1377. crng_ready() ||
  1378. (previous && (caller == READ_ONCE(*previous))))
  1379. return;
  1380. WRITE_ONCE(*previous, caller);
  1381. #ifndef CONFIG_WARN_ALL_UNSEEDED_RANDOM
  1382. print_once = true;
  1383. #endif
  1384. if (__ratelimit(&unseeded_warning))
  1385. printk_deferred(KERN_NOTICE "random: %s called from %pS "
  1386. "with crng_init=%d\n", func_name, caller,
  1387. crng_init);
  1388. }
  1389. /*
  1390. * This function is the exported kernel interface. It returns some
  1391. * number of good random numbers, suitable for key generation, seeding
  1392. * TCP sequence numbers, etc. It does not rely on the hardware random
  1393. * number generator. For random bytes direct from the hardware RNG
  1394. * (when available), use get_random_bytes_arch(). In order to ensure
  1395. * that the randomness provided by this function is okay, the function
  1396. * wait_for_random_bytes() should be called and return 0 at least once
  1397. * at any point prior.
  1398. */
  1399. static void _get_random_bytes(void *buf, int nbytes)
  1400. {
  1401. __u8 tmp[CHACHA_BLOCK_SIZE] __aligned(4);
  1402. trace_get_random_bytes(nbytes, _RET_IP_);
  1403. while (nbytes >= CHACHA_BLOCK_SIZE) {
  1404. extract_crng(buf);
  1405. buf += CHACHA_BLOCK_SIZE;
  1406. nbytes -= CHACHA_BLOCK_SIZE;
  1407. }
  1408. if (nbytes > 0) {
  1409. extract_crng(tmp);
  1410. memcpy(buf, tmp, nbytes);
  1411. crng_backtrack_protect(tmp, nbytes);
  1412. } else
  1413. crng_backtrack_protect(tmp, CHACHA_BLOCK_SIZE);
  1414. memzero_explicit(tmp, sizeof(tmp));
  1415. }
  1416. void get_random_bytes(void *buf, int nbytes)
  1417. {
  1418. static void *previous;
  1419. warn_unseeded_randomness(&previous);
  1420. _get_random_bytes(buf, nbytes);
  1421. }
  1422. EXPORT_SYMBOL(get_random_bytes);
  1423. /*
  1424. * Each time the timer fires, we expect that we got an unpredictable
  1425. * jump in the cycle counter. Even if the timer is running on another
  1426. * CPU, the timer activity will be touching the stack of the CPU that is
  1427. * generating entropy..
  1428. *
  1429. * Note that we don't re-arm the timer in the timer itself - we are
  1430. * happy to be scheduled away, since that just makes the load more
  1431. * complex, but we do not want the timer to keep ticking unless the
  1432. * entropy loop is running.
  1433. *
  1434. * So the re-arming always happens in the entropy loop itself.
  1435. */
  1436. static void entropy_timer(struct timer_list *t)
  1437. {
  1438. credit_entropy_bits(&input_pool, 1);
  1439. }
  1440. /*
  1441. * If we have an actual cycle counter, see if we can
  1442. * generate enough entropy with timing noise
  1443. */
  1444. static void try_to_generate_entropy(void)
  1445. {
  1446. struct {
  1447. unsigned long now;
  1448. struct timer_list timer;
  1449. } stack;
  1450. stack.now = random_get_entropy();
  1451. /* Slow counter - or none. Don't even bother */
  1452. if (stack.now == random_get_entropy())
  1453. return;
  1454. timer_setup_on_stack(&stack.timer, entropy_timer, 0);
  1455. while (!crng_ready()) {
  1456. if (!timer_pending(&stack.timer))
  1457. mod_timer(&stack.timer, jiffies+1);
  1458. mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
  1459. schedule();
  1460. stack.now = random_get_entropy();
  1461. }
  1462. del_timer_sync(&stack.timer);
  1463. destroy_timer_on_stack(&stack.timer);
  1464. mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
  1465. }
  1466. /*
  1467. * Wait for the urandom pool to be seeded and thus guaranteed to supply
  1468. * cryptographically secure random numbers. This applies to: the /dev/urandom
  1469. * device, the get_random_bytes function, and the get_random_{u32,u64,int,long}
  1470. * family of functions. Using any of these functions without first calling
  1471. * this function forfeits the guarantee of security.
  1472. *
  1473. * Returns: 0 if the urandom pool has been seeded.
  1474. * -ERESTARTSYS if the function was interrupted by a signal.
  1475. */
  1476. int wait_for_random_bytes(void)
  1477. {
  1478. if (likely(crng_ready()))
  1479. return 0;
  1480. do {
  1481. int ret;
  1482. ret = wait_event_interruptible_timeout(crng_init_wait, crng_ready(), HZ);
  1483. if (ret)
  1484. return ret > 0 ? 0 : ret;
  1485. try_to_generate_entropy();
  1486. } while (!crng_ready());
  1487. return 0;
  1488. }
  1489. EXPORT_SYMBOL(wait_for_random_bytes);
  1490. /*
  1491. * Returns whether or not the urandom pool has been seeded and thus guaranteed
  1492. * to supply cryptographically secure random numbers. This applies to: the
  1493. * /dev/urandom device, the get_random_bytes function, and the get_random_{u32,
  1494. * ,u64,int,long} family of functions.
  1495. *
  1496. * Returns: true if the urandom pool has been seeded.
  1497. * false if the urandom pool has not been seeded.
  1498. */
  1499. bool rng_is_initialized(void)
  1500. {
  1501. return crng_ready();
  1502. }
  1503. EXPORT_SYMBOL(rng_is_initialized);
  1504. /*
  1505. * Add a callback function that will be invoked when the nonblocking
  1506. * pool is initialised.
  1507. *
  1508. * returns: 0 if callback is successfully added
  1509. * -EALREADY if pool is already initialised (callback not called)
  1510. * -ENOENT if module for callback is not alive
  1511. */
  1512. int add_random_ready_callback(struct random_ready_callback *rdy)
  1513. {
  1514. struct module *owner;
  1515. unsigned long flags;
  1516. int err = -EALREADY;
  1517. if (crng_ready())
  1518. return err;
  1519. owner = rdy->owner;
  1520. if (!try_module_get(owner))
  1521. return -ENOENT;
  1522. spin_lock_irqsave(&random_ready_list_lock, flags);
  1523. if (crng_ready())
  1524. goto out;
  1525. owner = NULL;
  1526. list_add(&rdy->list, &random_ready_list);
  1527. err = 0;
  1528. out:
  1529. spin_unlock_irqrestore(&random_ready_list_lock, flags);
  1530. module_put(owner);
  1531. return err;
  1532. }
  1533. EXPORT_SYMBOL(add_random_ready_callback);
  1534. /*
  1535. * Delete a previously registered readiness callback function.
  1536. */
  1537. void del_random_ready_callback(struct random_ready_callback *rdy)
  1538. {
  1539. unsigned long flags;
  1540. struct module *owner = NULL;
  1541. spin_lock_irqsave(&random_ready_list_lock, flags);
  1542. if (!list_empty(&rdy->list)) {
  1543. list_del_init(&rdy->list);
  1544. owner = rdy->owner;
  1545. }
  1546. spin_unlock_irqrestore(&random_ready_list_lock, flags);
  1547. module_put(owner);
  1548. }
  1549. EXPORT_SYMBOL(del_random_ready_callback);
  1550. /*
  1551. * This function will use the architecture-specific hardware random
  1552. * number generator if it is available. The arch-specific hw RNG will
  1553. * almost certainly be faster than what we can do in software, but it
  1554. * is impossible to verify that it is implemented securely (as
  1555. * opposed, to, say, the AES encryption of a sequence number using a
  1556. * key known by the NSA). So it's useful if we need the speed, but
  1557. * only if we're willing to trust the hardware manufacturer not to
  1558. * have put in a back door.
  1559. *
  1560. * Return number of bytes filled in.
  1561. */
  1562. int __must_check get_random_bytes_arch(void *buf, int nbytes)
  1563. {
  1564. int left = nbytes;
  1565. char *p = buf;
  1566. trace_get_random_bytes_arch(left, _RET_IP_);
  1567. while (left) {
  1568. unsigned long v;
  1569. int chunk = min_t(int, left, sizeof(unsigned long));
  1570. if (!arch_get_random_long(&v))
  1571. break;
  1572. memcpy(p, &v, chunk);
  1573. p += chunk;
  1574. left -= chunk;
  1575. }
  1576. return nbytes - left;
  1577. }
  1578. EXPORT_SYMBOL(get_random_bytes_arch);
  1579. /*
  1580. * init_std_data - initialize pool with system data
  1581. *
  1582. * @r: pool to initialize
  1583. *
  1584. * This function clears the pool's entropy count and mixes some system
  1585. * data into the pool to prepare it for use. The pool is not cleared
  1586. * as that can only decrease the entropy in the pool.
  1587. */
  1588. static void __init init_std_data(struct entropy_store *r)
  1589. {
  1590. int i;
  1591. ktime_t now = ktime_get_real();
  1592. unsigned long rv;
  1593. mix_pool_bytes(r, &now, sizeof(now));
  1594. for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
  1595. if (!arch_get_random_seed_long(&rv) &&
  1596. !arch_get_random_long(&rv))
  1597. rv = random_get_entropy();
  1598. mix_pool_bytes(r, &rv, sizeof(rv));
  1599. }
  1600. mix_pool_bytes(r, utsname(), sizeof(*(utsname())));
  1601. }
  1602. /*
  1603. * Note that setup_arch() may call add_device_randomness()
  1604. * long before we get here. This allows seeding of the pools
  1605. * with some platform dependent data very early in the boot
  1606. * process. But it limits our options here. We must use
  1607. * statically allocated structures that already have all
  1608. * initializations complete at compile time. We should also
  1609. * take care not to overwrite the precious per platform data
  1610. * we were given.
  1611. */
  1612. int __init rand_initialize(void)
  1613. {
  1614. init_std_data(&input_pool);
  1615. if (crng_need_final_init)
  1616. crng_finalize_init(&primary_crng);
  1617. crng_initialize_primary(&primary_crng);
  1618. crng_global_init_time = jiffies;
  1619. if (ratelimit_disable) {
  1620. urandom_warning.interval = 0;
  1621. unseeded_warning.interval = 0;
  1622. }
  1623. return 0;
  1624. }
  1625. #ifdef CONFIG_BLOCK
  1626. void rand_initialize_disk(struct gendisk *disk)
  1627. {
  1628. struct timer_rand_state *state;
  1629. /*
  1630. * If kzalloc returns null, we just won't use that entropy
  1631. * source.
  1632. */
  1633. state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
  1634. if (state) {
  1635. state->last_time = INITIAL_JIFFIES;
  1636. disk->random = state;
  1637. }
  1638. }
  1639. #endif
  1640. static ssize_t
  1641. urandom_read_nowarn(struct file *file, char __user *buf, size_t nbytes,
  1642. loff_t *ppos)
  1643. {
  1644. int ret;
  1645. nbytes = min_t(size_t, nbytes, INT_MAX >> (ENTROPY_SHIFT + 3));
  1646. ret = extract_crng_user(buf, nbytes);
  1647. trace_urandom_read(8 * nbytes, 0, ENTROPY_BITS(&input_pool));
  1648. return ret;
  1649. }
  1650. static ssize_t
  1651. urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
  1652. {
  1653. unsigned long flags;
  1654. static int maxwarn = 10;
  1655. if (!crng_ready() && maxwarn > 0) {
  1656. maxwarn--;
  1657. if (__ratelimit(&urandom_warning))
  1658. pr_notice("%s: uninitialized urandom read (%zd bytes read)\n",
  1659. current->comm, nbytes);
  1660. spin_lock_irqsave(&primary_crng.lock, flags);
  1661. crng_init_cnt = 0;
  1662. spin_unlock_irqrestore(&primary_crng.lock, flags);
  1663. }
  1664. return urandom_read_nowarn(file, buf, nbytes, ppos);
  1665. }
  1666. static ssize_t
  1667. random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
  1668. {
  1669. int ret;
  1670. ret = wait_for_random_bytes();
  1671. if (ret != 0)
  1672. return ret;
  1673. return urandom_read_nowarn(file, buf, nbytes, ppos);
  1674. }
  1675. static __poll_t
  1676. random_poll(struct file *file, poll_table * wait)
  1677. {
  1678. __poll_t mask;
  1679. poll_wait(file, &crng_init_wait, wait);
  1680. poll_wait(file, &random_write_wait, wait);
  1681. mask = 0;
  1682. if (crng_ready())
  1683. mask |= EPOLLIN | EPOLLRDNORM;
  1684. if (ENTROPY_BITS(&input_pool) < random_write_wakeup_bits)
  1685. mask |= EPOLLOUT | EPOLLWRNORM;
  1686. return mask;
  1687. }
  1688. static int
  1689. write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
  1690. {
  1691. size_t bytes;
  1692. __u32 t, buf[16];
  1693. const char __user *p = buffer;
  1694. while (count > 0) {
  1695. int b, i = 0;
  1696. bytes = min(count, sizeof(buf));
  1697. if (copy_from_user(&buf, p, bytes))
  1698. return -EFAULT;
  1699. for (b = bytes ; b > 0 ; b -= sizeof(__u32), i++) {
  1700. if (!arch_get_random_int(&t))
  1701. break;
  1702. buf[i] ^= t;
  1703. }
  1704. count -= bytes;
  1705. p += bytes;
  1706. mix_pool_bytes(r, buf, bytes);
  1707. cond_resched();
  1708. }
  1709. return 0;
  1710. }
  1711. static ssize_t random_write(struct file *file, const char __user *buffer,
  1712. size_t count, loff_t *ppos)
  1713. {
  1714. size_t ret;
  1715. ret = write_pool(&input_pool, buffer, count);
  1716. if (ret)
  1717. return ret;
  1718. return (ssize_t)count;
  1719. }
  1720. static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
  1721. {
  1722. int size, ent_count;
  1723. int __user *p = (int __user *)arg;
  1724. int retval;
  1725. switch (cmd) {
  1726. case RNDGETENTCNT:
  1727. /* inherently racy, no point locking */
  1728. ent_count = ENTROPY_BITS(&input_pool);
  1729. if (put_user(ent_count, p))
  1730. return -EFAULT;
  1731. return 0;
  1732. case RNDADDTOENTCNT:
  1733. if (!capable(CAP_SYS_ADMIN))
  1734. return -EPERM;
  1735. if (get_user(ent_count, p))
  1736. return -EFAULT;
  1737. return credit_entropy_bits_safe(&input_pool, ent_count);
  1738. case RNDADDENTROPY:
  1739. if (!capable(CAP_SYS_ADMIN))
  1740. return -EPERM;
  1741. if (get_user(ent_count, p++))
  1742. return -EFAULT;
  1743. if (ent_count < 0)
  1744. return -EINVAL;
  1745. if (get_user(size, p++))
  1746. return -EFAULT;
  1747. retval = write_pool(&input_pool, (const char __user *)p,
  1748. size);
  1749. if (retval < 0)
  1750. return retval;
  1751. return credit_entropy_bits_safe(&input_pool, ent_count);
  1752. case RNDZAPENTCNT:
  1753. case RNDCLEARPOOL:
  1754. /*
  1755. * Clear the entropy pool counters. We no longer clear
  1756. * the entropy pool, as that's silly.
  1757. */
  1758. if (!capable(CAP_SYS_ADMIN))
  1759. return -EPERM;
  1760. if (xchg(&input_pool.entropy_count, 0) && random_write_wakeup_bits) {
  1761. wake_up_interruptible(&random_write_wait);
  1762. kill_fasync(&fasync, SIGIO, POLL_OUT);
  1763. }
  1764. return 0;
  1765. case RNDRESEEDCRNG:
  1766. if (!capable(CAP_SYS_ADMIN))
  1767. return -EPERM;
  1768. if (crng_init < 2)
  1769. return -ENODATA;
  1770. crng_reseed(&primary_crng, &input_pool);
  1771. WRITE_ONCE(crng_global_init_time, jiffies - 1);
  1772. return 0;
  1773. default:
  1774. return -EINVAL;
  1775. }
  1776. }
  1777. static int random_fasync(int fd, struct file *filp, int on)
  1778. {
  1779. return fasync_helper(fd, filp, on, &fasync);
  1780. }
  1781. const struct file_operations random_fops = {
  1782. .read = random_read,
  1783. .write = random_write,
  1784. .poll = random_poll,
  1785. .unlocked_ioctl = random_ioctl,
  1786. .compat_ioctl = compat_ptr_ioctl,
  1787. .fasync = random_fasync,
  1788. .llseek = noop_llseek,
  1789. };
  1790. const struct file_operations urandom_fops = {
  1791. .read = urandom_read,
  1792. .write = random_write,
  1793. .unlocked_ioctl = random_ioctl,
  1794. .compat_ioctl = compat_ptr_ioctl,
  1795. .fasync = random_fasync,
  1796. .llseek = noop_llseek,
  1797. };
  1798. SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
  1799. unsigned int, flags)
  1800. {
  1801. int ret;
  1802. if (flags & ~(GRND_NONBLOCK|GRND_RANDOM|GRND_INSECURE))
  1803. return -EINVAL;
  1804. /*
  1805. * Requesting insecure and blocking randomness at the same time makes
  1806. * no sense.
  1807. */
  1808. if ((flags & (GRND_INSECURE|GRND_RANDOM)) == (GRND_INSECURE|GRND_RANDOM))
  1809. return -EINVAL;
  1810. if (count > INT_MAX)
  1811. count = INT_MAX;
  1812. if (!(flags & GRND_INSECURE) && !crng_ready()) {
  1813. if (flags & GRND_NONBLOCK)
  1814. return -EAGAIN;
  1815. ret = wait_for_random_bytes();
  1816. if (unlikely(ret))
  1817. return ret;
  1818. }
  1819. return urandom_read_nowarn(NULL, buf, count, NULL);
  1820. }
  1821. /********************************************************************
  1822. *
  1823. * Sysctl interface
  1824. *
  1825. ********************************************************************/
  1826. #ifdef CONFIG_SYSCTL
  1827. #include <linux/sysctl.h>
  1828. static int min_write_thresh;
  1829. static int max_write_thresh = INPUT_POOL_WORDS * 32;
  1830. static int random_min_urandom_seed = 60;
  1831. static char sysctl_bootid[16];
  1832. /*
  1833. * This function is used to return both the bootid UUID, and random
  1834. * UUID. The difference is in whether table->data is NULL; if it is,
  1835. * then a new UUID is generated and returned to the user.
  1836. *
  1837. * If the user accesses this via the proc interface, the UUID will be
  1838. * returned as an ASCII string in the standard UUID format; if via the
  1839. * sysctl system call, as 16 bytes of binary data.
  1840. */
  1841. static int proc_do_uuid(struct ctl_table *table, int write,
  1842. void *buffer, size_t *lenp, loff_t *ppos)
  1843. {
  1844. struct ctl_table fake_table;
  1845. unsigned char buf[64], tmp_uuid[16], *uuid;
  1846. uuid = table->data;
  1847. if (!uuid) {
  1848. uuid = tmp_uuid;
  1849. generate_random_uuid(uuid);
  1850. } else {
  1851. static DEFINE_SPINLOCK(bootid_spinlock);
  1852. spin_lock(&bootid_spinlock);
  1853. if (!uuid[8])
  1854. generate_random_uuid(uuid);
  1855. spin_unlock(&bootid_spinlock);
  1856. }
  1857. sprintf(buf, "%pU", uuid);
  1858. fake_table.data = buf;
  1859. fake_table.maxlen = sizeof(buf);
  1860. return proc_dostring(&fake_table, write, buffer, lenp, ppos);
  1861. }
  1862. /*
  1863. * Return entropy available scaled to integral bits
  1864. */
  1865. static int proc_do_entropy(struct ctl_table *table, int write,
  1866. void *buffer, size_t *lenp, loff_t *ppos)
  1867. {
  1868. struct ctl_table fake_table;
  1869. int entropy_count;
  1870. entropy_count = *(int *)table->data >> ENTROPY_SHIFT;
  1871. fake_table.data = &entropy_count;
  1872. fake_table.maxlen = sizeof(entropy_count);
  1873. return proc_dointvec(&fake_table, write, buffer, lenp, ppos);
  1874. }
  1875. static int sysctl_poolsize = INPUT_POOL_WORDS * 32;
  1876. extern struct ctl_table random_table[];
  1877. struct ctl_table random_table[] = {
  1878. {
  1879. .procname = "poolsize",
  1880. .data = &sysctl_poolsize,
  1881. .maxlen = sizeof(int),
  1882. .mode = 0444,
  1883. .proc_handler = proc_dointvec,
  1884. },
  1885. {
  1886. .procname = "entropy_avail",
  1887. .maxlen = sizeof(int),
  1888. .mode = 0444,
  1889. .proc_handler = proc_do_entropy,
  1890. .data = &input_pool.entropy_count,
  1891. },
  1892. {
  1893. .procname = "write_wakeup_threshold",
  1894. .data = &random_write_wakeup_bits,
  1895. .maxlen = sizeof(int),
  1896. .mode = 0644,
  1897. .proc_handler = proc_dointvec_minmax,
  1898. .extra1 = &min_write_thresh,
  1899. .extra2 = &max_write_thresh,
  1900. },
  1901. {
  1902. .procname = "urandom_min_reseed_secs",
  1903. .data = &random_min_urandom_seed,
  1904. .maxlen = sizeof(int),
  1905. .mode = 0644,
  1906. .proc_handler = proc_dointvec,
  1907. },
  1908. {
  1909. .procname = "boot_id",
  1910. .data = &sysctl_bootid,
  1911. .maxlen = 16,
  1912. .mode = 0444,
  1913. .proc_handler = proc_do_uuid,
  1914. },
  1915. {
  1916. .procname = "uuid",
  1917. .maxlen = 16,
  1918. .mode = 0444,
  1919. .proc_handler = proc_do_uuid,
  1920. },
  1921. #ifdef ADD_INTERRUPT_BENCH
  1922. {
  1923. .procname = "add_interrupt_avg_cycles",
  1924. .data = &avg_cycles,
  1925. .maxlen = sizeof(avg_cycles),
  1926. .mode = 0444,
  1927. .proc_handler = proc_doulongvec_minmax,
  1928. },
  1929. {
  1930. .procname = "add_interrupt_avg_deviation",
  1931. .data = &avg_deviation,
  1932. .maxlen = sizeof(avg_deviation),
  1933. .mode = 0444,
  1934. .proc_handler = proc_doulongvec_minmax,
  1935. },
  1936. #endif
  1937. { }
  1938. };
  1939. #endif /* CONFIG_SYSCTL */
  1940. struct batched_entropy {
  1941. union {
  1942. u64 entropy_u64[CHACHA_BLOCK_SIZE / sizeof(u64)];
  1943. u32 entropy_u32[CHACHA_BLOCK_SIZE / sizeof(u32)];
  1944. };
  1945. unsigned int position;
  1946. spinlock_t batch_lock;
  1947. };
  1948. /*
  1949. * Get a random word for internal kernel use only. The quality of the random
  1950. * number is good as /dev/urandom, but there is no backtrack protection, with
  1951. * the goal of being quite fast and not depleting entropy. In order to ensure
  1952. * that the randomness provided by this function is okay, the function
  1953. * wait_for_random_bytes() should be called and return 0 at least once at any
  1954. * point prior.
  1955. */
  1956. static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u64) = {
  1957. .batch_lock = __SPIN_LOCK_UNLOCKED(batched_entropy_u64.lock),
  1958. };
  1959. u64 get_random_u64(void)
  1960. {
  1961. u64 ret;
  1962. unsigned long flags;
  1963. struct batched_entropy *batch;
  1964. static void *previous;
  1965. warn_unseeded_randomness(&previous);
  1966. batch = raw_cpu_ptr(&batched_entropy_u64);
  1967. spin_lock_irqsave(&batch->batch_lock, flags);
  1968. if (batch->position % ARRAY_SIZE(batch->entropy_u64) == 0) {
  1969. extract_crng((u8 *)batch->entropy_u64);
  1970. batch->position = 0;
  1971. }
  1972. ret = batch->entropy_u64[batch->position++];
  1973. spin_unlock_irqrestore(&batch->batch_lock, flags);
  1974. return ret;
  1975. }
  1976. EXPORT_SYMBOL(get_random_u64);
  1977. static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u32) = {
  1978. .batch_lock = __SPIN_LOCK_UNLOCKED(batched_entropy_u32.lock),
  1979. };
  1980. u32 get_random_u32(void)
  1981. {
  1982. u32 ret;
  1983. unsigned long flags;
  1984. struct batched_entropy *batch;
  1985. static void *previous;
  1986. warn_unseeded_randomness(&previous);
  1987. batch = raw_cpu_ptr(&batched_entropy_u32);
  1988. spin_lock_irqsave(&batch->batch_lock, flags);
  1989. if (batch->position % ARRAY_SIZE(batch->entropy_u32) == 0) {
  1990. extract_crng((u8 *)batch->entropy_u32);
  1991. batch->position = 0;
  1992. }
  1993. ret = batch->entropy_u32[batch->position++];
  1994. spin_unlock_irqrestore(&batch->batch_lock, flags);
  1995. return ret;
  1996. }
  1997. EXPORT_SYMBOL(get_random_u32);
  1998. /* It's important to invalidate all potential batched entropy that might
  1999. * be stored before the crng is initialized, which we can do lazily by
  2000. * simply resetting the counter to zero so that it's re-extracted on the
  2001. * next usage. */
  2002. static void invalidate_batched_entropy(void)
  2003. {
  2004. int cpu;
  2005. unsigned long flags;
  2006. for_each_possible_cpu (cpu) {
  2007. struct batched_entropy *batched_entropy;
  2008. batched_entropy = per_cpu_ptr(&batched_entropy_u32, cpu);
  2009. spin_lock_irqsave(&batched_entropy->batch_lock, flags);
  2010. batched_entropy->position = 0;
  2011. spin_unlock(&batched_entropy->batch_lock);
  2012. batched_entropy = per_cpu_ptr(&batched_entropy_u64, cpu);
  2013. spin_lock(&batched_entropy->batch_lock);
  2014. batched_entropy->position = 0;
  2015. spin_unlock_irqrestore(&batched_entropy->batch_lock, flags);
  2016. }
  2017. }
  2018. /**
  2019. * randomize_page - Generate a random, page aligned address
  2020. * @start: The smallest acceptable address the caller will take.
  2021. * @range: The size of the area, starting at @start, within which the
  2022. * random address must fall.
  2023. *
  2024. * If @start + @range would overflow, @range is capped.
  2025. *
  2026. * NOTE: Historical use of randomize_range, which this replaces, presumed that
  2027. * @start was already page aligned. We now align it regardless.
  2028. *
  2029. * Return: A page aligned address within [start, start + range). On error,
  2030. * @start is returned.
  2031. */
  2032. unsigned long
  2033. randomize_page(unsigned long start, unsigned long range)
  2034. {
  2035. if (!PAGE_ALIGNED(start)) {
  2036. range -= PAGE_ALIGN(start) - start;
  2037. start = PAGE_ALIGN(start);
  2038. }
  2039. if (start > ULONG_MAX - range)
  2040. range = ULONG_MAX - start;
  2041. range >>= PAGE_SHIFT;
  2042. if (range == 0)
  2043. return start;
  2044. return start + (get_random_long() % range << PAGE_SHIFT);
  2045. }
  2046. /* Interface for in-kernel drivers of true hardware RNGs.
  2047. * Those devices may produce endless random bits and will be throttled
  2048. * when our pool is full.
  2049. */
  2050. void add_hwgenerator_randomness(const char *buffer, size_t count,
  2051. size_t entropy)
  2052. {
  2053. struct entropy_store *poolp = &input_pool;
  2054. if (unlikely(crng_init == 0)) {
  2055. size_t ret = crng_fast_load(buffer, count);
  2056. count -= ret;
  2057. buffer += ret;
  2058. if (!count || crng_init == 0)
  2059. return;
  2060. }
  2061. /* Suspend writing if we're above the trickle threshold.
  2062. * We'll be woken up again once below random_write_wakeup_thresh,
  2063. * or when the calling thread is about to terminate.
  2064. */
  2065. wait_event_interruptible(random_write_wait,
  2066. !system_wq || kthread_should_stop() ||
  2067. ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits);
  2068. mix_pool_bytes(poolp, buffer, count);
  2069. credit_entropy_bits(poolp, entropy);
  2070. }
  2071. EXPORT_SYMBOL_GPL(add_hwgenerator_randomness);
  2072. /* Handle random seed passed by bootloader.
  2073. * If the seed is trustworthy, it would be regarded as hardware RNGs. Otherwise
  2074. * it would be regarded as device data.
  2075. * The decision is controlled by CONFIG_RANDOM_TRUST_BOOTLOADER.
  2076. */
  2077. void add_bootloader_randomness(const void *buf, unsigned int size)
  2078. {
  2079. if (IS_ENABLED(CONFIG_RANDOM_TRUST_BOOTLOADER))
  2080. add_hwgenerator_randomness(buf, size, size * 8);
  2081. else
  2082. add_device_randomness(buf, size);
  2083. }
  2084. EXPORT_SYMBOL_GPL(add_bootloader_randomness);