RE: Required Algorithms for Certificates

[Tim Polk <tim.polk@xxxxxxxx>]

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.

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!

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

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.

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

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

Thanks,

Tim Polk