Subject: RSA vs. DSA MUST

From: "Bob Jueneman" <[email-masked]>
Date: Mon, 27 Nov 2000 16:04:16 -0700

David, is the issue whether RSA should REPLACE DSA as a MUST, as opposed to merely adding an additional MUST for RSA for signatures?

I doubt that there would be any strong disagreement about adding RSA as a MUST, since it has been a commercial requirement and de facto standard all along, regardless of IETF politics.

But other than the patent issues, is there still a strong technical, marketing or other consensus in favor of continuing DSA as a MUST?

To date, we haven't implemented DSA in GroupWise, nor in the Novell Cert. Server, due to the complete absence of customer demand.  In fact, when we looked around, we couldn't find any certificates that used DSA (granted, we probably didn't look very hard.)

Do any of the US DoD PKI or e-mail initiatives have any serious plans to MANDATE the exclusive use of DSA?  

Does anyone else care strongly?

Regards,

Bob

Robert R. Jueneman
Security Architect
Novell, Inc -- the leading provider of Net services software

>>> "David P. Kemp" <[email-masked]> 11/27/00 01:49PM >>>

> 	Title		: S/MIME Version 3.1 Certificate Profile Addendum
> 	Author(s)	: B. Ramsdell
> 	Filename	: draft-ietf-smime-v31cert-00.txt
> 	Pages		: 
> 	Date		: 22-Nov-00
> 	
> In light of the expiration of the primary RSA patent, it is proposed
> that the RSA algorithm replace the DSS and Diffie-Hellman as the MUST
> implement algorithms in the S/MIME profile. This draft will describe
> only the proposed changes to the S/MIME Version 3 Certificate Handling
> RFC [SMIMEV3CERT], and the rest of that RFC will remain identical.

Did I miss the discussion and consensus on this?

I was under the impression that RSA does not replace DSA as a
MUST-implement, rather RSA becomes an additional MUST for signatures:

> Russ Housley <[email-masked]> on 07/31/2000 05:04:52 PM
>
> Proposed way forward:  Change the mandatory to implement algorithm set to:
>      One-way Hash:  SHA-1 (no change)
>      Signature:     Both DSA and RSA (PKCS#1 v1.5)
>      Key Mgmt: RSA (OAEP)
>      Eencryption:   Triple-DES in CBC mode

The Certificate Profile should reflect the results of the last meeting
and subsequent mail list discussion.

---

From: "Blake Ramsdell" <[email-masked]>
Date: Mon, 27 Nov 2000 16:51:28 -0800

I do not care strongly, but the strawpoll at the last IETF indicated a
preference for "both", and that was the path we were headed down, and that
Russ summarized.  Personally, I don't implement it, and I haven't had any
customer complaints telling me I should, and the backwards compatibility
issues are almost the same as for Diffie-Hellman certs (that is, I have not
seen anyone using them, so chucking them wouldn't break an installed base of
significant size, if at all).

Blake

-----Original Message-----
From: Bob Jueneman [mailto:[email-masked]]
Sent: Monday, November 27, 2000 3:04 PM
To: [email-masked]; [email-masked]
Subject: RSA vs. DSA MUST

David, is the issue whether RSA should REPLACE DSA as a MUST, as opposed to
merely adding an additional MUST for RSA for signatures?

I doubt that there would be any strong disagreement about adding RSA as a
MUST, since it has been a commercial requirement and de facto standard all
along, regardless of IETF politics.

But other than the patent issues, is there still a strong technical,
marketing or other consensus in favor of continuing DSA as a MUST?

To date, we haven't implemented DSA in GroupWise, nor in the Novell Cert.
Server, due to the complete absence of customer demand.  In fact, when we
looked around, we couldn't find any certificates that used DSA (granted, we
probably didn't look very hard.)

Do any of the US DoD PKI or e-mail initiatives have any serious plans to
MANDATE the exclusive use of DSA?  

Regards,

Bob

Robert R. Jueneman
Security Architect

---

From: "Tolga Acar" <[email-masked]>
Date: Tue, 28 Nov 2000 10:07:17 -0700

> In case this is useful as a data point, in my general wandering around looking
> for certs on the net the only publicly available DSA certs I've ever found were
> some old Thawte ones, presumably created just to show'em (all the standard
> Thawte certs are RSA, I don't think I've ever seen the DSA certs actually used
> to certify anything).  I've also very occasionally come across them being used
> in closed environments (ie ones where interoperability with the masses isn't
> really an issue).  I suspect the motivation for a lot of these is that there's
> a requirement to use a FIPS algorithm and DSA is the only choice.  I can't see
> a MUST RSA, MAY DSA as being any real problem, it's just recognising what has
> been reality for the last few years.

DSA is not the ONLY asymmetric algorithm certifiable in FIPS 140-1/2, as it references any algorithm published/referenced in a FIPS;  X9.31 and X9.62 are also specified in FIPS 186-2.
Remember that DSS it not DSA.
Looking forward (that's what this is about, isn't it?), there are three asymmetric algorithms in FIPS 68-2: DSA, X9.31 RSA, and X9.62 ECDSA.
So, the motivation for a lot of those certificates based on FIPS 186-1 and FIPS 140-1, is not there anymore.
It is enough to support one of them for FIPS purposes, then the most common one, RSA, should do fine. NIST certainly does not mandate all of them (FIPS 186-2, page 3, line 3).
Effective as of July 27, 2000, and with the prescribed transition period of FIPS 186-2 from July 27 2000 to July 27 2001, that should give enough time to make changes in a product line.

- Tolga

---

From: "Bob Jueneman" <[email-masked]>
Date: Tue, 28 Nov 2000 10:22:36 -0700

>Well, there is one problem, and it's due to the store-and-forward 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 Gresham'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
>
Although it isn't strictly interactive in the sense that SSL is, the SMIMECapabilities attribute allows the originator of a message to indicate his preference as to encryption algorithms, including 40-bit RC4 vs. 56-bit DES vs. 128-bit whatever vs. 196-bit triple-DES (and soon, presumably, 256-bit AES).   (Granted, some implementations ignore the attribute and default to the lowest common denominator (boo, hiss), and others use whatever algorithm and key size the originator selects, regardless of what the recipient specified.)

I don't have the text in front of me, but isn't it possible to indicate the preferred key exchange and signature algorithms (and hashing algorithms, in order to handle SHA-384 and SHA-512) in the same manner?

If not, it probably ought to be amended.

Bob

---

From: "Enzo Michelangeli" <[email-masked]>
Date: Wed, 29 Nov 2000 09:39:31 +0800

----- Original Message -----
From: "Bob Jueneman" <[email-masked]>
To: <[email-masked]>; <[email-masked]>; <[email-masked]>
Sent: Wednesday, November 29, 2000 1:22 AM
Subject: Re: RSA vs. DSA MUST

> Although it isn't strictly interactive in the sense that SSL is,
> the SMIMECapabilities attribute allows the originator of a message
> to indicate his preference as to encryption algorithms, including
> 40-bit RC4 vs. 56-bit DES > vs. 128-bit whatever vs. 196-bit
> triple-DES (and soon, presumably, 256-bit AES).

Yes, but on the open Internet most certificates are sent as part of the
message (presently in PKCS#7 format), not retrieved from global directories
as the X.500 folks initially hoped. In that context, the recipient would
have to send an initial signed message to the sender to indicate the user
agent's capabilities: and in most cases (like one I mentioned of the mailing
list) that's just not viable.

Enzo

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 29 Nov 2000 14:43:57 (NZDT)

"Bob Jueneman" <[email-masked]> writes:

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

How about trying to make the spec at least vaguely approximate reality in the
choice of algorithms?  It doesn't really matter if you include requirements
like "MUST DSA OR WE WILL KILL YOU[0], SHOULD NOT RSA", in practice the world
will interpret it as "MUST RSA, MAY DSA, SHOULD NOT X9.42 DH, BWAHAHAHAHAHA
X9.31 RSA" no matter what it says in the RFC (I think IBM does X9.31 in CCA but
does anything else in existence implement this?).  

