Fwd: Tor security advisory: DH handshake flaw

[astiglic at okiok.com]

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

Carmichael numbers with Fermat's test is a worst case example.  A
Carmichael number will pass Fermat's test for all bases.  So if you give
some one a Carmichael number (which is not a prime), and the person
verifying the primality uses Fermat's test, you are sure to fool him.

For Miller-Rabin, as you mentioned, it can be proven that in worst case,
for a particular n,  there is only 1/4 of bases for which the test will
return "prime" when in fact the candidate is composite.  But what I said
is that you can "maliciously construct an n that passes several rounds of
Miller-Rabin".   In worst case, you can construct a prime that will pass
several rounds of Miller-Rabin, for specific bases.
Of course, if the person testing n uses random bases, the more tests the
person does the greater the chance the person will catch the fact that n
is in fact composite.  But if you knew, in advance, the sequence of
candidates that will be used, than it's a different game.

The Miller true primality test I referred to in my initial post will
always work assuming the Extended Riemann Hypothesis (ERH).  In such a
test, you start with base 2 and test, as long as the test passes increment
by one, up to Poly(size(n)).  I would have no problem believe ERH and
using such an algorithm.  In the worst case, if my code happened to
generate a pseudo-prime, than I would have disproved the ERH hypothesis
and could make allot of money out of that
http://www.claymath.org/millennium/

If at the end all iterations passed, n is surely prime if ERH is true. 
The value of Poly(size(n)) that would need to be used for large n will be
much smaller than 1/4*n, but (the big ick, considering all of the
constants in the actual polynomial that needs to be considered) is still a
very large number.

In any case, go with Maurer's test, it really rocks and has been
standardized.

--Anton


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