65151 - PQG parameter generation fails

Status: RESOLVED FIXED

(NSS :: Libraries, defect)

Description

[Jamie Nicolson]

The algorithm tries to generate a prime, Q, by generating random numbers and
then testing them for primality. It loops around until it finds a prime, or
until MAX_ITERATIONS is exceeded. MAX_ITERATIONS is set to 5, which is usually
too low to find a prime.

Comment 1

[Wan-Teh Chang]

Ian, is this your code?

Comment 2

[Ian McGreer]

This is my code.  I believe the number does need to be larger.  I seem to 
remember the frequency of primes in 1024-bit numbers being about 1/300, so I 
suggest 500 (this operation is fairly fast).

I also want to change the number of Miller-Rabin primality tests to 50, which is 
what FIPS-186 specifies.

patch forthcoming.

Comment 3

[Ian McGreer]

Attachment: comments? Nelson, is 500 reasonable?

Comment 4

[Nelson Bolyard (seldom reads bugmail)]

Please don't change "the number of Miller-Rabin primality tests to 50"
until we can discuss it more.  I believe it is unnecessary.  I don't
want to elaborate here.

I'd say that the limit ought to be a function of the size of the prime,
and ought to be at least twice the frequency.  That is, if the frequency
is really 1/300 then I'd do up to 600.

Comment 5

[Ian McGreer]

I got the number 50 from FIPS 186, section 2.1.  I thought mpp_pprime was an 
implementation of Miller-Rabin, so I assumed that 50 would be the correct 
number.  Is that not the case?

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

The requirement is to produce a number whose probability of 
being non-prime is less than 1/(4**50).  Doing Miller-Rabin
50 times will assure that, but is overkill for very large 
values.  1/(4**n) is the upper bound for probability that 
the test will declare a composite number prime. As the 
numbers get larger, the probability of a pseudoprime
goes down.  

That is why mpp_make_prime adjusts the number of tests
according to the size of the number.

You'll find that quite a few other libraries also do this.
I'm looking for a citable reference on this (other than
third party source code).

Comment 7

[Nelson Bolyard (seldom reads bugmail)]

First , I need to correct what I wrote above.
The FIPS 186-1 requirement is that a "robust primality
test" be used on q and p to determine if they're prime
(Appendix 2.2, steps 4 and 11.  A footnote in that 
appendix defines "robust primality test" as "one where
the probability of a non-prime number passing the test
is at most 2**-80."

In the Handbook of Applied Cryptography, Table 4.4, 
part of note 4.49 (page 148) shows t, the number of 
MR tests that must be run on a k-bit candidate, for 
which the probability is at most (1/2)**80.   Section
4.4.3, especially note 4.57 (pages 150-151) state that
for randomly chosen 160 bit numbers (q), 18 MR tests
is enough, and that 5 is more than enough for all 
valid values of L (bits in P).  I'm going to replace
the code in mpp_make_prime with code that implements
table 4.4.

So, 50 is way overkill.  Please use the values 18 and 5
for q and p respectively.

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

Attachment: proposed changes to lib/freebl/mpi/mpprime.c

Comment 9

[Ian McGreer]

I verified the patch by checking the values in HAC table 4.4.

I will attach a revised patch for the PQG bug.  In it, the maximum number of 
iterations to attempt to generate a prime is fixed at 600.  Nelson, I read from 
your comments that this should be sufficient?  I don't believe it should be 
neccessary to make this number a function of the size of the prime, since it's 
really just there to prevent the library from spinning out of control.  

Comment 10

[Ian McGreer]

Attachment: patch as promised

Comment 11

[Nelson Bolyard (seldom reads bugmail)]

Ian, your patch looks good to me.

Comment 12

[Wan-Teh Chang]

Please check in the fix.

Comment 13

[Ian McGreer]

I have checked in the patch to pqg.c.

Comment 14

[Nelson Bolyard (seldom reads bugmail)]

My patch is also checked in.
Ian, is this bug realy to be marked resolved/fixed?

Comment 15

[Ian McGreer]

Yes, I believe so.  Marking as fixed.