Verification of primes in /etc/ssh/moduli file

Hubert Kario hkario at
Fri Sep 3 04:41:59 AEST 2021

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:
>> 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:
> 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 
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 
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic

More information about the openssh-unix-dev mailing list