Subject: [TLS] TLSv1.2 with DSA client cert and key size >1024 bits

From: Martin Rex <[email-masked]>
Date: Mon, 14 Feb 2011 17:48:18 +0100 (MET)

Dear implementors of TLSv1.2,

The use of TLSv1.2 with DSA client certs using key lengths > 1024
as defined by FIPS 186-3 appears slightly underspecified.
I would like to find out what current implementations of TLSv1.2
are doing -- and what they are doing when negotiating a protocol
version less that {0x03,0x03}.

The base protocol spec does not define what to do with a (L=2048,N=224),
(L=2048,N=256) or (L=3072,N=256) DSA key from FIPS 186-3 in a client cert
in TLSv1.1.  rfc4492 Page 20 provides a hint for how to represent
ECDSA signature values with hash algorithms other than SHA-1 but
does not describe a means to indicate to the receiver, which
other hash was actually used.

I think it would be sensible to imply SHA-256 whenever the DSA key
that is used for signature verification, does not allow creation of
SHA-1 based signatures according to FIPS 186-3, but does allow
creation of SHA-256 based signatures.  Avoiding SHA-224 entirely
would facilitate the Server Side verification of the CertificateVerify
handshake message with DSA client certificates using key sizes > 1024
for protocol version < TLSv1.2.

All TLS protocol specification (TLSv1.0->TLSv1.2 & SSLv3) share a
text that is limited to SHA-1 in Section 4.7 Cryptographic Algorihms:

   In DSS, the 20 bytes of the SHA hash are run directly through the
   Digital Signing Algorithm with no additional hashing.  This produces
   two values, r and s.  The DSS signature is an opaque vector, as
   above, the contents of which are the DER encoding of:

       Dss-Sig-Value  ::=  SEQUENCE  {
            r       INTEGER,
            s       INTEGER
       }

The hint from rfc4492 "ECC Ciphersuites for TLS" about SHA/sha_hash not
being limited to SHA-1/20-octets did not make it into TLSv1.2, so the
situation is still somewhat undefined for the TLS protocol versions
that are actually being negotiated and used on the internet.

    http://tools.ietf.org/html/rfc4492#page-20

                                                                 ECDSA
   signatures are generated and verified as described in Section 5.10,
   and SHA in the above template for sha_hash accordingly may denote a
   hash algorithm other than SHA-1. 

There was a change in the representation of a digitally signed element
between TLSv1.2 and TLSv1.1&prior, which avoids the problem of not
really knowing the signature algorithm that was used for (EC)DSA,
in that digital signatures are now explicitly tagged in TLSv1.2:

up to TLSv1.1    http://tools.ietf.org/html/rfc4346#section-4.7

   In digital signing, one-way hash functions are used as input for a
   signing algorithm.
                       A digitally-signed element is encoded as an
   opaque vector <0..2^16-1>, where the length is specified by the
   signing algorithm and key.

TLSv1.2          http://tools.ietf.org/html/rfc5246#section-4.7

   A digitally-signed element is encoded as a struct DigitallySigned:

      struct {
         SignatureAndHashAlgorithm algorithm;
         opaque signature<0..2^16-1>;
      } DigitallySigned;

The latter is building on the definitions from the SignatureAlgorithm
TLSv1.2 extension: 

    http://tools.ietf.org/html/rfc5246#section-7.4.1.4.1

      enum {
          none(0), md5(1), sha1(2), sha224(3), sha256(4), sha384(5),
          sha512(6), (255)
      } HashAlgorithm;

      enum { anonymous(0), rsa(1), dsa(2), ecdsa(3), (255) }
        SignatureAlgorithm;

      struct {
            HashAlgorithm hash;
            SignatureAlgorithm signature;
      } SignatureAndHashAlgorithm;

-Martin

---

From: Wan-Teh Chang <[email-masked]>
Date: Mon, 14 Feb 2011 12:50:31 -0800

The problem isn't limited to DSA client certs.  DSA server certs have
the same problem with DHE_DSS cipher suites.

I believe TLS 1.2 assumes DSA keys are 1024 bits and needs to be
updated for the larger DSA keys specified in FIPS 186-3.

The avoid the need to buffer the handshake messages for the
CertificateVerify message, the hash algorithm should ideally be chosen
so that it can be reused for the verify_data in the Finished message.
But clients with 1024-bit DSA client certs
already need to either buffer the handshake messages or compute their
SHA-1 hash, in addition to their SHA-256 hash for verify_data.

Wan-Teh Chang

---

From: Martin Rex <[email-masked]>
Date: Mon, 14 Feb 2011 23:31:07 +0100 (MET)

> the same problem with DHE_DSS cipher suites.

There are two different issues.

The handshake message hash that goes into the CertificateVerify when
a client certificate is requested and used is orthogonal to DHE_DSS
cipher suites.

For the Handshake message hash, an implementation currently needs:

   sha-1 for SSLv3, TLSv1.0 & TLSv1.1
         and for TLSv1.2 with DSA (L=1024,N=160) client cert

   md5   for SSLv3

   sha-256 for TLSv1.2,
           and for TLSv1.x with DHE_DSS cipher suites and
             server certs with 2048 bits (FIPS 186-3)
           and for TLSv1.x with DSA client certs with 2048 bits (FIPS 186-3)
             certs with 2048 bits

