openssh unix dev - Aug 2021 - Verification of primes in /etc/ssh/moduli file

On Wed, 18 Aug 2021, Hubert Kario wrote:
> Hello everybody!
> 
> For the past few years we've used a tool to double-check the security
of
> the primes shipped in the OpenSSH moduli file:
> https://github.com/tomato42/ecpp-verifier
> 
> In short, it uses primality certificates to mathematically prove that all 
> the 
> parameters use safe primes and a bit of simple maths to check if
they're
> not
> vulnerable to Special Number Field Sieve.
> 
> I wrote an article on why it's necessary, a high level overview how it
> does it and how you can run it yourself:
>
https://www.redhat.com/en/blog/understanding-and-verifying-security-diffie-hellman-parameters
Excellent - one question: how do you generate/prove safe primes? I was
never able to figure out how to prove that both N and (N-1)/2 are prime
(though I thought it might be possible using Pocklington's criteria).

-d

On 8/21/21 6:06 AM, Damien Miller wrote:
> On Wed, 18 Aug 2021, Hubert Kario wrote:
> 
>> Hello everybody!
>>
>> For the past few years we've used a tool to double-check the
security of
>> the primes shipped in the OpenSSH moduli file:
>> https://github.com/tomato42/ecpp-verifier
>>
>> In short, it uses primality certificates to mathematically prove that
all
>> the 
>> parameters use safe primes and a bit of simple maths to check if
they're
>> not
>> vulnerable to Special Number Field Sieve.
>>
>> I wrote an article on why it's necessary, a high level overview how
it
>> does it and how you can run it yourself:
>>
https://www.redhat.com/en/blog/understanding-and-verifying-security-diffie-hellman-parameters
> 
> Excellent - one question: how do you generate/prove safe primes? I was
> never able to figure out how to prove that both N and (N-1)/2 are prime
> (though I thought it might be possible using Pocklington's criteria).
One can prove primality using the Miller-Ramin test, which will
detect composites with probability at least 3/4 per round.  After 64
rounds the likelihood of a composite not being detected is not more
than 2????, even for adversarial choices of moduli.  Note that
the primality testing APIs in cryptographic libraries are often not
designed for this, as they perform optimizations that are not valid for
adversarially chosen numbers.

That said, a much simpler approach is to simply regenerate the file;
this avoids all of the above complications.

Sincerely,

Demi
-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_0xB288B55FFF9C22C1.asc
Type: application/pgp-keys
Size: 4874 bytes
Desc: OpenPGP public key
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20210826/03e3abfe/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL:
<http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20210826/03e3abfe/attachment.asc>