[HN Gopher] New and improved Linux Random Number Generator ready...
___________________________________________________________________
New and improved Linux Random Number Generator ready for testing
Author : feross
Score : 97 points
Date : 2021-11-17 18:01 UTC (2 days ago)
(HTM) web link (portswigger.net)
(TXT) w3m dump (portswigger.net)
| jeffbee wrote:
| QQ: why does this belong in the kernel at all?
| jdlyga wrote:
| tl;dr the solution is a USB-powered cup of Yahtzee dice. There
| was some debate over the color of the dice and usb-c vs usb-a.
| But it will be included in the next kernel release and shipped
| out to every user of the linux kernel with the next update.
| ape4 wrote:
| You never hear about developments of the RNG on other OSes. It
| gives me more confidence that the Linux RNG is constantly being
| reviewed.
| loeg wrote:
| https://aka.ms/win10rng
| masklinn wrote:
| > You never hear about developments of the RNG on other OSes.
|
| Probably because you don't listen?
|
| > It gives me more confidence that the Linux RNG is constantly
| being reviewed.
|
| It took decades for the linux devs to abandon their idiotic
| concept of running out of entropy and making /dev/random stop
| blocking (that happened last year in the 5.6 kernel).
|
| Hell, after getentropy was introduced by openbsd, not only did
| linux decide to invent their own variant they just had to
| replicate /dev/random's running-out-of-entropy behaviour.
| zamadatix wrote:
| > It took decades for the linux devs to abandon their idiotic
| concept of running out of entropy and making /dev/random stop
| blocking (that happened last year in the 5.6 kernel
|
| It wasn't an idiotic concept it was 1 part "No longer needed
| for trust in the algorithms used by /dev/urandom" and 1 part
| "Did 2 functions but was really used for 1". Since the
| majority of people were using it just as a source of secure
| random data (not the 2nd use of aggregating sources of
| entropy) and CSPRNGs (and the implementation of in the
| kernel) are much more trusted now it made sense to change.
| That doesn't mean it was an idiotic concept it just outlived
| its reasons for having been implemented that way and was
| changed.
|
| For clarity's sake to others that may not be as familiar
| /dev/random still blocks it was the concept of the blocking
| pool that was removed. I.e. once it has been fully
| initialized post boot it will serve an endless stream of
| random data as fast as it can regardless of how much new
| entropy enters the system. This is what tools actually need,
| some other systems have provided this via a separate
| /dev/arandom. /dev/urandom still acts the same way it always
| has, it'll serve you the output of the CSPRNG regardless if
| it has had enough time to properly seed it with entropy yet
| (so may act more like a standard PRNG very early into the
| boot cycle).
| DeathArrow wrote:
| I hope NSA is not involved.
|
| https://twitter.com/matthew_d_green/status/14334701097425182...
| rurban wrote:
| Which comes directly from a suspected NSA mouth. No, it's from
| the German BSI, which is a NSA collaborator.
|
| Still better than the current implementation.
| joconde wrote:
| Who suspects Matthew Green of being an "NSA mouth", and why?
| He's constantly advocating for more privacy and stronger
| crypto in software.
| zrm wrote:
| Also, what he's talking about is from the Snowden stuff:
|
| https://en.wikipedia.org/wiki/Dual_EC_DRBG
| salmo wrote:
| This is something that has frustrated me for years. There has
| been no interest in modernizing the Linux PRNG really ever. This
| article doesn't go into more depth so I don't know if it's just
| tacking on more entropy sources and algorithm support or a real
| modernization.
|
| Windows, MacOS, every BSD, Solaris, etc. have moved past the
| (blocking) /dev/random vs /dev/urandom to more mathematically
| sound solutions. (Seriously, measuring entropy?) But Torvalds,
| Ts'o, etc. have blocked, belittled, or ignored any movement
| there.
|
| It's crazy that the OS that runs all the things essentially has a
| roll-your-own-crypto PRNG at its core rather than relying on
| actual experts for that.
|
| Unfortunately, it's "good enough" to not HAVE to change. Use
| /dev/random sparingly to seed your own PRNG, change your Java
| config to use /dev/urandom, or (shudder) use rngd to make it seed
| itself.
|
| At least once a year I hit some COTS product that craps itself
| under load blocking on /dev/random on a VM, causing an outage.
| Yes, it's a "worked on my laptop" problem, but an unnecessary
| rake to leave out in the garden.
| gerdesj wrote:
| This is from early last year:
|
| https://lwn.net/Articles/808575/ "Removing the Linux
| /dev/random blocking pool"
| jeltz wrote:
| Linux has also moved past it, but only quite recently.
|
| https://lwn.net/Articles/808575/
| daneel_w wrote:
| I wonder why they just didn't take a cue from OpenBSD's
| arc4random solution years ago, instead of this drawn-out
| contortion.
| iamgopal wrote:
| How to measure randomness ? Even distribution ? Volatility ?
| Independence ?
| e0a74c wrote:
| A few approaches: https://en.wikipedia.org/wiki/Diehard_tests
| and https://en.wikipedia.org/wiki/Randomness_test
| genewitch wrote:
| Don't forget the NIST test suite
|
| https://csrc.nist.gov/CSRC/media/Projects/Random-Bit-
| Generat...
| kevincox wrote:
| You can't truly measure randomness, by definition a true random
| source would have exactly the same probably to produce any
| sequence of bits, so given any two sequences it is impossible
| to say for sure that one is "more random" than another.
|
| However there are many well-accepted tests for judging that a
| sequences of bits is likely to be random. Basically these tests
| are looking for common failure modes and expected statistics
| that are likely to fail if your source isn't truly random (for
| example distribution skew, repeating patterns, ...).
|
| But it is important to clarify that these tests are guesses.
| The have both false-positives and false-negatives. For example
| a "random number generator" that just has a large hardcoded
| list of random-looking values and loops over the list may pass
| a test if the list is long enough that the loop can't be
| detected, even though the values are decidedly not random. On
| the other hand a true random source may generate a very long
| sequence of zeros, the probability would be infinitesimal, but
| it is entirely possible and doesn't mean that the source isn't
| random.
| asdf_snar wrote:
| I have a question about the statement "you can't truly
| measure randomness", if it's alright (since you seem
| knowledgeable about this).
|
| > For example a "random number generator" that just has a
| large hardcoded list of random-looking values and loops over
| the list may pass a test if the list is long enough that the
| loop can't be detected, even though the values are decidedly
| not random.
|
| My understanding is that's entirely fine from a statistical
| point of view. One can establish properties of this sequence
| up to some probabilistic error, perhaps also depending on the
| total number of values from the list that end up being used.
|
| Isn't this in some sense analogous to measurement error? As
| far as I know, nothing can be precisely "measured" either. Is
| there a deeper sense in which the quality of the random
| sequence can't be analogously assessed?
| kevincox wrote:
| > since you seem knowledgeable about this
|
| I should probably state to be clear that I am not a
| cryptographer. I just have an interest in the subject.
|
| It also depends a lot what you mean by random. I generally
| take "random value" to mean "a value which can not be
| predicted". Of course in cryptography we often use a CSPRNG
| which can be perfectly predicted, it is deterministic, not
| random at all! However in that case what we actually care
| about is "a value which can not be predicted without
| knowing the secret state". For many use cases this is
| sufficiently close to true random. (Or the predictability
| can actually be useful, for example using a CSPRNG as a
| stream cypher.)
|
| The reason why I said that my large hardcoded list was not
| random is that it is predictable. It is easily predictable
| if you know the hardcoded list of course. But even if you
| declare that list as "secret state" it is still predictable
| once it starts repeating and spews out the exact sequence
| of bits over and over again.
|
| > My understanding is that's entirely fine from a
| statistical point of view.
|
| Sure, but statistics are different than cryptography. If
| you just want your simulation to work well it is probably
| fine (unless the repeating causes funny artifacts in the
| simulation). I would argue that for most non-cryptographic
| use cases you don't even need anything close to "true
| random", you just need a distribution that matches your
| desired distribution with little bias and ideally doesn't
| repeat in a way that aligns poorly with how you use the
| numbers.
|
| > Isn't this in some sense analogous to measurement error?
|
| I'm not sure I completely follow here but I think the
| answer is "no". The difference is that randomness is a
| property of the generation process, not the output.
| https://xkcd.com/221/ is a great way to highlight this. In
| this case 4 was a very good quality random number. No once
| could have predicted it with greater that 1/6 probability.
| However once you check it into source code it isn't
| "random" any more. This is because the die produces "random
| numbers" but there is nothing special about the number
| itself. There is no test that will tell you that "4" is
| random or non-random, the question doesn't really make
| sense.
|
| What the tests do is they take a list of values and try to
| detect "problems" (situations in the output that would be
| unlikely if the source was truly random). For example if
| you have a weighed die that rolls 6 80% of the time a good
| test will tell you that your random source is _likely_
| biased based on a sample of output values. Of course the
| more data you feed to the test the more likely that it is
| that failures are true failures. If you roll a die 10 times
| and don 't get a 6 it isn't proof that the die is unfair or
| predictable in some way. If you roll that same die 1000
| times without a six it is looking much more suspicious, but
| still impossible to prove just by looking at the outputs.
| nvarsj wrote:
| > For example a "random number generator" that just has a
| large hardcoded list of random-looking values and loops over
| the list may pass a test if the list is long enough that the
| loop can't be detected, even though the values are decidedly
| not random.
|
| Even cryptographically secure RNGs have fixed periods, they
| are not infinite. What's important is how long that "list"
| is. So for purposes of computer randomness, a long fixed list
| may indeed be okay if it is truly long enough. It will need
| to be truly massive to pass Diehard though.
| kevincox wrote:
| For sure. However most CSPRNGs have "huge" periods which
| would be infeasible to hardcode into a software
| implementation. Knowing your period is important any time
| you use a PRNG for cryptography.
| davidgrenier wrote:
| http://simul.iro.umontreal.ca/testu01/tu01.html
|
| Maybe? I'm not familiar, summarily discussed it with research
| director.
| [deleted]
| DevX101 wrote:
| > According to Muller, LPRG incorporates four entropy sources
| that operate completely independent of each other including
| execution timing jitter and the timing of the arrival of
| interrupts.
|
| Can you 'lie' to the operating system about these sources of
| entropy in order to control the random number generation?
| CodeArtisan wrote:
| Last time i checked, /dev/random was receiving entropy from
|
| * The kernel command line string at boot.
|
| * Every time there is an input event (mouse, keyboard, ...).
|
| * Every time there is a disk event.
|
| * By retrieving the cpu cycles counter (RDTSC on x86) from
| random interrupts.
|
| * Hardware RNGs(RDRAND on x86).
|
| * From latent entropy every time a process is created.
|
| Latent entropy is a 64 bits unsigned that has its state
| modified every time a procedure with the attribute
| latent_entropy is executed. The latent_entropy attribute is
| implemented by a GCC plugin and adds random operations on the
| latent_entropy seed to a procedure. For example
| void foo(bool a) __attribute__((latent_entropy)) {
| if (a) bar(); else
| baz(); }
|
| become void foo(bool a)
| __attribute__((latent_entropy)) { if (a)
| { latent_entropy OP NUMBER;
| bar(); } else {
| latent_entropy OP NUMBER; baz(); }
| }
|
| where OP (*= += -= ^= ...) and NUMBER are randomly generated at
| compilation time.
|
| Many kernel procedures handling interrupts have the
| latent_entropy attribute.
|
| more information at
| https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
| not-elite wrote:
| Of course.
|
| https://groups.google.com/g/randomness-generation/c/eNnepJ_6...
| danuker wrote:
| If lives (or life savings) are at stake, I'd still xor some dice
| values in the mix.
|
| https://glacierprotocol.org/docs/deposit/generate-cold-stora...
| beermonster wrote:
| Or some lava lamps
| kuroguro wrote:
| Probably a reference to cloudflare:
| https://www.cloudflare.com/learning/ssl/lava-lamp-
| encryption...
| hoytech wrote:
| lavarand was invented and patented by SGI in 1996:
| https://www.lavarand.org/news/lavadiff.html
| genewitch wrote:
| There was a library to use webcams for entropy called
| lavarnd up until about 8 years ago, as well. I am unsure
| if the api to the os changed or there's a functional
| difference between ccd and cmos or whatever.
|
| I do a lot of entropy research, and was annoyed I had to
| roll my own implementation for a no-photon camera entropy
| source.
| throw0101a wrote:
| See also Diceware:
|
| * https://en.wikipedia.org/wiki/Diceware
|
| Useful site:
|
| * https://www.rempe.us/diceware/
| ncmncm wrote:
| We should be stirring in the low bits of image pixels on attached
| cameras, and the bottom bits of mic and radio receiver input.
| willis936 wrote:
| Only if we trust the camera to not have a specific upper limit
| on image processing. It's also a decent attack vector. Any old
| USB plug could lower system entropy. If everything else is done
| properly this isn't an issue, but it still seems to increase
| attack surface area for little gain.
| ncmncm wrote:
| It is not possible for any such attack to "lower system
| entropy". Bytes stirred into the pool can only ever add
| entropy.
| strenholme wrote:
| If we use a secure cryptographic algorithm which combines
| different entropy sources and then hashes them together, even
| a completely insecure additional source of entropy will not
| reduce the security of /dev/random [1]
|
| If we have 10 different sources of entropy for our random
| number generator, and only one of them is truly random, our
| random number generator is still secure.
|
| [1] There's an issue where /dev/random will have less actual
| entropy than it think it has, but as long as we have 128
| bits[2] or more of actual entropy, the output will still be
| secure.
|
| [2] 256 bits if worrying about quantum computers or
| theoretical future computers the size of a continent
| IgorPartola wrote:
| What exactly is the point of adding 9 known insecure
| sources if only one is doing the actual useful work? Is it
| less secure? I guess not. Is it more secure? Doesn't seem
| like it.
| [deleted]
| wizeman wrote:
| > Is it more secure? Doesn't seem like it.
|
| Why not? Unless all 9 "insecure" sources are 100%
| attacker-controlled or broken at the same time, they
| would still be adding entropy.
|
| Each additional source is adding one more hoop for the
| attacker to have to jump through.
|
| The more sources are added, the less the chance that all
| of them are broken or attacker-controlled at the same
| time on the same computer.
|
| Conversely, if you only have one (presumably good)
| entropy source it would be much easier for it to be
| compromised than if you have 10 sources, including the
| good one (even though some of them are easier to break
| than others).
| zrm wrote:
| Suppose you have 10 sources of entropy and you don't know
| which ones are good. If you pick one, and you pick the
| wrong one, you lose. If you use all of them with an
| algorithm that works as long as any one of them is good,
| and any one of them is good, you're good.
| CJefferson wrote:
| The question is, which sources are "known secure"? There
| have been AMD systems where RDRAND is broken and always
| returns the same value -- I bet those users would have
| been happy if their webcam got mixed in.
| IgorPartola wrote:
| Even if their webcam was pointed at a black wall in a
| dark room?
| CJefferson wrote:
| I just checked and my camera, even if a close the cover
| and put it under a blanket, still doesn't return straight
| zeroes. As long as there is some "fuzz" there is
| something useful to generate randomness.
|
| Also, it would be reasonable for the RNG to notice some
| source is returning input of no value (straight zeroes)
| and reject it.
| adzm wrote:
| You can actually use a camera sensor as a kind of Geiger
| counter by blocking normal light eg with foil and
| measuring fluctuations in the results!
| BenjiWiebe wrote:
| If you add 9 known not-very-good sources of randomness,
| it's still better than adding no sources of randomness.
|
| Now if your 9 bad sources are _100%_ predictable, then
| yes, there 's no point in adding them.
| charcircuit wrote:
| You wouldn't. He is just talking about a worst case
| scenario. He's is saying that as long as one of your
| sources of randomness is "truly" random you are fine.l
| viraptor wrote:
| That's more high level then what kernel normally deals with.
| You can use rngd in userland to do it though.
| rp1 wrote:
| Turning on the camera for any reason would creep me out
| ncmncm wrote:
| So, stir them in only if it is being used anyway.
| ploxiln wrote:
| Stephan Muller has proposed his "LRNG" rewrite 5 years ago, and
| it was not well received by the linux random subsystem maintainer
| Ted Ts'o:
|
| https://lkml.org/lkml/2016/4/21/839
|
| but there has been a notable development in the subsystem this
| year, finally `/dev/random` blocks only before initialization,
| and never after!
|
| https://lore.kernel.org/lkml/20200131204924.GA455123@mit.edu...
| pierreprinetti wrote:
| FILIPPOOOOOOOOOOO come and save us
| charcircuit wrote:
| >The /dev/random is the "very foundation" of cryptography on
| Linux, developer Stephan Muller told The Daily Swig. "If
| /dev/random breaks, the entire cryptography on Linux is broken,"
| Muller said.
|
| I thought using /dev/random was depricated and that you should
| instead use a getrandom syscall that blocks if you don't have
| enough entropy.
| kenniskrag wrote:
| in the the man page they say only legacy
|
| > The /dev/random device is a legacy interface which dates back
| to a time where the cryptographic primitives used in the
| implementation of /dev/urandom were not widely trusted. It will
| return random bytes only within the estimated number of bits of
| fresh noise in the entropy pool, blocking if necessary.
| /dev/random is suitable for applications that need high quality
| randomness, and can afford indeterminate delays.
|
| and recommend:
|
| > Linux 3.17 and later provides the simpler and safer
| getrandom(2) interface which requires no special files; see the
| getrandom(2) manual page for details.
| cperciva wrote:
| You're right, but when kernel developers talk about /dev/random
| they generally mean the underlying RNG, not the interface by
| which you access it. To a userland developer the phrase "read
| from /dev/random via the getrandom system call" is nonsense but
| to a kernel developer it sounds reasonable.
| dTal wrote:
| /dev/random _does_ block "if you don't have enough entropy"
| (in contrast to /dev/urandom, which doesn't). The only
| difference is that getrandom() doesn't require a file
| descriptor to use.
|
| Note that "if you don't have enough entropy" is not based on
| any rigorous formal analysis, which is why /dev/urandom has
| been recommended for a long time, and why the entire concept of
| blocking randomness syscalls is controversial in kernel-land:
|
| https://lwn.net/Articles/800509/
| shaicoleman wrote:
| Since Linux 5.6, /dev/random only blocks during initialization
| until it gets the initial entropy, and behaves like
| /dev/urandom afterwards.
|
| https://www.phoronix.com/scan.php?page=news_item&px=Linux-5....
| ur-whale wrote:
| > blocks if you don't have enough entropy
|
| Which, in most cases I can think of is a rather undesirable
| behavior.
|
| I would really be interested to understand which use cases
| justify using an actual blocking call to retrieve random bits.
|
| I've always been under the impression that the only valid use
| case for raw entropy bits is regularly seeding crypto-hard RNGs
| that can generate an endless stream of random bits (a la
| /dev/urandom).
|
| Looking forward to being educated on the topic.
| GoblinSlayer wrote:
| https://crypto.stackexchange.com/questions/9694/technical-
| de...
| rainworld wrote:
| Correct behavior: Block (or don't be available) until you can
| securely generate an effectively endless stream of random
| bits, then never.
|
| Correct API: https://fuchsia.dev/fuchsia-
| src/reference/syscalls/cprng_dra...
| uvesten wrote:
| I decided to have a quick look, and this caught my eye: ---
| zx_cprng_draw() terminates the calling process if buffer is
| not a valid userspace pointer. ----
|
| "Terminates the calling process"? That sounds different and
| interesting, do you know more about this aspect of Fuchsia?
| rainworld wrote:
| I'm not too familiar with Fuchsia, but other syscalls
| return ZX_ERR_INVALID_ARGS so I suspect the idea was to
| keep this particular, security-critical call as simple as
| possible. This behavior shouldn't break any code that
| wasn't already broken.
| m_eiman wrote:
| > I would really be interested to understand which use cases
| justify using an actual blocking call to retrieve random
| bits.
|
| The only case I can think of is when you've mass produced a
| million devices that each need unique certificates that are
| generated on first boot. If no good source of randomness is
| available, there's a decent risk you'll have duplicates.
| strenholme wrote:
| There is a lot said for making the Linux random number generator
| configurable. A good entropy (random number) source takes entropy
| from a number of different sources and combines it with a
| cryptographic strong algorithm: Either a strong hash whose output
| is made the key and IV for a stream cipher, or directly using an
| Extendable-Output Function (XOF) such as a cryptographic sponge.
| [1]
|
| For example, there is some controversy with the RDRAND (the x86
| "give me random bits" op code) operation, with concerns that
| maybe the numbers weren't truly random, and at least one known
| security hole where the RDRAND output could leak under some
| circumstances. However, it's widely available and probably makes
| good random bits. However, if it doesn't, we want other sources
| of entropy (microphone output low bits, interrupt timings, etc.)
| so /dev/random or /dev/urandom still gives us strong entropy even
| if RDRAND is completely busted.
|
| [1] I personally think a cryptographic sponge is ideal for this,
| since sponge functions have absorb, output, and duplex (absorb
| after output, i.e. accept new entropy from the system after
| outputting bits) functionality
| jstanley wrote:
| When I first got my Ryzen CPU, it had some bug where RDRAND
| always returned -1! Fortunately this was fixed in a microcode
| update.
| 0x0 wrote:
| Experienced something similar here. NodeJS node-sass would
| crash with "rdrand failed". Super weird experience to have to
| apply a BIOS update to fix a node_modules build failure, but
| that's 2021.
| CJefferson wrote:
| While having it configurable is one option, I'd prefer to just
| "chuck everything in".
|
| A feature I would like (which would make things more
| complicated I realise) would be to have a variety of sources,
| which estimated quality for each source, and then check the
| quality is still high even if one of the sources is "broken".
___________________________________________________________________
(page generated 2021-11-19 23:01 UTC)