Fwd: Tor security advisory: DH handshake flaw

[Simon Josefsson]

Ben Laurie <ben at algroup.co.uk> writes:

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

Right.  The attack I mentioned was a tangent off the Fermat test.

However, controlling the prime numbers seem to be comparable to
controlling the random number generator.  I.e., you have some access
to the subject's hardware, and want to trick the software into using
crackable parameters for RSA, DH etc.  If the application doesn't use
prime numbers without a proof, neither of these two attacks aren't
possible.  So this is actually a class of attacks.

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

No, the certificate is verifiable in deterministic polynomial time.
The test is probabilistic, though, but as long as it works, I don't
see why that matters.  However, I suspect the ANSI X9.80 or ISO 18032
paths are more promising.  I was just tossing out URLs.

Regards,
Simon

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