Subject: [TLS] Remove signature algorithms from cipher suites in 1.3

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Tue, 23 Dec 2014 04:04:46 +0100

Dear WG,

This topic has been brought up in previous discussions but, following 
private discussion with ekr, I would like to bring it up again.

The current draft of TLS 1.3 relies exclusively on signatures to prove 
ownership of private keys in certificates, dropping support for static 
DH shares in certificates. Furthermore, it mandates support of a 
dedicated negotiation mechanism for signature algorithms. This 
negotiation is a bit asymmetric, since the client sends its supported 
pairs of algorithm and hash function in the "signature_algorithms" 
extension while the server uses the "supported_signature_algorithms" 
field of the CertificateRequest message (I won't elaborate any more on 
this topic but it may be worth thinking about).

In this design, keeping the legacy of including the signature algorithm 
to be used in the ServerCertificateVerify message within the selected 
cipher suite name can be a burden to the modularity and extensibility of 
the protocol, since adding support for new signature algorithms comes at 
the cost of an exponential increase in the length of the list of cipher 
suites sent by the client, even though the security guarantees of the 
handshake are now fully modular w.r.t authentication goals achieved by 
certificate and signatures.

The tensions between cipher suite and signature algorithm negotiation 
already existed in 1.2 and it led to oddities in the protocol, such as 
the inability to use FF-DHE authenticated by ECDSA, even though there 
isn't anything inherently wrong with this combination. The following 
paragraph, taken from the current 1.3 draft, is another instance of this 
awkwardness:

"If the client has offered the "signature_algorithms" extension, the 
signature algorithm and hash algorithm MUST be a pair listed in that 
extension. Note that there is a possibility for inconsistencies here. 
For instance, the client might offer DHE_DSS key exchange but omit any 
DSA pairs from its "signature_algorithms" extension. In order to 
negotiate correctly, the server MUST check any candidate cipher suites 
against the "signature_algorithms" extension before selecting them. This 
is somewhat inelegant but is a compromise designed to minimize changes 
to the original cipher suite design."

Hence, I am proposing to create a pull request that includes the 
following changes:

- Any new cipher suite introduced from version 1.3 onwards MUST NOT 
contain any signature algorithm name (e.g. 
ECDHE_CHACHA20_POLY1305_SHA256). Keeping a hash algorithm even for AEAD 
ciphers remains necessary to determine the PRF to use;
- For compatibility with previous protocol versions, existing cipher 
suite names are preserved; however, servers MUST NOT select any cipher 
suite that includes a signature algorithm other than RSA in a 1.3 handshake;
- The server must use one of the client's supported signature algorithms 
in its CertificateVerify message. The precise algorithm used may depend 
on the client's indicated preferences and on the server's policy (in the 
spirit of current cipher suite negotiation). All certificates in a chain 
MUST also be signed with signature algorithms supported by the client. 
The same requirements apply even if a pre-1.3 cipher suite (such as 
ECDHE_RSA_AES256_GCM_SHA384) was selected: the algorithm in the cipher 
suite name is ignored.

Do note that there are several possible alternatives to the propositions 
above, and I am not set on any particular choice. For instance, it may 
be easier to forbid all pre-1.3 cipher suites and create a fresh list.

Even though these changes should be straightforward to understand, it 
appears that they would require significant edits to many parts of the 
current draft, which is why I would like to see if a consensus could 
emerge on this question before proceeding with the necessary work on a 
pull request.

The main motivation for proposing these changes is to introduce support 
for PSS signatures in TLS and in certificates. You may have heard about 
the Bleichenbacher-like universal forgery attack in NSS that I recently 
discovered with Brian this summer (also known as "BERserk", name by 
Intel): such bugs should remind us that PKCS#1v1.5 is a fragile 
signature algorithm ([EC]DSA can also be hazardous in its randomized 
variant, as shown by Sony hack and recent bitcoin thefts), and the fact 
that TLS not only mandates its use, but also explicitly prohibits better 
alternatives ("a certificate with RSASSA-PSS signature key cannot be 
used because TLS defines no corresponding signature algorithm") is 
hardly acceptable.

Hence, I propose to include with this change the introduction of a new 
SignatureAlgorithm value rsa-pss(4) that denotes PKCS#1v2.2 RSASSA-PSS 
signatures with default parameters (mgf1SHA1 for mask generation and the 
length of the message digest function output as salt length). It may 
take time before this change impacts PKIX and CAs, but it is at least a 
necessary first step.

Best,

Antoine

---

From: Brian Smith <[email-masked]>
Date: Mon, 22 Dec 2014 22:07:35 -0800

Antoine Delignat-Lavaud <[email-masked]> wrote:
> ownership of private keys in certificates

How would your proposal change if signature-less authentication
mechanisms were added (later)? How would we indicate support for the
signature-less authentication?

> In this design, keeping the legacy of including the signature algorithm to
> be used in the ServerCertificateVerify message within the selected cipher
> suite name can be a burden to the modularity and extensibility of the
> protocol, since adding support for new signature algorithms comes at the
> cost of an exponential increase in the length of the list of cipher suites
> sent by the client, even though the security guarantees of the handshake are
> now fully modular w.r.t authentication goals achieved by certificate and
> signatures.

In theory, that sounds like a problem. Is it really a problem in
practice, if we're not concerned about the specific case of RSA-PSS?

> already existed in 1.2 and it led to oddities in the protocol, such as the
> inability to use FF-DHE authenticated by ECDSA, even though there isn't
> anything inherently wrong with this combination.

On the other hand, nobody has ever seemed to want TLS_DHE_ECDSA_*
cipher suites, so it doesn't seem like it caused any problem.

> The following paragraph,
> taken from the current 1.3 draft, is another instance of this awkwardness:
>
> extension. Note that there is a possibility for inconsistencies here. For
> instance, the client might offer DHE_DSS key exchange but omit any DSA pairs
> from its "signature_algorithms" extension. In order to negotiate correctly,
> the server MUST check any candidate cipher suites against the
> "signature_algorithms" extension before selecting them. This is somewhat
> inelegant but is a compromise designed to minimize changes to the original
> cipher suite design."

In other words, the client might offer DHE_DSS cipher suites that are
only to be used by older servers that do not understand TLS 1.2 and
the signature_algorithms extension, while TLS 1.2 implementations
should choose ECDSA. That's pretty reasonable/desirable behavior.

> - For compatibility with previous protocol versions, existing cipher suite
> names are preserved; however, servers MUST NOT select any cipher suite that
> includes a signature algorithm other than RSA in a 1.3 handshake;

What is the practical advantage of having this restriction? I would be
concerned that there might be an interoperability loss if servers
choose TLS_ECDHE_RSA_* but use an ECDSA certificate. It would be good
to see some measurement of the effects of doing that, but it is
difficult to do such measurement. I think there should be a clear
benefit to the restriction in order to justify the effort to measure
if it would work.

> current cipher suite negotiation). All certificates in a chain MUST also be
> signed with signature algorithms supported by the client. The same
> requirements apply even if a pre-1.3 cipher suite (such as
> ECDHE_RSA_AES256_GCM_SHA384) was selected: the algorithm in the cipher suite
> name is ignored.

Many (most?) clients already work this way, so I don't think this
would be too controversial. But, it seems better for the server to
choose the cipher suite that best identifies the signature algorithm
that it actually uses (e.g. TLS_x_ECDSA_* for a ECDSA certificate),
instead of always using the RSA one.

> The main motivation for proposing these changes is to introduce support for
> PSS signatures in TLS and in certificates.

Why should anybody add any new RSA-based signature scheme now?
Shouldn't we let the RSA algorithm die off with Windows XP and other
ancient stuff? If we're not happy with ECDSA because of the
requirement for a perfect PRNG for randomized signatures, why not just
specify that ServerKeyExchange in TLS 1.3 MUST use deterministic ECDSA
signatures when an ECDSA certificate is used, or something similar
that has similar server-side efficiency as ECDSA? There's got to be
better alternatives to spending time tweaking support for RSA.

Cheers,
Brian

---

From: Hanno Böck <[email-masked]>
Date: Tue, 23 Dec 2014 10:26:35 +0100

Hello,

On Tue, 23 Dec 2014 04:04:46 +0100
Antoine Delignat-Lavaud <[email-masked]> wrote:

