Weak DH primes and openssh

[mancha]

On Wed, May 27, 2015 at 02:55:39AM +0000, mancha wrote:
> On Tue, May 26, 2015 at 03:10:01PM -0400, Daniel Kahn Gillmor wrote:
> > Does anyone have a pointer to any decent free software for
> > generating and verifying primality proofs?
> > 
> >           --dkg
> 
> OpenSSH generates strong pseudoprimes to k random bases (that if prime
> would be "safe primes"). I think Darren uses k=100 (confirmation?) so
> the way the math works out, each number he generates has at most a
> 1/(4^100) probability of being composite.  
> 
> In comparison, it's estimated the odds of getting crushed to death by
> a vending machine are 1 in 112 million.
> 
> Death-by-chocolate-bar is about
> 14,347,661,109,455,270,317,338,947,253,046,094,665,376,812,444,489,221
> more likely to happen to you than having a given "Darren-prime" turn
> out to be composite.
> 
> The take-away, of course, is to always snack responsibly.
> 
> Nonetheless, the most we can currently say is the numbers are almost
> surely prime. Certainty would be nice.
> 
> ECPP is the fastest prime proving algorithm that also provides
> certificates (I think) and PRIMO is the king-of-the-hill
> implementation (others exist but are significantly slower with bigger
> numbers).
> 
> Though as you mentioned PRIMO's not libre (just free), the math in the
> certificates is open-source and that's really the critical part here.
> 
> The proofs themselves are sequences of steps that at each step (except
> the last) prove a number N is prime if a smaller number R is prime.
> Every subsequent step takes its N from the previous step's R and this
> continues until we arrive at an R < 34*10^13 because such an R can be
> proven prime if it is a strong pseudoprime to the base of the 7 primes
> smaller than 19 (i.e. 2, 3, 5, 7, 11, 13, 17)
> 
> TL;DR
> 
> With PRIMO's help, I've proved the first 200 strong pseudoprimes in
> the latest v1.12 moduli file are indeed prime. Darren, so far you're
> batting a thousand!
> 
> I've uploaded my proofs to factordb.com for independent verification
> and complementary confirmation proofs.
> 
> For example, check out the 4th prime in Darren's new moduli file: 
> 
> https://tinyurl.com/pg66aq5
> 
> As I write this I've checked through #209. Those with spare CPU cycles
> on 64-bit Linux can help with the 65 strong pseudoprimes remaining
> (#210 to #274). 
> 
> Those who wish to help should get PRIMO [1] and grab the full set of
> input files I made:
> 
> http://sf.net/projects/mancha/files/misc/openssh-moduli-20150522_primo.tar.bz2
> 
> The 7680-bit moduli (#225 - #248) and 8192-bit moduli (#249 - #274)
> are up for grabs. Probably best if you claim your range to avoid
> effort duplication.
> 
> --mancha
> 
> PS In addition to factordb.com, ecpp-dj [2] can verify PRIMO certs.
> ecpp-dj also proves primality but it is slower than PRIMO and more
> importantly its cert format can't be independently verified.
> 
> ------
> 
> [1] http://www.ellipsa.eu/public/primo/files/primo-411-lx64.7z
> [2] http://sti15.com/nt/ecpp-dj-1.04.tar.gz

I was not as clear in my above postscript as I should have been. What I
meant to say is there aren't independent software implementations that
can verify ecpp-dj generated proofs.  

That said, the certificate format is documented so one can be manually
check ecpp-dj certs by verifying requisite conditions are satisfied for
the math theorems used by its tests.

Time permitting, I plan to dig deeper into this promising program.

--mancha
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.mindrot.org/pipermail/openssh-unix-dev/attachments/20150602/29958413/attachment.bin>