Requiring TLS implementations to also carry along SHA-224 hashes
does not seem to make any sense.

As it is described in FIPS 180-3, SHA-224 is equivalent to SHA-256
and SHA-384 is equivalent to SHA-512 as far as algorithmic strength
and computational requirements are concerned -- in both cases the
shorter hash uses the exact same algorithm, just with an differing
initialization vector and truncation of the final output.

When computing DSA signatures, the two integers "r" and "s" representing
the DSA digital signature are the result of a modulo operation with the
public prime q (see FIPS 186-3 section 4.6).
And when computing the DSA signature with a SHA hash whose size exceeds
the size of the public prime q, the hash is truncated first
(see FIPS 186-3, Section 4.3, 2nd paragraph of page 16).

Something similar may apply to ECDSA digital signatures.  Hashes may
need to be truncated with ECDSA as well (FIPS 186-3, Section 6.1.1,
top of page 28).  I'm not into crypto math and don't have X9.62
nor Schneiers Applied Cryptography around, so don't know what exact
modulo operation applies to r&s for ECDSA (it's still r&s according
to rfc4492).

So when sha-224 was added (late) into TLSv1.2 (rfc5246) somewhere
after March 04, 2008
     http://www.ietf.org/mail-archive/web/tls/current/mail10.html

it newly created a problem rather than solving one.

While the "SignatureAndHashAlgorithm" tag should have applied only
to the digital signatures created by TLS itself (in the KeyExchange
and CertificateVerify handshake message, the defintion of the
changed PDU for CertificateRequest says this:

   -  Any certificates provided by the client MUST be signed using a
      hash/signature algorithm pair found in
      supported_signature_algorithms.

which IMHO is a pretty bad idea.  It is an Anti-Agility requirement,
precluding the PKI implementation outside of TLS that is doing the
certificate path validation from evolving independent of TLS.
This restriction is especially silly considering that this information
can not even be conveyed if a protocol version below TLSv1.2 is
negotiated.  It is adding an interoperability impairment that did not
exist in prior versions of TLS...

> updated for the larger DSA keys specified in FIPS 186-3.

TLSv1.2 (rfc5246) does have a reference to a FIPS 186-3 draft.

IMHO rather than rushing sha-224 into TLSv1.2 and creating pain and
confusion, the above mentioned new restriction on signatures within
certificates should have been removed from 7.4.4 CertificateRequest.

> SHA-1 hash, in addition to their SHA-256 hash for verify_data.

It is extremely rare for TLS clients and servers to actually negotiate
TLSv1.2, and I currently do not expect this to change significantly
during the next couple of years.

There seem to be two reasons for this:

  - at least one vendor sees a performance problem with enabling
    TLSv1.2 for the server by default

  - clients proposing ClientHello.client_version  TLSv1.1{0x03,0x02}
    instead of TLSv1.0 {0x03,0x01} experience an increased amount
    of handshake failures, and it becomes even worse when proposing
    TLSv1.2{0x03,0x03}

Personally, I think it would be reasonable to define/standardize
a workaround for the latter interop problem through (ab)use of
two special cipher suite values.  The approach that a number of
Web Browsers are currently doing, trying reconnect fallback after
failed handshakes, is an application-level workaround instead
of a TLS-level fix for a genuine TLS interop problem.

-Martin

---

From: Michael D'Errico <[email-masked]>
Date: Mon, 14 Feb 2011 15:21:34 -0800

>     TLSv1.2 for the server by default

This is not a problem with TLS 1.2 itself, but of that vendor's
implementation of it.  My server shows virtually no difference in
throughput for any SSL/TLS version, though SSL3 is a tiny bit
slower than the rest.  This could be explained by the slightly
more complicated MAC computation in SSLv3 vs HMAC in TLS.

Mike

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 15 Feb 2011 09:40:04 +0100

> other hash was actually used.

Currently gnutls uses SHA-1 on versions prior to TLS 1.2. For TLS 1.2
it uses a hash that corresponds to the length of q (i.e. chooses between
SHA-1, SHA-224 and SHA-256).

regards,
Nikos

---

From: Dr Stephen Henson <[email-masked]>
Date: Tue, 15 Feb 2011 14:19:23 +0000

> version less that {0x03,0x03}.

OpenSSL uses SHA-1 for TLS v1.1 and below. OpenSSL doesn't currently support TLS
v1.2.

As I mentioned elsewhere FIPS 186-3 also includes comments about RSA (section
5). For example it limits keys sizes to 1024, 2048 and 3072 bits. 4096 bit RSA
keys are not that uncommon and oddball keylengths like 2047 bits crop up quite
often too.

There is a similar comment about SHA-1 though not an outright prohibition:

"A hash function that provides a lower security strength than the security
strength associated with the bit length of the modulus ordinarily should not be
used, since this would reduce the security strength of the digital signature
process to a level no greater than that provided by the hash function."

Using SHA-2 algorithms isn't possible in TLS 1.1 and earlier with RSA as they
hard code the SHA1+MD5 signature.

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: Martin Rex <[email-masked]>
Date: Tue, 15 Feb 2011 17:18:58 +0100 (MET)

Dr Stephen Henson wrote:
> 
>  [...] a similar comment about SHA-1 though not an outright prohibition:
> 
> "A hash function that provides a lower security strength than the
> security strength associated with the bit length of the modulus
> ordinarily should not be used, since this would reduce the security
> strength of the digital signature process to a level no greater
> than that provided by the hash function."

It's true that the wording in FIPS 186-3 section 4.2 (page 16 2nd paragraph)
uses "should not" (while the same description for ECDSA uses "shall not").

However, this looks to me like a transitional exception that might have ended
on 31.12.2010.  In the same section, last paragraph on page 15, it reads:

  Both the security strength of the hash function used and the
  security strength of the (L, N) pair shall meet or exceed the
  security strength required for the digital signature process.

> 
> Using SHA-2 algorithms isn't possible in TLS 1.1 and earlier with RSA
> as they hard code the SHA1+MD5 signature.

I agree.  The hash algorithm(s) in the digital signature of the
KeyExchange and CertificateVerify handshake messages prior
to TLSv1.2 is implied and fixed.

Support for longer DSA keys with hashes from the SHA-2 family will
require code changes to the installed base, where some may wonder
why not implementing TLSv1.2.  One of the problem appears to be
the default reluctance to offer/use TLSv1.2 even by those implementations
that already contain the code and the resulting TLS handshake failures
with non-marginal parts of the installed base of servers for clients
proposing TLSv1.2 through ClientHello.client_version.

-Martin

---

From: Dr Stephen Henson <[email-masked]>
Date: Tue, 15 Feb 2011 16:42:52 +0000

> uses "should not" (while the same description for ECDSA uses "shall not").

It also says:

"In addition, an RSA digital signature key pair shall not be used for other
purposes (e.g., key establishment)."

I can't imagine many servers using two distinct certificates for ephemeral and
static RSA ciphersuites, even is the server software supports it.

Steve.

---

From: Martin Rex <[email-masked]>
Date: Tue, 15 Feb 2011 18:01:42 +0100 (MET)

Dr Stephen Henson wrote:
> [FIPS 186-3] also says:

I noticed that as well.  :)

