News for hackers. Stuff that matters.
Re:Entropy and the NetBSD Kernel by tialaramex on Sunday May 17, 2020 @03:48PM (#23214777)
> you could just do the old "read twice: discard if results match; otherwise take the first value" trick to get an unbiased source.

Huh?

If I have a legitimately random source that gives 00, 10 or 11 entirely at random (but never 01 which is why we're filtering it), and you feed it through your proposed process to get a 16-bit number you always get 1111111111111111 which is clearly no sort of random.

Re:Entropy and the NetBSD Kernel by cipher_314159 on Sunday May 17, 2020 @05:51PM (#23215836)
I suppose I should have made it explicit that this construction relies on the unpredictability of SINGLE-bit reads. I had actually considered some wording about that and the independence of each sample, but figured I'd sound pedantic.

Under the system you outlined, that single-bit unpredictability condition doesn't hold, so you're right that the construction totally breaks down. Given a starting bit of 0, you can predict the next bit with absolute certainty.

For something like your random source, it would be best to just skip every other bit and look at the result as a biased bit generator. In that case, the construction works: you would have (0, 1) and (1, 0) each happening with probability 2/9, while the matching sets (0, 0) and (1, 1) happen with a combined probability 5/9. That gives (0, 1) and (1, 0) as equally likely outputs, so just consistently take one of them, and you have an unbiased source.

But what you mention DOES have some relevance to bit generators, too. One of the Bernstein scenarios deals with a hypothetical backdoored RDRAND instruction on x86. The basic idea is that the instruction is designed with some understanding of the system the values will be used in, and doing a short brute-force to see which value would fix the first four bits to a desired pattern. With the "sample, check unmatched, take first" construction, that pattern would be SUPER easy to fix.

Re:Entropy and the NetBSD Kernel by a1369209993 on Sunday May 17, 2020 @05:35PM (#23215702)
In context, they were talking about the specific case of a source that outputs 33% 1s and 67% 0s, with no correlation between successive outputs. For the general case of a entropy source that's (not provably not) biased in some arbitary way that you don't know about, you obviously need a cryptographically secure hash function.