[6879] in cryptography@c2.net mail archive
Re: PRNG State [was: KeyTool internal state]
daemon@ATHENA.MIT.EDU (Andrew Cooke)
Mon Apr 3 12:04:46 2000
Message-ID: <38E85464.6DD780FE@intertrader.com>
Date: Mon, 03 Apr 2000 09:20:53 +0100
From: Andrew Cooke <andrew@intertrader.com>
MIME-Version: 1.0
To: cryptography@c2.net
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Hi,
OK, I had - stupidly - confused key lengths for public key and private
key systems. Provided Sun has a good implementation everything is OK
(for example, 160 bits of state is sufficient for 3DES). (I spent hours
yesterday banging my head against a wall trying to work out how to get
"extra" state out of a PRNG...)
Thanks to A Reinhold (I think he has copied his email here, although I
haven't seen it on the list yet) and apologies to Sun (I hope in all my
posts I have been clear about my reasoning, so hopefully only people
even more silly than me have been led astray ;-).
Cheers,
Andrew
Andrew Cooke wrote:
>
> Hi,
>
> Can someone please correct the following?
>
> 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? If
> so, then doesn't a PRNG used to generate a key require at least as large
> an internal state as the key length (otherwise, given the first n bits,
> the rest is predictable, reducing teh effective length to n)?
>
> This is the basis of my earlier post questioning the security of Sun's
> keytool. I've included the relevant parts of my post and the reply
> below - I've also checked the FIPS document, which doesn't mention this
> (I cannot find a public copy of the IEEE document).
>
> My apologies if the reasoning above is incorrect - I would really
> appreciate comments on this as it is important that I understand whether
> or not the keytool is useful (and also, given the response, I suspect I
> am labouring under some pretty major misconception about random PRNGs).
>
> Thanks,
> Andrew
>
> Gary Ellison wrote:
> > >>>>> " " == Andrew Cooke <andrew@intertrader.com> writes:
> [...]
> > > Most importantly, as far as I can tell, keytool does not generate "fully
> > > random" keys when used "naively".
> [...]
> > The Sun provider for SecureRandom follows the IEEE P1363 standard,
> > Appendix G.7: "Expansion of source bits", and uses SHA1 as the
> > foundation of the PRNG. Additionally, we verify that the Sun
> > SecureRandom provider complies with NIST's FIPS PUB 140-1 section 4.11.
> [...]
> > > - The Java SecureRandom class contains only 20 bytes of random state and
> > > these are initialised by some kind of thread contention process (which
> > > may not generate "really random" values either).
> [...]
> > In 1996 when SecureRandom was implemented 20 bytes of state seemed
> > sufficient for FIPS 140-1 compliance. Perhaps this is no longer a
> > sufficient target (your suggestions are welcome). The Sun provider
> > for SecureRandom mixes in other sources of entropy with the results
> > from the thread contention process. Among other things this includes
> > the current time, the state of the VM's memory usage, system
> > properties, and file system activity.
> [...]