So I looked at the next best SSL Server cert (happened to be issued
by Thawte SGC) and noticed that it does not contain a KeyUsage
extension (only ExtendedKeyUsage and BasicConstraints cA=FALSE).

static RSA ciphersuites need KeyUsage "keyEncipherment", and
DHE_RSA would need "digitalSignature".  But asserting both in a
cert seems literally incompatible with FIPS 186-3.  

I also noticed the distinction between PKCS1-v1.5 and PKCS1-PSS signatures,
and that RSA keys should be used for only one of the two for their entire
lifetime.  While it is sensible in general to distinguish credentials for
online authentication and credentials for longterm digital signatures,
PKCS1-v1.5 is hardwired into SSLv3 and all current versions of TLS.
I didn't see reference to or definition of an ExtendedKeyUsage OID
to recognize/distinguish RSA PKCS1-PSS keys in FIPS 186-3, which
looks somewhat inconsequential for the v1.5/PSS issue.

-Martin

---

From: "Kemp, David P." <[email-masked]>
Date: Tue, 15 Feb 2011 12:54:11 -0500

The wording could probably use clarification - a "digital signature" key
pair is used by an entity to bind its identity to a piece of
information.  If the only external result of an ephemeral ciphersuite is
an authenticated shared key, then the RSA key is being used for the
purpose of key establishment even if a signature algorithm is used
internally by the key establishment process.

If a client purported to have data signed by a server as a result of
having performed a key exchange using a key establishment certificate,
it would be misrepresenting the results of the key exchange.  No relying
party would accept as valid data "signed" using a key establishment
certificate, protecting the server from unintended consequences.

Dave

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Dr
Stephen Henson
Sent: Tuesday, February 15, 2011 11:43 AM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [TLS] TLSv1.2 with DSA client cert and key size >1024 bits

It also says:

"In addition, an RSA digital signature key pair shall not be used for
other
purposes (e.g., key establishment)."

I can't imagine many servers using two distinct certificates for
ephemeral and
static RSA ciphersuites, even is the server software supports it.

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.
_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: Martin Rex <[email-masked]>
Date: Thu, 17 Feb 2011 00:35:00 +0100 (MET)

> more complicated MAC computation in SSLv3 vs HMAC in TLS.

The more I think about it, the more I believe it is, in fact, a
design flaw in TLSv1.2 responsible for a handshake performance issue
(at least when a client certificate is requested).

While the PRF was changed from SSLv3->TLSv1.0, there was no change to
the CertificateVerify handshake message.  So for creating and
verifying a CertificateVerify handshake message, two hashes must
be maintained over all handshake messages:  MD5 + SHA1.

With TLSv1.2, if a server does not want to artificially limit the
signature algorithms on acceptable client certificates, it must
send a long list of acceptable combinations

(sha1,rsa), (sha1,dsa), (sha256,rsa), (sha384,rsa), (sha512,rsa),
(sha224,dsa), (sha256,dsa), ...

So unless both, server and client must either hold on to all handshake
messages up to CertificateVerify or carry along hash contexts for all
of the possible algorithms.

