News for hackers. Stuff that matters.
Re:/dev/random – a new approach by Tomte on Sunday April 24, 2016 @05:37PM (#11561476)
If I read this correctly, this new suggestion also keeps the entropy estimation voodoo:

"By using the primary DRBG to serve /dev/random, the LRNG ensures that each random number generated by the primary DRBG must be backed by an equal amount of entropy that seeded the DRBG. Hence, the data derived from /dev/random is backed by information theoretical entropy."

(page 21 of the PDF documentation)

Re:/dev/random – a new approach by twic on Sunday April 24, 2016 @06:13PM (#11561605)
For an explanation of the voodoo nature of the blocking /dev/random, see:

http://www.2uo.de/myths-about-urandom/

EDIT: or read tptacek's root comment on this very page.

Re:/dev/random – a new approach by sunnyps on Sunday April 24, 2016 @10:57PM (#11562347)
Thanks! This article was very helpful.
Re:/dev/random – a new approach by ibotty on Tuesday April 26, 2016 @08:40AM (#11571305)
Note, that tomte is the author.
Re:/dev/random – a new approach by cesarb on Sunday April 24, 2016 @06:40PM (#11561701)
I used to think that entropy estimation was nonsense, but last year I finally understood it. Copying my comment at https://lwn.net/Articles/642839/:

Think of the pool's entropy as a "measure of unpredictability". If the entropy is ten bits, for instance, you'd need at most 1024 guesses to find the pool state.

You should think of the random generator as having two separate and independent parts: the pool itself and the output function.

Inputs are mixed into the pool using a cryptographic function which takes two values: the previous pool state and the input value, and outputs the new pool state. This function thoroughly mixes its inputs, such that a one-bit difference on any of them would result on average to half of the output bits changing, and other than by guessing it's not possible to get from the output back to the inputs.

Suppose you start with the pool containing only zeros. You add to it an input containing one bit of entropy. Around half of the pool bits will flip, and you can't easily reverse the function to get back the input, but since it's only one bit of entropy you can make two guesses and find one which matches the new pool state. Each new bit of entropy added doubles the number of guesses you need to make; but due to the pigeonhole principle, you can't have more entropy than the number of bits in the pool.

To read from the pool, you use the second part, the output function. It again is a cryptographic function which takes the whole pool as its input, mixes it together, and outputs a number. Other than by guessing, it's not possible to get from this output to the pool state.

Now let's go back to the one-bit example. The pool started with zero entropy (a fixed initial state), and got one bit of entropy added. It can now be in one of two possible states. It goes through the output function, which prevents one reading the output from getting back to the pool state. However, since there were only two possible states (one bit of entropy), you can try both and see which one would generate the output you got... and now the pool state is completely predictable, that is, it now has zero bits of entropy again! By reading from the pool, even with the protection of the output function, you reduced its entropy. Not only that, but there were only two possible outputs, so the output itself had only one bit of entropy, no matter how many bits you had asked for.

Now if you read a 32-bit number from a pool with 33 bits of entropy, you can make many guesses and find out a possible pool state. However, again due to the pigeonhole principle, there's on average two possible pool states which will generate the same 32-bit output. Two pool states = one bit. So by reading 32 bits, you reduced the remaining entropy to one bit.

This is important because if you can predict the pool state, you can predict what it will output next, which is obviously bad.

----

Now, why isn't the situation that bad in practice? First, the input entropy counter tends to underestimate the entropy being added (by design, since it's better to underestimate than to overestimate). Second, "by guessing" can take a long enough time to be impractical. Suppose you have a 1024-bit pool, and read 1023 bits from it. In theory, the pool state should be almost completely predictable: there should be only two possible states. In practice, you would have to do more than 2^1000 guesses (a ridiculously large number) before you could actually make it that predictable.

However, that only applies after the pool got unpredictable enough. That's why the new getrandom() system call (which you should use instead of reading /dev/random or /dev/urandom) will always block (or return failure in non-blocking mode) until the pool has gotten enough entropy at least once.

Re:/dev/random – a new approach by tptacek on Sunday April 24, 2016 @07:34PM (#11561833)
No. This would matter if entropy was somehow directly provided to applications. But no modern system does this. Instead, entropy is hashed into a key for a keystream generator (based either on a hash function, a MAC, or a stream cipher).

That's the entire point of a DRBG†: to securely incorporate inputs of wildly varying randomness into an RNG whose future outputs are as difficult to predict from past output as keys are to recover from ciphers.

To somehow "predict" the output of the system from its input, you would need to be able to work back from the output of a cryptographic keystream generator back to its key. If you can do that, forget the RNG: you've broken most modern cryptography.

† and even prior to this proposal, that's what the LRNG implemented

Re:/dev/random – a new approach by cesarb on Sunday April 24, 2016 @08:05PM (#11561903)
You can easily predict the output of a system from its input, if said input can only take a few possible values, by simply trying all possible inputs until you find one which matches the output. The extra step of hashing the pool into a key to a keystream generator does not prevent that. If the key has only a few possible values, and you can observe enough of its output, you can brute force it.

If, for instance, the pool has only 256 possible values (8 bits of entropy), perhaps because the system just booted and almost nothing has been added yet to the pool, there will be only 256 possible keys, and only 256 possible output streams. If you have enough of the output (on average around one byte), you can try the 256 possible pool states, and see which one would give you the same output you have. And since now you know both the pool and generator state, the system's entropy is now zero: it's completely predictable.

The only way to prevent that is to never output anything, until the number of possible states is large enough (like 2^128 or more) that brute forcing is not viable. Which AFAIK is what the new getrandom() syscall does.

Re:/dev/random – a new approach by Freaky on Sunday April 24, 2016 @08:12PM (#11561927)
The complaint isn't about blocking before you've been seeded, it's blocking afterwards because you've generated some random numbers and feel like you've somehow "used up" your entropy pool in doing so.
Re:/dev/random – a new approach by wtbob on Monday April 25, 2016 @02:05AM (#11562701)
> The only way to prevent that is to never output anything, until the number of possible states is large enough (like 2^128 or more) that brute forcing is not viable.

Fortunately, it's easy to store a value which can take one of 2^128 possible states: it's 16 bytes. That's all. That's all you need. That's all you'll ever need.

Take that one value; use it to key a keyed hash or an HMAC or a stream cypher or a block cypher. Encrypt the 16-byte value for 0, then 1, then 2 &c. You will get an effectively infinite sequence of random numbers.

'But wait!' you say, 'maybe I'm worried that I might expose some of that state!' Then just periodically rekey that keyed hash or HMAC or stream cypher or block cypher. There are a number of ways to do that: one possibility would be to hash the current key and the new entropy, but there are other, smarter ways to do it as well.

That's it. That's all you need.

Re:/dev/random – a new approach by Tomte on Sunday April 24, 2016 @08:57PM (#11562024)
Nobody is advancing pathological one bit starting entropy cases. Of course you need entropy. But you don't need thousands of fresh bits every millisecond. You need a few hundred once.

More important: nobody knows if the entropy counter is truly conservative, because nobody knows how to properly count entropy. Linux makes educated guesses by assuming a model of entropy for the inputs (inter-arrival times of events). That's far less solid than the rest of the random subsystem.