Subject: Re: RSA vs. DSA MUST

From: "Bob Jueneman" <[email-masked]>
Date: Tue, 28 Nov 2000 16:33:50 -0700

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

---

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

Considering that the patents issues with RSA have gone away, and that RSA
Security in the past has been willing to grant royalty-free RC2 licenses for
S/MIME products, is there any remaining reason for not requiring complete
S/MIME v.2 backward compatibility as a MUST? If there aren't, I would add to
the MUST list at least D-H, DSA and 3DES, just to prevent a global shutdown
of secure e-mail if tomorrow someone finds flaws in one of the v.2
algorithms.

I don't think that implementing some additional well understood and
royalty-free algorithm would represent such a large cost to the industry,
especially considering the wide availability of OpenSource libraries,
licensed under BSD license or even more liberal terms, that can be used as a
building block.

Enzo

----- Original Message -----
From: "Bob Jueneman" <[email-masked]>
To: <[email-masked]>; <[email-masked]>
Sent: Wednesday, November 29, 2000 7:33 AM
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.

---

From: "Bonatti, Chris" <[email-masked]>
Date: Wed, 29 Nov 2000 16:58:58 -0500

Reading through this thread, I am astonished at a couple of apparent truisms that are emerging from the various earnest statements made.  These are (employing a little editorial license):

   * The implementation cost of DSA/D-H/3DES was acceptable when RSA was patented, but now that some of us have actually built/tested this the cost has gone up into the "too high" range.

   * Specifying a single MUST algorithm suite was sufficient to make S/MIME algorithm independent, but actually requiring two algorithms suites will cost too much.  If we've really achieved algorithm independence in the sense that Dave Kemp suggests, this should be a debate about a relatively small math module.

   * We have an 'SMIMECapabilities' attribute for which support is MUST, but some implementations ignore it so we have to use the lowest common denominator to force interoperability.  What make anybody think a MUST on an algorithm choice would be taken any more seriously?

    I don't think I actually have an opinion on this issue myself.  I'm of the mindset to mandate nothing and let Darwin decide.  However, I find the seeming illogic of these collective opinions very troubling.  It leads me to think that we're not getting to the REAL reasoning behind this move.

    I think Blake was closest to this in stating that there has been no customer demand for DSA.  Is this the REAL reason to dump DSA?  Are customers demanding RSA be used?  Do customers express demand for any algorithms, or do they just want it to be "secure"?  Are we just drifting to the path of least resistance?

    Personally, I favor products that support LOTS of interoperability modes... not just lowest common denominators.  Call me crazy, but...

Chris B.

---

From: Rich Salz <[email-masked]>
Date: Wed, 29 Nov 2000 19:08:41 -0500

I think your perception is slightly (but significantly) off.

Some folks implemented DSA-family, but most folks paid money and licensed RSA
and did that.  Apparently some of those DSA implementors would rather not bear
the continued cost of maintaining a code branch that has seen no customer
demand.  That's a high cost just to be able to claim IETF SMIME compliance.

To be algorithm independant, you make sure you always identify the algorithm,
and don't mistakenly say "encrypted data" without specifying the mechanism. 
During development of the standards, a good way to do that is to make sure
multiple mechanisms are specified. In this case, the theoretical (DSA) and the
practical (RSA).

Peter Gutman said it best a few weeks ago, shortly after RSA expired. 
Something along the lines of "we all pretended to do DSA, but in reality
everyone did RSA."  For political reasons, the IETF bent over backwards to
avoid mandating patented technology.

>Personally, I favor products that support LOTS of interoperability modes.

That's nonsensical.  Do you prefer BER over DER? :)

The marketplace has decided and the common crypto mechanism is RSA, and
practically nobody cares about DSA.  Certainly, making DSA not MUST will not
hurt the DSA-using community.

It's not the IETF's job to raise the bar.  It's the IETF's job to make sure we
all speak the same language, and clearly that language is mod-exp.
	/r$

---

From: Dr S N Henson <[email-masked]>
Date: Thu, 30 Nov 2000 00:17:46 +0000

>    * The implementation cost of DSA/D-H/3DES was acceptable when RSA was patented, but now that some of us have actually built/tested this the cost has gone up into the "too high" range.

I'd say in the DH case (and to some extent DSA) there's the issue of how
practical it is. The only DH certificates I've ever seen were in the
S/MIME examples draft. I suspect there are problems with the parameters
but despite repeated queries I never found anyone who could
independently check them.

If public CAs issuing DSA certificates are rare then I'd say CAs issuing
DH certificates are virtually non existent. Does anyone know of a single
example?

Its all very nice adding support for DSA and DH but if users can't get
any certificates from public CAs then their value is severely limited.

Steve.
-- 
Dr Stephen N. Henson.   http://www.drh-consultancy.demon.co.uk/
Personal Email: [email-masked] 
Senior crypto engineer, Celo Communications: http://www.celocom.com/
Core developer of the   OpenSSL project: http://www.openssl.org/
Business Email: [email-masked] PGP key: via homepage.

---

From: "Bonatti, Chris" <[email-masked]>
Date: Thu, 30 Nov 2000 10:21:00 -0500

> multiple mechanisms are specified. In this case, the theoretical (DSA) and the

I had the sense that what Dave was alluding to was something more.  It sounds like
an algorithm independent infrastructure, or maybe a multi-algorithm infrastructure
is a better way to say it.  (Dave, I don't want to put words in your mouth, but it
seemed to me this is what your 11/28 message was saying.)  This strikes me as a
good idea from a robustness point of view as has already been stated.  It seems
like we're saying on the one hand that this is a good idea, yet on the other that
everybody building to a lowest common denominator is all we're willing to do.
That seems a little disconnected to me.

> avoid mandating patented technology.

I missed this statement the first time around, but I think it's probably
accurate.  However, consider just what it says about IETF's overall impact on
industry.  I think we take the whole MUST/SHOULD/MAY debate way too seriously.
Industry does what it wants.

> That's nonsensical.  Do you prefer BER over DER? :)

For some things, yes.  It's better for one-pass processing for instance.

> all speak the same language, and clearly that language is mod-exp.

I agree on these points.

Cheers,
Chris B.

---

From: "Bonatti, Chris" <[email-masked]>
Date: Thu, 30 Nov 2000 10:21:23 -0500

> independently check them.

I agree about D-H certs.  They are not deployed as far as I can see.

> DH certificates are virtually non existent. Does anyone know of a single

For "public CAs" I'd have to agree.  I think the US government has issued *lots* of DSA certs, but they generally don't emit them because the interoperability picture is rather bleak.  I don't
think secure mail gets used much outside of fairly closed environments for this very reason.  It's exceedingly rare that I even see a signed message in this forum.

> any certificates from public CAs then their value is severely limited.

It's a bit of a chicken and egg problem, though.

Chris