[6881] in cryptography@c2.net mail archive
Re: PRNG State [was: KeyTool internal state]
daemon@ATHENA.MIT.EDU (Sandy Harris)
Mon Apr 3 12:04:54 2000
Message-ID: <38E89A44.F2D23B0E@storm.ca>
Date: Mon, 03 Apr 2000 09:19:00 -0400
From: Sandy Harris <sandy@storm.ca>
MIME-Version: 1.0
To: Andrew Cooke <andrew@intertrader.com>
Cc: cryptography@c2.net
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
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
