Mailing List Archive

Verification of primes in /etc/ssh/moduli file
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
--
Regards,
Hubert Kario
Senior 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

_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Verification of primes in /etc/ssh/moduli file [ In reply to ]
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
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Verification of primes in /etc/ssh/moduli file [ In reply to ]
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
Re: Verification of primes in /etc/ssh/moduli file [ In reply to ]
On Thu, 26 Aug 2021, Demi Marie Obenour wrote:

> On 8/21/21 6:06 AM, Damien Miller wrote:
> >
> > 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.

Yeah, that leads us to the point at which I ended up - you could have
a primality proof for the prime, but have to put up with Miller-Rabin
evidence that it's safe. It didn't seem like a big enough win, given
the ostensible goal was to get away from heuristic methods to begin
with. But like I said, I was limited by my mathematicaly knowledge :)

-d
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Verification of primes in /etc/ssh/moduli file [ In reply to ]
On Thu, 26 Aug 2021, Demi Marie Obenour wrote:

> 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.

I assumed the safety of most libraries in the adversarial model was
fixed a while ago, after https://eprint.iacr.org/2018/749.pdf pointed
out a bunch of flaws. Shame on me for not checking thoroughly...

-d
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Verification of primes in /etc/ssh/moduli file [ In reply to ]
On Saturday, 21 August 2021 12:06:52 CEST, 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).

You generate safe primes by selecting numbers at random, and checking if
they are a safe prime using something like Miller-Rabin test. Repeat until
you
get a safe prime.

You prove the primality of them using Atkin-Goldwasser-Kilian-Morain
certificates (and few others as shortcuts, but Atkin ones do the heavy
lifting).
--
Regards,
Hubert Kario
Senior 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

_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Verification of primes in /etc/ssh/moduli file [ In reply to ]
On Monday, 30 August 2021 06:42:52 CEST, Damien Miller wrote:
> On Thu, 26 Aug 2021, Demi Marie Obenour wrote:
>
>> 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.
>
> I assumed the safety of most libraries in the adversarial model was
> fixed a while ago, after https://eprint.iacr.org/2018/749.pdf pointed
> out a bunch of flaws. Shame on me for not checking thoroughly...

I haven't looked into OpenSSH or libssh, but for TLS the clients generally
_don't_ check if the p is a prime, let alone a safe prime, so it doesn't
really matter if the isPrime() function is hardened or not as it's not used
in
the first place...

(Unless you run in FIPS mode with a recently certified module, then you
can use only few hardcoded primes from rfc3526 or rfc7919)
--
Regards,
Hubert Kario
Senior 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

_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
Re: Verification of primes in /etc/ssh/moduli file [ In reply to ]
On Thu, 2 Sep 2021, Hubert Kario wrote:

> I haven't looked into OpenSSH or libssh, but for TLS the clients generally
> _don't_ check if the p is a prime, let alone a safe prime, so it doesn't
> really matter if the isPrime() function is hardened or not as it's not used
> in the first place...

It doesn't matter in the context of a single connection, where the
endpoints have to trust each other not to divulge session contents or
keys.

But we use BN_is_prime() in the moduli verification tools we ship
for users to verify that we're not shipping out composite numbers.
This is an adversarial use case.

Of course, having actual primality certificates is better.

-d

_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@mindrot.org
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev