Fwd: Tor security advisory: DH handshake flaw

[Ben Laurie]

Jerrold Leichter wrote:
> | Apologies, slightly at cross-purposes here. For a start, Sophie Germain primes
> | are needed for D-H (or rather, safe primes), and secondly, I was talking about
> | proving arbitrary primes, rather than constructing provable primes.
 >
> Isn't *proving* primality rather overkill for the purpose at hand (which seems 
> to be verifying that an alleged prime isn't a non-prime, sent to "spike" the 
> system).  Are there any known sets of numbers - much less ways to *choose* 
> members of those sets - which will show up as prime with significant 
> probability to Miller-Rabin?  As far as I know, M-R has a *worst case* false 
> positive rate of 1/4.  Even a fairly small number of random M-R tests should 
> make slipping in a non-prime less probable than a variety of other attacks.

There aren't any such sets known to me. Can I be sure there are none 
known to anyone? No.

Not sure I agree with the false positive rate. What is known is that 3/4 
of the bases are strong witnesses for a composite number. But is it 
known that these are evenly distributed? I don't know, but that would be 
required for a 1/4 false positive rate.

> If you want to go further, there's the Baille-PSW test 
> (http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html) which it appears 
> has no "false positives" for any integer of less than about 10,000 digits - 
> way beyond what you would likely use in the near future.

Based on a statistical argument from a closed source prover and 
verifier. Hmm.

The point of proofs (at least, useful proofs) is that they produce 
certificates that are cheap to verify. So, yeah, sure it may be 
overkill, but I'll do the killing so you don't have to.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com