Young, Adam [NCSUS Non J&J] <[EMAIL PROTECTED]>:
> I found a cryptographic bug in bn_prime.c in the function
> BN_is_prime_fasttest().
> [...] the value
> check, which may turn out to be a witness of compositeness for the
> value being tested for primality is not being drawn using the correct
> probability distribution. In Miller-Rabin, it is supposed to be
> drawn uniformly from 1 to p-1 inclusive where p is the candidate prime.
Yup, true.
> This code does not sample values uniformly since it "wraps" values that
> exceed A1 (in the call BN_sub(check,check,A1). This is a common bug
> in implemented cryptosystems. To make the code conform to Miller-Rabin
> as defined by Miller,
I guess you mean "as defined by Rabin"? Gary L. Miller's thesis
(J. Comp. and Sys. Sci 13 (1976) 300-317) presents a deterministic
algorithm which recognizes all composites assuming that the Extended
Riemann Hypothesis holds. The probabilistic variant is due to
M. O. Rabin (J. Number Theory 12 (1980) 128-138), and as we
use the results of Damg�rd, Landrock, and Pomerance (Math. Comp. 61
(1993) 177-194) in our BN_prime_checks_for_size() macro, we certainly
should use uniformly chosen witnesses so that the intended upper
bound of 2^-80 on the error rate for random candidates is really ensured.
(Considering that inverting witnesses leaves the test result invariant,
the effective skew of the witness distribution is actually smaller than
it might appear at first sight. Also, of course, it is not clear
whether this skew actually deteriorates the test -- it might just as
well improve it, and probably it does not matter at all. But as the
analysis of the primality test assumes a uniform distribution, that is
what we should use.)
> the standard Von Neuman type las vegas algorithm
> should be used: if check isn't less than A1, then pick check randomly
> until it does, don't wrap. This will remove the bias that the code above
> introduces.
Actually we already have a function for generating uniformly chosen
integers in some interval (countermeasure against Bleichenbacher's
attack on DSA).
> It is also possible to choose the candidate
> witnesses to be the values less than 2* (log_2 p)^2,
Sure, but we are not that patient :-)
For DSA parameter generation, we use 50 random rounds of Rabin-Miller
following the FIPS document -- try 'openssl dsaparam 1024' and
observe the plus signs (one Rabin-Miller round each).
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
