Subject: [TLS] TLS 1.2 and hash agility for signatures

From: <[email-masked]>
Date: Tue, 6 Mar 2007 13:01:42 +0200

There's one area in TLS 1.2 that still doesn't give me a warm 
fuzzy feeling that "yes, this is the way it should be done", and 
that's the algorithm agility for signatures (in certificates and
ClientKeyExchange/ServerKeyExchange messages).

I'd like to get some more discussion about this, and fresh
ideas on what's the best way to implement it in TLS 1.2.

Some issues that don't yet seem right:

1) Asymmetry: The server sends its list of supported hashes in the
CertificateRequest message, together with list of trusted CAs (DNs)
and ClientCertificateTypes. The client sends the list of supported
hashes in cert_hash_types extension, list of trusted CAs (DNs or
hashes) in trusted_ca_keys extension, and there's no equivalent of
ClientCertificateType.  In addition, we have the "cert_type" extension
for non-X.509 certs (draft-ietf-tls-openpgp-keys).

To make things worse, ClientCertificateTypes field seems quite
redundant, since at this point we already know the ciphersuite, and
that limits our choice (it doesn't make sense to request dss_sign
certificate if you've already negotiated RSA ciphersuite). Or if it's
not redundant, then we need more text in the spec explaining why not.

Perhaps we can't avoid this asymmetry completely, but is there any way
to make this a bit nicer? Perhaps remove the ClientCertificateTypes
field in TLS 1.2, and use cert_hash_types extension also from server
to client?

2) Wrong concept: instead of telling what hash algorithms we support
we'd really like to tell what kinds of signatures we can verify.
E.g. for RSA, we have at least three different schemes (PKCS#1 v1.5,
PSS and ANSI X9.32), all of which can be used with different hashes.
And we also have DSS and ECDSA.

For TLS level signatures (ServerKeyExchange/CertificateVerify), some
part of this is already determined by the ciphersuite's key exchange
algorithm (e.g. RSA here means PKCS#1 v1.5; if someone wants to use
RSA PSS we'd define new ciphersuites). But for certificates, the
situation is not the same; we could have certificate containing RSA
public key signed with DSS, or something.

Should we have signature_schemes extension instead of cert_hash_types?
(with values like rsa_pkcs15_sha256, dss_sha1, ecdsa_sha512, etc.)  
Or separate lists for certificate signatures and signatures in TLS?

3) Tying algorithm in ServerKeyExchange/CertificateVerify and
certificate. The current spec says that for RSA, signatures in TLS
(ServerKeyExchange and CertificateVerify) use the same hash as was
used by the CA in the certificate.

The idea itself is not wrong: if you're worried about using SHA-1,
then it's much more important to use something better in certificates
(usually long-lived) than in ServerKeyExchange/CertificateVerify
(which include fresh nonces, and are verified only once immediately
following signature generation -- so offline attacks don't count).

However... what if the cert isn't signed with RSA? Or it's signed with
RSA PSS? And is it OK to require the peer to parse its own certificate
(something not previously required)? Perhaps we should decouple these?

4) RSA-specific text. It looks like much of the text (and whole
cert_hash_types) is really specific to RSA ciphersuites, since the
spec fixes SHA-1 for DSS, and RFC4492 specifies that for ECDSA, the
hash is always SHA-1 unless otherwise specified by yet-unspecified
extension in the certificate.

It may not be possible to avoid RSA-specific text, but then it should
be easy to see what parts are specific to RSA and what are not. And we
should probably plan for hash agility in DSS as well?

Comments? I think we'd want something reasonably simple in the spec,
but on the other hand, it should be technically coherent as well.
I'm planning to sketch something before Prague, but any kinds
of ideas (or alternative ways of looking at the problem) would
be welcome...

Best regards,
Pasi

_______________________________________________
TLS mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tls

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 6 Mar 2007 15:30:01 +0100

> not redundant, then we need more text in the spec explaining why not.

I don't think that there's anything wrong with using a DSA certificate
in an RSA ciphersuite.  The only cases where symmetry is required are
the fixed_dh certificate types (and, similarly, the fixed_ecdh
certificate types from RFC 4492), since in these the client
certificate is tied to the actual key exchange and client
authentication does not use the separate CertificateVerify message.

