When is the blocking RNG called?

[Bodo Moeller]

Charles Duffy <cduffy at mvista.com>:
> Bodo Moeller:
>> Enzo Michelangeli:
>>> "Bodo Moeller" <bmoeller at hrzpub.tu-darmstadt.de>:
>>>> Enzo Michelangeli <em at who.net>:

>>>>>                                                   I'm pretty happy with a
>>>>> PRNG for just every task, as long as two conditions be satisfied:

>>>>> 1) It must be impossible to guess its future output without knowing its internal state
>>>>> (which implies: 1.1 It must be impossible to guess its internal state from its output)
>>>>> 
>>>>> 2) The PRNG is initially seeded with a sufficient amount of entropy
>>>>> 
>>>>> In this case, the generator is as good as a true RNG.

>>>> Wrong.  This definition is met by a "PRNG" that outputs only zeros and
>>>> never advances its internal state, as long as this internal state
>>>> starts with sufficient seeding.

>>> Huh? If it outputs only zeros, it's not a PRNG at all, as its future output
>>> is totally predictable...

>> That's the point.  The requirements that you stated do not cover this problem.
>> If the example appears too trivial, think, say, of a PRNG composed of a "bad"
>> PRNG and a "good" PRNG such that every other bit is taken from each of
>> these PRNGs.  The resulting output will still be bad, even though you
>> can neither guess all of the internal state that determines the output
>> nor predict all of the future output.

> No, his requirements do work -- or, at minimum, your suggestion fails
> the definition.
> 
> If the "PRNG" outputs only 0s, it is possible to guess its future
> output without any knowledge of internal state, thus failing
> requirement (1).

You're right; I looked at 1.1 instead of 1.  The actual problem with 1
is that it doesn't say anything about *previous* outputs: Take a great
PRNG (or even a real RNG) and prepend a k-bit hash of its first k bits
to the sequence output by it, where k is a security parameter (160, say).
The resulting "PRNG" satisfies all of the above conditions if the
underlying PRNG does and the security parameter and hash function are
chosen appropriately (according to the presumed computational strength
of the attacker); but it is a bad PRNG because after publishing the
second k-bit block output by it, the first block is no longer secret.

(This is the problem that I intended to point out at first, until I
incorrectly thought I had spotted a more basic problem with that PRNG
definition -- see above.  Sorry for the confusion.)