Subject: Re: [TLS] A la carte handshake negotiation

From: Manuel Pegourie-Gonnard <[email-masked]>
Date: Sun, 19 Jul 2015 20:53:52 +0200

Hi,

sorry for resurecting an old message on a fairly tangential point.

On 6/12/15 10:31, Ilari Liusvaara wrote:
> AFAICT, In TLS 1.2, DHE+ECDSA is legal, if client signals support for
> both DHE (via ciphersuites) and ECDSA (via (possibly implicit default)
> signature_algorithms).
>
> (In TLS 1.1 and earlier, there is seemingly no way to use DHE+ECDSA)
>
Either we're not talking about the same thing, or we don't read RFC 5246 
in the same way. Section 7.4.2 (pages 47-48) says:

    -  The end entity certificate's public key (and associated
       restrictions) MUST be compatible with the selected key exchange
       algorithm.

       Key Exchange Alg.  Certificate Key Type
       [...]
       DHE_RSA            RSA public key; [...]

To me that clearly means that if the server selects a DHE_RSA 
ciphersuite, it MUST NOT use a certificate that contains an EC key, even 
if the client offered ECDSA in the signature_algorithm extension. 
However, in that case the certificate may be signed using ECDSA, which 
is not the same.

> Also, there is no "double negotiation" in TLS 1.2 either. TLS 1.2 is
> quite clear about interaction of signature algorithms in ciphersuites
> and explicit signature negotiation (explicit negotiation always takes
> percedence).
>
I'm afraid we both agree that TLS 1.2 is quite clear, but disagree about 
what it says, which is ironic :) My understanding is that, regarding the 
key in the server's certificate, there is indeed double negotiation, 
with a clear rule that the set of allowed choices is the intersection of 
what is allowed by the ciphersuite and what is allowed by the 
signature_algorithms extension.

    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.

To me, the "MUST check against" does not suggest "may still pick the 
DHE_DSS suite and use an RSA cert with it if signature_algorithms 
contains acceptable RSA pairs".

Regarding other signatures in the certificate chain, only 
signature_algorithms apply, so there is no "double negotiation" indeed.

> Of course, I wouldn't be surprised if there was fair bit of software
> that got those rules wrong...
>
Regardless of whether your interpretation or mine is correct, I'm pretty 
sure various implementations will do things in different ways here. 
Anyway, a large proportion of servers deployments only have one cert, in 
which case the RFC says "it [the server] SHOULD attempt to validate that 
it [the certificate] meets these criteria", which may be interpreted as 
an indication that the server may try to send its only certificate 
anyway and let the client decide how to deal with it.

Manuel.

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 19 Jul 2015 20:58:27 +0200

On Sun, Jul 19, 2015 at 8:53 PM, Manuel Pegourie-Gonnard <[email-masked]>
wrote:

> To me that clearly means that if the server selects a DHE_RSA ciphersuite,
> it MUST NOT use a certificate that contains an EC key, even if the client
> offered ECDSA in the signature_algorithm extension. However, in that case
> the certificate may be signed using ECDSA, which is not the same.
>
> key in the server's certificate, there is indeed double negotiation, with a
> clear rule that the set of allowed choices is the intersection of what is
> allowed by the ciphersuite and what is allowed by the signature_algorithms
> extension.
>
> DHE_DSS suite and use an RSA cert with it if signature_algorithms contains
> acceptable RSA pairs".
>

This is how I understand the situation as well. I am sad to hear that we
didn't
manage to make the document clear on this point.

-Ekr

> sure various implementations will do things in different ways here. Anyway,
> a large proportion of servers deployments only have one cert, in which case
> the RFC says "it [the server] SHOULD attempt to validate that it [the
> certificate] meets these criteria", which may be interpreted as an
> indication that the server may try to send its only certificate anyway and
> let the client decide how to deal with it.
>
> Manuel.
>
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Dave Garrett <[email-masked]>
Date: Sun, 19 Jul 2015 16:22:47 -0400

Since the last time I posted it here, I've made some changes. Everything is rebased on top of what is now PR #201 (it's not really severable from that).

https://github.com/davegarrett/tls13-spec/compare/alertsandcerts...davegarrett:alacarte

