[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: MODP groups draft concern

Jesse,

    In practice, one cannot achieve the kind of certainty you propose. All
computations are subject to failure, even if they software itself is
bug-free. How much more common are random bit errors than, say, a composite
surviving 200 iterations of Miller-Rabin.

    I think the only algorithm which can, in reasonable time, prove the
primality of such a large prime is the ECPP algorithm Tero mentioned. It is
very complicated and I would not be surprised to find bugs in any
implementation of it. Miller-Rabin is much simpler. Given the probabilities
at play here, it is only fair to analyze the effect that random bit errors
might have on the comptutations in ECPP. Might such an error at a critical
stage of the ECPP computation lead it to declare a composite prime? Of
course! Why have more faith in an ECPP "proven" prime than a Miller-Rabin
"probable prime". I guess one could retain the ECPP proof forever as a
certificate of primality and subject it to periodic reverification, but I
suspect only Francois Morain, Tero, and a few others could actually do so.

    Is it not conjectured that no composites can survive a small number of
Miller-Rabin tests? Or that none can survive a small number of Miller-Rabin
and Lucas tests?

    The number in question is prime with either probability 1 or probability
0, but proving such a large number is prime may be impossible in this
universe.



Greg Stark, gstark@ethentica.com
Chief Security Architect
Ethentica, Inc.
www.ethentica.com



----- Original Message -----
From: "Walker, Jesse" <jesse.walker@intel.com>
To: "'Tero Kivinen'" <kivinen@ssh.fi>
Cc: <ipsec@lists.tislabs.com>
Sent: Tuesday, December 19, 2000 10:26 AM
Subject: RE: MODP groups draft concern


> Tero:
>
> A probability like 1/4^200 always impresses people but misses the point.
> There is a class of composite integers for which Miller-Rabin always gives
> the wrong answer, for any and all bases we try. To be acceptable for our
> application, I think we would want to verify that the candidate does not
> belong to this class before accepting the probability as reliably
indicating
> that it has the security properties we desire.
>
> And I don't buy the argument that since this kind of probability is good
> enough for RSA, it must be good enough for the modulus of a standardized
> Diffie-Hellman group. We expect Miller-Rabin to fail very rarely, but if
it
> does for an RSA prime, so what? Presumably only one principal uses that
> "prime" to generate its public/private key pair, and presumably it will
> replace its keys soon enough anyway, at key expiry. In our case, however,
we
> are trying to define a standardized Diffie-Hellman value that is good for
> all time; if we subsequently discover Miller-Rabin failed, there will be
> hundreds of thousands or millions of implementations relying on this
value.
> The reach of a failure is potentially much more catostraphic in our case
> than for RSA. We can compromise everyone's security by failing to do our
> homework, whereas a Miller-Rabin failure wouldn't necessarily be as bad in
> the RSA case.
>
> I don't know a good characterization of Miller-Rabin pusedo-primes, but
> since Miller-Rabin is strictly stronger than the Fermat primality test,
> every value that fails Miller-Rabin must fail Fermat as well and therefore
> must be a Carmichael number. Let p denote the 8K candidate prime. Since
> every Carmichael number is the product of at least three distinct primes,
it
> seem like we could get a much warmer feeling that the 8K value is actually
> prime by doing trial by division for primes up to the cube root of p
(ditto
> for q, where p = 2q + 1). Is computing all 8192/3 = 2731 bit primes within
> reach? Or does someone know an eaiser way to check that the candidate is
not
> a Miller-Rabin pseudo-prime?
>
> -- Jesse
>
> -----Original Message-----
> From: Tero Kivinen [mailto:kivinen@ssh.fi]
> Sent: Monday, December 18, 2000 7:39 AM
> To: Walker, Jesse
> Cc: ipsec@lists.tislabs.com
> Subject: MODP groups draft concern
>
>
> Walker, Jesse writes:
> > This e-mail asks whether it is appropriate at this time to include the
> > suggested 8192-bit MODP group in the draft. If I correctly understood
your
> > presentation at the San Diego IPsec meeting, not only do we not know
> whether
> > the proposed 8192-bit modulus is a Sophie-Germain prime, but we don't
even
> > know if it is prime. If this is true, then we aren't at all certain of
its
> > security properties, so don't know whether it meets its design goal of
> > providing the level of security suggested as necessary for AES-192.
> > Probabalistic assurances are something we have never agreed to before
for
> > well-known IKE groups. In the past our standard has been the modulus for
> any
> > well-known group must be a verified Sophie-Germaine prime. This criteria
> has
> > served us well for every well-known group to date. Why abandon it now?
>
> Because I haven't had enough time to check the prime. My search
> program searches the primes by using Miller-Rabin test with limit 200.
> This gives the information that number is not prime the propability of
> 1/4^200 ==
>
1/25822498780869085896559191720030118743297057928292235128306593565406476220
> 16841194629645353280137831435903171972747493376.
>
> I agree, that might not be enough for some people to use the group,
> but those should verify all the groups given in the draft themselfs
> anyways, and not to trust somebody else to verify the groups for them.
>
> You should also remember that almost all RSA key pairs are generated
> by using the propabilistic primes. Also when generating those primes
> the limit is normally used only up to 20 or so... So it is much more
> likely that your RSA key pair is weak than this group being weak.
> Anyways I will try to run the tests on it if I just have enough cpu to
> do it.
>
> > I can think of at least three plausible ways forward:
> >
> > a. The IPsec community could dedicate resources to help verify that the
> > value is indeed a Sophie-Germain prime (assuming it is). In the
> eventuality
> > of a successful verification, it would be appropriate for the value to
> > remain in the draft. Many would see this as the most desirable outcome,
> > because we would possess a value anyone could use, safe in the knowledge
> > that it actually provides the level of security we hope it does.
>
> If you have spare alpha machine available, just go to
>
> http://ultralix.polytechnique.fr/~morain/Prgms/ecpp.english.html
>
> and fetch the ECPP program we have been using. The only problem is
> that it is only available for the alpha machines, thus limiting the
> number of machines that can run it. Also running it can take lots of
> time...
>
> > It is not obvious to me that the need for an 8K or larger group is
> > sufficiently urgent to abandon our long standing criteria. Let the
> > verification algorithm crank a few months or years or however long is
> > necessary to tell us whether the value has the right properties we need
> for
> > security. We can standardize a new 8K group whenever this completes with
a
> > verified Sophie-Germain prime, or generates a Schnorr group, or whatever
> we
> > define as safe. Until then, let's not tell the world this value is OK to
> use
> > by including it in the draft, because we just don't know.
>
> I am going to leave it in the draft for now on, but if I don't have
> the verification for it when we are going to RFC, then I will consider
> things more. I might end up having two RFC, one with the proven groups
> and second with those checked only using propabilistic methods.
> --
> kivinen@ssh.fi                               Work : +358 303 9870
> SSH Communications Security                  http://www.ssh.fi/
> SSH IPSEC Toolkit                            http://www.ssh.fi/ipsec/
>
>
References: