Last Comment Bug 335016 - mpp_pprime (Miller-Rabin probabilistic primality test) may choose 0 or 1 as the random integer
: mpp_pprime (Miller-Rabin probabilistic primality test) may choose 0 or 1 as t...
Product: NSS
Classification: Components
Component: Libraries (show other bugs)
: 3.11
: All All
P1 trivial (vote)
: 3.12.3
Assigned To: Nelson Bolyard (seldom reads bugmail)
Depends on:
Blocks: FIPS2008
  Show dependency treegraph
Reported: 2006-04-21 16:26 PDT by Wan-Teh Chang
Modified: 2008-11-17 16:15 PST (History)
2 users (show)
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---

Proposed patch for (c) (1.19 KB, patch)
2008-11-14 15:49 PST, Wan-Teh Chang
nelson: review+
Details | Diff | Splinter Review

Description User image Wan-Teh Chang 2006-04-21 16:26:40 PDT
mpp_pprime implements the Miller-Rabin probabilistic
primality test.  This algorithm is documented in
1. Handbook of Applied Cryptography (HAC), Algorithm 4.24
on page 139.
2. FIPS 186-2, 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 <=  a-2  (HAC), or
  2 <= x <=  a-1  (FIPS 186-2)
where 'a' is the integer to be tested for primality
(the first parameter to mpp_pprime).

Ignoring the a-2 vs. a-1 issue, we know that x cannot
be 0 or 1.  But mpp_pprime chooses x as follows:

    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 Miller-Rabin
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.
Comment 1 User image glen beasley 2008-10-16 11:10:38 PDT
Marking P1. Request fix by Nov 17th for FIPS.
Comment 2 User image Nelson Bolyard (seldom reads bugmail) 2008-11-13 21:46:23 PST
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, non-iterative, 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.
Comment 3 User image Nelson Bolyard (seldom reads bugmail) 2008-11-13 22:08:42 PST
Would a patch like this be acceptable?

+   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 

+   MP_CHECKOK( mpl_set_bit(&x, 1, 1) );
    MP_CHECKOK( mp_mod(&x, a, &x) );
Comment 4 User image Wan-Teh Chang 2008-11-14 15:49:58 PST
Created attachment 348272 [details] [diff] [review]
Proposed patch for (c)

(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.
Comment 5 User image Nelson Bolyard (seldom reads bugmail) 2008-11-14 18:05:37 PST
Comment on attachment 348272 [details] [diff] [review]
Proposed patch for (c)

Comment 6 User image Wan-Teh Chang 2008-11-17 16:15:32 PST
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

Note You need to log in before you can comment on or make changes to this bug.