Subject: IPS security draft: SRP groups

From: Paul Koning <[email-masked]>
Date: Wed, 3 Jul 2002 11:51:21 -0400

The security draft lists the groups from the SRP reference software,
and in addition it says that the IKE groups may be used.  (It doesn't
appear to allow the 768 bit IKE group, even though it does allow the
768 bit group from the SRP reference code.  I wonder why.)

Tom Wu said in a message dated 4/17/2002:
   g MUST be a generator; omitting half of the possible residues mod P
   is NOT a virtue for SRP because it can lead to an attack.  For the
   IKE moduli, which are all 7 mod 8, g cannot be 2, and it usually
   ends up being either 5 or 7.  g^((N-1)/2) must be -1 (mod N).

This means that the IKE groups cannot be used as they are defined in
the references given, because those do use the value g == 2 (for
reasons that apply to IKE but not to SRP).

Incidentally, the IKE groups come fully documented with a statement
that N was proven (rigorously, not probabilistically) to be prime; I
haven't found the equivalent for the SRP groups.  Does that exist?  If
yes, it would be useful to have a reference pointing to it.

Does the statement in section 2.4.2 (verifying N and g) mean:
  a. An implementation may match N and g against the list in Appendix A
     and refuse any others
or
  b. An implementation may match N and g against the list in Appendix A
     but on a mismatch is required to verify that N and g define a
     valid group
?

The text says "MAY start..." which seems to suggest (b).  But (b) is
very expensive, and it doesn't seem to be a good idea to mandate (or
even encourage) a denial of service opportunity like that.

	paul

---

From: [email-masked]
Date: Mon, 8 Jul 2002 10:34:03 -0400

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: [email-masked]
Date: Fri, 12 Jul 2002 10:11:16 -0600

Hi Paul,

I suspected as much, since I don't have a supercomputer on my desktop. Mathematica apparently also has the capability to perform a mathematical proof of primality and to produce a "certificate" using which Mathematica's results may be independently and easily verified. When I attempted to perform the proof on the smallest modulus (the one with 768 bits) my computer was rendered useless for over 20 minutes which just happened to be my threshold of tolerance for this morning. I will try again when I leave the office tonight and if I get any useful  results I will look deeper into the method.

Vince

|-----Original Message-----
|From: Paul Koning [mailto:[email-masked]]
|Sent: Friday, July 12, 2002 7:15 AM
|To: [email-masked]
|Cc: [email-masked]; [email-masked]; [email-masked]
|Subject: RE: IPS security draft: SRP groups
|
|
|>>>>> "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
|

---

From: [email-masked]
Date: Mon, 15 Jul 2002 14:36:32 -0600

I was unsuccessful at getting Mathematica to prove the primality of the SRP moduli.

If we cannot prove the primality of our chosen moduli I thought why not use moduli whose primality has been proven such as the well known groups in Oakley. Tom Wu told me that would not be a problem provided we found generators for them other than 2 (the generator that is given in Oakley RFC), since 2 in not useful for SRP. 

Using Mathematica I have been able to find other generators for the groups. The 768-bit modulus from IPSEc has 7 as a generator. The 1024-bit prime from IPsec RFC-2539 has  5 as a generator. I have used the PrimitiveRoot function in the NumberTheory package of Mathematica. As a simple (incomplete) verification I have raised the generator to the power equal to one less than the moduli and have gotten an answer that is congruent to 1 as would be expected for any generator.

Vince

|-----Original Message-----
|From: CAVANNA,VICENTE V (A-Roseville,ex1) 
|Sent: Friday, July 12, 2002 9:11 AM
|To: 'Paul Koning'; CAVANNA,VICENTE V (A-Roseville,ex1)
|Cc: [email-masked]; [email-masked]; [email-masked]
|Subject: RE: IPS security draft: SRP groups
|
|
|Hi Paul,
|
|I suspected as much, since I don't have a supercomputer on my 
|desktop. Mathematica apparently also has the capability to 
|perform a mathematical proof of primality and to produce a 
|"certificate" using which Mathematica's results may be 
|independently and easily verified. When I attempted to perform 
|the proof on the smallest modulus (the one with 768 bits) my 
|computer was rendered useless for over 20 minutes which just 
|happened to be my threshold of tolerance for this morning. I 
|will try again when I leave the office tonight and if I get 
|any useful  results I will look deeper into the method.
|
|Vince
|
|
|
||-----Original Message-----
||From: Paul Koning [mailto:[email-masked]]
||Sent: Friday, July 12, 2002 7:15 AM
||To: [email-masked]
||Cc: [email-masked]; [email-masked]; [email-masked]
||Subject: RE: IPS security draft: SRP groups
||
||
||>>>>> "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
||
|