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
Attachment:
signature.asc
Description: PGP signature
_______________________________________________ openssh-unix-dev mailing list openssh-unix-dev@xxxxxxxxxxx https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev