Subject: [TLS] Revised hybrid key exchange draft

From: Douglas Stebila <[email-masked]>
Date: Tue, 11 Jan 2022 14:07:42 -0500

Hello TLS working group,

We've posted a revised version of "Hybrid key exchange in TLS 1.3" [1].  Based on revision requests from the last draft, the main change is removing the unnecessary appendix of the past design considerations, and a few wording changes.

Last September, Nimrod Aviram, Benjamin Dowling, Ilan Komargodski, Kenny Paterson, Eyal Ronen, and Eylon Yogev posted a note [2,3] with some concerns about whether the approach for constructing the hybrid shared secret in this document -- direct concatenation -- was risky in a scenario where the hash function used in TLS key derivation and transcript hashing is not collision resistant.  Nimrod and his colleagues exchanged many emails with us over the past few months to help us understand their concerns.  In the end we think the concerns are low and we have not made any changes in this draft, although if we receive different guidance from the working group, we'll do so.

There were two types of concerns that Nimrod and his colleagues identified [2,3]:

a) An attacker who can find collisions in the hash function can cause different sessions to arrive at the same session key.  This concern is largely independent of this hybrid key exchange draft, as it focuses on collisions in the transcript hash, and affects existing TLS 1.3 even without this draft being adopted.  If the TLS working group thinks this is a concern that should be addressed, it seems like it should be addressed at the overall level of TLS 1.3, rather than for this specific hybrid key exchange draft.

b) An attacker who can find collisions in the hash function and has a certain level of control over the first of the two shared secrets in the hybrid shared secret concatenation may be able to carry out an iterative attack to recover bytes of the second shared secret.  The iterative is similar to the APOP attacks [4,5] and also somewhat similar to the CRIME attack [6].  After discussing further with Nimrod and his colleagues, we identified that the following conditions need to be satisfied for this attack:
	i) Chosen-prefix collisions can be found in the hash function within the lifetime of the TLS handshake timeout of the victim.
	ii) The victim reuses ephemeral keying material several hundred times and for a time lasting at least as long as the time for part (i) of the attack.
	iii) The attacker can learn or control the value of the first shared secret in the hybrid shared secret concatenation.
	iv) The attacker is able to control the length of the first shared secret, so that -- for the iterative component of the attack -- the hash block boundary lands at different positions within the second shared secret.

Although different standardized groups do not all have the same shared secret length, for all DH/ECDH groups for TLS 1.3 standardized in RFC 8446, once the group is fixed (during negotiation), the shared secret is fixed length, so condition (iv) is not satisfied for stock TLS 1.3.  All NIST Round 3 finalist and alternate candidate KEMs currently have fixed-length shared secrets, so they would not satisfy condition (iv) either, if a post-quantum KEM was used as the first component in concatenation.  It may be possible that other organizations have bespoke key exchange methods they would want to use in a hybrid format, which might be variable length, but we don't have any information about that.  Even still, the three other conditions of the attack would need to be satisfied.  We think that's a pretty high barrier and as such have decided not to incorporate countermeasures at this time, but if the working group prefers otherwise, we can do so.  For example, Nimrod and his colleagues have proposed a KDF design that would be secure even in this scenario, but it has substantially more hash function applications that the current HKDF-based approach does.

Douglas

[1] https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/
[2] https://mailarchive.ietf.org/arch/msg/tls/F4SVeL2xbGPaPB2GW_GkBbD_a5M/
[3] https://github.com/nimia/kdf_public#readme
[4] Practical key-recovery attack against APOP, an MD5-based challenge-response authentication. Leurent, Gaetan.
[5] Practical Password Recovery on an MD5 Challenge and Response. Sasaki, Yu and Yamamoto, Go and Aoki, Kazumaro.
[6] https://en.wikipedia.org/wiki/CRIME

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 11 Jan 2022 13:01:27 -0800

Hi Douglas,

8446 already says:

   Note that HKDF-Expand implements a pseudorandom function (PRF) with
   both inputs and outputs of variable length.  In some of the uses of
   HKDF in this document (e.g., for generating exporters and the
   resumption_master_secret), it is necessary that the application of
   HKDF-Expand be collision resistant; namely, it should be infeasible
   to find two different inputs to HKDF-Expand that output the same
   value.  This requires the underlying hash function to be collision
   resistant and the output length from HKDF-Expand to be of size at
   least 256 bits (or as much as needed for the hash function to prevent
   finding collisions).

With that said, defense in depth is good. Does it help to have just a
structured input, e.g.,

opaque KeyInput<0..2^16-1>;

struct {
   KeyInput inputs<2..2^16-1>;
} KeyScheduleInput;

-Ekr

On Tue, Jan 11, 2022 at 11:08 AM Douglas Stebila <[email-masked]> wrote:

> Hello TLS working group,
>
> We've posted a revised version of "Hybrid key exchange in TLS 1.3" [1].
> Based on revision requests from the last draft, the main change is removing
> the unnecessary appendix of the past design considerations, and a few
> wording changes.
>
> Last September, Nimrod Aviram, Benjamin Dowling, Ilan Komargodski, Kenny
> Paterson, Eyal Ronen, and Eylon Yogev posted a note [2,3] with some
> concerns about whether the approach for constructing the hybrid shared
> secret in this document -- direct concatenation -- was risky in a scenario
> where the hash function used in TLS key derivation and transcript hashing
> is not collision resistant.  Nimrod and his colleagues exchanged many
> emails with us over the past few months to help us understand their
> concerns.  In the end we think the concerns are low and we have not made
> any changes in this draft, although if we receive different guidance from
> the working group, we'll do so.
>
> a) An attacker who can find collisions in the hash function can cause
> different sessions to arrive at the same session key.  This concern is
> largely independent of this hybrid key exchange draft, as it focuses on
> collisions in the transcript hash, and affects existing TLS 1.3 even
> without this draft being adopted.  If the TLS working group thinks this is
> a concern that should be addressed, it seems like it should be addressed at
> the overall level of TLS 1.3, rather than for this specific hybrid key
> exchange draft.
>
> b) An attacker who can find collisions in the hash function and has a
> certain level of control over the first of the two shared secrets in the
> hybrid shared secret concatenation may be able to carry out an iterative
> attack to recover bytes of the second shared secret.  The iterative is
> similar to the APOP attacks [4,5] and also somewhat similar to the CRIME
> attack [6].  After discussing further with Nimrod and his colleagues, we
> identified that the following conditions need to be satisfied for this
> attack:
>         i) Chosen-prefix collisions can be found in the hash function
> within the lifetime of the TLS handshake timeout of the victim.
>         ii) The victim reuses ephemeral keying material several hundred
> times and for a time lasting at least as long as the time for part (i) of
> the attack.
>         iii) The attacker can learn or control the value of the first
> shared secret in the hybrid shared secret concatenation.
>         iv) The attacker is able to control the length of the first shared
> secret, so that -- for the iterative component of the attack -- the hash
> block boundary lands at different positions within the second shared secret.
>
> Although different standardized groups do not all have the same shared
> secret length, for all DH/ECDH groups for TLS 1.3 standardized in RFC 8446,
> once the group is fixed (during negotiation), the shared secret is fixed
> length, so condition (iv) is not satisfied for stock TLS 1.3.  All NIST
> Round 3 finalist and alternate candidate KEMs currently have fixed-length
> shared secrets, so they would not satisfy condition (iv) either, if a
> post-quantum KEM was used as the first component in concatenation.  It may
> be possible that other organizations have bespoke key exchange methods they
> would want to use in a hybrid format, which might be variable length, but
> we don't have any information about that.  Even still, the three other
> conditions of the attack would need to be satisfied.  We think that's a
> pretty high barrier and as such have decided not to incorporate
> countermeasures at this time, but if the working group prefers otherwise,
> we can do so.  For example, Nimrod and his colleagues ha
>  ve proposed a KDF design that would be secure even in this scenario, but
> it has substantially more hash function applications that the current
> HKDF-based approach does.
>
> Douglas
>
>
> [4] Practical key-recovery attack against APOP, an MD5-based
> challenge-response authentication. Leurent, Gaetan.
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 12 Jan 2022 11:07:21 +1100

I was operating under the assumption that inputs to concatenation were fixed length.  It seems that the attack mentioned did not.  It seems like that is a far simpler way of achieving that goal.  

