[openssl-dev] common factors in (p-1) and (q-1)

[paul at securecottage.com]

I'd like to thank several people for looking into my assertion that it  
is possible for common factors in p-1 and q-1 to leak from the  
factorisation of n-1.

Particularly, Viktor Dukhovni, for trying tens of thousands of key  
generation iterations to see if common factors are possible.  From  
Viktor's work and other people's comments I drew the following  
conclusions:

Viktor Dukhovni reports, after looking at the rsa key generation code  
of openssl, that p-1 and q-1 are both checked for the first 2048  
factors (up to 17863). As such such low primes are not possible as  
factors of either p-1 or q-1. However, common factors higher than  
17863 are possible as factors of both p-1 and q-1.  But it takes  
20,000 key generations (not in safe mode) before such an event  
happens. He managed to get a common factor of gcd(p-1,q-1) = 2 * 28559  
from the following 1024 bit rsa generated key (factorisation of p*q-1  
is shown):

n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 *
5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628 67234233761906471233193768567784328338581360170038166729050302672416075037390699071355182394190448204086007354388034161296410061846686501  
4941425056336718955019

Any rsa key generation in SAFE mode will always have a gcd(p-1,q-1)=2,  
so SAFE mode always avoids common factors.

My conclusion is that openssl code can have common factors (must be  
above 17863) in its rsa keys every 20,000 key generations or so when  
not generated in SAFE mode, and that at this time approximately 30  
bits of the totient will be revealed out of the 1024 bits of the full  
totient. There is, of course, no way of knowing which of the 20,000  
key generations will have the common factors.

Most people felt that the check (for gcd(p-1,q-1)> 16) was possible  
but they were not sure it was worth doing.

I'd like to point out from a cyber-attack possibility the check is  
worth doing.  In RSA_generate_key_ex() in rsa_gen.c the following code  
is seen:

int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb)
{
#ifdef OPENSSL_FIPS
     if (FIPS_mode() && !(rsa->meth->flags & RSA_FLAG_FIPS_METHOD)
         && !(rsa->flags & RSA_FLAG_NON_FIPS_ALLOW)) {
         RSAerr(RSA_F_RSA_GENERATE_KEY_EX, RSA_R_NON_FIPS_RSA_METHOD);
         return 0;
     }
#endif
     if (rsa->meth->rsa_keygen)
         return rsa->meth->rsa_keygen(rsa, bits, e_value, cb);
#ifdef OPENSSL_FIPS
     if (FIPS_mode())
         return FIPS_rsa_generate_key_ex(rsa, bits, e_value, cb);
#endif
     return rsa_builtin_keygen(rsa, bits, e_value, cb);
}

Third party modules, or methods, can be added to openssl code and  
these can do the rsa key generation as in:

if (rsa->meth->rsa_keygen)
         return rsa->meth->rsa_keygen(rsa, bits, e_value, cb);

As such it is appropriate that some checks be made at   
RSA_generate_key_ex() to make sure that the other software hasn't  
returned a bad key.  Openssl software is a significant part of the  
Internet security infastructure and so it would obviously be the  
target of hacking and cyber infiltration.  Some redundant checks are  
appropriate because of this.

A gcd(p-1,q-1)>16 check will disallow less than 1 percent of the  
currently acceptable keys, won't take much time to run, and would  
defeat cyber attempts to create a key with a significant common factor  
within it.

Thanks

Paul Cheffers