If both the client and the server support all of RSA and DSA and
ECDSA, then it might just happen to be the case that the server has an
RSA certificate, say, while the client has an ECDSA certificate.  So
you might see an RSA ciphersuite in the handshake, but the client
would still use ECDSA in the CertificateVerify.  (This scenario can
make quite a lot of sense in certain configurations: RSA signature
verification and RSA encryption are usually very easy to do for the
client, but ECDSA signing might be much faster than RSA signing.)

So it's quite useful if the server can indicate to the client what
kinds of signatures it can verify.

> Or separate lists for certificate signatures and signatures in TLS?

I don't think that there's anything basically wrong with using
ClientCertificateType.  The list of ClientCertificateType values alone
doesn't provide complete information since RSA might mean RSA PKCS#1
v1.5 with a limited selection of hash algorithms only, or might allow
much more flexibility.  Adding a list of HashType values, as you point
out, doesn't quite address this issue since there are more aspects
that can be varied than just the choice of hash algorithm.  (Also,
sometimes, different choices of hash algorithms might be available
with different signature algorithms.)  Also often (but not always)
it's the complete certificate chain that must be considered, i.e. not
just the CertificateVerify signature but additionally each and every
signature in the client's certificate chain up to some anchor that the
server is willing to rely on for verification purposes.  (Sometimes
the server might not need to validate the actual certificate chain, if
permissible client certificates have been made available for direct
verification without the computational overhead of a PKI.)

So things can be quite complicated.  I don't think, though, that we
really have to solve all of this in the TLS specification!

