[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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/
Follow-Ups: