RE: Required Algorithms for Certificates

[Al Arsenault <aarsenault@xxxxxxxxx>]

Tim,

	Comments in-line, prefaced by my initials "AWA".

-----Original Message-----
From:	Tim Polk [SMTP:tim.polk@nist.gov]
Sent:	Thursday, December 21, 2000 5:05 PM
To:	ietf-pkix@imc.org
Subject:	RE: Required Algorithms for Certificates

Folks,

Since different algorithms are a natural fit for different applications,
the selection of a single MUST algorithm for PKIX seems a bad idea.  That
is the reason Jeff Schiller let us avoid this issue in the first place.  If 
S/MIME chooses RSA but IPsec chooses DSA and D-H, we would be in conflict
with at least one of them.  PKIX should not be in the position of dictating 
algorithms to other working groups.  If PKIX decides to specify MUSTs or
SHOULDs, they should be designed to support broad interoperability.

AWA: Agreed.

Interoperability is a prime concern here at NIST.  In terms of algorithm
independence, we have come to the conclusion that interoperability
*requires* multi-algorithm clients.  Yes, it would be nice to move the
burden to CAs since there will be relatively few CAs.  However, CAs that
can sign with multiple algorithms doesn't help clients that verify with
only one unless they issue each certificate multiple times, using each
supported signing algorithm.  Not a solution, IMHO!

AWA: Agreed, in general.  Although we've found that for some specialized 
cases, it winds up being easier to just issue two certs, one with each of 
two signing algorithms.  That way it means we can support a wider set of 
clients, without having to modify them. I certainly don't want to force 
that solution on the populace at large; I'm just saying that it sometimes 
works out to be an acceptable solution.

This implies that we need to move the burden to the clients, even though
that will impact many clients.  If a PKIX client can validate both DSA and
RSA signatures, it can handle certificates from any CA when signed with a
PKIX-specified algorithm.  The client will never be forced to reject the
certificate based on the signing algorithm - to me, that's
interoperability.  (I am assuming, of course, that the client knows how to
use the end entity's public key.  If the certificate contains a D-H key,
and the client can't do D-H we still break down.  It wasn't the signature
algorithm on the certificates that broke it, though...)

AWA: Here I disagree.  As Ari has already pointed out, PKIX - and Russ' 
suggestion - allows the CA to use whatever algorithm it wants.  Thus, a CA 
can use ECDSA (to pick on one algorithm) and it's still completely 
PKIX-compliant, as long as it could have also done RSA but chose not to. 
Any client that doesn't support ECDSA will choke on this certificate, and 
reject it with some error message or another. Thus, we have "PKIX 
compliance" at both the client and CA, but no interoperability.

The question is whether multiple algorithm support is a practical
requirement for clients.  I just took a few minutes to scan the FIPS 140-1
validated crypto module list.  This list currently has 130 modules - some
hardware, some software.  (For those interested, see
http://csrc.nist.gov/cryptval/140-1/1401val.htm)  Many of those
cryptographic modules already support multiple signature algorithms.   I
didn't count, but it appears that most of the recent products (both
hardware and software) support both DSA and RSA for signatures.

To me, this implies that multiple algorithm support is reasonable unless
the device footprint must be very small.  This may be a biased data set,
though.  Validated products are required to support at least one
FIPS-approved algorithm, and RSA has only recently become a FIPS-approved
algorithm.

AWA: for typical "Internet clients", you're almost assuredly right. 
 However, I tend to work with a set of client devices that are more 
constrained than most Internet developers typically see, so I'm 
particularly sensitive to this.  (If anyone has ever tried to implement a 
PKI client on a device with less than a 23 byte stack and 147 bytes of RAM, 
let me know.  :-)

Anyway, I personally like Russ's proposal.  I believe it doesn't put too
great a burden on PKI clients and would foster interoperability.

AWA:  I'm more inclined to say that DSA should be a "SHOULD" at this point. 
Yes, as Phill pointed out, it seems to be breaking faith with those who 
implemented non-RSA PKIX, and so I wouldn't be terribly saddened to see DSA 
be a "MUST", but I'd rather it be a SHOULD for the client at this point.

My $0.02 (which may in fact be overpriced.)

Thanks,

Tim Polk

		Al Arsenault