In practice, the most important part of the CertificateRequest message
is certificate_authorities, the list of distinguished names of
acceptable CAs.  If the client happens to pick a certificate using a
chain for which the server does not have an appropriate anchor, then
it does not matter at all if the server can handle the hash algorithm
(or even the signature algorithm) used by the client for the
CertificateVerify or not -- either way the server won't be able to use
the signature.  But if the client has a certificate signed by a CA
that the server is willing to rely on, then generally that CA's
policies will determine what signature algorithms (with what hash
algortihms, etc.) can be encountered in certificate chains.  This is
usually enough since, for obvious pragmatic reasons, CAs don't tend to
mix lots of different techniques in their certificate chains.  (It's
similar for the use of the signing key in the client's end-entity
certificate -- for the case of RSA, the TLS 1.2 draft quite
reasonably, yet somewhat problematically [see below], says that "the
same function (denoted Hash) must be used as was used to create the
signature for the client's certificate".)

So we could spend a lot of time on coming up with a detailed solutions
allowing a find-grained negotiation of signing algorithm details, but
I think we don't really have to do that.  Reality always could be more
complicated than what we foresee (a complete solution would, for
example, have to provide the server with means to specify the X.509
extensions that it can parse, lest the client use a certificate chain
that has to be rejected due to an unknown critical extension).  In
practice, a rather simple solution should work very well.

The list of ClientCertificateType values in the CertificateRequest may
be a useful hint.  Besides, it is very brief, and we've always had
this in the protocol; so there's no reason to throw this out.  Maybe
adding a list of HashType values (as the TLS 1.2 draft does) is
reasonable too, but I don't really see compelling reasons to do so.
An optional TLS extension mirroring the client's Cert Hash Types
extension would look quite appropriate to me (why use a different tool
for server-to-client communcation than for client-to-server
communication?) -- also to be interpreted as a hint, not a complete
specification of what the server can handle.

I don't really think we need signature_schemes in place of
cert_hash_types.  The rsa_sign client certificate type currently is
restricted to RSA PKCS#1 v1.5 signatures, and if there was demand to
use PSS, say, a separate client certificate type for RSA-PSS would be
reasonable.  But then in practice, a demand for PSS would probably
mean separate PKIs with end-entity certificates intended for PSS
signing anyway (it would be rather silly to use a single RSA key both
for PKCS#1 v1.5 and PSS signing), so maybe we shouldn't worry about
this too much.

> (something not previously required)? Perhaps we should decouple these?

Well, the client wouldn't really have to actively parse its own
certificate, just know what's in there.  That's additional data, just
like the secret key matching the certificate's public key is
additional data.

Arguably, the TLS specification should not make such strict rules for
the hash algorithm to be used during signing, though, because it's
very reasonable to assume that the client's end-entity certificate
would completely specify the client's signing algorithm, including the
hash algorithm to be used.  And this might not match the hash
algorithm used by the CA while signing the respective certificate, so
the rule in the TLS 1.2 draft might be incompatible with keys that
otherwise would be absolutely acceptable for use.  (E.g., the CA might
have a 4096-bit RSA key and use a 256-bit hash for certificates, but
issue certificates on 2048-bit keys intended for use with 224-bit
hashes.)  The algorithm given in SubjectPublicKey might be more
explicit than just an unspecific "rsaEncryption" and might fix the
hash algorithm; and even if the SubjectPublicKey does not reveal it,
the hash algorithm might be fixed.

> should probably plan for hash agility in DSS as well?

Yes, limiting DSA to SHA-1 quite obviously has historic reasons -- or
qrather, reasons that hopefully *will* become historic soon when FIPS
186-3 (with support for the newer SHA variants) finally is released!

> of ideas (or alternative ways of looking at the problem) would

My take is that it is very reasonable to describe quite many things as
"SHOULD"s only, since the ability to verify certificates depends on
PKIs and their policies anyway, and much of the responsibility can be
put there.  If a CA is willing to sign certificates that are hard to
verify and if a server is willing to accept a PKI relying on such a
CA, then why not let them do this?  Generally, this won't happen,
since CAs will take care to issue certificates that work well in the
intended environment.  We don't have to freeze all the details of this
in the TLS specification.

Probably the TLS 1.2 specification should say more about how the
individual methods for ClientVerify work, e.g., that rsa_sign strictly
means RSASSA-PKCS1-v1_5, or possibly that RSASSA-PKCS1-v1_5 is what
SHOULD be used for rsa_sign.  I think we should keep
ClientCertificateTypes in the CertificateRequest, but maybe remove the
HashType list from the CertificateRequest and instead offer a server
hello extension for this.  (There's a similar client hello extension,
so this would provide more consistency within the protocol.)

Fixing the hash to SHA-1 for DSA is bad.  (As an aside, indeed there
are some cases where the new TLS 1.2 draft correctly says "DSA"
instead of the incorrect "DSS" -- maybe this finally should be
corrected throughout the document; i.e., merely mention the "DSS"
terminology in a historical note.)  This SHA-1-only approach won't
work well when FIPS 186-3 is released, so we should prepare something
for the new SHAs.  (This affects both the ServerKeyExchange and the
CertificateVerify messages.)

Similarly, the rule that ties the hash used for RSA signing to the
hash used for the respective certificate's signature is problematic.
In both cases (ServerKeyExchange and CertificateVerify), the "Cert
Hash Types" extension could be turned into a more general "Signature
Hash Types" extension (both as a client-side extension and a
server-side extension) that also covers the signatures within TLS, not
just those appearing in certificates.  The "rsa" and "dsa" cases of
the Signature type probably should be equipped with HashType fields so
that signatures can be verified without having to guess!

Bodo

---

From: Mike <[email-masked]>
Date: Fri, 16 Mar 2007 10:23:28 -0700

> for non-X.509 certs (draft-ietf-tls-openpgp-keys).

If you want to make this symmetrical and have the server send this
information in extensions, then it is up to the client to send
the extensions in its ClientHello since the server can't send them
without being requested.  Leaving it in the CertificateRequest
message takes the client out of the picture since the format of the
message dictates what information must be present.

> not redundant, then we need more text in the spec explaining why not.

I think it's perfectly OK to negotiate an RSA ciphersuite and then
ask for either an RSA or DSS client certificate.  The client cert
is only used for authenticating the client, so it doesn't need to
match the server's certificate.

> Or separate lists for certificate signatures and signatures in TLS?

I think that signature_schemes is better than cert_hash_types.  In
my code, that is what I implemented anyway.  One problem I encountered
is if SHA-1 is specified, you need to look for either an RSA or DSS
certificate, but maybe only RSA is desired -- there is no way to say
that.  With signature_schemes, you get to ask for exactly what you
want.

> (something not previously required)? Perhaps we should decouple these?

Just throwing out an idea, you could use the hash algorithm specified
by the cipher suite (same as used by HMAC).

Mike

---

From: <[email-masked]>
Date: Sat, 17 Mar 2007 19:28:45 +0200

Hi Bodo,

And thanks for a detailed reply! I had overlooked the fact that TLS
indeed does not require the *client* certificate's algorithm to match
the cipher suite.

Regarding the Signature structure (in ServerKeyExchange and
CertificateVerify), I agree that we probably need to include a field
that tells which hash algorithm was used. In RSASSA-PKCS1-v1_5, the
signature itself includes the algorithm identifier, but this is not
the case for DSA (or ECDSA, for what matter)... so if the certificate
does not specify a single unique allowed algorithm, we need to tell
which was used in TLS.

Given that some signature algorithms have more tweakable parameters
than just the hash algorithm (e.g. PSS has salt length, MGF and the
MGF's hash algorithm), perhaps the simplest solution would be just to
use DER-encoded AlgorithmIdentifier structures (instead of defining
a new IANA-maintained number space just for TLS)? 

(Of course, a sane implementation probably wouldn't include a 
DER encoder/decoder, but just list of octet strings for things it
supports; e.g. 0x3021300906052b0e03021a05000414 for RSASSA-PKCS1-v1_5
with SHA-1.)

If we use the AlgorithmIdentifier structure in the Signature,
would that also work for the cert_hash_types extension? (Which,
as you point, could be really called "signature_hash_types" 
since it also covers signatures outside certs.)

Comments?

Best regards,
Pasi 

> -----Original Message-----
> From: ext Bodo Moeller [mailto:[email-masked]] 
> Sent: 06 March, 2007 16:30
> To: Eronen Pasi (Nokia-NRC/Helsinki)
> Cc: [email-masked]
> Subject: Re: [TLS] TLS 1.2 and hash agility for signatures
>

---

From: Martin Rex <[email-masked]>
Date: Mon, 19 Mar 2007 18:40:03 +0100 (MET)

> supports; e.g. 0x3021300906052b0e03021a05000414 for RSASSA-PKCS1-v1_5

Aren't the RSA-PSS additional parameters included in the algorithm
identifier structure, which results in a non-static Octetstring?
 
-Martin

---

From: <[email-masked]>
Date: Mon, 19 Mar 2007 20:17:08 +0200

Martin Rex wrote:

> > supports; e.g. 0x3021300906052b0e03021a05000414 for 
> > RSASSA-PKCS1-v1_5 with SHA-1.)
> 

Yes and no... the additional parameters are included in the algorithm
identifier structure, but probably a PSS implementation would support
only a couple of different combinations. And those could be hardcoded.

(And I wouldn't expect anyone to really use PSS... but we want 
the signature algorithm agility done right, so we don't need to
revisit this topic in TLS 1.3 :-)

Best regards,
Pasi

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 20 Mar 2007 13:27:37 +0100

> does not specify a single unique allowed algorithm, we need to tell

The Signature structure not only does not specify the hash, it does
not even specify anything about the SignatureAlgorithm.  The
server-side SignatureAlgorithm, of course, is determined by the
ciphersuite, which always is known by both parties.  The client-side
SignatureAlgorithm, however, is only determined by the
ClientCertificateType, which is never explicitly transmitted: there's
just a list of type values sent by the server in the
CertificateRequest, so the client's choice of one of these is meant to
be implied by what it sends in the Certificate message, and
additionally in certain cases by whether or not the it sends a
CertificateVerify message.

I guess it's best to include a ClientCertificateType field into the
client's Certificate message (not the CertificateVerify message since
some methods don't use it):

       struct {
           select (sender_of_this_message) {
              case client:
                  ClientCertificateType certificate_type;
              case server:
           };

           ASN.1Cert certificate_list<0..2^24-1>;
       } Certificate;

(Here I'm using a "select" construction and not a separate
ClientCertificate type since it makes some sense to keep the current
handshake type for this message, and since there's currently a
correspondence between handshake types and structure names.
I.e., using ClientCertificate would either introduce a new
inconsistency in the presentation of the protocol, or require an
otherwise unnecessary new handshake type client_certificate.)

You are right that including an algorithm identifier field into the
Signature type make sense.  I'd prefer to keep this optional since
it's not always needed, since for example the "rsa" case of Signature
really means RSA PKCS#1 v1.5, which does not need the algorithm
identifier.  Any other use of RSA signatures, such as PSS, would
require new ciphersuites and new "ClientCertificateType" values (sort
of a misnomer, since distinct client authentication methods don't
necessarily imply distinct X.509 certificates ...), or possibly other
(extension-based) ways of negotiating the use of PSS or whatever.  If
such ciphersuites, "ClientCertificateType" values, or extensions are
ever defined, that would be the appropriate time to define an
appropriate new case for the Signature structure.

It seems that DSA and ECDSA indeed will be cases where we'll often
need to use such an AlgorithmIdentifier (identifying the signature
type, not just the hash).  I think this is very unfortunate since
really the *certificate* containing an DSA or ECC key should restrict
the key to be used with a single specific signing algorithm (and,
thus, only a single hash function), but since it doesn't look like we
can rely on PKIX imposing such restrictions, we have to adapt to such
flexibility.

> since it also covers signatures outside certs.)

