[13240] in cryptography@c2.net mail archive
Re: Randomness
daemon@ATHENA.MIT.EDU (Ben Laurie)
Sun May 11 13:09:41 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sun, 11 May 2003 14:01:45 +0100
From: Ben Laurie <ben@algroup.co.uk>
To: Paul Onions <paul_onions@siliconinfusion.com>
Cc: cryptography@metzdowd.com
In-Reply-To: <E19E8RQ-0004Qm-00@mta03.btfusion.com>
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@metzdowd.com
