On Sun, Aug 02, 2015 at 12:59:49AM +0000, p...@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
pgpHjc5ziJSkT.pgp
Description: PGP signature
_______________________________________________ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev