PRNG design document?

[Joshua Hill]

On Mon, Aug 25, 2003 at 09:15:00PM -0400, Thor Lancelot Simon wrote:
> 1) Various entities have already had various versions of 
>    OpenSSL FIPS-140-2 certified.

The stock OpenSSL generator is neither the ANSI X9.31 A.2.4 generator
(which is, indeed, identical to an interpretation of the ANSI X9.17
Appendix C PRNG), nor is it an implementation of the FIPS 186-2 Appendix
3.1 PRNG.  These are the only two approved general purpose PRNGs for
FIPS 140-2.  (The FIPS 186-2 Appendix 3.2 PRNG is not really a general
purpose PRNG, and the ANSI X9.62 A.4 PRNG is basically the FIPS 186-2
appendix 3.1 PRNG)

Any version of the OpenSSL library that had been through the FIPS 140-2
evaluation process would have to either implement an an approved PRNG
in order to generate keys for FIPS approved algorithms, or not generate
keys for FIPS approved algorithms in FIPS mode.

You could seed the approved PRNG with some other non-approved PRNG (like
Yarrow), as long as you could argue that this seeding method resulted in
the approved PRNG having a computational resistance to attack equivalent
to the computational resistance to attack of the resulting key.

I'll note that it's fairly easy to seed the FIPS 186-2 Appendix 3.1 PRNG
with a respectable amount of entropy.  The initial XKEY value (and thus
the PRNG's internal state) can be up to 512 bits (for an implementation
with a SHA-1 based G function).  The FIPS 186-2 PRNG also allows for
periodic seeding (through XSEED), which can be used to add additional
entropy into the PRNG.  Finally, it's quick; each round only requires
one SHA-1-like operation. (for the SHA-1 based G function, once again)

This as compared to the ANSI X9.31 A.2.4 PRNG which, even if you stuff
it to the gills, can't support more than 296 bits of seeding material
(64 bits for the starting DT, 64 bits for the initial V, and 168 bits
for the three key triple DES key).  In fact, if you would prefer to be
conservative, three key triple DES only has a computational resistance to
attack of 112 bits, so really you it's more like 240 bits of computational
resistance to attack, for an ideal implementation. (many implementations
actually actually have a maximum closer to 80-112 bits, actually).
This PRNG also can't be periodically easily periodically seeded, short
of re-initializing the PRNG.  Finally, X9.31 A.2.4 is slow, particularly
in software.  It takes 9 DES operations per round.

In another forum, you mentioned that you didn't like the FIPS 186-2 PRNG.
(You referred to it as "a SHA1-based generator which has some problems").
I'm curious what you meant.

I'm aware of a few problems which can be easily dealt with:
	1) The original specification includes	a (mod q) final step,
	which makes the output slightly non-uniform.  This is dealt
	with by change notice 1 of FIPS 186-2, which simply removes this
	(mod q) step for general purpose (i.e. non-DSA) use.

	2) If an attacker can completely specify the XSEED value, they
	can force the PRNG to enter a stuck state, and generate the same
	value indefinitely.  FIPS 140-2 mitigates this with the continuous
	RNG test (if the PRNG outputs the same value twice, this is viewed
	as a fatal error in FIPS 140).	In addition, good design dictates
	that you not give an attacker the ability to completely specify
	this value.  Even if you can't prevent attacker from specifying,
	this input, you could at least hash it to mitigate this attack.

	3) The standard allows for arbitrary entropy seeding.  In order
	to prevent an attacker from guessing the seed, the designer
	ought to assure than they have an appropriate amount of entropy
	before feeding it to the PRNG.	It isn't, strictly speaking,
	fair to call this a FIPS 186-2 problem, as it is generally true
	for any PRNG that allows periodic seeding.

	4) The SHA-1 based G function isn't quite SHA-1, which is fairly
	odd; it's SHA-1 without SHA-1's padding applied, which is just
	different enough to require some special purpose code.	This is,
	admittedly, irritating.

That's about it.  This as compared to the X9.31 generator, which is slow,
can't be periodically seeded, can't contain enough entropy for all uses,
and smells funny.  OK, so I made up the last part, but still...

> [...] there is no requirement for _how_ it is rekeyed save that the 
> input must not have demonstrably less entropy than the output

Just as a note: FIPS 140-2 does _not_ require approved PRNGs to be
information theoretic secure, only secure against a computationally
bounded attacker.  For FIPS 140-2, if your initial seed has 512 bits
of entropy, you can produce 512 bit keys indefinitely without ever
re-seeding.

The requirement that pertains here requires that breaking the
deterministic RNG should require at least as many operations as guessing
the largest key produced by the PRNG.  Ideally, a designer would
periodically re-seed with new entropy, but this is not required by the
FIPS standard.  It is certainly not required that you can argue that you
have put as much entropy into the generator as it has output key material.

> I am informed that in the past, implementations using Yarrow have, in
> fact, been certified, passing the code examination in the lab by
> documenting that Yarrow's output stage is, in fact, algorithmically
> equivalent to the X9.17 generator.  Unfortunately, since those products
> were certified, there have been some particularly ill-considered
> interpretations of the X9.17 RNG specification by NIST which I believe
> would now make it impossible to have a Yarrow implementation certified;
> but you can get very close.

This is interesting; I do not see how one could view Yarrow as equivalent
to X9.31/X9.17.  It does have a triple-DES encrypt final stage, and it
has a counter, but that's about where the similarity ends.

NIST has, from time to time, allowed all sorts of wacky stuff.  That
doesn't mean that they were "correct" from a standards perspective,
though.

				Josh

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com