On Fri, 17 May 1996 11:29:36 +0200, Harald Anlauf
<anlauf@crunch.ikp.physik.th-darmstadt.de> said:
>> It seems that most of the people who are flaming on this topic have
>> no idea how weak a pseudo-random number generator really is. Only
>> a few values is all you generally need before you can completely
>> predict the output of such a best.
> People seem to be too paranoid about the quality of pseudo random
> number generators, but why don't you just ask the experts out there?
I'm sorry, but this is too much --- Ted Ts'o *IS* one of "the experts
out there".
> A friend of mine pointed me to the errata list of volume two of Donald
> E. Knuth's "The Art of Computer Programming". There, DEK has suggested
> a very good portable random number generator. It generates 30-bit
> integers with the following properties:
> ...
> - it can create at least 2^30 - 2 independent sequences
> (Sorry, I don't have the period length and hand, but it's fairly long.
>> 2^137 ?)
And therefore it is useless for situations where unpredictability is
necessary.
People seem to be missing the point. Getting a number sequence which
satisifies statistical random properties is quite easy, but it can be
done happily in user space. For some applications, however, TOTAL
unpredictability is necessary. We're talking about things like
generating unpredictable sequence numbers, encryption keys and RSA
keys here. If an intruder can reduce the search space of possible
keys by observing some sequence, then you are much more vulnerable to
attack.
Knuth's algorithms may be good, but if there are only 2^30 sequences
then any observations of the sequence will allow you to compromise the
safety of future keys. "Statistically random" and "unpredictable" are
two entirely separate measures of the "goodness" of an RNG; Knuth's
may have the former but it isn't good enough on the latter.
The ONLY reason for having /dev/random in the kernel is so that we can
capture genuine entropy from the running system and so come up with a
byte stream which is not only statistically random, but in fact
completely unpredictable, and which does not have any persistant
internal state which can be deduced by an attacker.
If all you want is a RNG for simulations, do it in user space.
/dev/random is really only necessary for security reasons.
Now, look at the fiasco which resulted when netscape's security was
broken. The attack there involved the observation of keys to deduce
part of the RNG's internal state, so allowing the search space for
future keys to be massively reduced. This is the kind of problem you
get if you try to use pseudo-random numbers for security purposes, and
it's exactly this type of application which can benefit from
/dev/random.
Cheers,
Stephen.
-- Stephen Tweedie <sct@dcs.ed.ac.uk> Department of Computer Science, Edinburgh University, Scotland.