That is, it seems to be sufficient to state that assumption as a requirement.

Constructing a length-prefixed encoding would work if we thought that supporting variable length secrets was a good idea.  We could even do that on a per-secret basis, adding a length only when needed.  However, I can't think of any way in which a variable length input would be advisable. So I'm going to recommend that we stick to fixed lengths.  As Douglas notes, there aren't any primitives under consideration that want a variable-length secret once the parameters are decided.

That TLS is vulnerable in the event of a collision will remain, even if we fix this, so while I'm not happy that our defense is that thin, the four conditions here on the second attack are each layers in that defense.  Short timeouts mean that the massive computation involved in even SHA-1 collisions seems unlikely.  Ephemeral key reuse is already advised against fairly strongly.  We try to choose strong key agreement methods.  And inputs are fixed length (or unambiguously encoded if deemed to be necessary).

Cheers,
Martin

On Wed, Jan 12, 2022, at 08:01, Eric Rescorla wrote:
>> Although different standardized groups do not all have the same shared secret length, for all DH/ECDH groups for TLS 1.3 standardized in RFC 8446, once the group is fixed (during negotiation), the shared secret is fixed length, so condition (iv) is not satisfied for stock TLS 1.3.  All NIST Round 3 finalist and alternate candidate KEMs currently have fixed-length shared secrets, so they would not satisfy condition (iv) either, if a post-quantum KEM was used as the first component in concatenation.  It may be possible that other organizations have bespoke key exchange methods they would want to use in a hybrid format, which might be variable length, but we don't have any information about that.  Even still, the three other conditions of the attack would need to be satisfied.  We think that's a pretty high barrier and as such have decided not to incorporate countermeasures at this time, but if the working group prefers otherwise, we can do so.  For example, Nimrod and his colleagues ha
>>  ve proposed a KDF design that would be secure even in this scenario, but it has substantially more hash function applications that the current HKDF-based approach does.
>> 
>> Douglas
>> 
>>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 12 Jan 2022 04:38:09 +0000

From: TLS <[email-masked]> On Behalf Of Eric Rescorla
Sent: Tuesday, January 11, 2022 4:01 PM
To: Douglas Stebila <[email-masked]>
Cc: <[email-masked]> <[email-masked]>
Subject: Re: [TLS] Revised hybrid key exchange draft

…
With that said, defense in depth is good. Does it help to have just a structured input, e.g.,

struct {

I don’t believe that the structured input idea would do much to frustrate the attack.  The attack relies on the attacker controlling the initial part of the concatenated shared secret, and implementing a collision if one of the bytes of the shared secret he does not know is a specific value.

What the structured input would do is set certain bytes of the initial part of the concatenated shared secret to known (to the attacker) values; that is, instead of the concatenated shared secret being:

  XX XX XX … XX XX XX YY YY … YY YY YY    (XX are the bytes from the weak key exchange, YY being the ones from the strong one),
It would look like
  02 00 20 00 XX XX XX … XX XX XX 20 00 YY YY … YY YY YY  (this example assumes both key inputs are 32 bytes long)

As long as he can find collisions where those specific bytes are fixed to those set by the structured inputs in both blocks (that is, with the 02 00 20 00 XX XX XX … XX XX XX 20 00 pattern, with the differences being confined to the XX bytes), then the attack can proceed exactly as normal.  Now, allowing the attacker less flexibility when setting up the collision would (one would expect) make finding collisions harder; however we can’t assume it makes them impractical.

What would address the attack would be to pad the KeyInput (should they be of variable length) to a fixed maximum length (for example, the longest that key exchange algorithm can output).

This would also address a weakness someone found in TLS 1.2, where the DH shared secret was effectively variable length (as the leading 0’s were stripped off), which could lead to a timing attack.  Now, the attack that used that weakness relied on other properties of DH – however, that could also be used as precedence to forbid variable length shared secrets.

---

From: Douglas Stebila <[email-masked]>
Date: Wed, 12 Jan 2022 09:44:07 -0500

> That is, it seems to be sufficient to state that assumption as a requirement.

Indeed we do state that in Section 6:

