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

*To*: "'Tero Kivinen'" <kivinen@ssh.fi>*Subject*: RE: MODP groups draft concern*From*: "Walker, Jesse" <jesse.walker@intel.com>*Date*: Tue, 19 Dec 2000 07:26:03 -0800*Cc*: ipsec@lists.tislabs.com*Sender*: owner-ipsec@lists.tislabs.com

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/

**Re: MODP groups draft concern***From*: "Greg Stark" <gstark@ethentica.com>

- Prev by Date:
**Re: Fw: IPSec vs. SSL** - Next by Date:
**Re: Fw: IPSec vs. SSL** - Prev by thread:
**Re: MODP groups draft concern** - Next by thread:
**Re: MODP groups draft concern** - Index(es):