Subject: Re: arc4random(9)
To: None <tls@rek.tjls.com>
From: Steven M. Bellovin <smb@research.att.com>
List: tech-kern
Date: 05/29/2002 11:48:31
In message <20020529093528.GA17404@rek.tjls.com>, Thor Lancelot Simon writes:
>On Wed, May 29, 2002 at 11:17:14AM +0200, Steven M. Bellovin wrote:
>> 
>> Not necessarily -- reproducibility is important for other reasons.  
>> PRNGs, in general, should not be reseeded except by explicit program 
>> action, and the usual choice is a constant or "random" initial seed.
>> 
>> The question about rekeying is "why?"  Why do I want a PRNG to rekey 
>> itself at random times?  I think we agree that we're not producing 
>> key-grade random numbers, and that's the application that most needs 
>> rekeying.
>
>The Yarrow-160 paper hints at this: if you use a cipher as a PRNG, you
>risk the disclosure of *all* of the outputs if the key is disclosed.  (Of
>course, their solution, to use a cipher in combination with a MAC, is
>better; but as you point out, we aren't producing key-grade numbers here
>and that's very expensive).
>
>Even if you're not generating cryptographic keys, this would seem to me
>to be an undesirable result.  Periodic rekeying at least limits the
>scope of the damage resulting from the compromise of the key -- this
>doesn't seem like a bad thing to me, so long as you can turn it off when
>you want to.
>
>The other reason I can think of off the top of my head is if you're using
>a block cipher with a small block size (even 64 bits).  There, you need
>to rekey simply because you've sucked a certain amount of output out of
>it, no?

Again -- what is the problem we're trying to solve?  Yarrow *is* 
designed for producing key-grade randomness.  Someone doing a Monte 
Carlo simulation doesn't need Yarrow, because there's no issue of 
trying to hide state for anything.

I'm not sure what you mean about block ciphers, since we're not talking 
about using one.  But the issue for non-crypto PRNGs (apart, of course, 
from "random"-seeming output, is the cycle length, and that is bounded 
by the size of the internal state.  random() is actually quite good in 
that regard.  32-bit linear congruential generators are not.  64-bit 
LCGs are ok in that regard, though they don't do well for randomness, 
especially in the low-order bits.

		--Steve Bellovin, http://www.research.att.com/~smb (me)
		http://www.wilyhacker.com ("Firewalls" book)