Re: FIPS compliance for DiffieHellman  Openssl
This is a discussion on Re: FIPS compliance for DiffieHellman  Openssl ; Hi,
Thanks for a nice explaination Joshua!
As a solution, since g is supposed to fall in the multiplicative group of
order q OR 2q, the g can be therefore adjusted such that it satisfies either
of [g^q mod p ...

Re: FIPS compliance for DiffieHellman
Hi,
Thanks for a nice explaination Joshua!
As a solution, since g is supposed to fall in the multiplicative group of
order q OR 2q, the g can be therefore adjusted such that it satisfies either
of [g^q mod p = 1] or [g^2q mod p = 1].
Since that can be found in a deterministic way, setting up proper 'g' on a
randomly generated safe prime 'p' is easier and predictable. And it passes
the test in one go.
 Nilay
On Tue, Jul 8, 2008 at 10:40 PM, Joshua Hill wrote:
> On Tue, Jul 08, 2008 at 03:27:08PM +0530, Nilay Tripathi wrote:
> > Generating 'p' randomly as a safe prime and using 'g' order as 5, the
> > keys generated are not consistently passing Sec 5.6.2.4 KAT test.
>
> It would be a good idea for you to understand why this is, rather than
> just iterate until it passes.
>
> Setting 'g' to 5 won't always work! The expectation of SP80056 is that
> the generator (g) generates the qordered multiplicative subgroup of Z_p.
> Because p is a safeprime, the only possible value for q is (p1)/2 (this
> can be otherwise stated as "q is a Sophie Germain prime and p=2q+1").
> Because of this selection for p, the multiplicative group Z_p is very
> simple: it has a subgroup of size 2q (the whole group) a subgroup of
> size q, a subgroup of size 2 and a subgroup of size 1.
>
> g=5 is going to be either order q or order 2q. To be consistent with
> SP80056 you need it to be order q. If you run the required public key
> validation test on a public key where g is 2qordered, then it will
> fail roughly half the time. This doesn't mean that you need to just
> keep trying until it works, this means that your selection for g wasn't
> compliant with SP80056 in the first place!
>
> When generating domain parameters you can test to see if you have an
> orderq generator by taking g^q mod p and verifying that it equals 1.
> If it instead equals (p1) then you have a 2qordered generator; you
> should either choose a different generator or choose a different value
> for p.
>
> Josh
>

Re: FIPS compliance for DiffieHellman
On Wed, Jul 09, 2008 at 05:53:42PM +0530, Nilay Tripathi wrote:
> As a solution, since g is supposed to fall in the multiplicative group of
> order q OR 2q, the g can be therefore adjusted such that it satisfies either
> of [g^q mod p = 1] or [g^2q mod p = 1].
When p is a safe prime, a few things happen that make this discussion
simpler.
As long as you don't choose g=1 or g=p1, you're going to get a generator
of either the qordered or 2qordered group.
All elements in the multiplicative group are in the 2qordered group by
definition (the 2qordered group is the full group!). As such, _all_
selections for g (even 1 and p1) will satisfy [g^(2q) mod p = 1].
The public key validation routine required by NIST SP80056 is
effectively a test to make sure that the public key resides within the
qordered group. If it does not, that test fails. If you've chosen g
to generate the qordered group, all public keys will automatically be
in the qordered group.
More to the point, if you haven't selected g such that it generates the
qordered group, you're not in compliance with NIST SP80056. If you're
required to be compliant with that document (because of, for example,
a FIPS 140 validation), that will be a problem.
> Since that can be found in a deterministic way, setting up proper 'g' on a
> randomly generated safe prime 'p' is easier and predictable. And it passes
> the test in one go.
I don't understand. If you only care that the public key is either
in the qordered group or the 2qordered group and not in the 1 or 2
ordered group, then don't bother with a test using modular exponentiation.
A simple range test will suffice: make sure 1
That's clearly not what NIST SP80056 requires, but that's fine from a
security perspective. If you have be be NIST SP80056 compliant, then
you are required to use a qordered element for g, and that will also
make it so that you consistently pass the public key validation test as
specified in that document.
Josh
__________________________________________________ ____________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssldev@openssl.org
Automated List Manager majordomo@openssl.org