> Hence, I propose to include with this change the introduction of a
> new SignatureAlgorithm value rsa-pss(4) that denotes PKCS#1v2.2
> RSASSA-PSS signatures with default parameters (mgf1SHA1 for mask
> generation and the length of the message digest function output as
> salt length). It may take time before this change impacts PKIX and
> CAs, but it is at least a necessary first step.

Thanks for bringing PSS for TLS 1.3 up, I wanted to do this for quite
some time.

Do I understand your proposal right that it'd result in:

a) If we use the normal RSA certificates we have today TLS 1.3 would
continue using RSA-PKCS#1v1.5
b) If the user gets a designated RSA-PSS key/certificate it'd use PSS?

I think this would result in a near-zero-adoption for PSS probably for
a very long time because you'd depend on the CA to do anything.

Why not go the much simpler route: Define that TLS 1.3 uses PSS by
default.

Certificates / Keys for RSA-PSS are no different from PKCS#1v1.5 keys.
We can just use the existing ones.

(Please note that the algorithm identifier for PSS already exists for
X509, it's RFC 4055. It allows Keys with an algorithm identifier
restricting to PSS, but that's no requirement - you can use the old
keys for PSS as well, as technically they're no different.)

Best,
-- 
Hanno Böck
http://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

---

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Tue, 23 Dec 2014 12:26:27 +0100

Hi,

> a very long time because you'd depend on the CA to do anything.

No, in my proposal, the algorithm used in CertificateVerify messages is 
negotiated based on advertised support in the "signature algorithms" 
extension (and supported_signature_algorithms field in 
CertificateRequest). Clients are encouraged to prioritize rsa-pss/sha256 
over rsa/sha256 or rsa/sha1, and supporting servers may pick PSS even if 
their certificate chain only contains rsa/sha256 and rsa/sha1.

> keys for PSS as well, as technically they're no different.)

If anything, my own concern is the opposite. Allowing the same RSA key 
to be used to sign with both PSS and PKCS#1v1.5 is considered 
cryptographic malpractice, as the composition of secure and weak 
signatures may very well be broken. However, servers have the ability to 
avoid this risk by sending a different certificate depending on whether 
the client advertises support for PSS or not, even if the two 
certificates are signed with PKCS#1 (the proof of the protocol will 
probably assume servers enforce this behavior).

Furthermore, one of the issues of PSS in RFC 4055 is its reliance on 
signature parameters, which have tricky agility characteristics. For 
everyone's sake, it may help adoption if new OIDs for PSS signatures 
were used that correspond to fixed parameters. In any case, this 
discussion is out of the scope of the TLS WG.

Best,

Antoine

---

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Tue, 23 Dec 2014 13:11:02 +0100

> signature-less authentication?

Such schemes would either require an extension or a custom cipher suite 
because of their different state machine.

> practice, if we're not concerned about the specific case of RSA-PSS? On the other hand, nobody has ever seemed to want TLS_DHE_ECDSA_* cipher suites, so it doesn't seem like it caused any problem.

Right now, it isn't a problem in practice, but it is not clear either 
that DSA (maybe in danger of being removed?), ECDSA and PKCS#1v1.5 are a 
good set of signature algorithms to commit to for the long run. Even in 
the short term, a MAC-based signature scheme may be useful for PSK and 
resumption.

> benefit to the restriction in order to justify the effort to measure

An alternative would be to allow any pre-1.3 cipher suite to be used, 
while allowing the signature algorithm used to authenticate the server 
may be different from the one included in the cipher suite name (e.g. 
server picks TLS_DHE_RSA_* but signs CertificateVerify with PSS).

> instead of always using the RSA one.

Indeed, even miTLS works like this in TLS 1.2 even though this behavior 
is not permitted by current specification. As I said, I am not 
particularly set on the specifics of how to make the transition from 
pre-1.3 cipher suite names, and I'm fine with what you suggest.

> better alternatives to spending time tweaking support for RSA.

It is currently impossible to get a non-RSA certificate signed by any 
public CA (I know because I tried hard to get one). Only Google can 
concretely deploy EC certs today. Hence, there's is currently NO 
alternative to RSA signatures for authentication.

By the way, it may be a good idea to recommend or mandate RFC6979-style 
deterministic ECDSA signatures in TLS to prevent entropy-exhaustion 
attacks against clients and servers. Off-topic though.

