Fwd: Tor security advisory: DH handshake flaw

[Simon Josefsson]

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.

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

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.

Regards,
Simon

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