Re: [TLS] Requesting working group adoption of draft-stebila-tls-hybrid-design

[Ilari Liusvaara <[e-mail]>]

On Wed, Feb 12, 2020 at 02:26:21PM -0500, Douglas Stebila wrote:
> Dear TLS working group,
> 
> We would like to request the working group adopt
> draft-stebila-tls-hybrid-design, "Hybrid key exchange in TLS 1.3", as
> a working group item.  We have updated the draft based on feedback
> we've received over the past few months, including from our
> presentations at IETF 104 and 105, and think the current version
> represents the view of the WG to date.
> 
> https://datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/

Some comments and related sidenotes:

- If additional round trips are to be avoided, the public key size
  should be kept low so client hello does not grow so large that
  significant amount of servers barf on it. [LANGLEY] notes that
  3300 bytes was about the maximum they could use.

- That TLS 1.3 does not talk about client-side key reuse seems to
  be a mistake. It for example says SHOULD NOT reuse tickets, with
  rationale that also appiles to client side keys.

- The draft talks about "any KEM used in this document". Which sounds
  odd, given that this document does not define any KEMs.

- The reasons to not reuse public keys, even with CCA-secure KEMs,
  impiles that the relevant benchmarks are:

  * Combined key generation and decapsulation time.
  * Single-thread encapsulation time.
  * Peak memory usage by key generation and decapsulation.
  * Peak memory usage by encapsulation.
  * Size of public key
  * Size of ciphertext
 
  For KEMs used as key exchanges, using decapsulation time alone is
  perverse due to problems with key reuse, again even with CCA-secure
  KEMs.

- Assigning specific range for Hybrid KEX. What is the use of that?
  The server recognizing that client supports Hybrid KEX even if there
  is no algorithm overlap? What the server would do with that
  information?

- The draft has specific data structures. This only makes sense if
  other drafts are to refer to it or are intended to copy the data
  structure definitions. It also has processing algorithms, which only
  makes sense to me if other drafts are to refer to this one.

  Being informational, referencing could lead to downref, but this
  should not be a significant problem.

- I do not view supporting large public keys or ciphertexts as
  realistic.

  Making larger extension would mean extending TLS to support
  "extended extensions". This would impily extra RTT for most key
  exchanges, altough it could be absorbed into extra RTT for client
  missing speculation on group (so it would be 2-RTT).

  Referencing external key is not acceptable:

  * The client would need to have a way to publish its key.
  * Strong incentives to reuse keys, despite problems doing so.
  * The server would need to be able to fetch keys, which causes
    difficult security issues.
  * The server would need to freeze the handshake for obtaining
    the public key. Unless the server API already supports handshake
    freezing, adding that capability is going to be virtually
    impossible (let alone the annoyance of implementing it).

  Additionally, even if blowing the practical ClientHello size limit
  (4kB or so) would already force additional round trip, the >64kB
  key algorithms have such big keys that result would be severe
  performance degradation.

  So in summary, unless all the smaller algorithms are broken beyond
  repair (which is highly unlikely due to complexity reasons) the
  >64kB keys should not be accomodiated. And even in that case, external
  keys are not acceptable.

- Avoiding duplication of key shares is difficult problem:

  * Using traditional scheme is easy on client and server, but can
    result in duplication of shares. And even single duplication of
    PQ share is signficant.
  * Making ServerHello key_share a list is clean specification-wise,
    but might be anything but clean implementation-wise.
  * Making separate extension could cause issues when doing
    hybrid -> next-gen transition in future.
  * Backreferences could be annoying to implement.

- On resumption, I do not think there are currently any restrictions
  in TLS 1.3 about DH groups used in resumption?

  If that is indeed the case, I suspect that implementing such
  restrictions might turn to be annoying to implement.

- On failures: All CCA-secure key exchanges have negligible failure
  rates (because anything else leads to attacks). And even if one
  considers non-CCA key exchanges from the NISTPQC 2nd round, AFAIK
  all of them meant for actual use have failure rate <10^-9.

- On schemes vulernable to chosen-ciphertext attack, SIDH (which
  underlies SIKE) key can be recovered bit-by-bit (even with just
  guess oracle, instead of full decryption oracle) by sending suitable
  chosen ciphertexts. This takes a few hundred samples for full key
  recovery.


-Ilari