Compare:
   SSLv3, TLSv1.0/1.1  md5 + sha1
   TLSv1.2             md5 + sha1 + sha224 + sha256 + sha384 + sha512

If you look at this list, look at how TLS uses hashes for digital
signatures and think about the algorithmic relationships between
sha224&sha256 and between sha384&sha52, then sha224 and sha384
are utterly useless fifth and sixth wheel on the TLS cart.
For TLS itself, sha256 -- or maybe even sha256 alone would have
been PERFECTLY sufficent, and a LOT less work.

What I also don't understand is the idea behind "default signature
algorithms".  For implementing TLSv1.2, SHA-256 _must_ be supported,
but unless explicitly negotiated with the TLS SignatureAlgorithm
extension, SHA-256 appears not allowed to be used for CertificateVerify.

That would mean, when TLSv1.2 is negotiated, but no SignatureAlgorithms
extension exchanged, the resulting signature with an RSA client cert
in CertificateVerify no longer uses MD5+SHA-1 as in TLS up to v1.1,
but _only_ SHA-1 (which slightly weakens that signature compared to
prior protocol versions...).  The use of SHA-256 is prohibited!??!

Weird, really.

-Martin

---

From: Michael D'Errico <[email-masked]>
Date: Wed, 16 Feb 2011 16:03:30 -0800

I see the potential problem.  For me, though, I just hold onto all of
the handshake messages until the handshake concludes.  It may use a bit
more memory for a short amount of time, but the issue you raise is
completely avoided.  Call it a space <-> code complexity trade-off.

In TLS 1.2, a CertificateRequest message is where the server tells the
client which signature algorithms are acceptable.  I don't think it's
allowed to be an empty list, but if it is, the sensible thing to do is
to assume the same hash functions are supported as previous versions
which didn't have that parameter.  In other words choose rsa/sha1,
rsa/md5 or dsa/sha1.

This issue would have been avoided if the supported_signature_algorithms
extension was symmetric and allowed the server to specify its list of
algorithms in a ServerHello extension.  Alas, that was not the design
we ended up with.

Mike

---

From: Wan-Teh Chang <[email-masked]>
Date: Wed, 16 Feb 2011 17:31:13 -0800

> prior protocol versions...).  The use of SHA-256 is prohibited!??!

I think you're right.  RFC 5246 Section 7.4.1.4.1 seems to say that
{sha1,rsa} is the default RSA signature algorithm.

I guess the solution is for a TLS 1.2 client to always send the
signature_algorithms extension, and for a TLS 1.2 server to use
a non-empty supported_signature_algorithms field in the
Certificate Request message.

Alternatively, we can amend RFC 5246 to change the default
RSA signature algorithm to {sha256,rsa} .  It seems that anything
that uses MD5+SHA-1 in TLS 1.0 and 1.1 should use SHA-256
by default in TLS 1.2, for consistency.

Wan-Teh Chang

---

From: Yoav Nir <[email-masked]>
Date: Thu, 17 Feb 2011 08:07:08 +0200

> by default in TLS 1.2, for consistency.

If you change that, it becomes TLS 1.3. This is a non-backwards-compatible change in default behavior.

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Thu, 17 Feb 2011 09:47:08 +0100

On 02/17/2011 01:03 AM, Michael D'Errico wrote:
> I see the potential problem.  For me, though, I just hold onto all
> of the handshake messages until the handshake concludes.  It may use
> a bit more memory for a short amount of time, but the issue you raise
> is completely avoided.  Call it a space <-> code complexity
> trade-off.

Indeed. There is no other way to correctly implement TLS 1.2 except
from holding a copy of all the handshake messages. This is problematic
when converting an implementation of TLS 1.0 or 1.1 to that, since
those protocols only required to hold the state of 1 or 2 running hashes.

This is also not easy to fix in TLS 1.3. Even if TLS 1.3 only
requires to hold the state of a single hash, implementations
must be prepared to hold the entire state just in case TLS 1.2
is negotiated.

> This issue would have been avoided if the
> supported_signature_algorithms extension was symmetric and allowed
> the server to specify its list of algorithms in a ServerHello
> extension.  Alas, that was not the design we ended up with.

That was a bad design decision in TLS 1.2 (if we assume that not caching
all messages was a requirement).

regards,
Nikos

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 17 Feb 2011 11:35:28 +0200

> those protocols only required to hold the state of 1 or 2 running hashes.

Is that really true?. My memory from the discussions and briefly
refreshed by looking at the
doc is that you only need to hold the messages until you see the
ServerHello at which point
you know the PRF and so you can just start storing hashes.

Best,
-Ekr

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Thu, 17 Feb 2011 10:49:06 +0100

> you know the PRF and so you can just start storing hashes.

Note that you're talking about the hashes required for the finished
messages and you're correct on this note. However there is also the
hash required for the CertificateVerify message. If the server requests
a client certificate then it has to store all messages up to (but not
including) the CertificateVerify message.
That is because he cannot possibly know which signature algorithm
hash the client will use.

In TLS 1.0 and 1.1 the same hashes as the ones in the finished
messages were being used, so that was not an issue.

