Verification of primes in /etc/ssh/moduli file

[Hubert Kario]

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