Now that resumption is PSK-based, some of the language might need tweaking for that, but I not everything is sorted out for PSK-based resumption yet. (there's TODOs in the draft; e.g., doesn't yet say what cipher suites are to be used for resumption)

Other than that, it's at a state that (with PR #201) I could submit a PR if we can agree that this is the general path forward. The highlights of this proposal, for those who didn't follow the previous (long) discussions on the topic:

* All DH, DHE, ECDH, RSA, and DSS cipher suites are deprecated. (some could still be offered for backwards compatibility, just like before)
* The only compatible cipher suites would be those with a handshake portion of ECDHE_ECDSA, ECDHE_PSK, PSK, or ECDHE_anon. (there is an exception in there for completely new stuff, which will essentially be amending this anyway)
* All ECDHE_ECDSA suites can negotiate ECHDE/DHE & ECDSA/DSA/RSA via the existing extensions. (no new extensions need to be defined to do this)
* Likewise, ECDHE_PSK and ECDHE_anon can negotiate ECHDE/DHE via the existing extension.
* A new standards track RFC to promote ECDHE suites from informational is needed, but that was already true.
* In addition to reducing combinatorial nonsense with the suites, it results in deprecation of existing DHE suites in favor or DHE done via ECDHE labeled suites only with strong groups.

This is the general result of previous discussions. The alternate route that came up was just to ditch the concept of cipher suites entirely and add a new extension to negotiate the AEAD cipher/hash to use with the existing extensions. There's nothing that would preclude moving to that more extreme route if this were to be accepted first, as ECDHE/DHE negotiation via the extension would be needed for that too. I think the WG is more in favor of the route proposed in this changeset at the moment, though.

Dave

---

From: Dave Garrett <[email-masked]>
Date: Tue, 21 Jul 2015 22:02:20 -0400

I've updated the a la carte proposal again with some improvements to readability. I've also added in the ECDHE PSK cipher suites in the current draft, as they are required for this.

current WIP text:
https://github.com/davegarrett/tls13-spec/blob/alacarte/draft-ietf-tls-tls13.md#cipher-suites
diff from PR #201:
https://github.com/davegarrett/tls13-spec/compare/alertsandcerts...davegarrett:alacarte

Dave

---

From: Kyle Rose <[email-masked]>
Date: Wed, 22 Jul 2015 04:50:08 -0400

I'd like to see the bits of the cipher suite associated entirely with
ephemeral data tied together roughly by security margin, to avoid
combinations that don't make sense (e.g., straw men of RSA384 + AES256
or AES256 + CRC32). This means: the type/size of the (EC)DHE group and
the symmetric cipher (and possibly the MAC, if it's anything other
than "GCM"). So, you'd potentially have something like

ECDHE256-AES256-GCM
DHE2048-AES256-GCM
DHE1536-AES128-GCM

etc.

The signature algorithm (ECDSA, RSA, etc.) would be entirely separate.
This isn't like the old days when the RSA key was used to exchange the
keys: in the FS world, RSA is never used for key agreement, so
RSA/ECDSA is used only to authenticate the server and is therefore
orthogonal to the cipher suite negotiated above... and it's also
implicit from the set of certificates the server has available.

This unfortunately means we can't really tie the signature security
margin to the cipher suite (going back to the RSA384 straw man), but
since it's a pre-existing credential nothing can be done by the client
other than to hang up if it's spooked by that. To fix this, we'd
really need to go down the road of specifying the key size in the
cipher suite, e.g. RSA2048 or ECDSA25519, which I'm not sure anyone
wants.

Does anyone want that? I ask because there are a ton of servers with
1024-bit RSA keys negotiating AES256-GCM, which tells an attacker
exactly what to focus on. (In theory: a tire iron is still probably
faster than factoring RSA1024.)

The nice thing about the above approach is that IMO it actually makes
things simpler for an implementer: the cipher suite list becomes a lot
smaller but still covers most of the options, avoiding the complexity
of full a la carte, while the signature algorithm is implicit for the
server. So, we're not at libsodium level of simplicity, but closer.

The one thing I'm having trouble pinning down is PSK. I fear it's not
a separate dimension, because it replaces both signature and KEX.

Kyle

---

From: Martin Thomson <[email-masked]>
Date: Wed, 22 Jul 2015 02:16:43 -0700

