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