Re: strengthening /dev/urandom

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 08/19/04 

Date: Thu, 19 Aug 2004 23:27:10 +0200

Jean-Luc Cooke wrote:

> Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>
>>I don't understand. In my mental picture, a system/device
>>delivering true randomness should be somehow like the shelves
>>of a supermarket. I never know how much the supermarket
>>has certain commodities in reserve. If the an article is
>>not on the shelves, then I have bad luck and have to wait.
>
>
>>I could be typing to do many things, e.g. composing a Word
>>document that doesn't need any entropy. What has that to
>>do with the entropy delivering? What could the attacker
>>exploit from that behaviour? And I may on the other hand
>>have initiated some processes that do time and again need
>>entropy. They may pause, if there isn't enough entropy
>>supply. So what?
>
>
> wow.
>
> They pause until you've typed. This is not good design. There is a
> reason why the figner protocol doesn't report idle time anymore.

Who said that my typing immediately feeds the entropy pool?
The system could even decide that only what it got yesterday
would be made available today. Further the processes that
pause may have plenty reasons, e.g. waiting data from me,
for which I have first to phone my friend, etc. I don't see
a direct/intimate connection between what I do currently and
the entropy supply. If that's what /dev/random does now,
then it needs be corrected in some appropriate way.

>
> There is no way to get true randomnes, ever. Not from Transisters, not
> from anything. We can get very very close, but never true. The
> computer system has some things which are very very hard to predict.
> So let's use those asa input into a PRNG. Blocking untill we "have
> enough" is foolsih because you have no real way of measuring "enough".
> SO get rid of it.

What do you mean? Either one knows that certain true random
bits come to the pool or not. If the demand can't be
met, then stop. One should like e.g. one's bank account always
have some reserve and never let it go to zero in my opinion,
i.e. stop a bit before the pool is empty. It is better to
have a larger reserve than a small one.

>
>>> 2) We need to chose what is viewed as the best PRNG (using system
>>> events as input). If the user doesn't like the choice of everal
>>> people who know what they're doing contact me and explain why you
>>> don't like it and I'll certainly consider it or re-write it
>>> yourself. This is the open source way.
>>>
>>>That being said, I have to say that talking with Ted is vastly more
>>>enjoyable than 80% of the people on sci.crypt. :P
>
>
>>That's not the proper attitude to improve /dev/random in
>>my view. First discuss whether 'any' PRNG is needed. If
>>that turns out to be a unanimous 'yes', then pool what the
>>people want as PRNG. (I am afraid there would be a chaos
>>in this case, as most people have their pet PRNG.)
>
>
> You are now part of that 80%.
>
> A PRNG is needed. I explained why. You can't have users (or programs!) on your system
> knowing about which hard disks are seeing what kind of activity. What
> letters you are typing at the keyboard. You need to hide that from
> them. How? Crypto. What kind? PRNG.

Have a sufficiently high minimum reserve and you will see
there is barely any correlation between generation and
supply of entropy. (Consider as analogy a water resevoir
with intake and outlet.)

> As for pet PRNG, fine. /dev/random already has a PRNG which very few
> people like. I'm proposing one that is qualitativly better. You need a
> PRNG in /dev/random ONE way or another.

So wipe out that PRNG from /dev/random in my opinion. That
needs to be discussed in the first place, right?

M. K. Shen

Relevant Pages

  • Re: strengthening /dev/urandom
    ... >>a possibility to supply limited true randomness (without ... >>PRNG for some personal reason. ... delivering true randomness should be somehow like the shelves ... document that doesn't need any entropy. ...
    (sci.crypt)
  • Re: strengthening /dev/urandom
    ... > delivering true randomness should be somehow like the shelves ... I never know how much the supermarket ... > document that doesn't need any entropy. ... First discuss whether 'any' PRNG is needed. ...
    (sci.crypt)
  • Re: strengthening /dev/urandom
    ... >>i.e. stop a bit before the pool is empty. ... >>have a larger reserve than a small one. ... Please re-read JLC's posts about the necessity of the PRNG. ... to provide 'genuine' true randomness. ...
    (sci.crypt)
  • Re: new /dev/random
    ... For a proper PRNG, with the assumption that the algorithms are robust, ... is said to contain 40 bits of entropy if I could, ... If I want to attack a stream of 56 bits produced by a PRNG with a seed ... RNG resistance therefore relies on the same two classes of assumptions ...
    (sci.crypt)
  • Re: new /dev/random
    ... > is said to contain 40 bits of entropy if I could, ... > efficient attack would be to try the exhaustive search on the seed. ... > than the PRNG: evolution of computer science (the robustness of the ... > because, for a given length of random bits requested, the RNG will have ...
    (sci.crypt)