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? This would suggest that we really do want primality proofs (and a good way to verify them). Do those algorithms hold for creating composites that pass M-R tests for both p and (p-1)/2 ?> I'd be against shipping any primes that are not generated from known, expected > values, like hash of "OpenSSH 1024 bit DH prime, try #1"This is trying to put some sort of NUMS-y ("Nothing Up My Sleeve") constraint on prime generation -- presumably you'd count up from the hash value until you find something that passes M-R for both p and (p-1)/2, right? I observe that the values in ./moduli all seem quite similar in that respect (i.e. the values for any given length share most of the same prefix, and differ only in the trailing bits). Wouldn't primality proofs make this NUMS-y approach less relevant? --dkg
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> This would suggest > that we really do want primality proofs (and a good way to verify them).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> Do those algorithms hold for creating composites that pass M-R tests for > both p and (p-1)/2 ?that I don't know, I'd assume it's much harder, that being said, the A014233 is suspiciously short...> > I'd be against shipping any primes that are not generated from known, > > expected values, like hash of "OpenSSH 1024 bit DH prime, try #1" > > This is trying to put some sort of NUMS-y ("Nothing Up My Sleeve") > constraint on prime generationyes> -- presumably you'd count up from the > hash value until you find something that passes M-R for both p and > (p-1)/2, right?yes, use it as the base for the PRNG to get candidates> I observe that the values in ./moduli all seem quite > similar in that respect (i.e. the values for any given length share most > of the same prefix, and differ only in the trailing bits). > > Wouldn't primality proofs make this NUMS-y approach less relevant?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" -- 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/20150526/427c2768/attachment.bin>
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>