Closed
Bug 335016
Opened 15 years ago
Closed 13 years ago
mpp_pprime (MillerRabin probabilistic primality test) may choose 0 or 1 as the random integer
Categories
(NSS :: Libraries, defect, P1)
Tracking
(Not tracked)
RESOLVED
FIXED
3.12.3
People
(Reporter: wtc, Assigned: nelson)
References
Details
(Whiteboard: FIPS)
Attachments
(1 file)
1.19 KB,
patch

nelson
:
review+

Details  Diff  Splinter Review 
mpp_pprime implements the MillerRabin probabilistic primality test. This algorithm is documented in 1. Handbook of Applied Cryptography (HAC), Algorithm 4.24 on page 139. 2. FIPS 1862, Appendix 2.1 on page 13. This algorithm has an outer loop and an inner loop. It runs for outer loop for nt iterations, where nt is the second parameter to mpp_pprime. In each iteration of the outer loop, we choose a random integer x. The range of x is specified as 2 <= x <= a2 (HAC), or 2 <= x <= a1 (FIPS 1862) where 'a' is the integer to be tested for primality (the first parameter to mpp_pprime). Ignoring the a2 vs. a1 issue, we know that x cannot be 0 or 1. But mpp_pprime chooses x as follows: mpp_random(&x); MP_CHECKOK( mp_mod(&x, a, &x) ); So x may be 0 or 1, even though the probability is extremely low, <= (4/a)*nt. Let's see what the consequences are if x is 0 or 1. 1. If x = 0, we initialize z = (x ** m) mod a = 0. Then in each iteration of the inner loop, we let z = (z ** 2) mod a = 0. So z stays 0. When the inner loop ends, we report that a is NOT prime. This could be a false composite. The MillerRabin primality test is not supposed to return false composite. For our purposes, getting a false composite seems fine. 2. If x = 1, we initialize z = (x ** m) mod a = 1. So we immediately go on to the next iteration of the outer loop. The consequence is that we "waste" an iteration of the outer loop. This seems fine.
Assignee  
Updated•15 years ago

Whiteboard: FIPS
Assignee  
Updated•15 years ago

Priority:  → P4
Assignee  
Updated•13 years ago

Assignee: nobody → nelson
Priority: P4 → P2
Target Milestone:  → 3.12.3
Assignee  
Comment 2•13 years ago


My take on this is that as long as we don't ever accept 0 or 1 as a prime, we're OK. So, I'm not convinced this needs to be fixed. Some things we could do about it include: a) set the bit whose value is 2 (1<<1) to 1 in the "random" number b) compute a' = a  3, then compute x = (random % a') + 2 c) test initial random value, and if less than 2, get a new random value Of those, (a) is a single operation, noniterative, can't fail, efficient. (b) requires storage for one more bignum, and one extra computation. (hmm, what are the bounds on the modulus a? Could it be less than 4?) (c) requires two extra ops (compare, conditional jump), and potentially an extra iteration of the PRNG. It seems the most expensive.
Assignee  
Comment 3•13 years ago


Would a patch like this be acceptable? mpp_random(&x); + mpl_set_bit(&x, 1, 1); MP_CHECKOK( mp_mod(&x, a, &x) ); That mpl call can't fail because every mp_int always has at least one mp_digit, the least significant digit, even if it is zero. But you can be extra safe by coding it as mpp_random(&x); + MP_CHECKOK( mpl_set_bit(&x, 1, 1) ); MP_CHECKOK( mp_mod(&x, a, &x) );
Reporter  
Comment 4•13 years ago


(I'm fine with marking this bug WONTFIX. Might want to add my findings in comment 0 as a comment to the function to indicate that we considered this issue.) This patch implements (c). It relies on the existing outer for loop for retrying if x <= 1. Ignoring computational cost, I think (b) is the best solution. (a) may have unknown consequences because the 2 (1 << 1) bit of x will always be set. I'd rather avoid that risk.
Attachment #348272 
Flags: review?(nelson)
Assignee  
Updated•13 years ago

Attachment #348272 
Flags: review?(nelson) → review+
Assignee  
Comment 5•13 years ago


Comment on attachment 348272 [details] [diff] [review] Proposed patch for (c) r=nelson
Reporter  
Comment 6•13 years ago


I checked in the patch on the NSS trunk (NSS 3.12.3). Checking in mpprime.c; /cvsroot/mozilla/security/nss/lib/freebl/mpi/mpprime.c,v < mpprime.c new revision: 1.24; previous revision: 1.23 done
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution:  → FIXED
You need to log in
before you can comment on or make changes to this bug.
Description
•