Just to be clear, it's fine that you posted this! If checking search would have prevented you, that wouldn't be good. But you could always check search to find previous links to include for curiosity's sake (that's what I did), and to make sure that it hasn't had a significant discussion within the last year.
> About 256 bits of entropy are enough to get computationally secure numbers for a long, long time.
This isn't quite false, but it's deeply wrong; 256 bits is enough to produce 256-bit secure random numbers literally forever - the "long, long time" is precisely however long it takes a attacker to brute-force or otherwise recover a 256-bit RNG seed (aka private key).
> Look, I don't claim that injecting entropy is bad.
Note that injecting entropy less than 256 bits[0] at a time is bad, in that it wastes the entropy. If a attacker knows your RNG state (either due to compromise or because you just booted), injecting 128 bits, generating (≥128 bits of) output, and injecting another 128 bits, only gets you 128-bit security. If you inject in smaller chunks, say 32 bits (generating ≥32 bits of output in between), you might as well not be adding entropy at all.
Note, apropos of the above, that /dev/urandom must block during early boot (before X bits of entropy have been collected). If it doesn't, you have no entropy, because a attacker can repeatedly brute force your (say) <32-bit RNG state based on /dev/urandom outputs.
> If you inject in smaller chunks, say 32 bits, you might as well not be adding entropy at all.
Depends on how quickly state bits leak. If the state only leaks 2 bits per minute, then adding 32 bits every minute is perfectly sufficient. That's why even though actual leakage rate is >0 bits for any real-world CSPRNG it can still be perfectly acceptable (and even desirable, depending on threat profile) to add entropy at a rate of 0 bits.
> /dev/urandom must block during early boot
Assuming CPU jitter is a source of entropy[1], you can harvest 256 bits in a fixed amount of time. So it depends on the definition of "block". Does waiting an extra 2 seconds to boot constitute blocking if boot time already takes 1-2 seconds? On Linux I regularly see heavily loaded systems hang random processes for minutes just evicting VM pages (this is without swap, which is actually probably part of the problem), so I'm not sure what's so special about boot time in terms of how we define blocking operations. Faster is always better, of course.
[1] I'm dubious, but at least some kernel hackers think so. And Linus' personal opinions notwithstanding, he did add code that as a practical matter makes this assumption--because downstream users will never question it.
> Depends on how quickly state bits leak. If the state only leaks 2 bits per minute
Fixed, but I'm assuming you're actually using the RNG; if you only generate 2 bits of output per minute, you can get away with all kinds of dumb crap.
> So it depends on the definition of "block".
It's the same definition as any other (2)read syscall. Assuming a 32-byte read from /dev/random[0], it's equivalent to reading from a pipe with at least 32bytes buffered if the RNG is already initialized (read returns immediately); if the RNG is not initialized, its the same as reading from a empty pipe - the kernel switches to some other process after making a note to resume the calling process when some event happens ((2)write for a pipe, RNG initialization for /dev/random).
0: Or /dev/urandom, which should be literally the same character device, because there are never any legitimate reasons for them to differ.
You are misunderstanding the issue. If you only have two bits of entropy, than outputting two bits leaks the entire state, because two bits is brute forceable. This is true regardless of the quality of your RNG. The same is true of 32 bits, because 32 bits is also brute forceable. The reason to insert entropy in large chunks is so that an attacker cannot brute force the RNG state, between reseeds.
Regardless of your RNG algorithm, outputting 2 bits always[1] leaks a 2 bit state. If your state is only 2 bits[0], then there are only 4 possible states. With significant probability, your two output bits will be inconsistent with 3 of them.
In general, a N bit output will be inconsistent with 2^N - 1 of your 2^N possible internal states; the point of using ~256 bits of entropy is to ensure that it's computationally intractable to figure out which, and that only works if the attacker can't work out the first (second, etc) 32 bits separately from the subsequent ones.
0: of entropy, mind, not data. If the attacker knows your 64-byte RNG buffer, and you inject 2 bits of entropy, there are only 2^2=4 new 64-byte blobs that your buffer could have evolved to, so you have 512 bits of data with only 2 bits of entropy.
1: for any algorithm that is; on a per-event basis, there's obviously a chance that you happen to produce output that's consistent with multiple possible internal states.
> Depends on how quickly state bits leak. If the state only leaks 2 bits per minute, then adding 32 bits every minute is perfectly sufficient. That's why even though actual leakage rate is >0 bits for any real-world CSPRNG it can still be perfectly acceptable (and even desirable, depending on threat profile) to add entropy at a rate of 0 bits.
This isn’t the type information leak you should be concerned with. If you attacker has access to some segment of the output stream, they can detect whenever you update the RNG state, and brute force the new state unless you are updating it with a large enough chunks. 32-bits is certainly brute forceable.
Keep in mind that Linux 5.6 is imminent, and I haven't found time to investigate it beyond some short reporting in LWN, let alone update the article.
But it's still my intention to do that, with some restructuring along the way.
The more changes Linux makes (for the better!) and the more time passes and later versions are in common use, the less the format "tell everyone how bad it is and then backpeddle with sections about every improvement made" works, and the less the title itself stays relevant.
I don't have a good answer for that structural problem, yet, so I'm kind of procrastinating.
On that note, would it kill the OpenBSD guys to get on the getrandom(2) train? I get it, they're dying on the “arc4random is better” hill (and, yes, I agree), but they're literally the last people in the way of making getrandom(2) the new default across not only the usual BSDs and illumos, but also glibc/Linux.
OpenBSD has the getentropy(2) syscall which is pretty much the same. There is no "flags" parameter like in Linux. But the original rationale for having it be a syscall and not a device [not having an extra open(2) call that can fail] is addressed.
From a practical standpoint, I agree (I've started abusing getentropy(2) as a more portable replacement), but it violates the use case though: getentropy(2) is only intended to seed userspace RNGs. Breaking the usage scenario means breaking the API contract.
Doesn't `getrandom(2)` use `RDRAND`? Should hardware RNGs on ME or PSP enabled CPUs be inherently be trusted - I mean don't the BSD folks recommend not enabling hyperthreading due to Spectre, etc.
You think it's reasonable to have a function called arc4random, even though we know arc4 is insecure and creates biased (i.e. not pseudorandom) output, yet as we know that arc4random really is not "random numbers based on (a)rc4", because internally it's using something secure? So you'd have to actually know that this function named after an insecure stream cipher is a secure way to get random numbers?
I glanced at an online man page for this several minutes ago which informs that though this was originally RC4 based, it now stands for the "a replacement call for random".
I trust the OpenBSD team to get security right more than I do any other open source group. So no, I don't think a bandwagon argument is going to persuade them.
> And while appeal to authority is usually nothing to be proud of, in cryptographic issues you're generally right to be careful and try to get the opinion of a domain expert.
reminds me that cryptography is an area where subspecialty expertise has been in the professional consciousness forever
> About 256 bits of entropy are enough to get computationally secure numbers for a long, long time.
That's just word semantics that depends on how you define "computationally secure".
256 bits of entropy is good enough to get 1 random bit, 256 times. That's the hard fact.
For instance, 256 bits of entropy is not enough to generate more than one 256 bit key for a symmetric cipher. If you generate ten keys from it, you're allocating 25 bits of entropy to each one.
2017: https://news.ycombinator.com/item?id=13332741
2015: https://news.ycombinator.com/item?id=10149019
2014: https://news.ycombinator.com/item?id=7359992
(Links for the curious. Reposts are ok after a year: https://news.ycombinator.com/newsfaq.html)