Re: [openssl-dev] common factors in (p-1) and (q-1)
On Fri, Jul 31, 2015 at 06:46:22PM +, Viktor Dukhovni wrote: On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote: Cool observation. From running a bit of Python code, it looks like the probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at least for random numbers between 2048 and 4096 bits long. It looks like putting in a GCD(p-1, q-1) check will slow down finding suitable p and q by around a factor of 6.5. A smaller slow-down would be incurred one were to restrict both of p,q to 3 mod 4. In that case 2 would be the largest common even factor of (p-1) and (q-1), and any appreciably large common odd factor (necessarily above 17863 due to how each of p/q is chosen) would be very rare. Is there a good argument for adding the gcd test? How big does the common factor have to be for any information it might provide to be substantially useful in finding 1/e mod phi(m)? The larger the common factor is, the smaller the probability of p-1 and q-1 sharing it (for a given sufficiently large prime factor r of (p-1), the probability of (q-1) also having that factor is 1/(r-1)). If say r needs be 80 bits long to be useful in attacking RSA 1024, then only ~1 in 2^80 (p-1,q-1) pairs will have such a common factor, which is sufficiently rare not warrant any attention. Also one still needs to be able to fully factor (n-1). After tens of thousands of trials, I managed to generate a (p,q,n) triple with a 1024-bit modulus n in which (p-1,q-1) have a common odd factor. n = 123727085863382195696899362818055010267368591819174730632443285012648773223152448218495408371737254282531468855140111723936275062312943433684139231097953508685462994307654703316031424869371422426773001891452680576333954733056995016189880381373567072504551999849596021790801362257131899242011337424119163152403 e = F_4 = 65537 gcd(p-1,q-1) = 2 * 28559 What can the OP tell us about d, p or q? Can anyone produce a full factorization of n - 1? n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 * 5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628672342337619064712331937685677843283385813601700381667290503026724160750373906990713551823941904482040860073543880341612964100618466865014941425056336718955019 -- https://twitter.com/mancha140 pgpTqUnBerhoH.pgp Description: PGP signature ___ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
[openssl-dev] NEed help
I am trying to compile openssl 1.0.2 SNAP 20150801 and now I get if [ -n libcrypto.so.1.0.0 libssl.so.1.0.0 ]; then (cd ..; make libcrypto.so.1.0.0); fi [ -z ] || gcc -fPIC -DOPENSSL_PIC -DZLIB_SHARED -DZLIB -DOPENSSL_THREADS -pthread -D_THREAD_SAFE -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -DPERL5 -DL_ENDIAN -DTERMIOS -fomit-frame-pointer -O2 -march=pentium3 -Wall -g -DOPENSSL_EXPERIMENTAL_JPAKE -DOPENSSL_EXPERIMENTAL_LIBUNBOUND -DOPENSSL_EXPERIMENTAL_STORE -DOPENSSL_BN_ASM_PART_WORDS -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DRMD160_ASM -DAES_ASM -DGHASH_ASM -Iinclude -DFINGERPRINT_PREMAIN_DSO_LOAD -o fips_premain_dso fips_premain.c fipscanister.o libcrypto.a -ldl -lm -lc /usr/lib/libc.a(sha.o): In function `SHA': sha.o(.text+0x0): multiple definition of `SHA' libcrypto.a(sha_one.o):/usr/source/openssl-1.0.2-stable-SNAP-20150801/crypto/sha/sha_one.c:66: first defined here ld: Warning: size of symbol `SHA' changed from 142 to 92 in /usr/lib/libc.a(sha.o) /usr/lib/libc.a(malloc.o)(.text+0x16): undefined reference to `__progname' /usr/lib/libc.a(malloc.o)(.text+0xe0): undefined reference to `__progname' /usr/lib/libc.a(syslog.o): In function `vsyslog': syslog.o(.text+0x3a5): undefined reference to `__progname' /usr/lib/libc.a(getenv.o): In function `__findenv': getenv.o(.text+0x65): undefined reference to `environ' getenv.o(.text+0x72): undefined reference to `environ' /usr/lib/libc.a(exec.o): In function `execl': exec.o(.text+0x103): undefined reference to `environ' /usr/lib/libc.a(exec.o): In function `execv': exec.o(.text+0x26b): undefined reference to `environ' /usr/lib/libc.a(exec.o): In function `execvp': exec.o(.text+0x400): undefined reference to `environ' /usr/lib/libc.a(exec.o)(.text+0x4da): more undefined references to `environ' follow *** Error code 1 Stop. *** Error code 1 Stop. *** Error code 1 Stop. *** Error code 1 Stop. *** Error code 1 Stop. Pointers please on how to fix. -- Member - Liberal International This is doctor@@nl2k.ab.ca Ici doctor@@nl2k.ab.ca God,Queen and country!Never Satan President Republic!Beware AntiChrist rising! http://www.fullyfollow.me/rootnl2k Look at Psalms 14 and 53 on Atheism Abuse a man unjustly, and you will make friends for him. -Edgar Watson Howe ___ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
[openssl-dev] Debugging a compile issue
A few weeks ago, I overloaded my server and compiler and now I get signed content test streaming BER format, 2 DSA and 2 RSA keys, no attributes: OK signed content test streaming S/MIME format, 2 DSA and 2 RSA keys: verify error *** Error code 1 Stop. *** Error code 1 Stop. How can debug and rectify the situation? I do need to move forward. -- Member - Liberal International This is doctor@@nl2k.ab.ca Ici doctor@@nl2k.ab.ca God,Queen and country!Never Satan President Republic!Beware AntiChrist rising! http://www.fullyfollow.me/rootnl2k Look at Psalms 14 and 53 on Atheism Abuse a man unjustly, and you will make friends for him. -Edgar Watson Howe ___ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Re: [openssl-dev] common factors in (p-1) and (q-1)
On Sat, Aug 01, 2015 at 01:50:00PM +, Ben Laurie wrote: On Sat, 1 Aug 2015 at 14:22 mancha manc...@zoho.com wrote: On Fri, Jul 31, 2015 at 06:46:22PM +, Viktor Dukhovni wrote: On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote: Cool observation. From running a bit of Python code, it looks like the probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at least for random numbers between 2048 and 4096 bits long. It looks like putting in a GCD(p-1, q-1) check will slow down finding suitable p and q by around a factor of 6.5. A smaller slow-down would be incurred one were to restrict both of p,q to 3 mod 4. In that case 2 would be the largest common even factor of (p-1) and (q-1), and any appreciably large common odd factor (necessarily above 17863 due to how each of p/q is chosen) would be very rare. Is there a good argument for adding the gcd test? How big does the common factor have to be for any information it might provide to be substantially useful in finding 1/e mod phi(m)? The larger the common factor is, the smaller the probability of p-1 and q-1 sharing it (for a given sufficiently large prime factor r of (p-1), the probability of (q-1) also having that factor is 1/(r-1)). If say r needs be 80 bits long to be useful in attacking RSA 1024, then only ~1 in 2^80 (p-1,q-1) pairs will have such a common factor, which is sufficiently rare not warrant any attention. Also one still needs to be able to fully factor (n-1). After tens of thousands of trials, I managed to generate a (p,q,n) triple with a 1024-bit modulus n in which (p-1,q-1) have a common odd factor. n = 123727085863382195696899362818055010267368591819174730632443285012648773223152448218495408371737254282531468855140111723936275062312943433684139231097953508685462994307654703316031424869371422426773001891452680576333954733056995016189880381373567072504551999849596021790801362257131899242011337424119163152403 e = F_4 = 65537 gcd(p-1,q-1) = 2 * 28559 What can the OP tell us about d, p or q? Can anyone produce a full factorization of n - 1? n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 * 5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628672342337619064712331937685677843283385813601700381667290503026724160750373906990713551823941904482040860073543880341612964100618466865014941425056336718955019 That is not a prime factorisation. Just helping get things started. Feel free to take over and claim the last number in my product. pgp2BFvzlN2bz.pgp Description: PGP signature ___ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Re: [openssl-dev] common factors in (p-1) and (q-1)
On Sat, 1 Aug 2015 at 14:22 mancha manc...@zoho.com wrote: On Fri, Jul 31, 2015 at 06:46:22PM +, Viktor Dukhovni wrote: On Fri, Jul 31, 2015 at 11:19:39AM -0700, Bill Cox wrote: Cool observation. From running a bit of Python code, it looks like the probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at least for random numbers between 2048 and 4096 bits long. It looks like putting in a GCD(p-1, q-1) check will slow down finding suitable p and q by around a factor of 6.5. A smaller slow-down would be incurred one were to restrict both of p,q to 3 mod 4. In that case 2 would be the largest common even factor of (p-1) and (q-1), and any appreciably large common odd factor (necessarily above 17863 due to how each of p/q is chosen) would be very rare. Is there a good argument for adding the gcd test? How big does the common factor have to be for any information it might provide to be substantially useful in finding 1/e mod phi(m)? The larger the common factor is, the smaller the probability of p-1 and q-1 sharing it (for a given sufficiently large prime factor r of (p-1), the probability of (q-1) also having that factor is 1/(r-1)). If say r needs be 80 bits long to be useful in attacking RSA 1024, then only ~1 in 2^80 (p-1,q-1) pairs will have such a common factor, which is sufficiently rare not warrant any attention. Also one still needs to be able to fully factor (n-1). After tens of thousands of trials, I managed to generate a (p,q,n) triple with a 1024-bit modulus n in which (p-1,q-1) have a common odd factor. n = 123727085863382195696899362818055010267368591819174730632443285012648773223152448218495408371737254282531468855140111723936275062312943433684139231097953508685462994307654703316031424869371422426773001891452680576333954733056995016189880381373567072504551999849596021790801362257131899242011337424119163152403 e = F_4 = 65537 gcd(p-1,q-1) = 2 * 28559 What can the OP tell us about d, p or q? Can anyone produce a full factorization of n - 1? n-1 = 2 * 3^3 * 7 * 13 * 67 * 2399 * 28559 * 5485062554686449262177590194597345407327047899375366044215091312099734701911004226037445837630559113651708968440813791318544450398897628672342337619064712331937685677843283385813601700381667290503026724160750373906990713551823941904482040860073543880341612964100618466865014941425056336718955019 That is not a prime factorisation. -- https://twitter.com/mancha140 ___ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev ___ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Re: [openssl-dev] common factors in (p-1) and (q-1)
On Fri, Jul 31, 2015 at 11:31:08PM +, p...@securecottage.com wrote:
Hi Mancha,
Since p*q-1==(p-1)*(q-1)+(p-1)+q-1) any prime that divides (p-1) and
(q-1) will divide all 4 of the terms in the definition of p*q-1. Thus
it will be a common factor in the totient.
Hi Paul, many thanks for your reply.
Yes, it's clear any f that divides both (p-1) and (q-1) also divides
(pq-1), (p-1)(q-1), and p-q.
In another email in this thread, I mention one concern regarding having
p-1 and q-1 share a large factor is that searching for a private
exponent d becomes easier as lcm((p-1),(q-1)) decreases. However,
approximations for the distribution of g=gcd((p-1),(q-1)) for randomly
chosen 1024-bit primes p,q estimate P(g=20)=91% and P(g=100)=98% and
that largely allays this concern because it can be expected with high
probability lcm((p-1),(q-1)) and (p-1)(q-1) will be close in size.
That said, I am certainly supportive of your suggestion to use safe
primes, thereby ensuring gcd((p-1),(q-1))=2, as long as it's not overly
costly.
Your concerns appear different, however. Please correct me if I
misunderstood but it seems you require Mallory (who only has access to
{n,e}) discover a factor f common to (p-1) and (q-1). My question was on
the mechanics of how this discovery occurs assuming Mallory is able to
fully factor pq-1 (ie. n-1).
Thanks.
--mancha
I have checked through the key generation code of the openssl ssl
code. I hacked it to report the greatest common divisor of p-1 and
q-1. I then ran 100 key generations. It only had greatest common
divisors of 2, 4 , 8, and 16. There were no other primes reported
besides small powers of 2.
So there doesn't seem to be a practical problem with common divisors
in the openssl code.
Still, I think this is a theoretical problem. There should be a
gcd(p-1,q-1)16 check for the two primes in key generation.
Paul
Quoting mancha manc...@zoho.com:
On Fri, Jul 31, 2015 at 02:36:03AM +, p...@securecottage.com
wrote:
Hi there,
I have looked at the RSA protocol a bit and have concluded that
1) common factors in (p-1) and (q-1) are also in the factorisation
of (p*q-1). 2) by factoring (p*q-1) you can come up with candidates
for squares in the totient. 3) you can also come up with d mod
commonfactor^2 if there is a common factor.
the math is shown in my wikipedia users page math blog at:
https://en.wikipedia.org/wiki/User:Endo999#The_Bad_Stuff_That_Happens_When_There_Are_Common_Factors_Between_.28P-1.29_and_.28Q-1.29
[SNIP]
Hi. How are you finding a common factor f such that f|(p-1) and
f|(q-1)?
Thanks.
--mancha
-- https://twitter.com/mancha140
pgpvdeQxHAgIL.pgp
Description: PGP signature
___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Re: [openssl-dev] common factors in (p-1) and (q-1)
On Sun, Aug 02, 2015 at 12:59:49AM +, p...@securecottage.com wrote: 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 Note, the last factor is not a prime, but producing its prime factors may be non-trivial. Any rsa key generation in SAFE mode will always have a gcd(p-1,q-1)=2, so SAFE mode always avoids common factors. Safe (Sophie Germain) primes are too expensive to generate, if your concerns are warranted, the simpler approach is to reject q when GCD (p-1,q-1) != 2. We can set p = 3 mod 4, to ensure that no higher power of 2 is ever possible. The GCD check will then rarely fail, so the overhead is mostly just the GCD check (much faster than generating safe primes). 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. It is a bit of a leap to claim a leak of 30 bits, because there's no obvious way to know which if any of the prime factors of (n-1) are also shared by (p-1) and (q-1). Also knowing d (e^-1) modulo an ~30 bit number, is not nearly so tidy as knowing 30 bits of d. The key question is whether this information can help speed up GNFS. Speeding up a brute force search through a 1024-bit keyspace by 30 bits is no use at all. I don't know enough about GNFS to comment on whether such residues can actually help speed factoring. Perhaps you are arguing that the GCD check is cheap, and should be done out of an abundance of caution. That might be true, but I'd like to hear that advice from someone well versed in state of the art factorization methods. -- Viktor. ___ openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Re: [openssl-dev] common factors in (p-1) and (q-1)
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
___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
