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

[mancha]

On Sun, Aug 02, 2015 at 12:59:49AM +0000, paul at securecottage.com wrote:
> 
> 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.

Hi Paul.

I came across a paper by Mckee and Pinch [1] you might be interested in.
They describe an algo to factor n=pq when a common factor b of (p-1) and
(q-1) is known. Fortunately (for RSA), their algo is O(N^(1/4)/b) so to
just break even with GNFS the factor needs to be quite large:

modulus (n)   common factor (b)
(bits)        (bits)
 512            64
1024           169
2048           395
3072           629
4096           868

A literature review might uncover other interesting (and more recent)
ways to leverage common factors.

> (factorisation of p*q-1 is shown):
> 
> n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 *
> 5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628
> 67234233761906471233193768567784328338581360170038166729050302672416075037390699071355182394190448204086007354388034161296410061846686501
> 4941425056336718955019

Here's a slight improvement to my initial decomposition: 2 * 3^3 * 7 *
13 * 67 * 2399 * 28559 * 475108039391 * 2304683693240273 *
27081000093637206233815756979 *
184975060461462389844824492821434552152567410456158418229544246514131718793664172374877783767032501925392596713947281388784630550689770489020593012165694501623162932662905453122620777823162028887054350359842476275647758696138793577667109927

Note: factoring the last term in my product is left as an exercise to
the reader.

> 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.

Safe primes (p=2q+1) play an important role in Diffie-Hellman to avoid
subgroup confinement attacks. I just confirmed OpenSSL does indeed use
them for DH; from dh_builtin_genparams: 

  if (!BN_generate_prime_ex(ret->p, prime_len, 1, t1, t2, cb))
      goto err;

So, OpenSSL users are already quite used to whatever performance hit
is associated with them.

> 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

Given the low costs, one would be hard-pressed to find an intelligent
objection to your suggestion. Thanks for bringing this up.

--mancha (https://twitter.com/mancha140)

---
[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1333
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150803/e99dbf1a/attachment.sig>