Re: FIPS compliance for Diffie-Hellman - Openssl

This is a discussion on Re: FIPS compliance for Diffie-Hellman - 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 ...

+ Reply to Thread
Results 1 to 2 of 2

Thread: Re: FIPS compliance for Diffie-Hellman

  1. Re: FIPS compliance for Diffie-Hellman

    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 SP800-56 is that
    > the generator (g) generates the q-ordered multiplicative subgroup of Z_p.
    > Because p is a safe-prime, the only possible value for q is (p-1)/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
    > SP800-56 you need it to be order q. If you run the required public key
    > validation test on a public key where g is 2q-ordered, 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 SP800-56 in the first place!
    >
    > When generating domain parameters you can test to see if you have an
    > order-q generator by taking g^q mod p and verifying that it equals 1.
    > If it instead equals (p-1) then you have a 2q-ordered generator; you
    > should either choose a different generator or choose a different value
    > for p.
    >
    > Josh
    >



  2. Re: FIPS compliance for Diffie-Hellman

    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=p-1, you're going to get a generator
    of either the q-ordered or 2q-ordered group.

    All elements in the multiplicative group are in the 2q-ordered group by
    definition (the 2q-ordered group is the full group!). As such, _all_
    selections for g (even 1 and p-1) will satisfy [g^(2q) mod p = 1].

    The public key validation routine required by NIST SP800-56 is
    effectively a test to make sure that the public key resides within the
    q-ordered group. If it does not, that test fails. If you've chosen g
    to generate the q-ordered group, all public keys will automatically be
    in the q-ordered group.

    More to the point, if you haven't selected g such that it generates the
    q-ordered group, you're not in compliance with NIST SP800-56. 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 q-ordered group or the 2q-ordered 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 SP800-56 requires, but that's fine from a
    security perspective. If you have be be NIST SP800-56 compliant, then
    you are required to use a q-ordered 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 openssl-dev@openssl.org
    Automated List Manager majordomo@openssl.org


+ Reply to Thread