I would like to preface this bug report by saying that OpenSSL is a fantastic toolkit.
I found a cryptographic bug in bn_prime.c in the function BN_is_prime_fasttest().
The following is the code snippet:
for (i = 0; i < checks; i++)
{
if (!BN_pseudo_rand(check, BN_num_bits(A1), 0, 0))
goto err;
if (BN_cmp(check, A1) >= 0)
if (!BN_sub(check, check, A1))
goto err;
if (!BN_add_word(check, 1))
goto err;
/* now 1 <= check < A */
j = witness(check, A, A1, A1_odd, k, ctx, mont);
This function correctly insures that check < A1. However, 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.
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, 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. It is also possible to choose the candidate
witnesses to be the values less than 2* (log_2 p)^2, and thereby assume
that the Generalized Riemann Hypothesis (GRH) holds. Then there is no
random number generation at all, and may turn out to be provably correct
some day.
Adam Young
Cryptographer/Lead Systems Engineer
Lockheed Martin Global Telecommunications
