Re: [TLS] Drafts for batch signing and PKCS#1 v1.5

[David Benjamin]

On Tue, Jul 30, 2019 at 11:59 PM Martin Thomson  wrote:

> On Wed, Jul 31, 2019, at 13:54, Ben Schwartz wrote:
> > The batch signing idea is very cool. I'm not entirely sure I understand
> > the intended use case, though. The intro suggests that this motivated
> > by DoS defense, but presumably an attacker who controls their own TLS
> > client stack could simply omit support for these signature schemes. Do
> > you envision a future where servers can safely omit support for all the
> > non-batch signature schemes? Or are you thinking of attackers who don't
> > control the TLS client stack?
>
> The usual trick when under duress is to attempt to process some requests,
> and lowering the cost of handling those requests enables higher tolerance
> to attack and better continuity of service.  A server might choose not to
> serve clients that don't offer batching if it is stressed.
>

Yup. The signing cost of a batch-capable client is effectively zero. (I
expect it's already common to preferentially serve ECDSA-capable clients
when under load.) Also, if many clients implement this, serving load under
normal operation goes down, which is also valuable.


> > Minor question: in the tree diagrams, m2 goes to t04. Is there any
> > reason it couldn't go directly to t12? That would seem more natural to
> > me.
>
> The blinding process is explained in Section 4.3.
>

I think Ben is asking why the tree doesn't put m2 a level higher (like CT
does), instead of adding the padding nodes. That would work too. I chose
this one because I found it more straightforward, and it doesn't
particularly matter. Also it's what Roughtime did and I cribbed the
construction from Roughtime. :-)

In principle, the signer could pick any tree strategy as long as it
produced valid paths for each message. But I think it's probably better for
the draft to be opinionated, rather than risk implementers mess things up.

David
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Drafts for batch signing and PKCS#1 v1.5

[Martin Thomson]

On Wed, Jul 31, 2019, at 13:54, Ben Schwartz wrote:
> The batch signing idea is very cool. I'm not entirely sure I understand 
> the intended use case, though. The intro suggests that this motivated 
> by DoS defense, but presumably an attacker who controls their own TLS 
> client stack could simply omit support for these signature schemes. Do 
> you envision a future where servers can safely omit support for all the 
> non-batch signature schemes? Or are you thinking of attackers who don't 
> control the TLS client stack?

The usual trick when under duress is to attempt to process some requests, and 
lowering the cost of handling those requests enables higher tolerance to attack 
and better continuity of service.  A server might choose not to serve clients 
that don't offer batching if it is stressed.

> Minor question: in the tree diagrams, m2 goes to t04. Is there any 
> reason it couldn't go directly to t12? That would seem more natural to 
> me.

The blinding process is explained in Section 4.3.

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Martin Thomson]

On Wed, Jul 31, 2019, at 06:21, Benjamin Kaduk wrote:
> It's clear that anything we do needs to preserve compat with all four
> possibilities in the interop matrix for (old, enhanced) (client,
> server).  Your closing note about duplicating payloads is something of a
> different creature, though, and perhaps should be considered more
> explicitly.

Adam directly addressed that concern at the meeting; and others agreed.  25519 
shares are small enough that worrying about duplication isn't necessary.  The 
delta is tiny when considering the need to additionally signal combinatorics in 
the scheme imagined by Option 1.

So I'd like to add my voice to those in support of buttoning down a single 
scheme (i.e., Option 2).  The cost of the added indirection is significant.  
I'll take the addition of a few bytes to the ClientHello over that any time.

The other arguments all assume that we'll fail to narrow the parameter set or 
number of options.  My view is that deciding on a single parameter set is not 
just desirable, but necessary.  My experience suggests that clients won't want 
to expend the resources necessary to create and send two PQ shares.  No PQ 
scheme that I've seen are close enough in terms of efficiency - bytes or CPU - 
to allow for multiple shares to be offered.

Option 2 also allows us to defer the combination method.  While I imagine that 
concatenation will be injective for most schemes, which might be sufficient, we 
might want to change the combination method as we learn more.  Option 2 allows 
us to include a definition for how secrets produced by each scheme are merged 
into the key schedule for each combination.

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Adoption call for draft-lvelvindron-tls-md5-sha1-deprecate

[David Benjamin]

I'm in favor of adoption.

On Wed, Jul 24, 2019 at 11:28 AM Chris Inacio  wrote:

> Favor of adoption.
>
>
>
> On July 24, 2019 at 8:49:22 AM, Christopher Wood (c...@heapingbits.net)
> wrote:
>
> At TLS@IETF105, there was interest in the room to adopt
> draft-lvelvindron-tls-md5-sha1-deprecate as a WG item. The draft can be
> found here:
>
> https://datatracker.ietf.org/doc/draft-lvelvindron-tls-md5-sha1-deprecate/
>
> This email starts the call for adoption. It will run until August 7, 2019.
> Please indicate whether or not you would like to see this draft adopted.
>
> Best,
> Chris, on behalf of the chairs
>
> ___
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>
> ___
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Benjamin Kaduk]

On Tue, Jul 30, 2019 at 07:44:13PM +, Scott Fluhrer (sfluhrer) wrote:
> I believe that one important property (of either of the options I listed) is 
> a nice fallback if an enhanced client talks to an older server.  In both 
> cases, the server will see a series of named groups that it doesn’t know 
> (which it will ignore), and possibility an extension it doesn’t know (which 
> it will ignore); the server will accept either a named group that it does 
> understand (if the client did propose a traditional group as a fall back), or 
> it will come to the correct conclusion that the two sides have no mutually 
> acceptable security policy.
> 
> It is not clear if the proposal you outlined share this property; do you 
> duplicate a payload that an unenhanced server would assume only occurs once?

It's clear that anything we do needs to preserve compat with all four
possibilities in the interop matrix for (old, enhanced) (client,
server).  Your closing note about duplicating payloads is something of a
different creature, though, and perhaps should be considered more
explicitly.

Trying to uplevel a bit, option 1 is essentially introducing another
layer of indirection, with the need to carry the additional lookup table
on the side.  This has the disadvantages of both needing the extra layer
of indirection and also can have unfortunate impact from needing the
extra table on the side in more places than is immediately obvious
(i.e., the ESNI case that David mentioned).  The perceived benefit is
that we allocate fewer codepoints, avoid duplicating some KeyShare
information, and maybe get increased flexibility about how we combine
schemes.  In contrast, option 2 is more smoothly integrated into the
existing negotiation mechanism, but has the potential costs of allocating
more codepoints and duplicating some KeyShare information.

But, what are the KeyShare bits that will get duplicated?  If we're just
doing "X25519 plus one post-quantum", only the X25519 share gets
duplicated, even if we want to do several different post-quantum options
in "X25519 plus one post-quantum" form.  And X25519 shares are pretty
small, all things considered!  I'd find the concern about duplicated
KeyShares more compelling if we think we're going to end up needing to
negotiate between (X25519 plus PQ1 plus PQ2) and (X25519 plus PQ2 plus
PQ3) and (X25519 plus PQ1 plus PQ2 plus PQ3), where the PS shares add up
fast.  It's not clear that the ecosystem will end up in a place where we
need to do the latter.

-Ben

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Scott Fluhrer (sfluhrer)]

> -Original Message-
> From: Stephen Farrell 
> Sent: Tuesday, July 30, 2019 3:53 PM
> To: Scott Fluhrer (sfluhrer) ; Watson Ladd
> 
> Cc: TLS List 
> Subject: Re: [TLS] Options for negotiating hybrid key exchanges for
> postquantum
> 
> 
> I'm neutral as to how we represent this stuff for the moment as I think it's
> too early to tell until we get closer to the end of the algorithms 
> competition.

I'm of the opposite opinion; I think it is important to get this settled before 
(or at the time) the algorithm competition ends.  I really wouldn't want to see 
us wait for NIST to settle on (say) SIKE and NewHope, and then have us spend 
another year or two debating on how to integrate them into our protocols.  
Instead, I would rather spend the year or two now (when we're not on the 
critical path).

Now, there are certainly things we don't know yet about the results of the 
competition (how many algorithms, what types of parameter sets, what sizes of 
key shares do they have); however (based on the current round 2 submissions) we 
can certainly have some informed suspicions...

> 
> That said, I do want to second this...
> 
> On 30/07/2019 19:41, Scott Fluhrer (sfluhrer) wrote:
> > Here is one opinion (mine, but I'm pretty sure it is shared by
> > others): the various NIST candidates are based on hard problems that
> > were only recently studied (e.g. supersingular isogenies, Quasicyclic
> > codes), or have cryptanalytic methods that are quite difficult to
> > fully assess (e.g. Lattices).  Even after NIST and CFRG have blessed
> > one or more of them, it would seem reasonable to me that we wouldn't
> > want to place all our security eggs in that one basket.  We currently
> > place all our trust in DH or ECDH; however those have been studied for
> > 30+ years - we are not there yet for most of the postquantum
> > algorithms.
> >
> > Hence, it seems reasonable to me that we give users the option of
> > being able to rely on multiple methods.
> The only person with whom I've spoken who said he'd plan to deploy some
> of this soon is a VPN operator who explicitly wanted to start early and use >1
> PQ scheme (3-4 is what he
> said) plus a current scheme. His expectation was that that'd settle down to
> one PQ scheme, or one PQ and a current one, in time, but that time may be a
> decade after he'd like to start.
> 
> So, to the extent it matters, count me as a +1 for supporting that.
> 
> Cheers,
> S.

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

[TLS] SIKE vs SIDH (was Options for negotiating hybrid key exchanges for postquantum)

[Scott Fluhrer (sfluhrer)]

This is a side issue (we’re probably not going to talk about which postquantum 
primitives to use for another two years), but:


  *   What do you see as the advantage of SIDH?  The server can’t arbitrarily 
select the shared secret (at least, if we select the KEM version of SIKE); what 
specific advantage were you thinking of.
  *   The security proof of TLS 1.3 (at least, the ones I’ve seen) assume that 
the key exchange is CCA secure [1].  SIDH is not; I would prefer to stay with a 
key exchange that meets the assumptions of the proof, and barring an improved 
security proof that makes weaker assumptions, that means SIKE rather than SIDH.

[1] For people with real lives and who do not obsess over the minutiae of 
cryptography, CCA for a key exchange means that the private key is secure, even 
if the attacker is allowed to submit an arbitrary (possibly malformed) key 
share.  The conventional wisdom is that you don’t need to this level of 
protection for ephemeral key exchanges (where we generate a fresh private key 
for each exchange; we allow him to learn the shared secret for the exchange he 
is a party of, and learning the private key for this exchange tells him nothing 
about any other exchange); however the current proofs for TLS 1.3 make this 
assumption, even if you use a private key only once.

From: Blumenthal, Uri - 0553 - MITLL 
Sent: Tuesday, July 30, 2019 3:41 PM
To: Panos Kampanakis (pkampana) ; Scott Fluhrer (sfluhrer) 
;  
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

One more thing: I would expect to use SIDH rather than SIKE.

Because to emulate the security advantages of DH, you’d have to run two SIKE’s 
– one in each direction.


From: TLS mailto:tls-boun...@ietf.org>> on behalf of 
"Panos Kampanakis (pkampana)" mailto:pkamp...@cisco.com>>
Date: Tuesday, July 30, 2019 at 3:37 PM
To: "Scott Fluhrer (sfluhrer)" mailto:sfluh...@cisco.com>>, 
"mailto:tls@ietf.org>>" mailto:tls@ietf.org>>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

+1 for option 2. The combinatoric explosion and complexity of 1 is unnecessary. 
I expect that just a few, conservative, acceptably efficient, classical+PQ 
combinations need to be standardized and used. Combining a classical algo with 
more than one postquantum algorithms in a key exchange does not seem practical 
based on the PQ candidates key sizes and performance.

Panos


From: TLS mailto:tls-boun...@ietf.org>> On Behalf Of 
Scott Fluhrer (sfluhrer)
Sent: Tuesday, July 30, 2019 11:21 AM
To: mailto:tls@ietf.org>> mailto:tls@ietf.org>>
Subject: [TLS] Options for negotiating hybrid key exchanges for postquantum

During the physical meeting in Montreal, we had a discussion about postquantum 
security, and in particular, on how one might want to negotiate several 
different ‘groups’ simultaneously (because there might not be one group that is 
entirely trusted, and I put ‘groups’ in scarequotes because postquantum key 
exchanges are typically not formed from a Diffie-Hellman group).

At the meeting, there were two options presented:

Option 1: as the supported group, we insert a ‘hybrid marker’ (and include an 
extension that map lists which combination the hybrid marker stands for)
For example, the client might list in his supported groups 
hybrid_marker_0 and hybrid_marker_1, and there would be a separate extension 
that lists hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 + 
NTRUPR653.  The server would then look up the meanings of hybrid_marker_0 and 1 
in the extension, and then compare that against his security policy.
In this option, we would ask IANA to allocate code points for the various 
individual postquantum key exchanges (in this example, SIKEp434 and NTRUPR653), 
as well a range of code points for the various hybrid_markers.

Option 2: we have code points for all the various combinations that we may want 
to support; hence IANA might allocate a code point X25519_SIKEp434 and another 
code point for X25519_NTRUPR653.  With this option, the client would list 
X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.
In this option, we would ask IANA to allocate code points for 
all the various combinations that we want allow to be negotiated.

I would like to make an argument in favor of option 1:


-  It is likely that not everyone will be satisified with “X25519 plus 
one of a handful of specific postquantum algorithms”; some may prefer another 
elliptic curve (for example, x448), or perhaps even a MODP group; I have talked 
to people who do not trust ECC); in addition, other people might not trust a 
single postquantum algorithm, and may want to rely on both (for example) SIKE 
and NewHope (which are based on very different hard problems).  With option 2, 
we could try to anticipate all the common combintations (such as 
P384_SIKEp434_NEWHOPE512CCA), however that could very well end up as a lot of 

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Stephen Farrell]

I'm neutral as to how we represent this stuff for the moment
as I think it's too early to tell until we get closer to the
end of the algorithms competition.

That said, I do want to second this...

On 30/07/2019 19:41, Scott Fluhrer (sfluhrer) wrote:
> Here is one opinion (mine, but I'm pretty sure it is shared by
> others): the various NIST candidates are based on hard problems that
> were only recently studied (e.g. supersingular isogenies, Quasicyclic
> codes), or have cryptanalytic methods that are quite difficult to
> fully assess (e.g. Lattices).  Even after NIST and CFRG have blessed
> one or more of them, it would seem reasonable to me that we wouldn't
> want to place all our security eggs in that one basket.  We currently
> place all our trust in DH or ECDH; however those have been studied
> for 30+ years - we are not there yet for most of the postquantum
> algorithms.
> 
> Hence, it seems reasonable to me that we give users the option of
> being able to rely on multiple methods.
The only person with whom I've spoken who said he'd plan to
deploy some of this soon is a VPN operator who explicitly
wanted to start early and use >1 PQ scheme (3-4 is what he
said) plus a current scheme. His expectation was that that'd
settle down to one PQ scheme, or one PQ and a current one,
in time, but that time may be a decade after he'd like to
start.

So, to the extent it matters, count me as a +1 for supporting
that.

Cheers,
S.



0x5AB2FAF17B172BEA.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Andrei Popov]

> It is not clear if the proposal you outlined share this property; do you 
> duplicate a payload that an unenhanced server would assume only occurs once?
I think this property is preserved: only a server that knows the 
hybrid-key-exchange extension (or perhaps, a more specific 
one-traditional-and-one-PQ extension) will send KeyShareServerHello with two 
KeyShareEntries.
An “unenhanced” server will send only one KeyShareEntry. We’d need to think 
about how the “enhanced” client can distinguish the two KeyShareServerHello 
formats, but there are easy solutions to this, I think.

From: Scott Fluhrer (sfluhrer) 
Sent: Tuesday, July 30, 2019 12:44 PM
To: Andrei Popov ; David Benjamin 
; Watson Ladd 
Cc: TLS List 
Subject: RE: [TLS] Options for negotiating hybrid key exchanges for postquantum

