Random numbers

[C de-Avillez]

On Wed, 03 Nov 2010 11:07:02 -0400
Kent Borg <kentborg at borg.org> wrote:

> C de-Avillez wrote:
> > It is common to see that on very busy HTTPS sites without a
> > good PRNG.
> >   
> 
> Aren't the ones running Linux going to use /dev/urandom?  If
> so--modulo any bugs in /dev/urandom that I don't know about--it is a
> very good random source.

Yes indeed. But I have seen many applications that use /dev/random
instead. Perhaps the reason is the perceived danger of /dev/urandom
when it falls back to a PRNG when low on entropy. 

Please note that I said *perceived*. To summarise how it works:

* /dev/random: pretty good RNG, will block when it needs more entropy
* /dev/urandom: uses same RNG as /dev/random, but falls back to a PRNG
  when low on entropy. I have not heard of any published attack on this
  PRNG.

/dev/urandom should be quite secure, with the usual precaution to
go to /dev/random for long-term key generation. And, of course, the
discussion keeps on...

<snip/>

> "True" random number generators had flaws.  Consider a random
> number 
> generator that actually flipped a coin.  Pretty solid, real
> randomness! Except any real coin probably has a little bias, given
> enough output one can start to make predictions that will be
> ~slightly~ better than 50-50, its output should be cleaned up, run
> through an algorithm, probably "whitened" a little.

Yes. Perhaps a good example of how things that seem random turn out
not to be so is Knuth's example of a sequence of operations that seem
to be getting random sequences of digits, operating on them, etc,
etc, only to find the output quickly converging to a stable
(constant) value.

I do not have the book with me right now (and, frankly, I am waiting
for the new edition), but if I remember correctly, Knuth had called
it a "colossal coincidence" and, -- again IIRC -- was his first try on
a PRNG..
 
<snip/>

> If https is using /dev/urandom, I don't see what is lacking
> there.

probably nothing, for short-lived keys. Probably the same apply to
long-lived keys, but I do not know of any confirmation/refutation. For
my own personal use I see no reason *not* to use /dev/urandom.

> 
> Note that not all uses of random data want cryptographic-quality
> random data.  Traditional-style PRNGs are great for Monte Carlo
> simulations. Something like Mersenne Twister has an enormous number
> of internal states (and so can run a very long time before
> repeating) yet by resetting the internal state to a known value one
> can get a repeatable sequence.  (Change your algorithm and do
> another test run...was the output different because of different
> random data or because of your code changes?  By being able to have
> the same random data for each run, you can control what changed.)

There is also that -- and this is an important point to be kept in
mind. And, of course, the other side: change your seed, and repeat
with the same algorithm -- are the results compatible?

> 
> Mersenne Twister does not go to great effort to hide its internal
> state, and so is not suited to cryptographic uses where humans might
> be working hard to deduce the internal state and win the lottery,
> but, say you are doing a biological simulation, it is reasonable to
> assume that some virus simulation isn't going to deduce the internal
> state.
> 
> Yes, proving randomness is hard, but if a random number generator is
> (a) designed with thought, (b) carefully constructed, and (c) built
> out of good parts (i.e., SHA-1), the result can be very good.  The
> Linux random number generator makes a good stab at all three of
> those points.

I would only add (d) public independent peer-review.

Good summary, Kent. I do hope this will help the folks here.

Cheers,


-- 
C de-Avillez
IRC: hggdh

This email (and any attachments) is digitally signed using GNUpg
(http://gnupg.org). The public key is available at http://pgp.mit.edu.
The key Id is 0xD3133E56.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <https://lists.ubuntu.com/archives/ubuntu-users/attachments/20101103/6013f1ea/attachment.sig>