   Therefore, this specification MUST only be used with algorithms which
   have fixed-length shared secrets (after the variant has been fixed by
   the algorithm identifier in the NamedGroup negotiation in Section 3.1).

> Constructing a length-prefixed encoding would work if we thought that supporting variable length secrets was a good idea.

As Scott writes in a subsequent email, length-prefixed encoding doesn't thwart this type of attack.  Length-prefixed encoding ensures there's no *ambiguity* about which component is which, but that's not what the APOP-like attack exploits.  Instead it's helpful to the attacker to make parts of the input line up with hash function boundaries, and length-prefixed encoding of variable-length values don't stop that.  

Padding to a fixed length would be the solution if we thought some algorithms would have variable length secrets.  For the purposes of the APOP-style attack, I think it would even suffice to have a rule like "length-prefixed encoding + pad up to the nearest multiple of 32 bytes in length" -- this would mean the attacker's granularity in lining up something with respect to the hash function boundary would be 32 bytes = 256 bits, which would make the search space of the APOP-style attack infeasibly large.  

Douglas

---

From: Nimrod Aviram <[email-masked]>
Date: Wed, 19 Jan 2022 13:21:06 +0200

Hi Everyone,

As Douglas wrote, we have discussed the issues together at length, and we
thank him for the productive (and friendly :-)) conversation.

Our paper, which describes our concerns, can be found here:
https://eprint.iacr.org/2022/065

And a reference implementation of our proposed KDF:
https://github.com/nimia/kdf_reference_implementation/blob/main/kdf_reference_implementation.py#L60

A few points from our side:

Firstly, our proposed construction is simple to implement (see the Python
code above), and adds a modest overhead of a few microseconds (see the
paper).

Re: point a) from Douglas’ first mail: Admittedly, our concerns are broader
than Hybrid Key Exchange in TLS. However, we view the standardization of
Hybrid Key Exchange as an opportunity to add defense in depth. Missing this
opportunity would effectively further embed the problem. We don’t see
another such opportunity on the horizon: If we standardize a TLS extension
in a few years, getting everyone to deploy the extension would be hard.
Whereas here everyone has to deploy the new thing anyway, so we might as
well make it as robust as we can.

Consider the following: SHA-1 weaknesses to collisions were first really
highlighted in 2005. TLS version 1.0 was standardised in 2006 and hardcoded
the use of SHA-1, and MD5 (admittedly, for use in HMAC). TLS 1.2 was
standardised in 2008, and formal deprecation of SHA-1 occurred in 2011 by
NIST. The standard deprecating the use of SHA-1 in TLS 1.2 digital
signatures occurred in 2021. In 2016, TLS support (according to Qualys SSL
Labs SSL survey) was over 90%. In 2020, TLS 1.0 support was still above
50%, despite practical chosen-prefix collision attacks against SHA-1 being
possible. Being robust against future threats when given the option is
something that we should seriously take time to consider.

As to ekr’s response that the standard already states we need a
collision-resistant hash function: Brendel et al. [1] proved that the TLS
1.3 ECDHE handshake survives losing the collision resistance of the hash
function, as long as HKDF retains its pseudorandomness property. However,
HKDF does not provably possess this property to begin with, with respect to
the (EC)DH shared secret input, since this input is fed as the message
input to HMAC, and HMAC/HKDF is not a dual PRF.

To summarize, we recommend using our new proposed construction. It’s fast,
easy to implement, and provides provable security. We see no reason to
entrench a problem if we’re already changing the protocol in this area, and
requiring implementation changes anyway.

Best,

Nimrod, Ben, Ilan, Kenny, Eyal, and Eylon

[1] https://www.felixguenther.info/publications/ESORICS_BreFisGun19.pdf

---

From: "Martin Thomson" <[email-masked]>
Date: Fri, 21 Jan 2022 11:02:21 +1100

I am not convinced that the extra effort is justified.

However, I am convinced that the proposed construction is complex.

combined_key = H(HMAC(key=H1(k1), data=2||F(k2)) xor HMAC(key=H2(k2),
data=1||F(k1)))
H1(k) = H('derive1' || k)
H2(k) = H('derive2' || k)
F(m) = H(0||m1)||H(1||m1)||...||H(j-1||m1)||H(0||m2)||H(1||m2)||...||H(j-1||m2)||H(0||mn)||H(1||mn)||...||H(j-1||mn)
for m = m1||m2||...||mn and j =~ 3

