On Tue 2015-05-26 14:02:07 -0400, Hubert Kario wrote:> On Tuesday 26 May 2015 13:43:13 Daniel Kahn Gillmor wrote: >> On Tue 2015-05-26 12:57:05 -0400, Hubert Kario wrote: >> > creating composites that will pass even 100000 rounds of Miller-Rabin is >> > relatively simple.... >> > (assuming the values for M-R tests are picked randomly) >> >> Can you point me to the algorithms for doing that? > > OEIS A014233Hm, this is a sequence, but not an algorithm. It looks to me like it is not exhaustive, just a list of those integers which are known to have the stated property ("Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness"). Taking the final integer in that sequence (a(11)) fails even the default 25-round M-R test in gmp:>>> k = gmpy2.mpz(3825123056546413051) >>> gmpy2.is_prime(k)False>>>Indeed, the arxiv suggests that in 2012 people were still writing proofs about a(11) for this sequence: http://arxiv.org/abs/1207.0063 but i see no evidence that an algorithm for generating a(n) where n is arbitrarily large exists. Does such a thing exist?> yes, using ECPP and distributing proof with the prime (or just placing it on > the project website) is a reasonable minimum, that still leaves out the > possibility of a backdoor if the initial seed value is randomit sounds like we're heading into the same territory as the ECDH curve selection discussion -- the theory you're suggesting is that some safe-prime moduli could themselves have a backdoor that we don't know about. Am i understanding you correctly? I've been talking with several cryptographers for the last year about finite-field DH (FFDH) and i haven't heard any suggestion that any of them think there is likely to be such a class of backdoored moduli.> yes, it would basically exclude the chance that the primes are backdoored, > there's still the chance for the values to be composites > > for values to be used on this many machines, I'd say we should have primality > proofs, not just M-R "guess"Does anyone have a pointer to any decent free software for generating and verifying primality proofs? --dkg -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 948 bytes Desc: not available URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150526/467bdc1f/attachment.bin>
On May 26 15:10-0400, Daniel Kahn Gillmor wrote:> On Tue 2015-05-26 14:02:07 -0400, Hubert Kario wrote: > > On Tuesday 26 May 2015 13:43:13 Daniel Kahn Gillmor wrote:<snip>> I've been talking with several cryptographers for the last year about > finite-field DH (FFDH) and i haven't heard any suggestion that any of > them think there is likely to be such a class of backdoored moduli. > > > yes, it would basically exclude the chance that the primes are backdoored, > > there's still the chance for the values to be composites > > > > for values to be used on this many machines, I'd say we should have primality > > proofs, not just M-R "guess" > > Does anyone have a pointer to any decent free software for generating > and verifying primality proofs? > > --dkgI am currently running Debian's /etc/ssh/moduli (not sure if it is the same as distributed with openssh) through ecpp-dj . I found the code at http://www.mersenneforum.org/showthread.php?t=18283 (there is a 1.04 version in the download directory), I think he just split it out from his perl module at https://github.com/danaj/Math-Prime-Util-GMP . It is single-threaded, and I'm not sure how well it does with larger primes (at 1000 decimal digits (~3325 bits, if my math skills haven't failed me), his benchmarks show it took 10x as long as primo on the prime he chose). So far, it is running at 15-60 seconds ea for 1535-bit primes on my old i7 950 @ 3.07GHz, not sure how it will do with the larger ones. I'll probably need to move this to a cluster to have it complete in a reasonable amount of time. -- Eldon Koyle -- A fail-safe circuit will destroy others. -- Klipstein
On Tue, May 26, 2015 at 03:10:01PM -0400, Daniel Kahn Gillmor wrote:> Does anyone have a pointer to any decent free software for generating > and verifying primality proofs? > > --dkgOpenSSH generates strong pseudoprimes to k random bases (that if prime would be "safe primes"). I think Darren uses k=100 (confirmation?) so the way the math works out, each number he generates has at most a 1/(4^100) probability of being composite. In comparison, it's estimated the odds of getting crushed to death by a vending machine are 1 in 112 million. Death-by-chocolate-bar is about 14,347,661,109,455,270,317,338,947,253,046,094,665,376,812,444,489,221 more likely to happen to you than having a given "Darren-prime" turn out to be composite. The take-away, of course, is to always snack responsibly. Nonetheless, the most we can currently say is the numbers are almost surely prime. Certainty would be nice. ECPP is the fastest prime proving algorithm that also provides certificates (I think) and PRIMO is the king-of-the-hill implementation (others exist but are significantly slower with bigger numbers). Though as you mentioned PRIMO's not libre (just free), the math in the certificates is open-source and that's really the critical part here. The proofs themselves are sequences of steps that at each step (except the last) prove a number N is prime if a smaller number R is prime. Every subsequent step takes its N from the previous step's R and this continues until we arrive at an R < 34*10^13 because such an R can be proven prime if it is a strong pseudoprime to the base of the 7 primes smaller than 19 (i.e. 2, 3, 5, 7, 11, 13, 17) TL;DR With PRIMO's help, I've proved the first 200 strong pseudoprimes in the latest v1.12 moduli file are indeed prime. Darren, so far you're batting a thousand! I've uploaded my proofs to factordb.com for independent verification and complementary confirmation proofs. For example, check out the 4th prime in Darren's new moduli file: https://tinyurl.com/pg66aq5 As I write this I've checked through #209. Those with spare CPU cycles on 64-bit Linux can help with the 65 strong pseudoprimes remaining (#210 to #274). Those who wish to help should get PRIMO [1] and grab the full set of input files I made: http://sf.net/projects/mancha/files/misc/openssh-moduli-20150522_primo.tar.bz2 The 7680-bit moduli (#225 - #248) and 8192-bit moduli (#249 - #274) are up for grabs. Probably best if you claim your range to avoid effort duplication. --mancha PS In addition to factordb.com, ecpp-dj [2] can verify PRIMO certs. ecpp-dj also proves primality but it is slower than PRIMO and more importantly its cert format can't be independently verified. ------ [1] http://www.ellipsa.eu/public/primo/files/primo-411-lx64.7z [2] http://sti15.com/nt/ecpp-dj-1.04.tar.gz -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 819 bytes Desc: not available URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150527/2b0d51e4/attachment.bin>
On Wed, May 27, 2015 at 12:55 PM, mancha <mancha1 at zoho.com> wrote:> I think Darren uses k=100 (confirmation?)Yes. I use all of the default settings to ssh-keygen and the default for number of rounds is 100. The exact commands used for the single threaded version are here: http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/usr.bin/ssh/moduli-gen/ As previously mentioned I have a wrapper script to split up work over multiple processors but it only adds -J/-j flags for "start here" and "process this many" which I run over multiple machines. I will tidy up this script and publish that too when I get a chance. Once I have the complete list assembled I re-screen it on OpenBSD and make sure the output agrees (other than the timestamp). I would be happy to add a verification by an independent software implementation (for practical purposes it'd probably need to be free-as-in-speech; it sounds like ecpp-dj might be a candidate). -- Darren Tucker (dtucker at zip.com.au) GPG key 8FF4FA69 / D9A3 86E9 7EEE AF4B B2D4 37C9 C982 80C7 8FF4 FA69 Good judgement comes with experience. Unfortunately, the experience usually comes from bad judgement.
On Tuesday 26 May 2015 15:10:01 Daniel Kahn Gillmor wrote:> On Tue 2015-05-26 14:02:07 -0400, Hubert Kario wrote: > > On Tuesday 26 May 2015 13:43:13 Daniel Kahn Gillmor wrote: > >> On Tue 2015-05-26 12:57:05 -0400, Hubert Kario wrote: > >> > creating composites that will pass even 100000 rounds of Miller-Rabin > >> > is > >> > relatively simple.... > >> > (assuming the values for M-R tests are picked randomly) > >> > >> Can you point me to the algorithms for doing that? > > > > OEIS A014233 > > Hm, this is a sequence, but not an algorithm. It looks to me like it is > not exhaustive, just a list of those integers which are known to have > the stated property ("Smallest odd number for which Miller-Rabin > primality test on bases <= n-th prime does not reveal compositeness"). > > Taking the final integer in that sequence (a(11)) fails even the default > > 25-round M-R test in gmp: > >>> k = gmpy2.mpz(3825123056546413051) > >>> gmpy2.is_prime(k) > > FalseI'm quite sure that this means that gmpy doesn't use pure M-R with randomly selected witnesses.> Indeed, the arxiv suggests that in 2012 people were still writing proofs > about a(11) for this sequence: > > http://arxiv.org/abs/1207.0063 > > but i see no evidence that an algorithm for generating a(n) where n is > arbitrarily large exists. Does such a thing exist?As far as I know, the most computationally efficient algorithm is basically going over every non trivially composite number and checking all witnesses point is that this is a proof that such numbers exists, it also shows that the resistance to witnesses is not probabilistically independent.> > yes, using ECPP and distributing proof with the prime (or just placing it > > on the project website) is a reasonable minimum, that still leaves out > > the possibility of a backdoor if the initial seed value is random > > it sounds like we're heading into the same territory as the ECDH curve > selection discussion -- the theory you're suggesting is that some > safe-prime moduli could themselves have a backdoor that we don't know > about. Am i understanding you correctly?yes, it's so that they are "rigid" in ECC nomenclature> I've been talking with several cryptographers for the last year about > finite-field DH (FFDH) and i haven't heard any suggestion that any of > them think there is likely to be such a class of backdoored moduli.Hmm, I have a distinct recollection of reading of a possibility of a small subgroup attacks on primes (as in very few primes have this property, so randomly selected one are almost certainly not problematic, but if you can pick any prime, you can find them) Maybe what they mean is that this may does not apply to Sophie Germain primes, but to "DSA style" primes, I haven't dug too deep into this. Creating it pseudo-randomly from nothing up my sleeve numbers fixes this issue anyway. -- Regards, Hubert Kario Quality Engineer, QE BaseOS Security team Web: www.cz.redhat.com Red Hat Czech s.r.o., Purky?ova 99/71, 612 45, Brno, Czech Republic -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 819 bytes Desc: This is a digitally signed message part. URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150527/1f6a3a76/attachment.bin>
If the primality test is such a problem, one could implement a variant to the AKS polynomial time primality test: https://en.wikipedia.org/wiki/AKS_primality_test https://math.dartmouth.edu/~carlp/aks041411.pdf This test (and variants) are not statistical. I have no idea if they work in reasonable time on 1024-4096bits prime candidates. Aris Le 27/05/15 04:55, mancha a ?crit :> On Tue, May 26, 2015 at 03:10:01PM -0400, Daniel Kahn Gillmor wrote: >> Does anyone have a pointer to any decent free software for generating >> and verifying primality proofs? >> >> --dkg > > OpenSSH generates strong pseudoprimes to k random bases (that if prime > would be "safe primes"). I think Darren uses k=100 (confirmation?) so > the way the math works out, each number he generates has at most a > 1/(4^100) probability of being composite. > > In comparison, it's estimated the odds of getting crushed to death by a > vending machine are 1 in 112 million. > > Death-by-chocolate-bar is about > 14,347,661,109,455,270,317,338,947,253,046,094,665,376,812,444,489,221 > more likely to happen to you than having a given "Darren-prime" turn out > to be composite. > > The take-away, of course, is to always snack responsibly. > > Nonetheless, the most we can currently say is the numbers are almost > surely prime. Certainty would be nice. > > ECPP is the fastest prime proving algorithm that also provides > certificates (I think) and PRIMO is the king-of-the-hill implementation > (others exist but are significantly slower with bigger numbers). > > Though as you mentioned PRIMO's not libre (just free), the math in the > certificates is open-source and that's really the critical part here. > > The proofs themselves are sequences of steps that at each step (except > the last) prove a number N is prime if a smaller number R is prime. > Every subsequent step takes its N from the previous step's R and this > continues until we arrive at an R < 34*10^13 because such an R can be > proven prime if it is a strong pseudoprime to the base of the 7 primes > smaller than 19 (i.e. 2, 3, 5, 7, 11, 13, 17) > > TL;DR > > With PRIMO's help, I've proved the first 200 strong pseudoprimes in > the latest v1.12 moduli file are indeed prime. Darren, so far you're > batting a thousand! > > I've uploaded my proofs to factordb.com for independent verification > and complementary confirmation proofs. > > For example, check out the 4th prime in Darren's new moduli file: > > https://tinyurl.com/pg66aq5 > > As I write this I've checked through #209. Those with spare CPU cycles > on 64-bit Linux can help with the 65 strong pseudoprimes remaining > (#210 to #274). > > Those who wish to help should get PRIMO [1] and grab the full set of > input files I made: > >http://sf.net/projects/mancha/files/misc/openssh-moduli-20150522_primo.tar.bz2> > The 7680-bit moduli (#225 - #248) and 8192-bit moduli (#249 - #274) are > up for grabs. Probably best if you claim your range to avoid effort > duplication. > > --mancha > > PS In addition to factordb.com, ecpp-dj [2] can verify PRIMO certs. > ecpp-dj also proves primality but it is slower than PRIMO and more > importantly its cert format can't be independently verified. > > ------ > > [1] http://www.ellipsa.eu/public/primo/files/primo-411-lx64.7z > [2] http://sti15.com/nt/ecpp-dj-1.04.tar.gz > > > _______________________________________________ > openssh-unix-dev mailing list > openssh-unix-dev at mindrot.org > https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
On Wed 2015-05-27 05:23:41 -0400, Hubert Kario wrote:> On Tuesday 26 May 2015 15:10:01 Daniel Kahn Gillmor wrote: >> On Tue 2015-05-26 14:02:07 -0400, Hubert Kario wrote: >> > OEIS A014233 >> >> Hm, this is a sequence, but not an algorithm. It looks to me like it is >> not exhaustive, just a list of those integers which are known to have >> the stated property ("Smallest odd number for which Miller-Rabin >> primality test on bases <= n-th prime does not reveal compositeness"). >> >> Taking the final integer in that sequence (a(11)) fails even the default >> >> 25-round M-R test in gmp: >> >>> k = gmpy2.mpz(3825123056546413051) >> >>> gmpy2.is_prime(k) >> >> False > > I'm quite sure that this means that gmpy doesn't use pure M-R with randomly > selected witnesses.https://gmplib.org/manual/Prime-Testing-Algorithm.html#Prime-Testing-Algorithm suggests is chooses a random base, but it also runs some non-M-R tests before executing M-R: http://sources.debian.net/src/gmp/2:6.0.0%2Bdfsg-6/mpz/pprime_p.c/ GMP's M-R tests are using randomly selected witnesses, though: http://sources.debian.net/src/gmp/2:6.0.0%2Bdfsg-6/mpz/millerrabin.c/#L92> Hmm, I have a distinct recollection of reading of a possibility of a > small subgroup attacks on primes (as in very few primes have this > property, so randomly selected one are almost certainly not > problematic, but if you can pick any prime, you can find them) > > Maybe what they mean is that this may does not apply to Sophie Germain > primes, but to "DSA style" primes, I haven't dug too deep into > this. Creating it pseudo-randomly from nothing up my sleeve numbers > fixes this issue anyway.I think you mean "safe primes" where you say "Sophie Germain primes" -- if q = (p-1)/2, and p and q are primes, then p is a "safe prime" and q is a "Sophie Germain prime". Small subgroup attacks are not possible for safe primes as long as you test your peer's public share and the generator to ensure that they are in the range (exclusive) 1 < x < p-1. This is because totient(p) = p-1 (because p is prime), and p-1 has only two factors: 2 and q. So there exists one small subgroup, but it's of order 2, and its generator is p-1 (the subgroup cycles between p-1 and 1). All other elements are generators of order either q or p-1. There are no other subgroups, iiuc. If this is the only attack you're trying to address, and you've already limited yourself to safe primes, then NUMS properties don't really add anything. The NUMS approach is there are to try to avoid the possibility of other, unknown cryptanalytic attacks against some infrequent type of group, so that the entity who defines the group can't force you into this secret corner case if they have special knowledge. --dkg
On 27/05/15 04:55, mancha wrote:> As I write this I've checked through #209. Those with spare CPU cycles > on 64-bit Linux can help with the 65 strong pseudoprimes remaining > (#210 to #274). > > Those who wish to help should get PRIMO [1] and grab the full set of > input files I made: > > http://sf.net/projects/mancha/files/misc/openssh-moduli-20150522_primo.tar.bz2 > > The 7680-bit moduli (#225 - #248) and 8192-bit moduli (#249 - #274) are > up for grabs. Probably best if you claim your range to avoid effort > duplication./me claims 237 - 248
On Wed, May 27, 2015 at 02:55:39AM +0000, mancha wrote:> On Tue, May 26, 2015 at 03:10:01PM -0400, Daniel Kahn Gillmor wrote: > > Does anyone have a pointer to any decent free software for > > generating and verifying primality proofs? > > > > --dkg > > OpenSSH generates strong pseudoprimes to k random bases (that if prime > would be "safe primes"). I think Darren uses k=100 (confirmation?) so > the way the math works out, each number he generates has at most a > 1/(4^100) probability of being composite. > > In comparison, it's estimated the odds of getting crushed to death by > a vending machine are 1 in 112 million. > > Death-by-chocolate-bar is about > 14,347,661,109,455,270,317,338,947,253,046,094,665,376,812,444,489,221 > more likely to happen to you than having a given "Darren-prime" turn > out to be composite. > > The take-away, of course, is to always snack responsibly. > > Nonetheless, the most we can currently say is the numbers are almost > surely prime. Certainty would be nice. > > ECPP is the fastest prime proving algorithm that also provides > certificates (I think) and PRIMO is the king-of-the-hill > implementation (others exist but are significantly slower with bigger > numbers). > > Though as you mentioned PRIMO's not libre (just free), the math in the > certificates is open-source and that's really the critical part here. > > The proofs themselves are sequences of steps that at each step (except > the last) prove a number N is prime if a smaller number R is prime. > Every subsequent step takes its N from the previous step's R and this > continues until we arrive at an R < 34*10^13 because such an R can be > proven prime if it is a strong pseudoprime to the base of the 7 primes > smaller than 19 (i.e. 2, 3, 5, 7, 11, 13, 17) > > TL;DR > > With PRIMO's help, I've proved the first 200 strong pseudoprimes in > the latest v1.12 moduli file are indeed prime. Darren, so far you're > batting a thousand! > > I've uploaded my proofs to factordb.com for independent verification > and complementary confirmation proofs. > > For example, check out the 4th prime in Darren's new moduli file: > > https://tinyurl.com/pg66aq5 > > As I write this I've checked through #209. Those with spare CPU cycles > on 64-bit Linux can help with the 65 strong pseudoprimes remaining > (#210 to #274). > > Those who wish to help should get PRIMO [1] and grab the full set of > input files I made: > > http://sf.net/projects/mancha/files/misc/openssh-moduli-20150522_primo.tar.bz2 > > The 7680-bit moduli (#225 - #248) and 8192-bit moduli (#249 - #274) > are up for grabs. Probably best if you claim your range to avoid > effort duplication. > > --mancha > > PS In addition to factordb.com, ecpp-dj [2] can verify PRIMO certs. > ecpp-dj also proves primality but it is slower than PRIMO and more > importantly its cert format can't be independently verified. > > ------ > > [1] http://www.ellipsa.eu/public/primo/files/primo-411-lx64.7z > [2] http://sti15.com/nt/ecpp-dj-1.04.tar.gzI was not as clear in my above postscript as I should have been. What I meant to say is there aren't independent software implementations that can verify ecpp-dj generated proofs. That said, the certificate format is documented so one can be manually check ecpp-dj certs by verifying requisite conditions are satisfied for the math theorems used by its tests. Time permitting, I plan to dig deeper into this promising program. --mancha -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 819 bytes Desc: not available URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150602/29958413/attachment.bin>