Subject: RE: IPS security draft: SRP groups

From: [email-masked]
Date: Thu, 11 Jul 2002 20:07:53 -0600

Hi David,
I can't prove so, but Mathematica from Wolfram certifies as prime (in a matter seconds) all five moduli specified in the iSCSI security draft for use in SRP! I used the PrimeQ built-in function. PrimeQ first tests for divisibility using small primes, then uses the MillerRabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test. I have not explored the nature of these tests.
Vince

|-----Original Message-----
|From: [email-masked] [mailto:[email-masked]]
|Sent: Monday, July 08, 2002 7:34 AM
|To: [email-masked]
|Cc: [email-masked]
|Subject: RE: IPS security draft: SRP groups
|
|
|MANY THANKS -- Tom's earned his promised 30
|minutes of fame ... although those 30 minutes may come at
|the ipr BOF in Yokohama on Friday :-) :-).  
|
|For the security draft, specifying one of the acceptable
|generators from Tom's lists for each of the IKE groups and
|noting that the primes from the SRP distribution were
|probabilistically generated should be sufficient ...
|but there's still 30 minute of fame available for someone
|who tackles proving that the SRP primes are prime, as there
|is significant IETF interest in SRP outside of iSCSI - any takers?
|
|Thanks,  --David
|
|> -----Original Message-----
|> From: Tom Wu [mailto:[email-masked]]
|> Sent: Monday, July 08, 2002 12:23 AM
|> To: [email-masked]
|> Cc: [email-masked]
|> Subject: Re: IPS security draft: SRP groups
|> 
|> 
|> David,
|> 
|> I'll tackle the SRP generator issue:
|> 
|> For the Oakley Group 2 (1024 bit prime) defined in RFC2412:
|> Primitive roots (acceptable as SRP generators):
|> 5,11,13,19,29,31
|> Subgroup generators (NOT acceptable):
|> 2,3,7,17,23
|> 
|> (MODP moduli taken from draft-ietf-ipsec-ike-modp-groups-04.txt)
|> For the 1536-bit MODP group:
|> Acceptable generators:
|> 31
|> NOT acceptable generators:
|> 2,3,5,7,11,13,17,19,23,29
|> 
|> For the 2048-bit MODP group:
|> Acceptable generators:
|> 11,13,17,23,29,31
|> NOT acceptable generators:
|> 2,3,5,7,19
|> 
|> For the 3072-bit MODP group:
|> Acceptable generators:
|> 5,7,17,23,31
|> NOT acceptable generators:
|> 2,3,11,13,19,29
|> 
|> For the 4096-bit MODP group:
|> Acceptable generators:
|> 5,13,29,31
|> NOT acceptable generators:
|> 2,3,7,11,17,19,23
|> 
|> For the 6144-bit MODP group:
|> Acceptable generators:
|> 5,11,13,17,23,29
|> NOT acceptable generators:
|> 2,3,7,19,31
|> 
|> For the 8192-bit MODP group:
|> Acceptable generators:
|> 19,23,29,31
|> NOT acceptable generators:
|> 2,3,5,7,11,13,17
|> 
|> All the above generators are in base 10 (decimal).
|> 
|> As far as proving the primality of the SRP moduli, that 
|> should be done 
|> by someone with more expertise in the area.  I should point out that 
|> those moduli are also "safe primes", i.e. both N and (N-1)/2 
|> are prime, 
|> so it is easy to find generators for them, and I chose 
|> numbers that had 
|> 2 as safe SRP generators.
|> 
|> Tom
|> 
|> [email-masked] wrote:
|> > Missed this earlier, sorry ...
|> > 
|> > 
|> >>Ok.  I didn't know that but I probably would have learned 
|> it if I had
|> >>done the necessary reading about groups and generators.  
|> But the point
|> >>of my question wasn't "is it possible to compute g" but rather "how
|> >>about supplying g in the spec" (since the g=2 from IKE is not
|> >>appropriate).   It seems a bit redundant for everyone to repeat the
|> >>search for a suitable g...
|> >>
|> >>So what's the story about unlisted groups?  Is an 
|> implementation that
|> >>accepts only the groups listed in appendix A, but not any "locally
|> >>generated" ones, a compliant implementation?
|> >>
|> > 
|> > Yes - accepting those groups and only those groups is the minimum
|> > (MUST) requirement.  If the IKE groups are to remain allowed, we
|> > need to specify generators for their use with SRP - please consider
|> > this to be a serious *PLEA* for someone to volunteer to do the
|> > crpto-theoretic number crunching needed to find SRP generators for
|> > those groups and/or prove the primality of the SRP primes.  Lack of
|> > progress here has the potential to hold up the security draft on
|> > which *all* of our protocol drafts depend (normative references).
|> > We can promise at least 30 minutes of fame (*twice* the proverbial
|> > 15 ;-) ) to those who resolve this issue ...
|> > 
|> > Thanks,
|> > --David
|> > ---------------------------------------------------
|> > David L. Black, Senior Technologist
|> > EMC Corporation, 42 South St., Hopkinton, MA  01748
|> > +1 (508) 249-6449            FAX: +1 (508) 497-8018
|> > [email-masked]       Mobile: +1 (978) 394-7754
|> > ---------------------------------------------------
|> 
|> 
|> -- 
|> Tom Wu
|> Principal Software Engineer
|> Arcot Systems
|> (408) 969-6124
|> "The Borg?  Sounds Swedish..."
|> 
|

---

From: Paul Koning <[email-masked]>
Date: Fri, 12 Jul 2002 10:14:58 -0400

>>>>> "vince" == vince cavanna <[email-masked]> writes:

 vince> Hi David, I can't prove so, but Mathematica from Wolfram
 vince> certifies as prime (in a matter seconds) all five moduli
 vince> specified in the iSCSI security draft for use in SRP! I used
 vince> the PrimeQ built-in function. PrimeQ first tests for
 vince> divisibility using small primes, then uses the MillerRabin
 vince> strong pseudoprime test base 2 and base 3, and then uses a
 vince> Lucas test. I have not explored the nature of these tests.

Miller-Rabin is a probabilistic test.  As for "Lucas" -- the Handbook
of Applied Cryptography lists "Lucas-Lehmer primality test for
Mersenne numbers".  That suggests that this test has no meaning for
numbers that aren't Mersenne numbers (such as randomly chosen
numbers). 

So I think you have a probabilistic primality test here, similar to
what Tom did.  That's certainly useful confirmation, but it doesn't
sound like we have the primality proofs yet.  (Unfortunately, HAC is
not sufficiently helpful in pointing to an algorithm to to so...)

    paul