It's nice that this is a dual PRF; that's something I think we've wanted for a number of other reasons in TLS.  I might have preferred a more efficient option though.

Comparing that to k1 || k2 means - for me - this needs much stronger justification.  

Perhaps if the CFRG were to standardize a dual (or multi) PRF that were more efficient I would be more favourably inclined toward its inclusion - in a revision of the core specification.

The nice thing about the hybrid draft is that it isn't a firm commitment to any particular combination method.  Each new key exchange "group" can define its own combination method.  It only suggests a method.  So I don't agree that "[m]issing this opportunity would effectively further embed the problem" (or maybe "effectively" is doing a little too much work there).

On Wed, Jan 19, 2022, at 22:21, Nimrod Aviram wrote:
> Hi Everyone,
>
>
> As Douglas wrote, we have discussed the issues together at length, and 
> we thank him for the productive (and friendly :-)) conversation.
>
>
> Firstly, our proposed construction is simple to implement (see the 
> Python code above), and adds a modest overhead of a few microseconds 
> (see the paper).
>
>
> Re: point a) from Douglas’ first mail: Admittedly, our concerns are 
> broader than Hybrid Key Exchange in TLS. However, we view the 
> standardization of Hybrid Key Exchange as an opportunity to add defense 
> in depth. Missing this opportunity would effectively further embed the 
> problem. We don’t see another such opportunity on the horizon: If we 
> standardize a TLS extension in a few years, getting everyone to deploy 
> the extension would be hard. Whereas here everyone has to deploy the 
> new thing anyway, so we might as well make it as robust as we can.
>
>
> Consider the following: SHA-1 weaknesses to collisions were first 
> really highlighted in 2005. TLS version 1.0 was standardised in 2006 
> and hardcoded the use of SHA-1, and MD5 (admittedly, for use in HMAC). 
> TLS 1.2 was standardised in 2008, and formal deprecation of SHA-1 
> occurred in 2011 by NIST. The standard deprecating the use of SHA-1 in 
> TLS 1.2 digital signatures occurred in 2021. In 2016, TLS support 
> (according to Qualys SSL Labs SSL survey) was over 90%. In 2020, TLS 
> 1.0 support was still above 50%, despite practical chosen-prefix 
> collision attacks against SHA-1 being possible. Being robust against 
> future threats when given the option is something that we should 
> seriously take time to consider.
>
>
> collision-resistant hash function: Brendel et al. [1] proved that the 
> TLS 1.3 ECDHE handshake survives losing the collision resistance of the 
> hash function, as long as HKDF retains its pseudorandomness property. 
> However, HKDF does not provably possess this property to begin with, 
> with respect to the (EC)DH shared secret input, since this input is fed 
> as the message input to HMAC, and HMAC/HKDF is not a dual PRF.
>
>
> To summarize, we recommend using our new proposed construction. It’s 
> fast, easy to implement, and provides provable security. We see no 
> reason to entrench a problem if we’re already changing the protocol in 
> this area, and requiring implementation changes anyway.
>
>
> Best,
>

---

From: Nimrod Aviram <[email-masked]>
Date: Sat, 22 Jan 2022 13:35:00 +0200

> I might have preferred a more efficient option though.
By efficient, are you referring to the computation cost, or the
implementation complexity?
As to the former, the new construction requires ~7 microseconds, whereas
HKDF.extract requires ~1.
As to the implementation complexity, if that's your main concern, could you
please elaborate about your concern?
FWIW, our Python reference implementation
<https://github.com/nimia/kdf_reference_implementation/blob/main/kdf_reference_implementation.py#L54>
is quite short. We also provide a C implementation that wasn't hard to
write (for me). And I can't imagine this causing interop problems.

> The nice thing about the hybrid draft is that it isn't a firm commitment
to any particular combination method.
> It only suggests a method.
That's not my understanding. My reading is that the draft prescribes a
combination method, and if adopted and standardized, it would be
concatenation, for all group combinations.
Do you envision a scenario where a different combination method is
standardized? If so, could you please elaborate how this would come to pass
- perhaps as a revision of the eventual hybrid standard?
Douglas, could you please chime in regarding this issue? If standardized,
do you envision changing/adding combination methods?