regards,
Nikos

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 17 Feb 2011 12:54:35 +0200

> hash the client will use.

Agreed. I can't recall if we discussed this when this feature was being designed
for 5246 but ISTM that the only way to have this work that didn't have
this property would be for the client to offer all his certificates
up-front and the
server to select one, since it's possible that each cert comes with a specific
hash algorithm tied to it.

-Ekr

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Thu, 17 Feb 2011 12:17:54 +0100

> hash algorithm tied to it.

To which PKIX certificate field are you referring to?

regards,
Nikos

---

From: "Yngve N. Pettersen (Developer Opera Software ASA)" <[email-masked]>
Date: Thu, 17 Feb 2011 13:54:32 +0100

> hash algorithm tied to it.

How about removing the need to calculated the verify message based on a  
specific hash of the handshake message?

Currently the verify message is defined as

       struct {
            digitally-signed struct {
                opaque handshake_messages[handshake_messages_length];
            }
       } CertificateVerify;

How about changing that to this?

       struct {
            digitally-signed struct {
                 PRF(master_secret, verify_label, Hash(handshake_messages))
                           [0..f(Cert_Hash)-1];
            }
       } CertificateVerify;

This would remove the need to store all the handshake messages, or manage  
multiple hashes of the same data, since the handshake-hash would take care  
of that.

Using the PRF means that we can generate a string that is of sufficient  
length for each method, although an alternative if one think that is too  
complex, or generally unnecessary, is to just use Hash(handshake_messages).

A possible issue is how this would affect security if the Cert_Hash method  
is much more secure than the Hash method. My current opinion is that this  
can be handled by using f(Cert_Hash) to provide a sufficiently long PRF,  
unless there are issues I am unaware of with such a solution. I'll leave  
that to the members for experienced in cracking crypto constructs.

Of course, making this change requires a new TLS protocol version.

-- 
Sincerely,
Yngve N. Pettersen
********************************************************************
Senior Developer		     Email: [email-masked]
Opera Software ASA                   http://www.opera.com/
Phone:  +47 23 69 32 60              Fax:    +47 23 69 24 01
********************************************************************

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 17 Feb 2011 15:39:58 +0200

> To which PKIX certificate field are you referring to?

I'm not. I'm talking about environments where (for instance) some of
your keys are in
hardware and so, can only be used to with a specific hash algorithm.
It's not incredibly
common, but I have seen it.

-Ekr

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Thu, 17 Feb 2011 15:45:55 +0100

