Re: new /dev/random

From: Bill Unruh (unruh_at_physics.ubc.ca)
Date: 10/07/04


Date: Thu, 7 Oct 2004 09:51:00 -0700
To: "Patrick J. LoPresti" <patl@users.sourceforge.net>

On Thu, 7 Oct 2004, Patrick J. LoPresti wrote:

:> The following message is a courtesy copy of an article
] that has been posted to sci.crypt as well.
]
] Bill Unruh <unruh@physics.ubc.ca> writes:
]
] > On Thu, 7 Oct 2004, Patrick J. LoPresti wrote:
] >
] > The discussion was about the feasability of differentiating between a
] > PRNG and an RNG and what the definition of infeasible was.
]
] The discussion was about the design of a "new /dev/random".

Yes, that was the general discussion, but bits of it broke off and
discussed related matters. One of them was the definition of a PRNG and
an RNG.

]
] > I of course have no objection whatsoever to defining a notion of
] > sufficient infeasibility. But to argue that a PRNG should be
] > incapable of being differentiated from an RNG to an attacker with
] > infinite resources is just wrong. a PRNG always is differentiable
] > with infinite resources.
]
] Here you illustrate one point of confusion. Nobody, and I do mean
] NOBODY, with whom you are arguing ever said anything about attackers
] with infinite resources.

Untrue.

]
] You are talking to cryptographers. When they say "impossible for an
] attacker to do X", they mean "infeasible for an attacker to do X".
] This is not because they are sloppy thinkers; it is because they
] learned a long time ago that even mentioning "infinite resources" is a
] stupid waste of time.

Fine.

]
] > The question is, is there a difference between a PRNG and an RNG? The
] > answer is yes.
]
] The question is, what is an appropriate design for /dev/random and
] /dev/urandom? A properly designed /dev/urandom would be the right
] thing to use in 99.9% of all applications, so for some of us, seeing
] such a proper design in the kernel is the main issue.

Fine, I have no objection to that.

]
] The whole notion of a "true RNG" is just a distraction, because it is
] irrelevant to almost every application.

No, it is not a distraction because it forms the core of the attack on
the current /dev/random and /dev/urandom. Many have advocated that there
is no difference between them. There is /dev/random is supposed to be a
true RNG while /dev/urandom is supposed to be a PRNG seeded by a limited
amount from a true RNG.

]
] > The broader question is is there a difference between
] > /dev/random and /dev/urandom, and again the answer is yes. The former is
] > supposed to be an RNG based on physical events and the latter is a PRNG.
] > IMHO that difference should be retained.
] > Can one define the difference between a PRNG and an RNG? Again the
] > answer is yes, and I suggest it has to do with the definition of randomness I
] > gave.
]
] The concept you are ignoring, which happens to be 1000 times more
] relevant than either of the two you name, is that of
] "cryptographically secure PRNG".

I do not ignore it at all. /dev/urandom is supposed to be a
cryptographically secure PRNG. (That incidentally is what I mean when I
use the terms PRNG.) /dev/random is NOT supposed to be a
cryptographically secure PRNG. IT is supposed to be a true hardware
based RNG.

]
] (This is apart from the fact that there is no particularly good reason
] to think /dev/random is a true RNG. If you do not trust AES to
] produce output which is effectively random, why do you trust SHA-1 to
] "distill away" biases and correlations in its input? But this is
] really tangential to my point.)

There are many reasons to think that it is a true RNG. The issue of
whether or not SHA1 is a good distiller is central to that question and
to any proposal to change it. I trust SHA1 to be a distiller precisely
because it is a cryptographically good hash-- it is not its security
but its design to make sure that different inputs produce different
outputs that gives me that faith. It may be wrong, but IF you are going
to replace it, you had better replace it with something which is
demonstrably better.

]
] > > > The definition of random is that the shortest program required to
] > > > generate the output is of order the length of the output
] > > > itself.
] > >
] > This is the definition given by Kolmogorov and Chaitin for example. It
] > has a long pedigree.
]
] I am familiar with Kolmogorov (slash Chaitin, slash Solomonoff)
] complexity. And I am afraid you missed the point: Your definition of
] "random" is not the same as a cryptographer's, and it is this
] disconnect which is the main source of confusion on this thread.

??? Since I just introduced the definition to try to help clarify the
terms used I fail to seee how it is the source of confusion. The use of
random in a vauge undefined personal manner seems far more likely to
cause confusion.

]
] Here in sci.crypt, the cryptographer's definition is assumed. If you
] mean something else, you should make that very clear... And then be
] expected to be ignored, because cryptographers are comfortable with
] their definition.

You clearly have not read the innumerable posts in sci.crypt where
cryptographers have tried to define randomness. They have no agreed on definition
to be comfortable with.
 
]
] When someone shows up in sci.crypt arguing for the one-time pad as the
] only "REALLY SECURE" cryptosystem, the reaction is "yes, thank you, we
] know, please go away". You are seeing a similar reaction for the same
] reason: Information-theoretic security is boring and irrelevant.

Of course it is, but it is critical to the difference between
/dev/random and /dev/urandom.

]
] > Your definition, while of some intuitive utility in cryptography, is
] > too vague to be usefull.

] My hypothetical litle brother thinks ROT-13 is secure. Whom do we
] take as the arbiter of which ciphers are sufficiently difficult to
] break?
]
] Uh oh, we had BETTER ALL SWITCH TO THE ONE-TIME PAD!

do you always put words into others mouths when you arue?



Relevant Pages

  • Re: new /dev/random
    ... > PRNG and an RNG and what the definition of infeasible was. ... > sufficient infeasibility. ... You are talking to cryptographers. ...
    (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
    ... etc to provide the true random information for the RNG. ... >>into a PRNG for reasons he has failed to convince anyone but himself of. ... with input from "entropy sources" as it goes, ... In the current /dev/random implementation there is an entropy estimator ...
    (sci.crypt)
  • Re: new /dev/random
    ... PRNG and an RNG and what the definition of infeasible was. ... a PRNG always is differentiable with infinite resources. ... in cryptography, is too vague to be usefull. ...
    (sci.crypt)