thanks,
Nimrod

On Fri, 21 Jan 2022 at 02:03, Martin Thomson <[email-masked]> wrote:

> F(m) =
> H(0||m1)||H(1||m1)||...||H(j-1||m1)||H(0||m2)||H(1||m2)||...||H(j-1||m2)||H(0||mn)||H(1||mn)||...||H(j-1||mn)
> It's nice that this is a dual PRF; that's something I think we've wanted
> for a number of other reasons in TLS.  I might have preferred a more
> efficient option though.
>
> Perhaps if the CFRG were to standardize a dual (or multi) PRF that were
> more efficient I would be more favourably inclined toward its inclusion -
> in a revision of the core specification.
>
> The nice thing about the hybrid draft is that it isn't a firm commitment
> to any particular combination method.  Each new key exchange "group" can
> define its own combination method.  It only suggests a method.  So I don't
> agree that "[m]issing this opportunity would effectively further embed the
> problem" (or maybe "effectively" is doing a little too much work there).
>
> >> We've posted a revised version of "Hybrid key exchange in TLS 1.3"
> [1].  Based on revision requests from the last draft, the main change is
> removing the unnecessary appendix of the past design considerations, and a
> few wording changes.
> >>
> >> Last September, Nimrod Aviram, Benjamin Dowling, Ilan Komargodski,
> Kenny Paterson, Eyal Ronen, and Eylon Yogev posted a note [2,3] with some
> >>         iv) The attacker is able to control the length of the first
> shared secret, so that -- for the iterative component of the attack -- the
> hash block boundary lands at different positions within the second shared
> secret.
> >>
> >>  ve proposed a KDF design that would be secure even in this scenario,
> but it has substantially more hash function applications that the current
> >> [2]
> https://mailarchive.ietf.org/arch/msg/tls/F4SVeL2xbGPaPB2GW_GkBbD_a5M/
> >> [5] Practical Password Recovery on an MD5 Challenge and Response.
> Sasaki, Yu and Yamamoto, Go and Aoki, Kazumaro.

---

From: Russ Housley <[email-masked]>
Date: Sun, 23 Jan 2022 12:20:11 -0500

I think that Martin is asking what properties this provides that justify the additional complexity.  I'm sure that a few test vectors are sufficient to get interoperability, but what properties of the construction justify the effort to do something different?

Russ

> On Jan 22, 2022, at 6:35 AM, Nimrod Aviram <[email-masked]> wrote:
> 
> By efficient, are you referring to the computation cost, or the implementation complexity?
> As to the former, the new construction requires ~7 microseconds, whereas HKDF.extract requires ~1.
> As to the implementation complexity, if that's your main concern, could you please elaborate about your concern?
> FWIW, our Python reference implementation <https://github.com/nimia/kdf_reference_implementation/blob/main/kdf_reference_implementation.py#L54> is quite short. We also provide a C implementation that wasn't hard to write (for me). And I can't imagine this causing interop problems.
> 
> > The nice thing about the hybrid draft is that it isn't a firm commitment to any particular combination method.
> That's not my understanding. My reading is that the draft prescribes a combination method, and if adopted and standardized, it would be concatenation, for all group combinations.
> Do you envision a scenario where a different combination method is standardized? If so, could you please elaborate how this would come to pass - perhaps as a revision of the eventual hybrid standard?
> Douglas, could you please chime in regarding this issue? If standardized, do you envision changing/adding combination methods?
> 
> thanks,
> Nimrod
> 
> 
> 
> On Fri, 21 Jan 2022 at 02:03, Martin Thomson <[email-masked] <mailto:[email-masked]>> wrote:
> > https://eprint.iacr.org/2022/065 <https://eprint.iacr.org/2022/065>
> >
> > https://github.com/nimia/kdf_reference_implementation/blob/main/kdf_reference_implementation.py#L60 <https://github.com/nimia/kdf_reference_implementation/blob/main/kdf_reference_implementation.py#L60>
> >
> >
> > [1] https://www.felixguenther.info/publications/ESORICS_BreFisGun19.pdf <https://www.felixguenther.info/publications/ESORICS_BreFisGun19.pdf>
> >
> >
> >
> >
> > On Tue, 11 Jan 2022 at 21:08, Douglas Stebila <[email-masked] <mailto:[email-masked]>> wrote:
> >> Hello TLS working group,
> >> 
> >> [1] https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/ <https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/>
> >> [2] https://mailarchive.ietf.org/arch/msg/tls/F4SVeL2xbGPaPB2GW_GkBbD_a5M/ <https://mailarchive.ietf.org/arch/msg/tls/F4SVeL2xbGPaPB2GW_GkBbD_a5M/>
> >> [3] https://github.com/nimia/kdf_public#readme <https://github.com/nimia/kdf_public#readme>
> >> [6] https://en.wikipedia.org/wiki/CRIME <https://en.wikipedia.org/wiki/CRIME>
> >> [email-masked] <mailto:[email-masked]>
> >> https://www.ietf.org/mailman/listinfo/tls <https://www.ietf.org/mailman/listinfo/tls>
> > [email-masked] <mailto:[email-masked]>
> > https://www.ietf.org/mailman/listinfo/tls <https://www.ietf.org/mailman/listinfo/tls>
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/tls <https://www.ietf.org/mailman/listinfo/tls>