I believe that one important property (of either of the options I listed) is a 
nice fallback if an enhanced client talks to an older server.  In both cases, 
the server will see a series of named groups that it doesn’t know (which it 
will ignore), and possibility an extension it doesn’t know (which it will 
ignore); the server will accept either a named group that it does understand 
(if the client did propose a traditional group as a fall back), or it will come 
to the correct conclusion that the two sides have no mutually acceptable 
security policy.

It is not clear if the proposal you outlined share this property; do you 
duplicate a payload that an unenhanced server would assume only occurs once?

From: TLS mailto:tls-boun...@ietf.org>> On Behalf Of 
Andrei Popov
Sent: Tuesday, July 30, 2019 2:48 PM
To: David Benjamin mailto:david...@chromium.org>>; 
Watson Ladd mailto:watsonbl...@gmail.com>>
Cc: TLS List mailto:tls@ietf.org>>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

Given these options, I also prefer option 2, for some of the same reasons.

For my understanding though, why not have the client advertise support for 
hybrid-key-exchange (e.g. via a “flag” extension) and then KeyShareServerHello 
can contain two KeyShareEntries (essentially, using the same format as 
KeyShareClientHello? This would solve the Cartesian product issue.

Cheers,

Andrei

From: TLS mailto:tls-boun...@ietf.org>> On Behalf Of 
David Benjamin
Sent: Tuesday, July 30, 2019 11:24 AM
To: Watson Ladd mailto:watsonbl...@gmail.com>>
Cc: TLS List mailto:tls@ietf.org>>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

I think this underestimates the complexity cost of option 1 to the protocol and 
implementations. Option 1 means group negotiation includes entire codepoints 
whose meaning cannot be determined without a parallel extension. This compounds 
across everything which interacts with named groups, impacting everything from 
APIs to config file formats to even UI surfaces. Other uses of NamedGroups are 
impacted too. For instance, option 2 fits into draft-ietf-tls-esni as-is. 
Option 1 requires injecting hybrid_extension into ESNI somehow. Analysis must 
further check every use, say, incorporates this parallel lookup table into 
transcript-like measures.

The lesson from TLS 1.2 code points is not combined codepoints vs. split ones. 
Rather, the lesson is to avoid interdependent decisions:

* Signature algorithms in TLS 1.2 were a mess because the ECDSA codepoints 
required cross-referencing against the supported curves list. The verifier 
could not express some preferences (signing SHA-512 with P-256 is silly, and 
mixing hash+curve pairs in ECDSA is slightly off in general). As analogy to 
option 1's ESNI problem, we even forgot to allow the server to express curve 
preferences. TLS 1.3 combined signature algorithm considerations into a single 
codepoint to address all this.

* Cipher suites in TLS 1.2 were a mess because they were half-combined and 
half-split. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 said to use some ECDHE key 
exchange, but you need to check if you have a NamedGroup in common first. It 
said to use ECDSA, but you need to check signature algorithms (which themselves 
cross-reference curves) first. Early drafts of TLS 1.3 had it even worse, where 
a TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 full handshake morphed into 
TLS_ECDHE_PSK_WITH_AES_128_GCM_SHA256 on resumption. Thus, TLS 1.3 cipher 
suites negotiate solely AEAD + PRF hash.

In fairness to TLS 1.2, some of this was a consequence of TLS 1.2's evolution 
over time as incremental extensions over SSL 3.0. And sometimes we do need to 
pay costs like these. But hybrid key exchanges fit into the NamedGroup "API" 
just fine, so option 2 is the clear answer. Code points are cheap. Protocol 
complexity is much more expensive.

It's true that standards are often underspecified. This means the IETF should 
finish the job, not pass all variations through. RSA-PSS is a clear example of 
what to avoid. It takes more bytes to merely utter "RSA-PSS with SHA-256 and 
usual parameters" in X.509 than to encode an 

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Scott Fluhrer (sfluhrer)]

I believe that one important property (of either of the options I listed) is a 
nice fallback if an enhanced client talks to an older server.  In both cases, 
the server will see a series of named groups that it doesn’t know (which it 
will ignore), and possibility an extension it doesn’t know (which it will 
ignore); the server will accept either a named group that it does understand 
(if the client did propose a traditional group as a fall back), or it will come 
to the correct conclusion that the two sides have no mutually acceptable 
security policy.

It is not clear if the proposal you outlined share this property; do you 
duplicate a payload that an unenhanced server would assume only occurs once?

From: TLS  On Behalf Of Andrei Popov
Sent: Tuesday, July 30, 2019 2:48 PM
To: David Benjamin ; Watson Ladd 
Cc: TLS List 
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

Given these options, I also prefer option 2, for some of the same reasons.

For my understanding though, why not have the client advertise support for 
hybrid-key-exchange (e.g. via a “flag” extension) and then KeyShareServerHello 
can contain two KeyShareEntries (essentially, using the same format as 
KeyShareClientHello? This would solve the Cartesian product issue.

Cheers,

Andrei

From: TLS mailto:tls-boun...@ietf.org>> On Behalf Of 
David Benjamin
Sent: Tuesday, July 30, 2019 11:24 AM
To: Watson Ladd mailto:watsonbl...@gmail.com>>
Cc: TLS List mailto:tls@ietf.org>>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

I think this underestimates the complexity cost of option 1 to the protocol and 
implementations. Option 1 means group negotiation includes entire codepoints 
whose meaning cannot be determined without a parallel extension. This compounds 
across everything which interacts with named groups, impacting everything from 
APIs to config file formats to even UI surfaces. Other uses of NamedGroups are 
impacted too. For instance, option 2 fits into draft-ietf-tls-esni as-is. 
Option 1 requires injecting hybrid_extension into ESNI somehow. Analysis must 
further check every use, say, incorporates this parallel lookup table into 
transcript-like measures.

The lesson from TLS 1.2 code points is not combined codepoints vs. split ones. 
Rather, the lesson is to avoid interdependent decisions:

* Signature algorithms in TLS 1.2 were a mess because the ECDSA codepoints 
required cross-referencing against the supported curves list. The verifier 
could not express some preferences (signing SHA-512 with P-256 is silly, and 
mixing hash+curve pairs in ECDSA is slightly off in general). As analogy to 
option 1's ESNI problem, we even forgot to allow the server to express curve 
preferences. TLS 1.3 combined signature algorithm considerations into a single 
codepoint to address all this.

* Cipher suites in TLS 1.2 were a mess because they were half-combined and 
half-split. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 said to use some ECDHE key 
exchange, but you need to check if you have a NamedGroup in common first. It 
said to use ECDSA, but you need to check signature algorithms (which themselves 
cross-reference curves) first. Early drafts of TLS 1.3 had it even worse, where 
a TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 full handshake morphed into 
TLS_ECDHE_PSK_WITH_AES_128_GCM_SHA256 on resumption. Thus, TLS 1.3 cipher 
suites negotiate solely AEAD + PRF hash.

In fairness to TLS 1.2, some of this was a consequence of TLS 1.2's evolution 
over time as incremental extensions over SSL 3.0. And sometimes we do need to 
pay costs like these. But hybrid key exchanges fit into the NamedGroup "API" 
just fine, so option 2 is the clear answer. Code points are cheap. Protocol 
complexity is much more expensive.

It's true that standards are often underspecified. This means the IETF should 
finish the job, not pass all variations through. RSA-PSS is a clear example of 
what to avoid. It takes more bytes to merely utter "RSA-PSS with SHA-256 and 
usual parameters" in X.509 than to encode an entire ECDSA signature! We should 
not define more than a handful of options, regardless of the encoding..

On Tue, Jul 30, 2019 at 12:18 PM Watson Ladd 
mailto:watsonbl...@gmail.com>> wrote:

On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) 
mailto:sfluh...@cisco.com>> wrote:
During the physical meeting in Montreal, we had a discussion about postquantum 
security, and in particular, on how one might want to negotiate several 
different ‘groups’ simultaneously (because there might not be one group that is 
entirely trusted, and I put ‘groups’ in scarequotes because postquantum key 
exchanges are typically not formed from a Diffie-Hellman group).

