Re: /dev/random is hot garbage

[<Paul.Koning%dell.com@localhost>]

> On Jul 22, 2019, at 4:55 PM, Joerg Sonnenberger <joerg%bec.de@localhost> wrote:
> 
> 
> [EXTERNAL EMAIL] 
> 
> On Mon, Jul 22, 2019 at 04:36:41PM +0000, Paul.Koning%dell.com@localhost wrote:
>> 
>> 
>>> On Jul 22, 2019, at 10:52 AM, Joerg Sonnenberger <joerg%bec.de@localhost> wrote:
>>> 
>>> 
>>> [EXTERNAL EMAIL] 
>>> 
>>> On Sun, Jul 21, 2019 at 09:13:48PM +0000, Paul.Koning%dell.com@localhost wrote:
>>>> 
>>>> 
>>>>> On Jul 21, 2019, at 5:03 PM, Joerg Sonnenberger <joerg%bec.de@localhost> wrote:
>>>>> 
>>>>> 
>>>>> [EXTERNAL EMAIL] 
>>>>> 
>>>>> On Sun, Jul 21, 2019 at 08:50:30PM +0000, Paul.Koning%dell.com@localhost wrote:
>>>>>> /dev/urandom is equivalent to /dev/random if there is adequate entropy,
>>>>>> but it will also deliver random numbers not suitable for cryptography before that time.
>>>>> 
>>>>> This is somewhat misleading. The problem is that with an unknown entropy
>>>>> state, the system cannot ensure that an attacker couldn't predict the
>>>>> seed used for the /dev/urandom stream. That doesn't mean that the stream
>>>>> itself is bad. It will still pass any statistical test etc.
>>>> 
>>>> That's exactly my point.  If you're interested in a statistically high
>>>> quality pseudo-random bit stream, /dev/urandom is a gread source.  But
>>>> if you need a cryptographically strong random number, then you can't
>>>> safely proceed with an unknown entropy state for the reason you stated,
>>>> which translates into "you must use /dev/random".
>>> 
>>> That distinction makes no sense at all to me. /dev/urandom is *always* a
>>> cryptographically strong RNG. The only difference here is that without
>>> enough entropy during initialisation of the stream, you can brute force
>>> the entropy state and see if you get a matching output stream based on
>>> that seed.
>> 
>> I use a different definition of "cryptographically strong".  A bit string
>> that's guessable is never, by any useful definition, "cryptographically
>> strong" no matter what the properties of the string extender are.  The
>> only useful definition for the term I can see is as a synonym for
>> "suitable for security critical value in cryptographic algorithms".
>> An unseeded /dev/urandom output is not such a value.
> 
> Again, that's not really a sensible definition. It's always possible to
> guess the seed of used by the /dev/urandom CPRNG. By definition. That
> doesn't change the core properties though: there is no sensible way to
> predict the output of CPRNG without knowing the initial seed and offset.
> There is no known correlation between variations of the seed. As in: the
> only thing partial knowledge of the seed gives you is reducing the
> propability of guessing the right seed. It's a similar situation to why
> the concept of entropy exhaustion doesn't really make sense.

I guess I didn't state the requirement for "cryptographically strong" clearly enough.

A different but equivalent way of stating it: it must not be feasible, given the RNG output up to this point, to predict (with probability better than 50/50 guess) the future output.

The /dev/urandom output is a function only of its internal state, for any span of time where no additional entropy is injected.  So the requirement translates into: (a) you can't guess the internal state from the output, (b) you can't predict future output from past output without knowing the internal state.

Ok, now suppose you have the output from /dev/urandom up to now, and only a few bits of entropy were injected since startup.  Is the output strong?  No, because the small number of entropy bits means that you can enumerate the possible combinations of entropy bits, construct the corresponding internal state, and generate trials output.  The trial output string that matches what you observed tells you the internal state, and consequently the future output.

This means that "enough entropy" translates to "so many bits of entropy that it is infeasible to guess the RNG internal state".

For an example of how you can create a real world security defect by using an RNG with insufficient entropy in its seed, look up the Debian SSL bug (for example https://www.schneier.com/blog/archives/2008/05/random_number_b.html).

	paul