[TLS] DH group negotiation extension [was: Re: draft-sheffer-tls-bcp: DH recommendations]

[Daniel Kahn Gillmor <[e-mail]>]

On Sun 2013-09-22 00:46:52 -0400, Michael D'Errico wrote:
> Yoav Nir wrote:
>> On Sep 22, 2013, at 2:44 AM, Patrick Pelletier <[e-mail]> wrote:
>> 
>>> We *do* know how to move to 2048 bits without breaking anything: add
>>> an extension to negotiate DH size, just like how ECC curves are
>>> negotiated.  Although yes, this will take a while to deploy
>>> universally, it at least means early adopters can start using 2048
>>> now, without breaking the stragglers like Java.
>> 
>> Perhaps it would be better to have the client suggest the actual
>> group rather than bit length in that case. Perhaps we could reuse the
>> IKE numbering of groups, or else have the client specify it similar
>> to ServerDHParams struct.
>
> If the client chooses, then I'd prefer they choose from a list of
> standardized groups similar to RFC 3526 rather than requiring the
> server to (try to) verify that the parameters are usable.  We could
> also sneak in a 256-bit q parameter to speed up the computations.

I'm happy to see the ongoing thinking about TLS 1.3, but i would like to
be able to address the ability to negotiate DH group size with
less-invasive patches to existing implementations too, so i want to try
to flesh out what this DH group negotiation extension would look like.

Here are sketches of three different proposals for consideration:

The minmalist proposal:
-----------------------

 * compliant clients advertising a ciphersuite using EDH would include
   an extension indicating the smallest and largest EDH group sizes they
   are willing to accept.

 * compliant servers seeing this extension (and knowing what EDH
   group(s) they have been configured to use) will select or reject the
   EDH ciphersuite based on whether their group falls within the
   client's guidelines.

 * the rest of the key exchange continues as normal.  If the client
   receives an EDH ciphersuite with a group outside its declared range,
   then it terminates the connection (this is being done today by many
   TLS client libraries when they encounter too-weak EDH parameters
   anyway) and decides whether to retry (a new connection) without
   offering any EDH ciphersuites.

The standard-groups proposal:
-----------------------------

 * compliant clients advertising a ciphersuite using EDH would include
   an extension indicating which of the standard groups they prefer, via
   a series of bytes matching the identifiers of MODP groups listed in
   RFC 3526, listed in order of preference for the client.

 * compliant servers are configured to accept a subset of the well-known
   enumerated groups.  A server seeing this extension and selecting an
   EDH ciphersuite would select and use the first DH group from the set
   offered that the server is configured to use.  If there is no
   intersection, the server should not select an EDH ciphersuite.  when
   an EDH ciphersuite is selected, either:

   (a) the Server Key Exchange record would contain that group's
       parameters explicitly, like in a standard handshake, or

   (b) the server would offer a modified Server Key Exchange record that
       only indicates the group ID

   (i see these as two variants of the standard-groups proposal, not as
   two options within the standard-groups proposal -- if we go with
   this, we should pick one)

 * the rest of the key exchange continues as normal.  If the client gets
   a Server Key Exchange record that does not match one of the groups it
   specified, the client decides (as it does today) whether to accept
   the connection or to terminate the connection and/or to fall back to
   a reconnection without offering any EDH modes.
 

The client-chooses proposal:
----------------------------

 * compliant clients advertising a ciphersuite using EDH would include
   an extension indicating a single standard group they use, along with
   a freshly-picked ephemeral public key associated with that group.

 * compliant servers are configured to accept a subset of the well-known
   enumerated groups.  A server seeing this extension and configured to
   accept the offered group responds with a customized Server Key
   Exchange record indicating acceptance of the group, and offering its
   own public key.  A compliant server seeing this extension but not
   configured to accept the offered group should not select an EDH
   ciphersuite.

 * If a compliant client sees the customized Server Key Exchange record,
   it does not send a Client Key Exchange record.  If a compliant client
   sees a normal Server Key Exchange record, then it assumes the server
   is ignorant of the extension, and decides (as it does today) whether
   to accept the group, or to terminate the connection and/or fall back
   to a reconnection without offering any EDH modes.


(i've omitted a client-chooses proposal that does not involve standard
groups due to Michael's point about wanting to avoid requiring tha tthe
server validate the group)

I can imagine mixing elements of the above three proposals to create a
hybrid proposal, but i'll leave it at these three for now in hopes of
commentary.  What did i miss?

Some observations:
------------------

 A) the client-chooses extension is also likely to be much larger than
    the other two proposals.  I'm not so worried about this.

 B) the client-chooses proposal alters the handshake flow and connection
    state logic much more radically than the other two proposals.  This
    makes me much more nervous.

 C) the main gain of any of these proposals is that they allow/encourage
    an otherwise-conservative server implementation to use stronger DH
    groups without worrying about incurring a connection failure from
    non-compliant clients.  A compliant server implementation would
    still need to decide what to do when it hears from a client that
    does not offer the extension.  It would be great to be able to point
    to something like draft-sheffer-tls-bcp for guidance in this
    situation.

 D) settling on standard groups means a few things:
 
    * we'll have to either choose an existing registry or make up a new
      one.  I've mentioned RFC 3526 above because it seems like a
      reasonable existing registry
 
    * implementations adopting the registry won't need to bother with
      primality testing or length testing when using groups from the
      registry.

    * choosing standard groups smells a lot like the choice of which ECC
      curves to use, but i don't think i ever heard quite as much of a
      brouhaha over the groups in RFC 3526 as i've heard over the suiteB
      curves.  Does going with standard curves mean inviting this kind
      of struggle all over again in a different domain?  What kinds of
      mathematical assurances do we have to ensure that the standard
      groups themselves aren't somehow deliberately weakened by their
      selector?  Are there pre-computation or large-data attacks that a
      powerful adversary could use to target a widely-used group more
      effectively than an ever-changing sea of different DH groups? I
      don't know the math literature well enough to comment on any of
      this, but i would be curious to hear other people's thoughts.

 E) the client-side configuration options required for the minimalist
    proposal are a strict subset of the configuration options of the
    other proposals, since the other proposals still need to have DH
    group size limits to deal with servers unaware of the extension.


All of the observations above make me think that the minimalist proposal
seems to be the least likely to cause controversy and the simplest to
patch into existing implementations quickly and safely.

Also, none of these proposals preclude any of the other ones, so it's
conceivable that we could aim for a relatively rapid rollout of the
minimalist proposal while shooting for longer-term adoption of one of
the others.

So i'm currently leaning toward the minimalist proposal, because i think
it gives us much of the gains described in (C) without too much
additional implementation hand-wringing or controversy.

Thoughts?  I'd be willing to write up a draft of one of these proposals
and implement it if there's sufficient interest.

        --dkg