At the meeting, there were two options presented:

Option 1: as the supported group, we insert a ‘hybrid marker’ (and include an 
extension that map lists which combination the hybrid marker stands for)
For example, the client might list 

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Andrei Popov]

Sure, hybrid-key-exchange “flag” extension is too generic. We could have the 
client advertise something like one-traditional-and-one-PQ, and still avoid the 
Cartesian product.
From: TLS  On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: Tuesday, July 30, 2019 12:12 PM
To: David Benjamin 
Cc: TLS List 
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

The nuisance with just a flag is the client can't express [what I think are] 
reasonable preferences. It should be able to say things like:

Offhand, I don’t see at all why the client should be able to say any of these 
“don’t”s:

* Don't do X25519 + P-256. This is just silly.
* Don't do PQ1 on its own. I really want the PQ scheme paired with something 
more established.
* Don't do PQ1 + PQ2. I said something more established, please.
* Don't do PQ1 + X25519 + P-256. Why are you doing three of these?
* Don't do PQ1 + PQ2 + PQ3 + PQ4 + X25519 + P-256 + P-384 + FFDHE2048 + 
FFDHE3072, oww my head.

This is the only thing that IMHO the client should be able to say:

* PQ1 + X25519 is cool. I like that combo.




On Tue, Jul 30, 2019 at 2:48 PM Andrei Popov 
mailto:andrei.po...@microsoft.com>> wrote:
Given these options, I also prefer option 2, for some of the same reasons.

For my understanding though, why not have the client advertise support for 
hybrid-key-exchange (e.g. via a “flag” extension) and then KeyShareServerHello 
can contain two KeyShareEntries (essentially, using the same format as 
KeyShareClientHello? This would solve the Cartesian product issue.

Cheers,

Andrei

From: TLS mailto:tls-boun...@ietf.org>> On Behalf Of 
David Benjamin
Sent: Tuesday, July 30, 2019 11:24 AM
To: Watson Ladd mailto:watsonbl...@gmail.com>>
Cc: TLS List mailto:tls@ietf.org>>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

I think this underestimates the complexity cost of option 1 to the protocol and 
implementations. Option 1 means group negotiation includes entire codepoints 
whose meaning cannot be determined without a parallel extension. This compounds 
across everything which interacts with named groups, impacting everything from 
APIs to config file formats to even UI surfaces. Other uses of NamedGroups are 
impacted too. For instance, option 2 fits into draft-ietf-tls-esni as-is. 
Option 1 requires injecting hybrid_extension into ESNI somehow. Analysis must 
further check every use, say, incorporates this parallel lookup table into 
transcript-like measures.

The lesson from TLS 1.2 code points is not combined codepoints vs. split ones. 
Rather, the lesson is to avoid interdependent decisions:

* Signature algorithms in TLS 1.2 were a mess because the ECDSA codepoints 
required cross-referencing against the supported curves list. The verifier 
could not express some preferences (signing SHA-512 with P-256 is silly, and 
mixing hash+curve pairs in ECDSA is slightly off in general). As analogy to 
option 1's ESNI problem, we even forgot to allow the server to express curve 
preferences. TLS 1.3 combined signature algorithm considerations into a single 
codepoint to address all this.

* Cipher suites in TLS 1.2 were a mess because they were half-combined and 
half-split. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 said to use some ECDHE key 
exchange, but you need to check if you have a NamedGroup in common first. It 
said to use ECDSA, but you need to check signature algorithms (which themselves 
cross-reference curves) first. Early drafts of TLS 1.3 had it even worse, where 
a TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 full handshake morphed into 
TLS_ECDHE_PSK_WITH_AES_128_GCM_SHA256 on resumption. Thus, TLS 1.3 cipher 
suites negotiate solely AEAD + PRF hash.

In fairness to TLS 1.2, some of this was a consequence of TLS 1.2's evolution 
over time as incremental extensions over SSL 3.0. And sometimes we do need to 
pay costs like these. But hybrid key exchanges fit into the NamedGroup "API" 
just fine, so option 2 is the clear answer. Code points are cheap. Protocol 
complexity is much more expensive.

It's true that standards are often underspecified. This means the IETF should 
finish the job, not pass all variations through. RSA-PSS is a clear example of 
what to avoid. It takes more bytes to merely utter "RSA-PSS with SHA-256 and 
usual parameters" in X.509 than to encode an entire ECDSA signature! We should 
not define more than a handful of options, regardless of the encoding...

On Tue, Jul 30, 2019 at 12:18 PM Watson Ladd 
mailto:watsonbl...@gmail.com>> wrote:

On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) 
mailto:sfluh...@cisco.com>> wrote:
During the physical meeting in Montreal, we had a discussion about postquantum 
security, and in particular, on how one might want to negotiate several 
different ‘groups’ simultaneously (because there might not be one group that is 
entirely trusted, and I put ‘groups’ in scarequotes because postquantum key 
exchanges are typically not formed from a 

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Blumenthal, Uri - 0553 - MITLL]

One more thing: I would expect to use SIDH rather than SIKE. 

 

Because to emulate the security advantages of DH, you’d have to run two SIKE’s 
– one in each direction.

 

 

From: TLS  on behalf of "Panos Kampanakis (pkampana)" 

Date: Tuesday, July 30, 2019 at 3:37 PM
To: "Scott Fluhrer (sfluhrer)" , "" 

Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

 

+1 for option 2. The combinatoric explosion and complexity of 1 is unnecessary. 
I expect that just a few, conservative, acceptably efficient, classical+PQ 
combinations need to be standardized and used. Combining a classical algo with 
more than one postquantum algorithms in a key exchange does not seem practical 
based on the PQ candidates key sizes and performance.

 

Panos

 

 

From: TLS  On Behalf Of Scott Fluhrer (sfluhrer)
Sent: Tuesday, July 30, 2019 11:21 AM
To:  
Subject: [TLS] Options for negotiating hybrid key exchanges for postquantum

 

During the physical meeting in Montreal, we had a discussion about postquantum 
security, and in particular, on how one might want to negotiate several 
different ‘groups’ simultaneously (because there might not be one group that is 
entirely trusted, and I put ‘groups’ in scarequotes because postquantum key 
exchanges are typically not formed from a Diffie-Hellman group).

 

At the meeting, there were two options presented:

 

Option 1: as the supported group, we insert a ‘hybrid marker’ (and include an 
extension that map lists which combination the hybrid marker stands for)

For example, the client might list in his supported groups 
hybrid_marker_0 and hybrid_marker_1, and there would be a separate extension 
that lists hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 + 
NTRUPR653.  The server would then look up the meanings of hybrid_marker_0 and 1 
in the extension, and then compare that against his security policy.

In this option, we would ask IANA to allocate code points for the various 
individual postquantum key exchanges (in this example, SIKEp434 and NTRUPR653), 
as well a range of code points for the various hybrid_markers.

 

Option 2: we have code points for all the various combinations that we may want 
to support; hence IANA might allocate a code point X25519_SIKEp434 and another 
code point for X25519_NTRUPR653.  With this option, the client would list 
X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.

In this option, we would ask IANA to allocate code points for 
all the various combinations that we want allow to be negotiated.

 

I would like to make an argument in favor of option 1:

 

-  It is likely that not everyone will be satisified with “X25519 plus 
one of a handful of specific postquantum algorithms”; some may prefer another 
elliptic curve (for example, x448), or perhaps even a MODP group; I have talked 
to people who do not trust ECC); in addition, other people might not trust a 
single postquantum algorithm, and may want to rely on both (for example) SIKE 
and NewHope (which are based on very different hard problems).  With option 2, 
we could try to anticipate all the common combintations (such as 
P384_SIKEp434_NEWHOPE512CCA), however that could very well end up as a lot of 
combinations.