You mean, to indicate hash algorithms in this case (not signature
algorithms)?  I'd prefer using a brief list of identifiers defined in
the TLS specification (which is exactly what HashType is now), to be
interpreted as a hint and not as a complete description of what the
party in question can handle.

(In some cases, depending on the software design, we might have
implementations that can handle certain hash functions for some
signature algorithms but not for others.  We can't put all such
details into a HashType list.  Possibly we could cope with this by
using a list of *signature* AlgorithmIdentifiers, but such a list
easily could become very huge, and still wouldn't solve all problems
related to signature and certificate verification.  This would be a
lot of effort spent on an incomplete solution for a problem that
doesn't really matter that much.  In practice, if signature
verification works, this is usually to a large part because we have CA
procedures that ensure that certificates can be handled by many
clients.  And if signature verification doesn't work, then even if we
can detect this problem in advance through complex negotiation of
capabilities, this often won't buy us much since there's no
alternative certificate available.  We may still be able to continue
the handshake, though, if signature verification is not considered
crucial for the present session.)

If we change the current "Cert Hash Types" extension into a "Signature
Hash Types" extension to be used both by clients and servers, in
addition to including a ClientCertificateType field into the client's
Certificate message and including an optional algorithm identifier
into the Signature type, then I think this would achieve a reasonable
balance between keeping the protocol simple and keeping it flexible.