On 22 July 2015 at 01:50, Kyle Rose <[email-masked]> wrote:
> ephemeral data tied together roughly by security margin

I've seen this argument several times, but there are reasons why you
might want a non-homogenous strength profile.

The argument for consistency is appealing, but given that the design
of TLS is historically[1] vulnerable to the weakest *supported*
algorithm as opposed to the weakest *used* algorithm, I am not
concerned about ensuring consistency.

[1] ... and likely in future, despite our best efforts

> a separate dimension, because it replaces both signature and KEX.

Yes, this is a problem.  I like to think of PSK as KEX with null auth.

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 22 Jul 2015 12:31:43 +0300

> concerned about ensuring consistency.

Furthermore, comparing the strengths of kex, auth, ciphering and
PRF seems like comparing apples, orangles, pears and kumquants.

Even if the nominal strengths are the same, the scaling of strengths
is going to be different (e.g. the quadric vs. linear sub-treshold
scaling for ECDH vs. symmetric).

> Yes, this is a problem.  I like to think of PSK as KEX with null auth.

I think TLS has currently four non-obsolete key exchanges:
- GDHE_CERT
- GDHE_PSK
- GDHE_anon
- PSK

(I couple things here because I think that decoupling those would
lead to unacceptable interop problems).

-Ilari

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 22 Jul 2015 10:27:23 +0000

Ilari Liusvaara <[email-masked]> writes:

>Furthermore, comparing the strengths of kex, auth, ciphering and PRF seems
>like comparing apples, orangles, pears and kumquants.
>
>Even if the nominal strengths are the same, the scaling of strengths is going
>to be different (e.g. the quadric vs. linear sub-treshold scaling for ECDH vs.
>symmetric).

+1.  It's just more numerology:

  (In case you're wondering why you shouldn't go straight to 2048 bits, this
  is another piece of cryptographic numerology that arises from the confusing
  idea of algorithm pairings, that every conventional encryption algorithm or
  key size has to be somehow matched up to a public-key algorithm key size.
  Since conventional encryption algorithms generally have the property that
  every single bit added to the key doubles the work factor needed to break it
  by brute force while public-key algorithms don't, this means that attempts
  to pair conventional-encryption with public-key sizes leads to insanely
  large public keys as the conventional-encryption key sizes get larger.

  Using any known technology it's unlikely that humans can ever get beyond
  about 2^^100 operations, which means that common key sizes of 112 bits
  (triple DES), 128 bits (AES), 192 bits (AES again), and 256 bits (yet more
  AES, because you can never have too many key sizes) are all equally
  unbreakable, and yet the desire for algorithm pairing means that we're
  supposed to go to public-key sizes of 2048, 3072, 7680, and 15,360 bits
  respectively for all of these equally-unbreakable conventional key sizes
  ["Recommendations for Key Management --- Part 1: General", Elaine Barker,
  William Barker, William Burr, William Polk and Miles Smid, NIST Special
  Publication 800-57, 9 July 2012].  This is a good example of the strange
  places that cryptographic numerology can lead you if you believe in it too
  fervently).

So really the table of key sizes should be:

  Conventional        RSA/DH
  ---------------     ------
  100 bits            1536 bits
  112 (ie. > 100)     1536 bits
  128 (ie. > 100)     1536 bits
  192 (ie. > 100)     1536 bits
  256 (ie. > 100)     1536 bits
  Anything > 100      1536 bits

Peter.

---

From: Kyle Rose <[email-masked]>
Date: Wed, 22 Jul 2015 07:09:24 -0400

> +1.  It's just more numerology:

In that case, we should dispense with any larger key sizes and
recommend exactly one per algorithm, and vary only on algorithm.
Adopting this would simplify things even further by reducing the
cipher set list by an order of magnitude.

Sadly, I'm guessing there are numerological requirements in various
standards and regulations that make it necessary to keep both AES-128
and AES-256 around, for example. There are also a ton of existing
2048-bit RSA keys that aren't going anywhere for a while.

I'm also skeptical of statements like "Using any known technology it's
unlikely that humans can ever get beyond about 2^^100 operations",
because that's true exactly up until it isn't. An open question is
whether the innovation that undoes this will also subsume much larger
keys.

Kyle