-  There are likely to be several NIST-approved postquantum key 
exchanges, and each of those key exchanges are likely to have a number of 
supported parameter sets (if we take the specific postquantum key exchange as 
analogous to th ECDH protocool, the “parameter set” could be thought of an 
analogous to the specific elliptuc curve, and it modifies the key share size, 
the performance and sometimes the security properties).  In fact, one of the 
NIST submissoins currently has 30 parameter sets defined.  Hence, even if NIST 
doesn’t approve all the parameter sets (or some of them do not make sense for 
TLS in any scenario), we might end up with 20 or more different key 
exchange/parameter set combinations that do make sense for some scenario that 
uses tLS (be it in a tranditional PC client/server, a wireless client, two 
cloud devices communicating or an IOT device).

-  In addition, we are likely to support additional primitives in the 
future; possibly National curves (e.g. Brainpool), or additional Postquantum 
algorithms (or additional parameter sets to existing ones).  Of course, once we 
add that code point, we’ll need to add the additional code points for all the 
combinations that it’ll make sense in (very much like we had to add a number of 
ciphersuites whenever we added a new encryption algorithm into TLS 1.2).

 

It seemds reasonable to me that the combination of these two factors are likely 
to cause us (should we select option 2) to define a very large number of code 
points to cover all the various options that people need.

 

Now, this is based on speculation (both of the NIST process, and additional 
primitives that will be added to the 

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Panos Kampanakis (pkampana)]

+1 for option 2. The combinatoric explosion and complexity of 1 is unnecessary. 
I expect that just a few, conservative, acceptably efficient, classical+PQ 
combinations need to be standardized and used. Combining a classical algo with 
more than one postquantum algorithms in a key exchange does not seem practical 
based on the PQ candidates key sizes and performance.

Panos


From: TLS  On Behalf Of Scott Fluhrer (sfluhrer)
Sent: Tuesday, July 30, 2019 11:21 AM
To:  
Subject: [TLS] Options for negotiating hybrid key exchanges for postquantum

During the physical meeting in Montreal, we had a discussion about postquantum 
security, and in particular, on how one might want to negotiate several 
different 'groups' simultaneously (because there might not be one group that is 
entirely trusted, and I put 'groups' in scarequotes because postquantum key 
exchanges are typically not formed from a Diffie-Hellman group).

At the meeting, there were two options presented:

Option 1: as the supported group, we insert a 'hybrid marker' (and include an 
extension that map lists which combination the hybrid marker stands for)
For example, the client might list in his supported groups 
hybrid_marker_0 and hybrid_marker_1, and there would be a separate extension 
that lists hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 + 
NTRUPR653.  The server would then look up the meanings of hybrid_marker_0 and 1 
in the extension, and then compare that against his security policy.
In this option, we would ask IANA to allocate code points for the various 
individual postquantum key exchanges (in this example, SIKEp434 and NTRUPR653), 
as well a range of code points for the various hybrid_markers.

Option 2: we have code points for all the various combinations that we may want 
to support; hence IANA might allocate a code point X25519_SIKEp434 and another 
code point for X25519_NTRUPR653.  With this option, the client would list 
X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.
In this option, we would ask IANA to allocate code points for 
all the various combinations that we want allow to be negotiated.

I would like to make an argument in favor of option 1:


  *   It is likely that not everyone will be satisified with "X25519 plus one 
of a handful of specific postquantum algorithms"; some may prefer another 
elliptic curve (for example, x448), or perhaps even a MODP group; I have talked 
to people who do not trust ECC); in addition, other people might not trust a 
single postquantum algorithm, and may want to rely on both (for example) SIKE 
and NewHope (which are based on very different hard problems).  With option 2, 
we could try to anticipate all the common combintations (such as 
P384_SIKEp434_NEWHOPE512CCA), however that could very well end up as a lot of 
combinations.
  *   There are likely to be several NIST-approved postquantum key exchanges, 
and each of those key exchanges are likely to have a number of supported 
parameter sets (if we take the specific postquantum key exchange as analogous 
to th ECDH protocool, the "parameter set" could be thought of an analogous to 
the specific elliptuc curve, and it modifies the key share size, the 
performance and sometimes the security properties).  In fact, one of the NIST 
submissoins currently has 30 parameter sets defined.  Hence, even if NIST 
doesn't approve all the parameter sets (or some of them do not make sense for 
TLS in any scenario), we might end up with 20 or more different key 
exchange/parameter set combinations that do make sense for some scenario that 
uses tLS (be it in a tranditional PC client/server, a wireless client, two 
cloud devices communicating or an IOT device).
  *   In addition, we are likely to support additional primitives in the 
future; possibly National curves (e.g. Brainpool), or additional Postquantum 
algorithms (or additional parameter sets to existing ones).  Of course, once we 
add that code point, we'll need to add the additional code points for all the 
combinations that it'll make sense in (very much like we had to add a number of 
ciphersuites whenever we added a new encryption algorithm into TLS 1.2).

It seemds reasonable to me that the combination of these two factors are likely 
to cause us (should we select option 2) to define a very large number of code 
points to cover all the various options that people need.

Now, this is based on speculation (both of the NIST process, and additional 
primitives that will be added to the protocol), and one objection I've heard is 
"we don't know what's going to happen, and so why would we make decisions based 
on this speculation?"  I agree that we have lack of knowledge; however it seems 
to me that a lack of knowledge is an argument in favor of selecting the more 
flexible option (which, in my opinion, is option 1, as it allows the 
negotiation of combinations of key exchanges that the WG has not anticipated).

My plea: 

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Blumenthal, Uri - 0553 - MITLL]

The nuisance with just a flag is the client can't express [what I think are] 
reasonable preferences. It should be able to say things like: 

 

Offhand, I don’t see at all why the client should be able to say any of these 
“don’t”s:

 

* Don't do X25519 + P-256. This is just silly.

* Don't do PQ1 on its own. I really want the PQ scheme paired with something 
more established.

* Don't do PQ1 + PQ2. I said something more established, please.

* Don't do PQ1 + X25519 + P-256. Why are you doing three of these?

* Don't do PQ1 + PQ2 + PQ3 + PQ4 + X25519 + P-256 + P-384 + FFDHE2048 + 
FFDHE3072, oww my head.

 

This is the only thing that IMHO the client should be able to say:

 

* PQ1 + X25519 is cool. I like that combo.

 

 

 

 

On Tue, Jul 30, 2019 at 2:48 PM Andrei Popov  wrote:

Given these options, I also prefer option 2, for some of the same reasons.

 

For my understanding though, why not have the client advertise support for 
hybrid-key-exchange (e.g. via a “flag” extension) and then KeyShareServerHello 
can contain two KeyShareEntries (essentially, using the same format as 
KeyShareClientHello? This would solve the Cartesian product issue.

 

Cheers,

 

Andrei

 

From: TLS  On Behalf Of David Benjamin
Sent: Tuesday, July 30, 2019 11:24 AM
To: Watson Ladd 
Cc: TLS List 
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

 

I think this underestimates the complexity cost of option 1 to the protocol and 
implementations. Option 1 means group negotiation includes entire codepoints 
whose meaning cannot be determined without a parallel extension. This compounds 
across everything which interacts with named groups, impacting everything from 
APIs to config file formats to even UI surfaces. Other uses of NamedGroups are 
impacted too. For instance, option 2 fits into draft-ietf-tls-esni as-is. 
Option 1 requires injecting hybrid_extension into ESNI somehow.. Analysis must 
further check every use, say, incorporates this parallel lookup table into 
transcript-like measures.

 

The lesson from TLS 1.2 code points is not combined codepoints vs. split ones. 
Rather, the lesson is to avoid interdependent decisions:

 

* Signature algorithms in TLS 1.2 were a mess because the ECDSA codepoints 
required cross-referencing against the supported curves list. The verifier 
could not express some preferences (signing SHA-512 with P-256 is silly, and 
mixing hash+curve pairs in ECDSA is slightly off in general). As analogy to 
option 1's ESNI problem, we even forgot to allow the server to express curve 
preferences. TLS 1.3 combined signature algorithm considerations into a single 
codepoint to address all this.

 

* Cipher suites in TLS 1.2 were a mess because they were half-combined and 
half-split. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 said to use some ECDHE key 
exchange, but you need to check if you have a NamedGroup in common first. It 
said to use ECDSA, but you need to check signature algorithms (which themselves 
cross-reference curves) first. Early drafts of TLS 1.3 had it even worse, where 
a TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 full handshake morphed into 
TLS_ECDHE_PSK_WITH_AES_128_GCM_SHA256 on resumption. Thus, TLS 1.3 cipher 
suites negotiate solely AEAD + PRF hash.

 

In fairness to TLS 1.2, some of this was a consequence of TLS 1.2's evolution 
over time as incremental extensions over SSL 3.0. And sometimes we do need to 
pay costs like these. But hybrid key exchanges fit into the NamedGroup "API" 
just fine, so option 2 is the clear answer. Code points are cheap. Protocol 
complexity is much more expensive.

 

It's true that standards are often underspecified. This means the IETF should 
finish the job, not pass all variations through. RSA-PSS is a clear example of 
what to avoid. It takes more bytes to merely utter "RSA-PSS with SHA-256 and 
usual parameters" in X.509 than to encode an entire ECDSA signature! We should 
not define more than a handful of options, regardless of the encoding..

 

On Tue, Jul 30, 2019 at 12:18 PM Watson Ladd  wrote:

 

On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer)  
wrote:

