334533 - FIPS DSA PQG Generation test failures

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Wan-Teh Chang]

We are getting a very small number of FIPS DSA PQG Generation
test failures.  When we got the first test failure of this
kind, I attributed it to my fix for bug and backed out my fix.
But we are still getting this kind of test failures.

The only information we get from the testing lab about these
test failures is:
    REASON: DSA Prime Value failed
or
    REASON: Prime Value failed

I will attach some RESPONSE files that failed the tests.

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

For DSA primes, NSS uses an algorithm for generating "strong" primes, 
(primes for which (P-1)/2 is also prime) and that algorithm can take 
a very long time.  IIRC, after a certain number of attempts, the 
algorithm gives up, and asks to be reseeded.  In some of our test 
prorams, that results in a failure being reported, rather than in a
retry.  

Is that relevant to this issue?

Comment 2

[Wan-Teh Chang]

Attachment: PQGGen4.rsp (Windows XP SP2) failed Mod-768

This RESPONSE file was generated on Windows XP SP2,
using lib/freebl/pqg.c, rev. 1.9.2.1, with the fix for
bug 326754 (I forgot to note the bug number in comment 0).
It was this test failure that made me think the fix was
the culprit and back it out in rev. 1.9.2.2.  But the other
test failures proved that that fix did not cause the test
failure.

The testing lab said:

PQGGen4.rsp:
PQG Generation has passed for all the MOD values except for Mod-768.
- REASON: DSA Prime Value failed.

The test failed for Mod-768 for only 1 of 5 values. Here is the exact snapshot of the failed entry (It is actually the first entry under Mod-768):

************************************************************************************************************************************************************************************************************************************************
Mod 768:
DSA_PrimeVal failed:
P = ec08d2f3de86f4b8eb002fac4727eb36a4275a45ff4e903e3c0a31f5d0ee21edd2b7edc546ce7e78a56cbed2ff1aae185df531fdefb0edbc28a57a4528fa2ac1db15c1b2444c63f738b3fe891c36622751ae08d9f20bed642331d1a5d06d020b
Q = e62b9e4c82164ec89944e612e9c122024dc3ff01
G = d3cf4e32bcb2f9bf514c2a993a6cbf3eb1fa65bcd2d86518aa8c49fee8c7289c28811cc784540c27d546a92b6371655d0c6b9d5af1e79c1b7f13445b600617cf573c063f8ae9d7a93327e766d0fcd9bf10bc62b157d23d917dc54397a691c386
Seed = 00cd784edc03c68105df9b42afa3176132808d4d
c = 561
H = 7bcd94c0e78fb2aee53c8c5898fea0ac5916a68ffcdc68476fb2296b2bdb6ac83b8e923d9978cca9a03e437c3deda0ba9037af4b41b36b9cbef5afdf387edd6aa5ab565b8b4ce709af7dd9d6803db6ef75d4b1d92e4677bb47217823ff5ef355

************************************************************************************************************************************************************************************************************************************************

Comment 3

[Nelson Bolyard (seldom reads bugmail)]

My comment 1 was mistaken.  We do that for DH primes, not PQG primes. 

IIRC, there is a special FIPS prime generation algorithm for PQG primes.
Among its outputs are P, Q, g, and also seed, counter, and "h".
The values of seen, counter and h may be used to verify that the 
prime P was generated using the specified prime generation algorithm
NSS (freebl) contains a function to verify a PQG was generated by that
algorithm, using the seed, counter and h values.  

When we run that test against the PQG values that the lib indicted,
do those values pass our test?  

If so, then we should ask the lab if
a) do that also run that same test, and does it pass that test for them?
b) do they also run some other test?  

if not, then obviously we know what we must do.

Comment 4

[Wan-Teh Chang]

Attachment: PQGGen.rsp for RHEL3x86: Mod value 576 failed

The only information we have about the failures is:

  All the tests have passed for all Mod-sizes,
  except for Mod value 576 in PQG-Generation
  (REASON: Prime Value failed).

Comment 5

[Wan-Teh Chang]

Attachment: PQGGen.rsp for RHEL4x86: Mod value 768 failed

The only information we have about the failure(s) is:

  All the tests have passed for all Mod-sizes,
  except for Mod value 768 in PQG-Generation
  (REASON: Prime Value failed).

In this PQGGen.rsp, and in the PQGGen.rsp for
RHEL3x86 that I attached earlier, we don't know
which set(s) of parameters failed the test.

Comment 6

[Wan-Teh Chang]

Attachment: Proposed workaround for NIST CMVP's misinterpretation of the specification of SEED

When I mentioned this rare and probabilistic test failure
at the NSS meeting with a pessimistic outlook of fixing it,
Nelson quickly observed that the set of PQG parameters that
failed the test has a Seed value with a leading 00 byte.
He guessed that the NIST CMVP verification tool may consider
such a Seed value as shorter than 160 bits.

I searched for "Seed = 00" in the three PQGGen.rsp files
that contained parameters that failed the test.  Indeed,
they each have exactly one set of parameters whose Seed
begins with 00, and that set of parameters is in the
Mod size that the testing lab told us failed the test.
I also searched for "Seed = 00" in all the PQGGen.rsp
files that passed the test, and none of them contains
such a Seed value.  Finally, I observed that Seed values
that begin with a byte such as 02, 09, 0f, and 0d are
OK.

So this means the NIST CMVP verification tool only
rejects a most significant byte of 0.  It doesn't
insist on the most significant bit being equal to 1.
FIPS 186-2 Appendix 2.2 Step 1 (page 14) says:
  Choose an arbitrary sequence of at least 160 bits
  and call it SEED.
Note the word "arbitrary".  It doesn't impose any
constraint on the most significant byte or bit.
This is why we believe the NIST CMVP verification
tool misinterprets the specification of SEED.

Our workaround is to always set the most significant
bit of SEED to 1.  This ensures that the most significant
byte is nonzero, making the NIST CMVP verification tool
happy.

Comment 7

[Wan-Teh Chang]

Comment on attachment 219226 [details] [diff] [review]
Proposed workaround for NIST CMVP's misinterpretation of the specification of SEED

I forgot to mention that I also added a check to
PQG_ParamGenSeedLen to ensure that SEED is at
least 20 bytes (= 160 bits).

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 219226 [details] [diff] [review]
Proposed workaround for NIST CMVP's misinterpretation of the specification of SEED

r=nelson

Comment 9

[Wan-Teh Chang]

I checked in the proposed workaround on the NSS trunk (3.12)
and NSS_3_11_BRANCH (3.11.1).

Checking in pqg.c;
/cvsroot/mozilla/security/nss/lib/freebl/pqg.c,v  <--  pqg.c
new revision: 1.13; previous revision: 1.12
done

Checking in pqg.c;
/cvsroot/mozilla/security/nss/lib/freebl/pqg.c,v  <--  pqg.c
new revision: 1.9.2.3; previous revision: 1.9.2.2
done