Best,

Antoine

---

From: Brian Smith <[email-masked]>
Date: Tue, 23 Dec 2014 10:20:24 -0800

Antoine Delignat-Lavaud <[email-masked]> wrote:
>> practice, if we're not concerned about the specific case of RSA-PSS? On
>> the other hand, nobody has ever seemed to want TLS_DHE_ECDSA_* cipher
>> suites, so it doesn't seem like it caused any problem.
>
> Right now, it isn't a problem in practice, but it is not clear either that
> DSA (maybe in danger of being removed?), ECDSA and PKCS#1v1.5 are a good set
> of signature algorithms to commit to for the long run. Even in the short
> term, a MAC-based signature scheme may be useful for PSK and resumption.

OK. It seems like whether we need to solve the problem of whether
cipher suites specify the signature algorithm *now* depends on whether
we're going to standardize a replacement for ECDSA, PKCS#1, and DSA
*now*. If we're not going to replace them now, then I don't think we
need to solve this problem now (for 1.3).

> It is currently impossible to get a non-RSA certificate signed by any public
> CA (I know because I tried hard to get one). Only Google can concretely
> deploy EC certs today. Hence, there's is currently NO alternative to RSA
> signatures for authentication.

I am surprised that you had so much trouble getting an ECC cert.
Please ping me off-list and I will help you with that. I agree with
the more general point that deploying ECDSA certificates is harder
than it should be. That is a fixable problem.

> deterministic ECDSA signatures in TLS to prevent entropy-exhaustion attacks
> against clients and servers. Off-topic though.

I think it is a good idea to at least explore making RFC6979-style
ECDSA mandatory for TLS 1.3 when ECDSA is used. I don't think it is
off-topic though. If we did that, that would resolve the main problem
with ECDSA, and that would reduce (perhaps eliminate) the need for
RSA-PSS or other new/uncommon signature schemes, which would greatly
reduce the motivation for making the change you propose.

Cheers,
Brian

---

From: Hanno Böck <[email-masked]>
Date: Thu, 25 Dec 2014 21:21:41 +0100

Hi,

On Tue, 23 Dec 2014 12:26:27 +0100
Antoine Delignat-Lavaud <[email-masked]> wrote:

> No, in my proposal, the algorithm used in CertificateVerify messages
> is negotiated based on advertised support in the "signature
> algorithms" extension (and supported_signature_algorithms field in 
> CertificateRequest). Clients are encouraged to prioritize
> rsa-pss/sha256 over rsa/sha256 or rsa/sha1, and supporting servers
> may pick PSS even if their certificate chain only contains rsa/sha256
> and rsa/sha1.

Okay, then I misinterpreted you.

But my point remains: Why not just say "TLS 1.3 has to use RSA with
PSS, mo more PKCS #1 1.5"?

> If anything, my own concern is the opposite. Allowing the same RSA
> key to be used to sign with both PSS and PKCS#1v1.5 is considered 
> signatures may very well be broken. However, servers have the ability
> to avoid this risk by sending a different certificate depending on
> whether the client advertises support for PSS or not, even if the two 

I am aware that using same key for both protocol versions is bad
practice. However are you aware of any sign this may be a real risk?

Anyway, for the scenario that TLS 1.3 uses only PSS, could a server
send different keys for <=1.2 and 1.3?

> discussion is out of the scope of the TLS WG.

I know all the problems, I implemented this once :-)

cu,
-- 
Hanno Böck
http://hboeck.de/

---

From: Russ Housley <[email-masked]>
Date: Tue, 30 Dec 2014 13:35:31 -0500

> PSS, mo more PKCS #1 1.5"?

I am not aware of any "real" risk of new attacks on RSA signatures enabled by using the same key pair for both PKCS #1 v1.5 and PSS.  The good structure in PSS would probably meant that the security wouldn't get any worse by allowing PSS signatures than with PKCS #1 v1.5 alone.

That said, I believe that the PSS security proof makes the assumption that the key is only used with PSS.  The proof would probably need some modification to allow for the possibility that some signatures would be computed with PKCS #1 v1.5 and others with PSS.  Does anyone know of work on this topic?

Russ