Does shuffle() produce uniform result ?

[Steven D'Aprano]

On Mon, 03 Sep 2007 23:42:56 -0700, Paul Rubin wrote:

> Antoon Pardon <apardon at forel.vub.ac.be> writes:
>> > No the idea is that once there's enough entropy in the pool to make
>> > one encryption key (say 128 bits), the output of /dev/urandom is
>> > computationally indistinguishable from random output no matter how
>> > much data you read from it.
>> 
>> If you were talking about /dev/random I would agree. But this is what
>> the man page on my system says about /dev/urandom. ...
>>        the returned values are theoretically vulnerable to a
>>        cryptographic attack on the algorithms used by the driver.
> 
> Right.  The idea is that those attacks don't exist and therefore the
> output is computationally indistinguishable from random.

It is a huge leap from what the man page says, that they don't exist in 
the unclassified literature at the time the docs were written, to what 
you're saying, that they don't exist.

The man page is clear: there is a possible vulnerability in /dev/urandom. 
Any cryptographer worth his salt (pun intended) would be looking to close 
that vulnerability BEFORE an attack is made public, and not just wait for 
the attack to trickle down from the NSA to the script kiddies. The time 
to close the stable door is _before_ the horse gets away.


> Of course
> whether the idea is correct, an unproven conjecture, but it looks pretty
> good; certainly finding any problem with the specific algorithms in
> urandom would be a significant research discovery and not likely to
> affect the application being discussed.

I agree that this flaw doesn't sound like it will effect the application 
being discussed, but a problem has already been found and a solution is 
already known: block until there's enough entropy. That's what /dev/
random does.


[snip]
 
> In short, using /dev/random is fairly silly once you know there's enough
> entropy in the randomness pool to make a good key.  If /dev/urandom's
> algorithms are broken then whatever you're doing with the /dev/random
> output is probably also broken.

That doesn't follow. Antoon is specifically warning that /dev/urandom is 
non-blocking. If you knew there was enough entropy available, you 
wouldn't need /dev/random -- but how do you know there's enough entropy?

(I suppose you could look in /proc/sys/kernel/random/entropy_avail.)

For this specific application, it probably doesn't matter -- using /dev/
urandom is surely overkill, and on a single-user Linux desktop you're 
unlikely to have vast numbers of applications reading /dev/urandom 
without your knowledge. But why not use /dev/random? What's the downside?



-- 
Steven.