During the physical meeting in Montreal, we had a discussion about postquantum 
security, and in particular, on how one might want to negotiate several 
different ‘groups’ simultaneously (because there might not be one group that is 
entirely trusted, and I put ‘groups’ in scarequotes because postquantum key 
exchanges are typically not formed from a Diffie-Hellman group).

 

At the meeting, there were two options presented:

 

Option 1: as the supported group, we insert a ‘hybrid marker’ (and include an 
extension that map lists which combination the hybrid marker stands for)

For example, the client might list in his supported groups 
hybrid_marker_0 and hybrid_marker_1, and there would be a separate extension 
that lists hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 + 
NTRUPR653.  The server would 

Re: [TLS] Drafts for batch signing and PKCS#1 v1.5

[David Benjamin]

Oops. draft-davidben-tls-batch-signing-00 cites
draft-davidben-http2-tls13-00. That should be
draft-davidben-tls13-pkcs1-00. (The XML file took a really long time to be
created, so I manually tried to recreate it based on another file and
forgot to update one of the fields.) I'll fix this in -01.

On Mon, Jul 29, 2019 at 8:15 PM David Benjamin 
wrote:

> Hi all,
>
> I’ve just uploaded a pair of drafts relating to signatures in TLS 1.3.
> https://tools.ietf.org/html/draft-davidben-tls13-pkcs1-00
> https://tools.ietf.org/html/draft-davidben-tls-batch-signing-00
>
> The first introduces optional legacy codepoints for PKCS#1 v1.5 signatures
> with client certificates. This is unfortunate, but I think we should do it.
> On the Chrome side, we’ve encountered some headaches with the TLS 1.3 PSS
> requirement which are unique to client certificates. The document describes
> the motivations in detail.
>
> The second describes a batch signing mechanism for TLS using Merkle trees..
> It allows TLS clients and servers to better handle signing load. I think it
> could be beneficial for a number of DoS and remote key scenarios.
>
> Thoughts?
>
> David
>
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[David Benjamin]

The nuisance with just a flag is the client can't express [what I think
are] reasonable preferences. It should be able to say things like:

* Don't do X25519 + P-256. This is just silly.
* Don't do PQ1 on its own. I really want the PQ scheme paired with
something more established.
* Don't do PQ1 + PQ2. I said something more established, please.
* PQ1 + X25519 is cool. I like that combo.
* Don't do PQ1 + X25519 + P-256. Why are you doing three of these?
* Don't do PQ1 + PQ2 + PQ3 + PQ4 + X25519 + P-256 + P-384 + FFDHE2048 +
FFDHE3072, oww my head.

We can make things implicit by categorizing named groups and building all
this into the protocol itself, but I think that's an unnecessary moving
part.

On Tue, Jul 30, 2019 at 2:48 PM Andrei Popov 
wrote:

> Given these options, I also prefer option 2, for some of the same reasons..
>
>
>
> For my understanding though, why not have the client advertise support for
> hybrid-key-exchange (e.g. via a “flag” extension) and then
> KeyShareServerHello can contain two KeyShareEntries (essentially, using the
> same format as KeyShareClientHello? This would solve the Cartesian product
> issue.
>
>
>
> Cheers,
>
>
>
> Andrei
>
>
>
> *From:* TLS  *On Behalf Of * David Benjamin
> *Sent:* Tuesday, July 30, 2019 11:24 AM
> *To:* Watson Ladd 
> *Cc:* TLS List 
> *Subject:* Re: [TLS] Options for negotiating hybrid key exchanges for
> postquantum
>
>
>
> I think this underestimates the complexity cost of option 1 to the
> protocol and implementations. Option 1 means group negotiation includes
> entire codepoints whose meaning cannot be determined without a parallel
> extension. This compounds across everything which interacts with named
> groups, impacting everything from APIs to config file formats to even UI
> surfaces. Other uses of NamedGroups are impacted too. For instance, option
> 2 fits into draft-ietf-tls-esni as-is. Option 1 requires
> injecting hybrid_extension into ESNI somehow. Analysis must further check
> every use, say, incorporates this parallel lookup table into
> transcript-like measures.
>
>
>
> The lesson from TLS 1.2 code points is not combined codepoints vs. split
> ones. Rather, the lesson is to avoid interdependent decisions:
>
>
>
> * Signature algorithms in TLS 1.2 were a mess because the ECDSA codepoints
> required cross-referencing against the supported curves list. The verifier
> could not express some preferences (signing SHA-512 with P-256 is silly,
> and mixing hash+curve pairs in ECDSA is slightly off in general). As
> analogy to option 1's ESNI problem, we even forgot to allow the server to
> express curve preferences. TLS 1.3 combined signature algorithm
> considerations into a single codepoint to address all this.
>
>
>
> * Cipher suites in TLS 1.2 were a mess because they were half-combined and
> half-split. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 said to use some ECDHE
> key exchange, but you need to check if you have a NamedGroup in common
> first. It said to use ECDSA, but you need to check signature algorithms
> (which themselves cross-reference curves) first. Early drafts of TLS 1.3
> had it even worse, where a TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 full
> handshake morphed into TLS_ECDHE_PSK_WITH_AES_128_GCM_SHA256 on resumption.
> Thus, TLS 1.3 cipher suites negotiate solely AEAD + PRF hash.
>
>
>
> In fairness to TLS 1.2, some of this was a consequence of TLS 1.2's
> evolution over time as incremental extensions over SSL 3.0. And sometimes
> we do need to pay costs like these. But hybrid key exchanges fit into the
> NamedGroup "API" just fine, so option 2 is the clear answer. Code points
> are cheap. Protocol complexity is much more expensive.
>
>
>
> It's true that standards are often underspecified. This means the IETF
> should finish the job, not pass all variations through. RSA-PSS is a clear
> example of what to avoid. It takes more bytes to merely utter "RSA-PSS with
> SHA-256 and usual parameters" in X.509 than to encode an entire ECDSA
> signature! We should not define more than a handful of options, regardless
> of the encoding..
>
>
>
> On Tue, Jul 30, 2019 at 12:18 PM Watson Ladd 
> wrote:
>
>
>
> On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) 
> wrote:
>
> During the physical meeting in Montreal, we had a discussion about
> postquantum security, and in particular, on how one might want to negotiate
> several different ‘groups’ simultaneously (because there might not be one
> group that is entirely trusted, and I put ‘groups’ in scarequotes because
> postquantum key exchanges are typically not formed from a Diffie-Hellman
> group).
>
>
>
> At the meeting, there were two options presented:
>
>
>
> Option 1: as the supported group, we insert a ‘hybrid marker’ (and include
> an extension that map lists which combination the hybrid marker stands for)
>
> For example, the client might list in his supported groups
> hybrid_marker_0 and hybrid_marker_1, and there would be a separate
> extension that 

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Scott Fluhrer (sfluhrer)]

From: Watson Ladd  

