Andrew Cooke wrote:
> I expect a PRNG with an internal state of n bits to produce output
> that is predictable given n consecutive bits of output. Is that
> correct?
I don't think it is so necessarily, but two weaker constraints are.
If the internal state is n bits, then a brute force attack trying all
possible states requires 2^n tries worst case, 2^n-1 on average. So
for example, if you're using PRNG output as a symmetric cipher key
then the PRNG should have at least as much state as the key.
The Berlekamp-Massey algorithm breaks any PRNG which is equivalent to
a linear feedback shift register. For a register of length n bits, it
needs 2n bits of output.
> If so, then doesn't a PRNG used to generate a key
It is not clear that that can be done safely, whatever the PRNG
properties. It depends crucially on truly random inputs seeding the
PRNG.
> require at least as large an internal state as the key length
Yes, and all of that state randomly seeded.
> (otherwise, given the first n bits,
> the rest is predictable, reducing teh effective length to n)?
But not for exactly that reason.
> ... (and also, given the response, I suspect I am labouring under
> some pretty major misconception about random PRNGs).
Good references include RFC 1750 and the Yarrow papers at
counterpane.com
