> 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 <m...@lowentropy.net> wrote:
> 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.
> >
> >
> > 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
> >
> >
> >
> >
> > On Tue, 11 Jan 2022 at 21:08, Douglas Stebila <dsteb...@gmail.com>
> 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.
> >>
> >> 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 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
> >>
> >>
> >> [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
> >> _______________________________________________
> >> 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
>
_______________________________________________
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls
