On Fri 2015-05-22 00:06:29 -0400, Darren Tucker wrote:> On Thu, May 21, 2015 at 11:26 PM, Matthew Vernon <matthew at debian.org> wrote: >> >> You will be aware of https://weakdh.org/ by now, I presume; the >> take-home seems to be that 1024-bit DH primes might well be too weak. >> I'm wondering what (if anything!) you propose to do about this issue, >> and what Debian might do for our users? > > Would you (and any other vendors) consider generating your own moduli file > for your distribution? If a few vendors did that it'd increase the > diversity quite a lot and it'd stop us (well, specifically me) being the > point of failure for not making updates.(thanks for making the recent moduli update, Darren!) This is an interesting proposal as a way to increase group diversity, but it also creates a non-obvious fingerprinting channel. That is, distro-specific groups would provide a way that someone scanning to find out what distro is in use can make a more accurate guess based on the primes offered. I grant that debian's current patches that add the debian revision themselves provide a fingerprinting mechanism, but those can be disabled on Debian with "DebianBanner no" in sshd_config. We'd want to make sure that distro-specific moduli don't re-introduce fingerprinting for operators who want to hide their choice of distro. --dkg PS Darren, has there been any attempt at generating primality proofs for the values in ./moduli, as opposed to 100 rounds of Miller-Rabin? It would be a shame for a pseudoprime to slip in, however unlikely that would be.
On Fri, 22 May 2015, Daniel Kahn Gillmor wrote:> PS Darren, has there been any attempt at generating primality proofs for > the values in ./moduli, as opposed to 100 rounds of Miller-Rabin? It > would be a shame for a pseudoprime to slip in, however unlikely that > would be.I looked at it a few years ago, but couldn't figure out a way to generate provable safe primes. I'd love someone to get this working. AFAIK the number of Miller-Rabin tests we do is many times more than OpenSSL's baseline BN_is_prime() false positive rate of 2^-80. -d
On Sat 2015-05-23 06:16:04 -0400, Damien Miller wrote:> On Fri, 22 May 2015, Daniel Kahn Gillmor wrote: > >> PS Darren, has there been any attempt at generating primality proofs for >> the values in ./moduli, as opposed to 100 rounds of Miller-Rabin? It >> would be a shame for a pseudoprime to slip in, however unlikely that >> would be. > > I looked at it a few years ago, but couldn't figure out a way to > generate provable safe primes. I'd love someone to get this working.I've generated primality proofs for comparably large primes (and safe primes, at that) with Primo [0] for my work on TLS [1], but Primo is not free software; the proofs are complex to read and parse (and i know of no software other than Primo to verify them directly at the moment, which makes it a bit of a circular argument); and it takes quite a bit of compute power to produce them, especially for larger primes. I have not run Primo against any of the moduli shipped with OpenSSH.> AFAIK the number of Miller-Rabin tests we do is many times more than > OpenSSL's baseline BN_is_prime() false positive rate of 2^-80.Yep, but then we're all just relying on your (or Darren's) claims of Miller-Rabin tests, i guess. I trust you guys, but as Darren points out, it's a drag to have to be a single point of failure on something like this where corroboration would be better. In that spirit, i've just tested the moduli (both the 2012 versions and the recent update), using gmp's mpz_probab_prime_p() [2] with 400 rounds of randomized Miller-Rabin [3] on each modulus p and on q=(p-1)/2. the test is pretty straightforward in python, if anyone else wants to try an independent verification (make sure you've got the gmpy2 python module installed): ------------------- #!/usr/bin/python import gmpy2 f = open('/etc/ssh/moduli') for r in f: if len(r) == 0 or r[0] == '#': continue p = gmpy2.mpz('0x' + r.split(' ')[6]) q = (p-1)//2 if 2*q+1 != p: print("something is terribly wrong with", p) continue if gmpy2.is_prime(p, 400): if gmpy2.is_prime(q, 400): print('OK') else: print("q is bad for", z) else: print("p is bad for", z) -------------------- It should print out nothing but "OK"s, one for each line, though it may take several hours, depending on the speed of your CPU (someone who wants to parallelize the above code shouldn't have a hard time doing so, which would speed it up a lot on a multi-core machine). It produced all "OKs" for me :) Regards, --dkg [0] http://www.ellipsa.eu/public/primo/primo.html [1] https://dkg.fifthhorseman.net/ffdhe-primality-proofs/ [2] https://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions [3] https://gmplib.org/manual/Prime-Testing-Algorithm.html#Prime-Testing-Algorithm -------------- 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/20150524/d22a75a1/attachment.bin>
On Friday 22 May 2015 16:22:13 Daniel Kahn Gillmor wrote:> On Fri 2015-05-22 00:06:29 -0400, Darren Tucker wrote: > > On Thu, May 21, 2015 at 11:26 PM, Matthew Vernon <matthew at debian.org>wrote:> >> You will be aware of https://weakdh.org/ by now, I presume; the > >> take-home seems to be that 1024-bit DH primes might well be too weak. > >> I'm wondering what (if anything!) you propose to do about this issue, > >> and what Debian might do for our users? > > > > Would you (and any other vendors) consider generating your own moduli file > > for your distribution? If a few vendors did that it'd increase the > > diversity quite a lot and it'd stop us (well, specifically me) being the > > point of failure for not making updates. > > (thanks for making the recent moduli update, Darren!) > > This is an interesting proposal as a way to increase group diversity, > but it also creates a non-obvious fingerprinting channel. That is, > distro-specific groups would provide a way that someone scanning to find > out what distro is in use can make a more accurate guess based on the > primes offered. > > I grant that debian's current patches that add the debian revision > themselves provide a fingerprinting mechanism, but those can be disabled > on Debian with "DebianBanner no" in sshd_config. We'd want to make sure > that distro-specific moduli don't re-introduce fingerprinting for > operators who want to hide their choice of distro. > > --dkg > > PS Darren, has there been any attempt at generating primality proofs for > the values in ./moduli, as opposed to 100 rounds of Miller-Rabin? It > would be a shame for a pseudoprime to slip in, however unlikely that > would be.creating composites that will pass even 100000 rounds of Miller-Rabin is relatively simple.... (assuming the values for M-R tests are picked randomly) 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" -- 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/3f9030d4/attachment.bin>
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