Subject: RE: iSCSI: SRP groups in Security-14 strawman

From: [email-masked]
Date: Thu, 25 Jul 2002 12:33:16 -0400

Paul,

> You mentioned a short while ago that Tero Kivinen had undertaken to
> prove the primality of the SRP primes, but I don't remember seeing a
> followup report on that.  So until that is done, the IKE primes are
> proven and the SRP primes are not yet proven. 

The SRP primes have been proven by Tero Kivinen and
Markus Stenberg of SSH, as reported in:

http://www.pdl.cmu.edu/mailinglists/ips/mail/msg11332.html

which includes the location of the proof certificates.

> If I remember right, there are performance benefits in some bignum
> implementations to having a modulus with a bunch of leading and/or
> trailing 1 bits.  The IKE primes are constructed to achieve that, the
> SRP primes are not.  In other words, because of that construction
> there IS value in allowing those primes; the IKE primes are NOT
> superfluous and should be allowed whether or not there are primes in
> the SRP reference software package of the same size.  In other words,
> keep the 1024, 1536, and 2048 bit MODP primes, using the generator
> that Tom Wu identified.

Could you or someone double check on these performance impacts and
their magnitude?
 
> If you feel strongly that there should be only one prime modulus of
> any given size, then I would argue that the preference should be the
> IKE primes because of their construction.  

I don't know about "strongly", but I am inclined to agree with Vince's
suggestion that there's no additional value in multiple prime moduli
of the same size.  Does anyone else have implementation efficiency
concerns about the MODP vs SRP primes? 
 
> I agree that only a single generator should be picked, so with the
> proviso that we should also list the first acceptable generator for
> the other IKE primes, your proposal sounds good.

Good.
 
> I like the approach of proposing a group identifier.  That's also
> (roughly) what IKE does.

Good.  This will require text changes in the iSCSI draft, but I think
they're worth it at this late stage for interoperability.

> > (2) We need some requirements on what MUST be supported for
> > interoperability when SRP is supported.  I hesitate to require
> > support for all the groups up to the 8192-bit MODP group.  A glance
> > at draft-orman-public-key-lengths-05.txt suggests that the SRP
> > primes are adequate for now as the 1536-bit and 2048-bit primes
> > bracket the 96 bits of randomness that we require of CHAP secrets.
> > 
> > In practice, I think we need to allow local security policy to
> > disallow use of smaller primes, so the requirements would be
> > something like:
> > 
> > - MUST support all the SRP groups (up to 2048 bits)
> > - MAY support the MODP groups
> > - Target MUST offer SRP-2048 as one of the possible values of
> > 	SRP_GROUP and SHOULD offer all supported groups that are
> > 	allowed by local security policy.
> 
> I would tweak this slightly.
> 
> 1. Given the high cost of bignum arithmetic in software, I'd prefer
>    the mandatory lenghts to be smaller.  Orman's document says that
>    a modulus size of 1553 matches a brute force strength of 90 bits.
>    Given the amount of approximation in all that analysis, I'd say
>    that we should set 1536 as the largest mandated size.

That would be ok with me.  I agree that bignum performance is directly
related to the size of the bignums.
 
> 2. For the reason given earlier, mandate the MODP groups (rather
>    than the SRP groups) up to the chosen mandatory size.  I'd propose
>    1536, but if 2048 sticks then make it MODP-2048.  Reason: these are
>    just as good as the SRP reference primes, and may be more efficient
>    if your bignum implementation takes advantage of the clump of 1
>    bits at start and end.

I'd like to understand this performance issue better before signing
on to this.  In other words, my preference for the SRP primes is an
"if all other things are equal" based on the fact that they're widely
available with the SRP software (i.e., this is basically about implementer
convenience) and so I'd like to understand how much of a difference the
performance issue makes before stepping away from the primes usually
used with SRP.
 
> 3. "... MUST offer" -- it doesn't have to be the first choice, right?
>    I want to make sure that a customer who likes the cryptography
>    underlying SRP but is worried about the performance of login
>    (given a software implementation) is allowed to use, say, a 1024
>    bit modulus by making that the first choice.

Yes, that was my intent.  In this situation, the other side needs the
opportunity to enforce a security policy that requires a 1536 bit or
larger modulus, hence the need to always offer the largest one - if the
other side's policy allows the 1024 bit modulus, then it'll be used if
offered as the first choice.

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
---------------------------------------------------

---

From: Paul Koning <[email-masked]>
Date: Thu, 25 Jul 2002 15:08:00 -0400

>>>>> "Black" == Black David <[email-masked]> writes:

 >> trailing 1 bits.  The IKE primes are constructed to achieve that,
 >> the SRP primes are not.  In other words, because of that
 >> construction there IS value in allowing those primes; the IKE
 >> primes are NOT superfluous and should be allowed whether or not
 >> there are primes in the SRP reference software package of the same
 >> size.  In other words, keep the 1024, 1536, and 2048 bit MODP
 >> primes, using the generator that Tom Wu identified.

 Black> Could you or someone double check on these performance impacts
 Black> and their magnitude?
 
I looked in RFC2412, which mentions the benefit but doesn't quantify
it.  I also looked in the Handbook of Applied Cryptography, which
describes a whole bunch of exponentiation algorithms.  I'm not well
enough versed in this stuff to translate the brief comment in RFC 2412
plus the algorithms in HAC into a specific percentage benefit.

I wonder if one of the SSH folks can help answer this, since they seem
to have the necessary technical skills.

     paul

---

From: Tom Wu <[email-masked]>
Date: Thu, 25 Jul 2002 13:29:15 -0700

> plus the algorithms in HAC into a specific percentage benefit.

Also keep in mind that RFC 2412 also suggests advantages in using 2 as a 
generator/base for modexp, though those advantages aren't quantified 
either.  I generated the SRP primes to have 2 as a base, whereas the 
MODP primes cannot use 2 as a base with SRP.

Perhaps a simple benchmark might shed some more light on this.

Tom