> On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) 
>  wrote:
>> During the physical meeting in Montreal, we had a discussion about 
>> postquantum security, and in particular, on how one might want to negotiate 
>> several different ‘groups’ simultaneously (because there might not be one 
>> group that is entirely trusted, and I put ‘groups’ in scarequotes because 
>> postquantum key exchanges are typically not formed from a Diffie-Hellman 
>> group).
>> 
>> At the meeting, there were two options presented:
 >> 
>> Option 1: as the supported group, we insert a ‘hybrid marker’ (and include 
>> an extension that map lists which combination the hybrid marker stands for)
>>    For example, the client might list in his supported groups 
>>hybrid_marker_0 and hybrid_marker_1, and there would be a separate extension 
>>that lists hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 + 
>>NTRUPR653.  The server would then look up the meanings of hybrid_marker_0 and 
>>1 in the extension, and then compare that against his security policy.
>>In this option, we would ask IANA to allocate code points for the 
>> various individual postquantum key exchanges (in this example, SIKEp434 and 
>> NTRUPR653), as well a range of code points for the various hybrid_markers.
 >>
>> Option 2: we have code points for all the various combinations that we may 
>> want to support; hence IANA might allocate a code point X25519_SIKEp434 and 
>> another code point for X25519_NTRUPR653.  With this option, the client would 
>> list X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.
>>     In this option, we would ask IANA to allocate code points 
>> for all the various combinations that we want allow to be negotiated. 
>> 
>
> Are people actually going to use hybrid encryption post NIST? The actual 
> deployments today  for experiment have all fit option 2 and hybrids are 
> unlikely in the future. 

it sounds like you are questioning, not between option 1 or option 2, but 
instead whether we need either of them at all.  Those are both methods of 
negotiating multiple keygroups; it appears that you don’t see any need for such 
an option.

Perhaps we need to have such a debate.  Here is one opinion (mine, but I'm 
pretty sure it is shared by others): the various NIST candidates are based on 
hard problems that were only recently studied (e.g. supersingular isogenies, 
Quasicyclic codes), or have cryptanalytic methods that are quite difficult to 
fully assess (e.g. Lattices).  Even after NIST and CFRG have blessed one or 
more of them, it would seem reasonable to me that we wouldn't want to place all 
our security eggs in that one basket.  We currently place all our trust in DH 
or ECDH; however those have been studied for 30+ years - we are not there yet 
for most of the postquantum algorithms.

Hence, it seems reasonable to me that we give users the option of being able to 
rely on multiple methods.

>
> My objection to 1 is it gets very messy. Do we use only the hybrids we both 
> support? What if I throw a bunch of expensive things together? No reason we 
> need a hybrid scheme! 

Actually, I personally don't see the messiness; if the client wants to propose 
X25519 + NTRUPR653, he places hybrid_marker_1 in the supported groups list, and 
adds hybrid_marker_1 = X25519 + NTRUPR653 to his hybrid group extension.  If 
the server sees hybrid_marker_1 in the client's supported group list, he looks 
for the definition in the hybrid group extension, and processes the policy 
accordingly.  The logic in both direction would appear (at least to me) to be 
reasonably simple (and it doesn’t get more complex if we feel the need to 
negotiate three or more key exchanges).

As for the expense, that is for the user to judge.  If the user decides that he 
is willing to pay for a series of expensive key exchanges, that should be his 
decision to make.  Option 1 gives the user the ability to negotiate a series of 
expensive (but perhaps more trusted) algorithms, it doesn't mandate that the 
user do so.

And, as for a need for a hybrid scheme (either option 1, option 2 or something 
else), I do believe that there will be a demand for it, even after NIST and 
CFRG has given their blessing, as their will be users who will not fully trust 
a new scheme that was just endorsed (but they do want some protection against 
future quantum computers).

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[David Benjamin]

I think this underestimates the complexity cost of option 1 to the protocol
and implementations. Option 1 means group negotiation includes entire
codepoints whose meaning cannot be determined without a parallel extension.
This compounds across everything which interacts with named groups,
impacting everything from APIs to config file formats to even UI surfaces.
Other uses of NamedGroups are impacted too. For instance, option 2 fits
into draft-ietf-tls-esni as-is. Option 1 requires
injecting hybrid_extension into ESNI somehow. Analysis must further check
every use, say, incorporates this parallel lookup table into
transcript-like measures.

The lesson from TLS 1.2 code points is not combined codepoints vs. split
ones. Rather, the lesson is to avoid interdependent decisions:

* Signature algorithms in TLS 1.2 were a mess because the ECDSA codepoints
required cross-referencing against the supported curves list. The verifier
could not express some preferences (signing SHA-512 with P-256 is silly,
and mixing hash+curve pairs in ECDSA is slightly off in general). As
analogy to option 1's ESNI problem, we even forgot to allow the server to
express curve preferences. TLS 1.3 combined signature algorithm
considerations into a single codepoint to address all this.

* Cipher suites in TLS 1.2 were a mess because they were half-combined and
half-split. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 said to use some ECDHE
key exchange, but you need to check if you have a NamedGroup in common
first. It said to use ECDSA, but you need to check signature algorithms
(which themselves cross-reference curves) first. Early drafts of TLS 1.3
had it even worse, where a TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 full
handshake morphed into TLS_ECDHE_PSK_WITH_AES_128_GCM_SHA256 on resumption.
Thus, TLS 1.3 cipher suites negotiate solely AEAD + PRF hash.

In fairness to TLS 1.2, some of this was a consequence of TLS 1.2's
evolution over time as incremental extensions over SSL 3.0. And sometimes
we do need to pay costs like these. But hybrid key exchanges fit into the
NamedGroup "API" just fine, so option 2 is the clear answer. Code points
are cheap. Protocol complexity is much more expensive.

It's true that standards are often underspecified. This means the IETF
should finish the job, not pass all variations through. RSA-PSS is a clear
example of what to avoid. It takes more bytes to merely utter "RSA-PSS with
SHA-256 and usual parameters" in X.509 than to encode an entire ECDSA
signature! We should not define more than a handful of options, regardless
of the encoding.

On Tue, Jul 30, 2019 at 12:18 PM Watson Ladd  wrote:

>
>
> On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) 
> wrote:
>
>> During the physical meeting in Montreal, we had a discussion about
>> postquantum security, and in particular, on how one might want to negotiate
>> several different ‘groups’ simultaneously (because there might not be one
>> group that is entirely trusted, and I put ‘groups’ in scarequotes because
>> postquantum key exchanges are typically not formed from a Diffie-Hellman
>> group).
>>
>>
>>
>> At the meeting, there were two options presented:
>>
>>
>>
>> Option 1: as the supported group, we insert a ‘hybrid marker’ (and
>> include an extension that map lists which combination the hybrid marker
>> stands for)
>>
>> For example, the client might list in his supported
>> groups hybrid_marker_0 and hybrid_marker_1, and there would be a separate
>> extension that lists hybrid_marker_0 = X25519 + SIKEp434 and
>> hybrid_marker_1 = X25519 + NTRUPR653.  The server would then look up the
>> meanings of hybrid_marker_0 and 1 in the extension, and then compare that
>> against his security policy.
>>
>> In this option, we would ask IANA to allocate code points for the various
>> individual postquantum key exchanges (in this example, SIKEp434 and
>> NTRUPR653), as well a range of code points for the various hybrid_markers.
>>
>
>>
>> Option 2: we have code points for all the various combinations that we
>> may want to support; hence IANA might allocate a code point X25519_SIKEp434
>> and another code point for X25519_NTRUPR653.  With this option, the client
>> would list X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.
>>
>> In this option, we would ask IANA to allocate code points
>> for all the various combinations that we want allow to be negotiated.
>>
>>
>>
>> I would like to make an argument in favor of option 1:
>>
>>
>>
>>- It is likely that not everyone will be satisified with “X25519 plus
>>one of a handful of specific postquantum algorithms”; some may prefer
>>another elliptic curve (for example, x448), or perhaps even a MODP group; 
>> I
>>have talked to people who do not trust ECC); in addition, other people
>>might not trust a single postquantum algorithm, and may want to rely on
>>both (for example) SIKE and NewHope (which are based on very different 
>> hard
>>

Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

[Watson Ladd]

On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) 
wrote:

> During the physical meeting in Montreal, we had a discussion about
> postquantum security, and in particular, on how one might want to negotiate
> several different ‘groups’ simultaneously (because there might not be one
> group that is entirely trusted, and I put ‘groups’ in scarequotes because
> postquantum key exchanges are typically not formed from a Diffie-Hellman
> group).
>
>
>
> At the meeting, there were two options presented:
>
>
>
> Option 1: as the supported group, we insert a ‘hybrid marker’ (and include
> an extension that map lists which combination the hybrid marker stands for)
>
> For example, the client might list in his supported groups
> hybrid_marker_0 and hybrid_marker_1, and there would be a separate
> extension that lists hybrid_marker_0 = X25519 + SIKEp434 and
> hybrid_marker_1 = X25519 + NTRUPR653.  The server would then look up the
> meanings of hybrid_marker_0 and 1 in the extension, and then compare that
> against his security policy.
>
> In this option, we would ask IANA to allocate code points for the various
> individual postquantum key exchanges (in this example, SIKEp434 and
> NTRUPR653), as well a range of code points for the various hybrid_markers..
>

>
> Option 2: we have code points for all the various combinations that we may
> want to support; hence IANA might allocate a code point X25519_SIKEp434 and
> another code point for X25519_NTRUPR653.  With this option, the client
> would list X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups..
>
> In this option, we would ask IANA to allocate code points
> for all the various combinations that we want allow to be negotiated.
>
>
>
> I would like to make an argument in favor of option 1:
>
>
>
>- It is likely that not everyone will be satisified with “X25519 plus
>one of a handful of specific postquantum algorithms”; some may prefer
>another elliptic curve (for example, x448), or perhaps even a MODP group; I
>have talked to people who do not trust ECC); in addition, other people
>might not trust a single postquantum algorithm, and may want to rely on
>both (for example) SIKE and NewHope (which are based on very different hard
>problems).  With option 2, we could try to anticipate all the common
>combintations (such as P384_SIKEp434_NEWHOPE512CCA), however that could
>very well end up as a lot of combinations.
>- There are likely to be several NIST-approved postquantum key
>exchanges, and each of those key exchanges are likely to have a number of
>supported parameter sets (if we take the specific postquantum key exchange
>as analogous to th ECDH protocool, the “parameter set” could be thought of
>an analogous to the specific elliptuc curve, and it modifies the key share
>size, the performance and sometimes the security properties).  In fact, one
>of the NIST submissoins currently has 30 parameter sets defined.  Hence,
>even if NIST doesn’t approve all the parameter sets (or some of them do not
>make sense for TLS in any scenario), we might end up with 20 or more
>different key exchange/parameter set combinations that do make sense for
>some scenario that uses tLS (be it in a tranditional PC client/server, a
>wireless client, two cloud devices communicating or an IOT device).
>- In addition, we are likely to support additional primitives in the
>future; possibly National curves (e.g. Brainpool), or additional
>Postquantum algorithms (or additional parameter sets to existing ones)..  
> Of
>course, once we add that code point, we’ll need to add the additional code
>points for all the combinations that it’ll make sense in (very much like we
>had to add a number of ciphersuites whenever we added a new encryption
>algorithm into TLS 1.2).
>
>
>

Are people actually going to use hybrid encryption post NIST? The actual
deployments today  for experiment have all fit option 2 and hybrids are
unlikely in the future.

My objection to 1 is it gets very messy. Do we use only the hybrids we both
support? What if I throw a bunch of expensive things together? No reason we
need a hybrid scheme!

It seemds reasonable to me that the combination of these two factors are
> likely to cause us (should we select option 2) to define a very large
> number of code points to cover all the various options that people need.
>
>
>
> Now, this is based on speculation (both of the NIST process, and
> additional primitives that will be added to the protocol), and one
> objection I’ve heard is “we don’t know what’s going to happen, and so why
> would we make decisions based on this speculation?”  I agree that we have
> lack of knowledge; however it seems to me that a lack of knowledge is an
> argument in favor of selecting the more flexible option (which, in my
> opinion, is option 1, as it allows the negotiation of combinations of key
> 

[TLS] Options for negotiating hybrid key exchanges for postquantum

[Scott Fluhrer (sfluhrer)]

During the physical meeting in Montreal, we had a discussion about postquantum 
security, and in particular, on how one might want to negotiate several 
different 'groups' simultaneously (because there might not be one group that is 
entirely trusted, and I put 'groups' in scarequotes because postquantum key 
exchanges are typically not formed from a Diffie-Hellman group).

At the meeting, there were two options presented:

Option 1: as the supported group, we insert a 'hybrid marker' (and include an 
extension that map lists which combination the hybrid marker stands for)
For example, the client might list in his supported groups 
hybrid_marker_0 and hybrid_marker_1, and there would be a separate extension 
that lists hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 + 
NTRUPR653.  The server would then look up the meanings of hybrid_marker_0 and 1 
in the extension, and then compare that against his security policy.
In this option, we would ask IANA to allocate code points for the various 
individual postquantum key exchanges (in this example, SIKEp434 and NTRUPR653), 
as well a range of code points for the various hybrid_markers.

Option 2: we have code points for all the various combinations that we may want 
to support; hence IANA might allocate a code point X25519_SIKEp434 and another 
code point for X25519_NTRUPR653.  With this option, the client would list 
X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.
In this option, we would ask IANA to allocate code points for 
all the various combinations that we want allow to be negotiated.

I would like to make an argument in favor of option 1:


  *   It is likely that not everyone will be satisified with "X25519 plus one 
of a handful of specific postquantum algorithms"; some may prefer another 
elliptic curve (for example, x448), or perhaps even a MODP group; I have talked 
to people who do not trust ECC); in addition, other people might not trust a 
single postquantum algorithm, and may want to rely on both (for example) SIKE 
and NewHope (which are based on very different hard problems).  With option 2, 
we could try to anticipate all the common combintations (such as 
P384_SIKEp434_NEWHOPE512CCA), however that could very well end up as a lot of 
combinations.
  *   There are likely to be several NIST-approved postquantum key exchanges, 
and each of those key exchanges are likely to have a number of supported 
parameter sets (if we take the specific postquantum key exchange as analogous 
to th ECDH protocool, the "parameter set" could be thought of an analogous to 
the specific elliptuc curve, and it modifies the key share size, the 
performance and sometimes the security properties).  In fact, one of the NIST 
submissoins currently has 30 parameter sets defined.  Hence, even if NIST 
doesn't approve all the parameter sets (or some of them do not make sense for 
TLS in any scenario), we might end up with 20 or more different key 
exchange/parameter set combinations that do make sense for some scenario that 
uses tLS (be it in a tranditional PC client/server, a wireless client, two 
cloud devices communicating or an IOT device).
  *   In addition, we are likely to support additional primitives in the 
future; possibly National curves (e.g. Brainpool), or additional Postquantum 
algorithms (or additional parameter sets to existing ones).  Of course, once we 
add that code point, we'll need to add the additional code points for all the 
combinations that it'll make sense in (very much like we had to add a number of 
ciphersuites whenever we added a new encryption algorithm into TLS 1.2).

It seemds reasonable to me that the combination of these two factors are likely 
to cause us (should we select option 2) to define a very large number of code 
points to cover all the various options that people need.

Now, this is based on speculation (both of the NIST process, and additional 
primitives that will be added to the protocol), and one objection I've heard is 
"we don't know what's going to happen, and so why would we make decisions based 
on this speculation?"  I agree that we have lack of knowledge; however it seems 
to me that a lack of knowledge is an argument in favor of selecting the more 
flexible option (which, in my opinion, is option 1, as it allows the 
negotiation of combinations of key exchanges that the WG has not anticipated).

My plea: lets not repeat the TLS 1.2 ciphersuite mess; lets add an extension 
that keeps the number of code points we need to a reasonable bound.

The costs of option 1?

  *   It does increase the complexity on the server a small amount (I'm not a 
TLS implementor, however it would seem to me to be only a fairly small amount)
  *   It may increase the size of the client hello a small amount (on the other 
hand, because it allows us to avoid sending duplicate key shares, it can also 
reduce the size of the client hello as well, depending on what's actually