Bodo

---

From: <[email-masked]>
Date: Tue, 20 Mar 2007 14:55:11 +0200

> some methods don't use it):

Hmmm... why do we need ClientCertificateType in the Certificate 
message, if we also add the algorithm identifier to Signature type 
(also for RSA)?

<snip>
> identifier.  

In today's meeting somebody pointed out that we probably want the
identifier for RSA PKCS# v1.5 as well, since some crypto libraries
export an API that matches the "signature verification operation"
described in RFC 3447 Section 8.2.2. And there you actually need to
know which hash algorithm was used before you start verifying the
signature...

> Any other use of RSA signatures, such as PSS, would require new 
> ciphersuites and new "ClientCertificateType" values (sort
> (extension-based) ways of negotiating the use of PSS or whatever.  

I agree, PSS server certificates would be best handled by new cipher
suites, and PSS client certificates with new client certificate types.

<snip>
> related to signature and certificate verification.  

I was thinking about signature algorithm identifiers; but I do agree
that the list could easily get quite long. 

Best regards,
Pasi

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 20 Mar 2007 14:27:07 +0100

> message, if we also add the algorithm identifier to Signature type 

For the fixed-DH and fixed-ECDH client verification methods, there's
no CertificateVerify message and thus no Signature structure.  The
signature algorithm identifier applies only to client verification
methods that do use signatures.  Currently, fixed-DH and fixed-ECDH
are the only exceptions, and these can easily be detected by just
looking at what messages the client sends (just a Certifcicate --
empty ClientKeyExchange, no CertificateVerify).  This has a somewhat
kludgy feel, though, and new client verification methods may not
have such distinctive patterns.

> know which hash algorithm was used before you start verifying the

Well, I guess this makes sense.  Maybe *looking* at the algorithm
identifier should be made optional then.

Bodo