RE: RSA vs. DSA MUST

Bob, all:

NIST's announcement of FIPS 186-2
(http://csrc.nist.gov/csrc/fedstandards.html) explicitly recognizes PKCS #1
for a transitional period through mid-2001.  The topic of X9.31 vs. PKCS #1
was discussed at the June meeting of the U.S. Federal PKI Technical Working
Group, leading to a recommendation which was to be communicated (see also
minutes at http://csrc.nist.gov/pki/twg/y2000/twg00_6.htm) that FIPS 186-2
should be changed or interpreted to allow Federal use of PKCS #1 v. 1.5 for
a significant additional period, perhaps 5 years or more, anticipating a
migration after PSS signature definitions are suitably mature and stable.  I
don't know how this recommendation will act to impact the future of the FIPS
186 specification, but believe that it indicates an influential position
from a significant U.S. Government user community. 

X9.31 doesn't appear to have been widely adopted, and I'm not aware that its
padding structure offers security properties sufficiently different relative
to PKCS #1 v. 1.5 to motivate a mandated switch to X9.31 (with associated
installed base impact) at this point.  A later migration to PSS, which
affords qualitatively different provable security properties than either
PKCS #1 v. 1.5 or X9.31 is, I believe, a more compelling case.

--jl

> -----Original Message-----
> From: Bob Jueneman [mailto:bjueneman(_at_)novell(_dot_)com]
> Sent: Tuesday, November 28, 2000 6:34 PM
> To: ietf-smime(_at_)imc(_dot_)org; dpkemp(_at_)missi(_dot_)ncsc(_dot_)mil
> Subject: Re: RSA vs. DSA MUST
>
>
> Chicken and egg is exactly the situation we find ourselves 
> in.  Implementors certainly want to support their customers, 
> but don't want to be "required" by standards to implement 
> algorithms that no one uses or are willing to pay for.
>
> Ozan Gonenc also makes a good point in suggesting that 
> perhaps the MUST algorithms be limited to FIPS approved 
> algorithms.  I'm a slightly concerned that this may be too 
> US-centric a view, but on the other hand I haven't heard of 
> any other governments or customers requiring or promoting any 
> other algorithms, except for 
> unpublished/proprietary/classified algorithms used in certain 
> restricted sectors.  (An exception might be GOST, but so far 
> we can't even get the Russians to agree to pay anything for 
> the capability., much less anyone else) So maybe limiting the 
> MUST algorithms to a subset of the FIPS-approved list is 
> acceptable.  At least the FIPS listing implies a rather 
> serious degree of vetting as to the security of the 
> algorithms, which is something I don't think the IETF is 
> institutionally capable of, not withstanding the 
> cryptographic expertise of some of the members.
>
> The point about having at least one algorithm in the suite 
> that could be used if RSA were suddenly shown to be seriously 
> flawed is also valid, so long as we don't get carried away 
> with the list!
>
> FIPS 186-2 includes DSA, ANSI X9.31 RSA, and X9.31 Elliptic 
> Curve DSA; but not PKCS-1 RSA, the one interoperable 
> algorithm that everyone is using presently!
>
> Hmm.
>
> I'm not necessarily advocating this position -- I might like 
> to think about it some more myself -- but just for the sake 
> of argument and to take the pulse, what would people think of 
> making ANSI X9.31 RSA a MUST,  X9.31 EC-DSA a SHOULD, and DSA 
> and PKCS-1 RSA a MAY?
>
> It is my understanding that X9.31 RSA is considered to be 
> superior to PKCS-1 RSA in terms of resistance to certain 
> forms of attack, and should not be that great a stretch for 
> existing RSA implementations, and hence the MUST. We wouldn't 
> deprecate PKCS-1 RSA (at least not yet), since it must 
> continue to be supported for backwards compatibility.
>
> This wouldn't deprecate DSA either, but it wouldn't be 
> required  for people outside of the (quite limited) community 
> of interest presently using it. 
>
> EC-DSA certainly beats regular DSA in terms of speed and size 
> and deserves to be included in its own right, but I'm not 
> entirely clear as to the patent situation, hence the SHOULD 
> and not a MUST.
>
> In the area of symmetric algorithms, as soon as Rijndael is 
> officially certified as the AES algorithm I believe we should 
> promote AES to MUST, along with triple-DES and single DES for 
> backwards compatibility.  ( haven't heard of anyone clamoring 
> for SKIPJACK, so I think it can safely be ignored in favor of 
> triple-DES and/or AES.)
>
> Likewise, I think we will have to add SHA-386 and SHA-512 as 
> MUST algorithms, along with SHA-1, and probably deprecate MD2 and MD5.
>
> What think ye?
>
> Bob
>
>
> > Enzo has captured the chicken-and-egg essence of my concern. 
>  The U.S.
> > Government has a requirement to purchase products which support FIPS
> > 186-2 algorithms (this includes DSA and ANSI X9.31 RSA, but 
> not PKCS-1
> > RSA).  And, at least in the DoD, we have requirements coming from our
> > customers to be algorithm independent:
> >
> >  "PKI must support a variety of public key cryptographic algorithms
> >   both in the public/private key pairs created and certified by PKI,
> >   and in the algorithms used to apply digital signatures to 
> certificates
> >   and other PKI products.  PKI must support the concurrent 
> use of several
> >   digital signature algorithms for issuing certificates and 
> must be able
> >   to migrate over time to using new signature algorithms."
> >
> >           -- DoD PKI Operational Requirements Document, 22 
> October 2000
> > There is also the fact that DSA signatures are significantly smaller
> > than RSA signatures, especially as we move to public keys 
> above 1024 bits
> > and the signature could be bigger than the entire 
> to-be-signed certificate.
> > This doesn't matter in many environments, but it does in some.
> >
> > If vendors look at what certificates have already been 
> issued to decide
> > what certificates to support in products under development, 
> we will never
> > evolve.  I favor keeping DSA (in addition to RSA) as a MUST 
> for S/MIME
> > clients because algorithm independence is valuable in and of itself.
> >
> > Dave
> >
> >
> >
> > > From: "Enzo Michelangeli" <em(_at_)who(_dot_)net> 
> > >
> > > Well, there is one problem, and it's due to the 
> store-and-forwad nature of
> > > e-mail which prevents negotiation, making it impossible to 
> know whether a
> > > given algorithm is supported by a new recipient (think, 
> e.g., of signed
> > > messages sent to mailing list). The result is that 
> everybody ends up using
> > > ONLY the common denominator, i.e. the "MUST" algorithms. 
> Incidentally, this
> > > was precisely the root of the trouble with 40-bit security 
> in the bad old
> > > days: a sort of Grisham's Law for algorithms...
> > > In my opinion, "MAY" algorithms are pretty useless in 
> non-interactive
> > > contexts, and if DSA is not kept as a "MUST" (my preferred 
> choice), it might
> > > as well be dropped altogether.
> > >
> > > Enzo