---

From: Thom Wiggers <[email-masked]>
Date: Mon, 24 Jan 2022 12:18:11 +0100

Hi all,

I think this work is an interesting examination of the assumptions, and as
a new key schedule it might be worth considering for future version numbers
of TLS and other protocols that rely on dual-PRF. Computationally, a few
extra hashes won't hurt anyone.

However, I don't agree with the suggestion that this would be something
that would be easy to "just do" when negotiating Hybrid KEMs. As I
understand the proposal, it is a complete redesign of the key schedule,
which has significant pains when implementing this. The "beauty" of the
draft-Stebila proposal is the fact that all its complexity is hidden behind
the API of the key exchange algorithm. From the point of view of the TLS
state machine, it's just another code point, and nothing needs to be
changed if you just have "keygen", "generate hello keyshare" (aka encaps)
and "derive shared secret" (aka decapsulate) operations in your ClientHello
and ServerHello messages. To use the KeyCombine() function in hybrid-KEX
TLS 1.3 handshakes and "old-fashioned" HKDF.Extract in ECDH-KEX TLS 1.3
handshakes means having to keep track of which type of key derivation is
being used throughout the handshake state machine, which is a significant
deviation from the current "just input the secret and advance the ratchet"
construction. This is especially true for more highly "integrated"
implementations (ie. the code mixes the protocol message handling and key
derivation steps [1]).

Cheers,

Thom

[1]: It's not necessarily the "usual suspects" that do this: see for
example the (imo) high-quality Go TLS implementation:
https://github.com/golang/go/blob/master/src/crypto/tls/handshake_server_tls13.go#L657-L658

Op zo 23 jan. 2022 om 18:21 schreef Russ Housley <[email-masked]>:

> I think that Martin is asking what properties this provides that justify
> the additional complexity.  I'm sure that a few test vectors are sufficient
> to get interoperability, but what properties of the construction justify
> the effort to do something different?
>
> Russ
>
>
>> >>         ii) The victim reuses ephemeral keying material several
>> hundred times and for a time lasting at least as long as the time for part
>> (i) of the attack.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 24 Jan 2022 15:12:20 -0000

Nimrod Aviram writes:
> easy to implement, and provides provable security.

The baseline construction is faster and is easier to implement, so
you're saying it doesn't provide "provable security"? Can you please
clarify what precisely you mean by "provable security" here? 

---Dan

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 24 Jan 2022 15:19:38 +0000

I don't see much benefit in the revised construction.

--
Regards,
Uri
 
There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                     -  C. A. R. Hoare

On 1/24/22, 10:14, "TLS on behalf of D. J. Bernstein" <[email-masked] on behalf of [email-masked]> wrote:

    Nimrod Aviram writes:
    > To summarize, we recommend using our new proposed construction. Itâ€™s fast,

    ---Dan

---

From: Nimrod Aviram <[email-masked]>
Date: Mon, 24 Jan 2022 17:47:17 +0200

