Randomness

[Paul Onions]

On Friday 09 May 2003 12:45 pm, Ben Laurie wrote:
> Paul Onions wrote:
> > On Thursday 08 May 2003 3:07 pm, Ben Laurie wrote:
> >>It was my intention, and perhaps I should make it clearer, that the only
> >>difference between insecureprng() and the other PRNGs is the source of
> >>entropy. Hence, it does not leak state any more than the rest do.
> >>Clearly if the insecureprng() uses a cryptographically weak algorithm
> >>then it cannot share state.
> >
> > Oh okay.  But a small doubt still remains - is a secure-PRNG still a
> > secure-PRNG when multiple instantiations are run in parallel and (at
> > least partially) sharing the same state information?
>
> If they are literally parallel, then no, because they would produce the
> same output if run simultaneously, and that's obviously bad. However,
> what you'd fairly obviously do is lock the state so that they are
> actually run serially, and then they behave like a single instatiation.

Let me put it this way.  A design for a pseudo-random bit generator (PRBG) is 
analysed by assuming that it is seeded from a perfect random source and then 
showing that its output bit sequence is indistinguishable from a random bit 
sequence of the same length.

By perfect random source I mean the n-bit vector that is the seed has entropy 
n bits.

Now assume I have two PRBGs of the same design.  One is seeded with X, the 
other with Y.  Assume that X, when considered on its own, has entropy H(X) = 
n, but that Y is related to X such that H(Y|X) < n.  Now, if an adversary has 
access to the output streams of these two generators, is it able to 
distinguish them from the random case?  That is, in world 1 the adversary is 
presented with the two PRBG streams, and in world 2 is presented with random 
streams.  Is it possible that the adversary can determine the world in which 
it resides?

If so, then it may be possible to break some schemes that use one of the 
PRBGs, because the PRBG is being used outside of the model in which its 
security was analysed.

If all seeds of all PRBGs are independent, then I think we will regain our 
security guarantees, but without this then I think there may be problems.  I 
don't know if this is guaranteed by the system you propose because state is 
shared between generators.

Regards,
Paul(o)

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com