I've been sitting here watching this debate go on and on, but since no matter
what you put in the RFC the market will interpret it as MUST RSA and various
levels of deprecation for anything else maybe we could get Markov Chaney to
continue the debate for a while just for forms sake and then after enough
messages have been exchanged to satisfy everyone either put text in the RFC
which accepts what everyone's going to do anyway or which specifies all sorts
of options and alternatives secure in the knowledge that implementors will
ignore it and do what the market wants/expects, which ain't DSA or X9.31 RSA.

Peter.

[0] RFC 2026bis, "When MUST just isn't enough".

---

From: "Linn, John" <[email-masked]>
Date: Wed, 29 Nov 2000 08:27:33 -0500

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

> Sent: Tuesday, November 28, 2000 6:34 PM
> 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" <[email-masked]> 
> >> 
> >> Well, there is one problem, and it's due to the 
> store-and-forwad nature of
> >> days: a sort of Grisham's Law for algorithms...

---

From: "Blake Ramsdell" <[email-masked]>
Date: Wed, 29 Nov 2000 10:10:34 -0800

An inimitable Gutmannism.

This could also be summarized as Paul did it when we first started this
discussion back in July:

> Blake Ramsdell has turned in two drafts that are worthy of 
> consideration in this group. It's my opinion that they represent the 
> reality of the marketplace, and that it would be good to have our 
> RFCs reflect that if possible.

Which was exactly my intent.  There seems to be some disconnect between the
current discussion and the strawpoll consensus at the last IETF, which needs
to be resolved, however.

I would certainly welcome how I should interpret "BWAHAHAHAHAHA" in the
context of MUST and SHOULD, however.

Blake

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
Sent: Wednesday, November 29, 2000 6:44 AM
To: [email-masked]; [email-masked]; [email-masked]
Subject: Re: RSA vs. DSA MUST

>SHOULD, and DSA and PKCS-1 RSA a MAY?

How about trying to make the spec at least vaguely approximate reality in
the
choice of algorithms?  It doesn't really matter if you include requirements
like "MUST DSA OR WE WILL KILL YOU[0], SHOULD NOT RSA", in practice the
world
will interpret it as "MUST RSA, MAY DSA, SHOULD NOT X9.42 DH, BWAHAHAHAHAHA
X9.31 RSA" no matter what it says in the RFC (I think IBM does X9.31 in CCA
but
does anything else in existence implement this?).  

I've been sitting here watching this debate go on and on, but since no
matter
what you put in the RFC the market will interpret it as MUST RSA and various
levels of deprecation for anything else maybe we could get Markov Chaney to
continue the debate for a while just for forms sake and then after enough
messages have been exchanged to satisfy everyone either put text in the RFC
which accepts what everyone's going to do anyway or which specifies all
sorts
of options and alternatives secure in the knowledge that implementors will
ignore it and do what the market wants/expects, which ain't DSA or X9.31
RSA.

Peter.