Current proofs for TLS 1.3 generally require HKDF to act as a dual-PRF (or
as a random oracle - an even stronger assumption). HKDF has not yet been
proven to satisfy this property, under any assumption. Our construction
satisfies this property.

best,
Nimrod

On Mon, 24 Jan 2022 at 17:13, D. J. Bernstein <[email-masked]> wrote:

> fast,

---

From: "D. J. Bernstein" <[email-masked]>
Date: 24 Jan 2022 16:35:50 -0000

Nimrod Aviram writes:
  [ regarding the "dual-PRF" security property ]
> Our construction satisfies this property.

To make sure I understand:

   (1) You mean that the construction is _conjectured_ to satisfy this
       property, i.e., to be a dual PRF? There must be some sort of
       limit on the hash functions allowed here; is SHA-256 allowed?

   (2) The basis for this conjecture is your previous claim that the
       construction provides "provable security"?

   (3) Meanwhile you claim that the H(x,y) construction used in the
       hybrid-key-exchange draft doesn't provide "provable security"?

In any case, can you please clarify what precisely you mean by "provable
security" in the previous claim that the construction provides "provable
security"? Clarity is a prerequisite for evaluation of the claim. Thanks
in advance.

---Dan

---

From: Nimrod Aviram <[email-masked]>
Date: Mon, 24 Jan 2022 20:20:35 +0200

Thank you for the discussion :-)

1. The construction is proven to satisfy this property under precise
assumptions about its components. A formal theorem statement can be found
in Theorem 1 on page 11 of ePrint 2022/065
<https://eprint.iacr.org/2022/065>. A discussion of how to instantiate
those components can be found in Section 5 of the same paper. We think the
resulting assumptions are reasonable when SHA-256 is used in the
instantiation, as in our reference implementation
<https://github.com/nimia/kdf_reference_implementation/blob/main/reference_implementation.c>
.

2. There is no conjecture involved, beyond whether the assumptions required
for the proof hold. Such assumptions are quite common in cryptography.

3. Please see my previous email to the list: Current proofs for TLS 1.3
generally require HKDF to act as a dual-PRF (or as a random oracle - an
even stronger assumption). HKDF has not yet been proven to satisfy this
property, under any assumption.

best,
Nimrod

---

From: "D. J. Bernstein" <[email-masked]>
Date: 24 Jan 2022 19:37:15 -0000

Nimrod Aviram writes:
> The construction is proven to satisfy this property under precise
> assumptions about its components.

So, to be clear, the statement that a function F provides "provable
security" means that there's a proof that F achieves the security
property under discussion (in this case, dual PRF) under precise
assumptions about various functions declared to be "components" of F?

Katz and Lindell wrote that "One of the key intellectual contributions
of modern cryptography has been the realization that formal definitions
of security are _essential_ prerequisites for the design, usage, or
study of any cryptographic primitive or protocol." Surely the concept of
"provable security" should be defined, so that everyone can evaluate
claims that particular functions are "provably secure".

> We think the resulting assumptions are reasonable when SHA-256 is used
> in the instantiation

To support security evaluation, can you please list the assumptions
regarding SHA-256? Also, for people who prefer SHA-3, can you please
list any differences in the case of SHA-3? Thanks in advance.

Btw, I did read the paper before asking questions. Section 5 doesn't
have a clearly labeled list of hash-function hypotheses, never mind
proofs. Sometimes there was a clear flow of logic from something that I
would presume was intended as a hypothesis, but in general the section
doesn't follow basic falsifiability rules. A cryptanalyst wants to see
authors committing to a clear statement of the hypotheses being made
about SHA-256, so that the work for breaking those hypotheses is given
appropriate credit, rather than being met by a change in the rules.

---Dan

---

From: Douglas Stebila <[email-masked]>
Date: Tue, 25 Jan 2022 08:55:02 -0500

> Douglas, could you please chime in regarding this issue? If standardized, do you envision changing/adding combination methods?

I agree with Nimrod's understanding: as it stands now, I think the hybrid draft does not commit to any particular *combination* of groups, but the draft does commit to a particular *combination method*, namely concatenation of individual shared secrets, with the concatenation then used directly in the existing TLS 1.3 key schedule.  This certainly wouldn't preclude an alternative being proposed at a later date, but that would be in a new document.

Douglas