On Thu, Feb 17, 2011 at 1:54 PM, Yngve N. Pettersen (Developer Opera
>                PRF(master_secret, verify_label, Hash(handshake_messages))

This is a nice idea for 1.3. (I'd replace Cert_Hash with selected_hash though).

regards,
Nikos

---

From: Martin Rex <[email-masked]>
Date: Fri, 18 Feb 2011 20:28:29 +0100 (MET)

Eric Rescorla wrote:
> 
> Nikos Mavrogiannopoulos <[email-masked]> wrote:
> > If the server requests a client certificate then it has to store
> > all messages up to (but not including) the CertificateVerify message.
> Agreed. I can't recall if we discussed this when this feature was being
> designed for 5246 but ISTM that the only way to have this work that
> didn't have this property would be for the client to offer all his
> certificates up-front and the server to select one, since it's
> possible that each cert comes with a specific hash algorithm tied to it.

I am quite confused by a few issues in TLSv1.2 / rfc-5246 about hash
and signature algorithms.

In particular, that TLSv1.2 forces TLS-proprietary digital signatures
from the TLS handshake messages ServerKeyExchange and CertificateVerify
into the same single algorithm negotiation with digital signatures
on certificates appears to create significant new problems.

rfc-5246, 7.4.2  Server Certificate  last paragraph on page 49
   http://tools.ietf.org/html/rfc5246#page-49

   If the client provided a "signature_algorithms" extension, then all
   certificates provided by the server MUST be signed by a
   hash/signature algorithm pair that appears in that extension.  Note
   that this implies that a certificate containing a key for one
   signature algorithm MAY be signed using a different signature
   algorithm (for instance, an RSA key signed with a DSA key).
?                                                               This is
?  a departure from TLS 1.1, which required that the algorithms be the
?  same.

I searched TLSv1.1 (rfc4346) from top to buttom but did NOT find any
requirements about signature algorithms of certificates in that spec.
I have also not noticed any such restrictions in TLS implementations
I looked at.

So I created a DSA-rootCA, an rsa-2048 server cert, started a TLSv1.0
with this and WindowsXP, Firefox3 an OpenSSL all happily communicate
with it.

So this part of rfc-5246 purports to solve a problem that actually
does not exist in earlier versions of TLS.  The "solution" that
TLSv1.2 alleges to provides looks more like a cumbersome
limitation to me.  While there is zero problem of using certificate
chains with arbitrary mixtures of signature algorithms in TLSv1.1
and prior, this doesn't work anymore when negotiating TLSv1.2,
in particular for signature algorithms which can not be represented
with the code points of TLSv1.2.

TLS implementations that do not want to hang on to carry along all
handshake messages may want the list of hashes permitted for the
"digitally signed" construct in ServerKeyExchange and CertificateVerify
to be as small as possible, while they may want to remain a liberal
as possible about digital signature algorithms on certificates,
similar to all version of TLS up to v1.1.

It's unclear for me what motivated conflating two quite contradictory
objectives into a single protocol element (the SignatureAlgorithm list
in the ClientHelloExtension SignatureAlgorithm applying to both
ServerCertificate and ServerKeyExchange handshake messages,
and the list of SignatureAlgorithms in CertificateRequest applying
to both ClientCertificate and CertificateVerify handshake messages.

As a result of this, any PKIs with less common digital signature
algorithms on path certificates that may have worked perfectly fine
with SSLv3, TLSv1.0 and TLSv1.1, and continue to work with an
implementation of TLSv1.2 that negotiates only v1.0 or v1.1 are
required to fail by the TLSv1.2 spec when TLSv1.2 is negotiated,
because of a lack of code points to represent digital signature AlgIDs
plus the complete lack of knowledge about the AlgIDs supported
in the PKI implementation within the architecturally independent
TLS protocol stack.

A year ago we started shipping support for GOST ciphersuites based on this
proposal:

      http://tools.ietf.org/html/draft-chudov-cryptopro-cptls-04

in our (at that time OEM) implementation of TLSv1.0, with the
GOST crypto algorithms provided to the TLS stack through a plugin-
interface to a third-party (certifiable) GOST crypto plugin.

A very similar capability exists in Windows XPsp2, where the GOST cipher
suites can be used with SChannel and MSIE6 after installation
of an adequate CryptoCSP, although XP's SChannel is an implementation
of TLSv1.0 with _no_ TLS extensions.

I believe there exists more flexibility in TLSv1.0/v1.1 architecture
than rfc5246 asserts.

-Martin

---

From: Juho Vähä-Herttua <[email-masked]>
Date: Sat, 19 Feb 2011 00:39:56 +0200

> with the code points of TLSv1.2.

This discussion has been going on for quite long, but I just want to mention that I support Martin here and I don't think I have seen a good response yet. I found the same issue a bit weird when I was going through the TLSv1.2 specification, but it wasn't relevant at the time so I just ignored and forgot it.

Forcing the TLS implementation to buffer all handshake messages is one thing that probably a performance problem in TLSv1.2, but it's not a compatibility issue and as someone said fixing it would require releasing TLSv1.3. However I don't see ANY sensible reasons why TLS would care about which signature algorithm is used for signing the actual certificate. As long as the certificate contains the keys necessary to sign the key exchange it should be fine just like it was before.

Yes, it might be possible for a client to for example only support one single hash and one single signature algorithm, which is most likely a combination included in signature_algorithms. In that case, I would support that the server SHOULD choose the certificate chain according to the sent signature_algorithms if possible. However if there is no such certificate chain available, it MUST continue the handshake by sending some valid certificate. The server has no way to know if the client can verify certificate chains outside the defined TLS signature algorithms, therefore it would be plain stupid for the server to abort the handshake just because it has a certificate which is signed with an algorithm not supported by TLS. (especially if both sides can handle it)

I don't think changing this from MUST to SHOULD would cause major compatibility issues, because for TLSv1.0 and TLSv1.1 the clients need to prepare for any kinds of certificates anyway. If someone has actually written code that rejects certificates that don't match the sent signature_algorithms it might cause an error, has anyone on this list written that kind of code or seen it anywhere? Personally I find the meddling with certificate signature hash and type annoying enough that I am inclined to ignore it, even if that means incompatibility....

Juho

---

From: Michael D'Errico <[email-masked]>
Date: Fri, 18 Feb 2011 17:06:57 -0800

The point of the signature_algorithms extension is to permit a graceful
upgrade of server certificates to using better than SHA-1 hash functions.
You couldn't just suddenly switch your server cert to one signed with
RSA/SHA-256 and expect every client to cope.  It would certainly cause
problems for some.

To benefit from the extension, you would need to have two concurrent
server certificates: one signed with RSA/SHA-1, and another signed with
RSA/SHA-256.  Then based on the signature algorithms presented by the
client, your TLS code would choose the best one.

My server actually does this and you can try it out:

     https://www.mikestoolbox.net

If you connect using TLS 1.2 and tell it you support RSA/SHA-256, you
will get back a server certificate signed with that algorithm. Otherwise
you'll get the one signed with RSA/SHA-1.

Mike

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 19 Feb 2011 15:12:06 +1300

Martin Rex <[email-masked]> writes:

>The more I think about it, the more I believe it is, in fact, a design flaw
>in TLSv1.2 responsible for a handshake performance issue (at least when a
>client certificate is requested).

Yes.  I pointed this out a long time ago, you either have to cache all
handshake messages or run multiple hashes in parallel until you know which one
you need to settle on.  Either option leads to performance suckage.  From
memory the response was "well, yeah, you just need to do that then".

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 19 Feb 2011 15:16:06 +1300

Nikos Mavrogiannopoulos <[email-masked]> writes:

>This is also not easy to fix in TLS 1.3. Even if TLS 1.3 only requires to
>hold the state of a single hash, implementations must be prepared to hold the
>entire state just in case TLS 1.2 is negotiated.

But you know at the first message whether you're going to continue with TLS
1.2 or 1.3.  If you only start the hashing after the first handshake packet
then you only need to use the one hash that both sides have agreed on.  Heck,
you can even fix it right now with an extension (which is what my code does
iff it finds another copy of my code at the other end).

>That was a bad design decision in TLS 1.2 (if we assume that not caching all
>messages was a requirement).

Can I say "I toldja so" now?

Peter.

---

From: Martin Rex <[email-masked]>
Date: Sat, 19 Feb 2011 04:52:21 +0100 (MET)

> iff it finds another copy of my code at the other end).

What does your private extension look like?

I also think it should be fairly easy to fix with a simple TLS extension
that negotiates _only_ the hash that is going to be used for the
digitalSignature struct in ServerKeyExchange or CertificateVerify.

When the TLS extension carries a list of _only_ hash algorithms,
SHA-256 is always implied by the extension (need not be listed,
it will be the mandatory to implement hash).  Client can propose
other hashes, server will confirm exactly the one hash that
is going to be used (instead of SHA-1) for those ciphersuites
that do not imply/require something else (e.g. GOST).

Such an extension could be used with TLSv1.0 and TLSv1.1 as well
and would make the FIPS 186-3 DSA >1024 bit signatures work
as well as ECDSA signatures (rfc-4492) with SHA-256.

-Martin

---

From: Marsh Ray <[email-masked]>
Date: Fri, 18 Feb 2011 23:21:14 -0600

On 02/18/2011 08:12 PM, Peter Gutmann wrote:
>
> you either have to cache all
> you need to settle on.  Either option leads to performance suckage.

It seems like the bulk of the data in a handshake is in the certs, 
mostly sent by the server.

So one server-side optimization might be to buffer all the handshake 
messages /except/ the server's fixed certs. You can make a guess from 
the most common hashes and run one or two in parallel. You could 
reconstruct the full handshake data if you guess wrong.

More unfortunate complexity. :-(

It's ironic to the point of being sub-optimal that endpoints are 
expected to bear the cost of running multiple hashes over the data - 
just to then throw away half the results.

I saw somewhere NIST just standardized truncated SHA-512 variants. Isn't 
choice wonderful?

- Marsh

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 19 Feb 2011 20:24:24 +1300

>What does your private extension look like?

Just an I-am-here for my own code, which imples only SHA-256 will be used and
there's no need to do any other type of hashing (it also implies some other
things that allow shortcuts in processing).

>I also think it should be fairly easy to fix with a simple TLS extension that
>negotiates _only_ the hash that is going to be used for the digitalSignature
>struct in ServerKeyExchange or CertificateVerify.

Yup, that would be the more general way of doing it, the client provides a set
of choices and the server picks the one that it wants, so the client has to
cache at most one message and the server none.

>Such an extension could be used with TLSv1.0 and TLSv1.1 as well and would
>make the FIPS 186-3 DSA >1024 bit signatures work as well as ECDSA signatures
>(rfc-4492) with SHA-256.

Yup, it would certainly make the handshake less painful.

Peter.

---

From: Juho Vähä-Herttua <[email-masked]>
Date: Sat, 19 Feb 2011 10:40:59 +0200

> client, your TLS code would choose the best one.

Yes, but even in this case I think it would make much more sense to have the requirement as SHOULD and not MUST. Because if all the server has is RSA/SHA-1 and the client is requesting RSA/SHA-256, I think it's much better that the server will continue with RSA/SHA-1 and then the client can fail if it doesn't like it. How does your implementation work by the way if the requested SHA/SHA-256 is not found? I expect you have a client implementation as well, does it check that all the server certificate signatures match the signature_algorithms extension sent in ClientHello and fail if not?

I think it's ok to use signature_algorithms as a recommended list of algorithms and then fall back to locally configured preference if that is not found, worst case is that the handshake fails, but it would fail anyway if no suitable certificate is found... 

Juho

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Sat, 19 Feb 2011 09:57:02 +0100

> client, your TLS code would choose the best one.

It's pretty bad that a single extension is being used for two
distinct use-cases[0]. The use cases are:
* Negotiate which signature algorithms to use for Server Key Exchange,
and Certificate Verify messages.
* Specify the signature algorithms allowed by a certificate sent
by the server.

There is no reason to assume that these are related. The first
use-case applies to the server and client since they are the
ones doing the signing. On this use case a reply to this
extension with the selected algorithm is required to avoid
caching all messages up to the point of signing.

The latter use-case is relevant to the client only, and says,
I don't accept a certificate that is not signed with any
of these algorithms. The server however obtains his
certificate already signed through a 3rd party (a CA), so there
is little to do in the general case.  This use-case does
not require a reply to the extension from the server.

I think that those extensions could be split into two to
account for the different use-cases.

regards,
Nikos

[0]. What if I have a security module doing TLS that
supports only RSA-SHA256 for signatures, but I have
no restriction for the verification of the certificates
since this is done outside of the module?

---

From: Michael D'Errico <[email-masked]>
Date: Sat, 19 Feb 2011 01:44:27 -0800

> Yes, but even in this case I think it would make much more sense to have the requirement as SHOULD and not MUST. Because if all the server has is RSA/SHA-1 and the client is requesting RSA/SHA-256,…

Originally I made the server lenient; if there was no suitable certificate
chain, then it would choose the "best" match and hope the client would
accept it.

But then I got a bug report from someone who suggested that the server
should abort the handshake if there isn't a perfect match.  Initially I
disagreed, but their logic makes sense: if the client was willing to
accept a certificate signed with RSA/SHA-1, then it would have included
that algorithm in the list.  Since it didn't (and in this case the client
only wanted ECDSA certificates which I don't support yet), it was causing
the client trouble.

I'm pretty sure my client code is still lenient, but it's been a while
since I looked at that part of it.

Mike

---

From: Juho Vähä-Herttua <[email-masked]>
Date: Sat, 19 Feb 2011 11:57:09 +0200

> only wanted ECDSA certificates which I don't support yet), it was causing

The bug report makes sense in a way, because that's what the TLSv1.2 RFC currently says. However, I don't understand how it could cause the client any extra trouble, because it has to validate the certificate it is getting from the server anyway and abort the handshake. If sending the wrong certificate type would somehow crash the client, it would be an easy attack for anyone interested. Do you remember if they mentioned more precisely about what kind of trouble it caused?

The logic you mentioned doesn't really make sense to me, because as mentioned before the client might be willing to accept a certificate signed with RSA/SHA-1 but doesn't accept key exchange signed with RSA/SHA-1. Also as Martin has brought up, there are some signature combinations not supported by TLS at all, which the client has no possibility to put on the signature_algorithms.

So to try to conclude somehow, defining the certificate signature requirements as SHOULD instead of MUST would be a minor quick fix that would allow the above-mentioned lenient method. It would still allow the client to send a preference for certain signature algorithms and wouldn't fail any more handshakes than are already failed (assuming clients are properly implemented), making it pretty compatible. Separating the certificate selection signature algorithms and key exchange signature algorithms as separate fields would be a proper fix, but would need a new extension definition. Since the extension definition is included in TLSv1.2 itself and the change is not compatible with existing implementations, I suppose it would require TLSv1.3.

Juho

---

From: "Kyle Hamilton" <[email-masked]>
Date: Sun, 20 Feb 2011 16:36:07 -0800 (Pacific Standard Time)

> Forcing the TLS implementation to buffer all handshake messages is one thing that probably a performance problem in TLSv1.2, but it's not a compatibility issue and as someone said fixing it would r…

Because TLS is the layer where communications policies are negotiated.  The client is informing the server that (e.g.) it doesn't accept MD5 as a valid hash algorithm for realtime communication.  If it doesn't accept it for realtime communication, there is also no reason to accept it for an offline proof -- because an attacker has that much more time to find a preimage.

> Yes, it might be possible for a client to for example only support one single hash and one single signature algorithm, which is most likely a combination included in signature_algorithms. In that c…

Two reasons why this is inappropriate.  First, if the server doesn't have a certificate chain the client will accept, it doesn't need to waste the bandwidth (it doesn't need to broadcast the server's details to someone who won't accept them anyway).  Second, TLS already specifies a valid unauthenticated mode.  The only reason why unauthenticated modes are unpopular is because of the commonly-held view of "if you don't know who you're talking to, what's the point?"

-Kyle H

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Mon, 21 Feb 2011 09:42:18 +0100

On Mon, Feb 21, 2011 at 1:36 AM, Kyle Hamilton <[email-masked]> wrote:
>> Forcing the TLS implementation to buffer all handshake messages is one
>> thing that probably a performance problem in TLSv1.2, but it's not a
>> compatibility issue and as someone said fixing it would require releasing
>> TLSv1.3. However I don't see ANY sensible reasons why TLS would care about
>> which signature algorithm is used for signing the actual certificate. As
>> long as the certificate contains the keys necessary to sign the key exchange
>> it should be fine just like it was before.
> Because TLS is the layer where communications policies are negotiated.  The
> client is informing the server that (e.g.) it doesn't accept MD5 as a valid
> hash algorithm for realtime communication.  If it doesn't accept it for
> realtime communication, there is also no reason to accept it for an offline
> proof -- because an attacker has that much more time to find a preimage.

Actually TLS negotiates things related to the TLS connection. The whole
communication policy is something TLS shouldn't be concerned with.
You say that the certificate signature algorithms are important enough
to be negotiated with TLS, I would add that not only signature algorithms,
but also the key length of the certificate, and even the issuing date of
the certificate and the type of the SubjectAlternative name. This is perfectly
valid under your assumption that TLS should handle this stuff.

Fortunately TLS left all the "communication policy" parts that do not
concern TLS (i.e. details of certificates), outside its negotiation. The
signatureAlgorithms was the first extension to negotiate something that
is not relevant for the TLS protocol.

> Two reasons why this is inappropriate.  First, if the server doesn't have a
> certificate chain the client will accept, it doesn't need to waste the
> bandwidth (it doesn't need to broadcast the server's details to someone who
> won't accept them anyway).

Well, given the way certificates are being used today, that extension cannot
really do much. A server will not request a new certificate from a CA,
just because a
client added the signatureAlgorithms extension in his clientHello and requested
SHA-224.

regards,
Nikos