Fwd: Tor security advisory: DH handshake flaw

[Ben Laurie]

Simon Josefsson wrote:
> Ben Laurie <ben at algroup.co.uk> writes:
> 
> 
>>astiglic at okiok.com wrote:
>>
>>>So Miller-Rabin is good for testing random candidates, but it is easy to
>>>maliciously construct an n that passes several rounds of
>>>Miller-Rabin.  
>>
>>Interesting! So how does one go about constructing such an n?
> 
> 
> I wonder if the original author didn't think of Carmichael numbers,
> which are Fermat pseudoprime in every base.  Some applications,
> e.g. Libgcrypt used by GnuPG, use Fermat tests, so if you have control
> of the random number generator, I believe you could make GnuPG believe
> it has found a prime when it only found a Carmichael number.

Surely the attack of interest is where the attacker provides the prime - 
no control of RNGs is required for this.

> However, for Miller-Rabin, it has been proven that all composite
> numbers pass the test for at most 1/4 of the possible bases.  So as
> long as you do sufficiently many independent tests (different bases,
> preferably chosen at random), I don't see how you could be fooled.
> 
> http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
> 
> Doing the test for more than 1/4 of the bases (which would actually
> prove the number prime, although without a succinct witness) for large
> numbers is too expensive though.
> 
> One algorithm that results in a polynomially verifiable witness is:
> 
> Almost All Primes Can be Quickly Certified
> http://theory.lcs.mit.edu/~cis/pubs/shafi/1986-stoc-gk.pdf

This appears to be a probabilistic certificate, which strikes me as 
rather pointless.

> Btw, I've been playing with prime proving in the past, and if you want
> to specify a format for prime proofs that OpenSSL would understand, I
> would consider supporting the same format in GnuTLS.  Trusting that
> numbers are prime for cryptographic purposes should require a proof.
> There are several prime proof formats, but I can't tell if they are
> practical for this purpose.

I'd be interested in doing this, but first we need to choose a proving 
method!

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