Randomness

[Ben Laurie]

Paul Onions wrote:

> 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.

OK, what I'm suggesting is much less complex than what you think I'm
suggesting: when they share state, what they actually do is effectively
merge into a single PRNG. So, there isn't a second PRNG with some state
shared with the first, there's just one, and calls to any of the APIs
actually call the same underlying PRNG.

I guess I need to spell this out more carefully.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff


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