Weak DH primes and openssh

[Daniel Kahn Gillmor]

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>