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 [EMAIL PROTECTED] 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
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 1yp-1, and you're done. 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 [EMAIL PROTECTED]
FIPS compliance for Diffie-Hellman
Hi All, I have a query regarding FIPS compliance for Diffie-Hellman api's in the openssl stack. FIPS uses the recommendation for pairwise-key establishment schemes from NIST. Document is SP800-56A. Rev.1 As per FIPS compliance requirement for DH, there are a couple of KAT (Known Answer Test) specified in the aforementioned document (which are specified in Sec. 5.6.2.4 and Sec. 5.7.1.1). [Sec. 5.6.2.4 - FFC Full Public Key Validation] [Sec. 5.7.1.1 - FFC DH Primitive] 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. The public key does not fall into 'q' cyclic group where 'q' is defined as [q=(p-1)/2] and is a prime number. If I loop for few times I do get such generated values which passes this KAT. But I was expecting that FIPS compliant DH api's in openssl stack will generate and return only such values which satisfy this KAT. The only difference I found in normal and FIPS compliant DH code is that in latter, FIPS_self_tests api is also called; which really doesn't help in the issue noted above. I would really appreciate if anyone can throw some light on the state and any development on this issue. Regards, Nilay Tripathi One Convergence
Re: FIPS compliance for Diffie-Hellman
fips-1.1.2 does not have validation for Diffie-Hellmann. Which version are you looking at? -Kyle H On Tue, Jul 8, 2008 at 2:57 AM, Nilay Tripathi [EMAIL PROTECTED] wrote: Hi All, I have a query regarding FIPS compliance for Diffie-Hellman api's in the openssl stack. FIPS uses the recommendation for pairwise-key establishment schemes from NIST. Document is SP800-56A. Rev.1 As per FIPS compliance requirement for DH, there are a couple of KAT (Known Answer Test) specified in the aforementioned document (which are specified in Sec. 5.6.2.4 and Sec. 5.7.1.1). [Sec. 5.6.2.4 - FFC Full Public Key Validation] [Sec. 5.7.1.1 - FFC DH Primitive] 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. The public key does not fall into 'q' cyclic group where 'q' is defined as [q=(p-1)/2] and is a prime number. If I loop for few times I do get such generated values which passes this KAT. But I was expecting that FIPS compliant DH api's in openssl stack will generate and return only such values which satisfy this KAT. The only difference I found in normal and FIPS compliant DH code is that in latter, FIPS_self_tests api is also called; which really doesn't help in the issue noted above. I would really appreciate if anyone can throw some light on the state and any development on this issue. Regards, Nilay Tripathi One Convergence __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: FIPS compliance for Diffie-Hellman
fips-1.1 is not available, fips-1.1.1 is revoked, fips-1.1.2 is current (without DH), fips-1.2.0 is currently submitted for validation. Steve M (of the OSS Institute, which is the sponsor for the validation) stated that the fast-tracking of the fips-1.1.2 validation was possible because of the changes to the PRNG, but that the requirements for DH validation changed between the validation of 1.1.1 and 1.1.2. He has also stated that changes necessary for DH validation have been integrated into the 1.2.0 codebase. (Since I'm not intimately familiar with the code, I can't say one way or the other.) However, the code that was submitted for validation as fips-1.2.0 can be found at ftp://ftp.openssl.org/snapshot/openssl-fips-test-1.2.0.tar.gz if you're interested in poking at it. -Kyle H On Tue, Jul 8, 2008 at 3:36 AM, Nilay Tripathi [EMAIL PROTECTED] wrote: Thanks Kyle, Yes I was looking at fips-1.1.2 version only. Can you help me with some information, whether FIPS compliance for DH in openssl is available already in some other revision or expected in which future release down the line. Also, since the generation of 'q' cyclic order public key does not look deterministic to me, what is the approach which can be taken to tackle this compliance issue. Appreciate your help!! Nilay On Tue, Jul 8, 2008 at 3:48 PM, Kyle Hamilton [EMAIL PROTECTED] wrote: fips-1.1.2 does not have validation for Diffie-Hellmann. Which version are you looking at? -Kyle H On Tue, Jul 8, 2008 at 2:57 AM, Nilay Tripathi [EMAIL PROTECTED] wrote: Hi All, I have a query regarding FIPS compliance for Diffie-Hellman api's in the openssl stack. FIPS uses the recommendation for pairwise-key establishment schemes from NIST. Document is SP800-56A. Rev.1 As per FIPS compliance requirement for DH, there are a couple of KAT (Known Answer Test) specified in the aforementioned document (which are specified in Sec. 5.6.2.4 and Sec. 5.7.1.1). [Sec. 5.6.2.4 - FFC Full Public Key Validation] [Sec. 5.7.1.1 - FFC DH Primitive] 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. The public key does not fall into 'q' cyclic group where 'q' is defined as [q=(p-1)/2] and is a prime number. If I loop for few times I do get such generated values which passes this KAT. But I was expecting that FIPS compliant DH api's in openssl stack will generate and return only such values which satisfy this KAT. The only difference I found in normal and FIPS compliant DH code is that in latter, FIPS_self_tests api is also called; which really doesn't help in the issue noted above. I would really appreciate if anyone can throw some light on the state and any development on this issue. Regards, Nilay Tripathi One Convergence __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager [EMAIL PROTECTED] __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: FIPS compliance for Diffie-Hellman
Thanks very much Kyle !! Lemme see if I can make some progress with that 1.2.0 code-base on this. - Nilay On Tue, Jul 8, 2008 at 5:17 PM, Kyle Hamilton [EMAIL PROTECTED] wrote: fips-1.1 is not available, fips-1.1.1 is revoked, fips-1.1.2 is current (without DH), fips-1.2.0 is currently submitted for validation. Steve M (of the OSS Institute, which is the sponsor for the validation) stated that the fast-tracking of the fips-1.1.2 validation was possible because of the changes to the PRNG, but that the requirements for DH validation changed between the validation of 1.1.1 and 1.1.2. He has also stated that changes necessary for DH validation have been integrated into the 1.2.0 codebase. (Since I'm not intimately familiar with the code, I can't say one way or the other.) However, the code that was submitted for validation as fips-1.2.0 can be found at ftp://ftp.openssl.org/snapshot/openssl-fips-test-1.2.0.tar.gz if you're interested in poking at it. -Kyle H On Tue, Jul 8, 2008 at 3:36 AM, Nilay Tripathi [EMAIL PROTECTED] wrote: Thanks Kyle, Yes I was looking at fips-1.1.2 version only. Can you help me with some information, whether FIPS compliance for DH in openssl is available already in some other revision or expected in which future release down the line. Also, since the generation of 'q' cyclic order public key does not look deterministic to me, what is the approach which can be taken to tackle this compliance issue. Appreciate your help!! Nilay On Tue, Jul 8, 2008 at 3:48 PM, Kyle Hamilton [EMAIL PROTECTED] wrote: fips-1.1.2 does not have validation for Diffie-Hellmann. Which version are you looking at? -Kyle H On Tue, Jul 8, 2008 at 2:57 AM, Nilay Tripathi [EMAIL PROTECTED] wrote: Hi All, I have a query regarding FIPS compliance for Diffie-Hellman api's in the openssl stack. FIPS uses the recommendation for pairwise-key establishment schemes from NIST. Document is SP800-56A. Rev.1 As per FIPS compliance requirement for DH, there are a couple of KAT (Known Answer Test) specified in the aforementioned document (which are specified in Sec. 5.6.2.4 and Sec. 5.7.1.1). [Sec. 5.6.2.4 - FFC Full Public Key Validation] [Sec. 5.7.1.1 - FFC DH Primitive] 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. The public key does not fall into 'q' cyclic group where 'q' is defined as [q=(p-1)/2] and is a prime number. If I loop for few times I do get such generated values which passes this KAT. But I was expecting that FIPS compliant DH api's in openssl stack will generate and return only such values which satisfy this KAT. The only difference I found in normal and FIPS compliant DH code is that in latter, FIPS_self_tests api is also called; which really doesn't help in the issue noted above. I would really appreciate if anyone can throw some light on the state and any development on this issue. Regards, Nilay Tripathi One Convergence __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager [EMAIL PROTECTED] __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager [EMAIL PROTECTED]
Re: FIPS compliance for Diffie-Hellman
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 __ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager [EMAIL PROTECTED]
