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 <nimrod.avi...@gmail.com> wrote: > > > 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 > <mailto: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 <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 > > > > <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 > > <https://www.felixguenther.info/publications/ESORICS_BreFisGun19.pdf> > > > > > > > > > > On Tue, 11 Jan 2022 at 21:08, Douglas Stebila <dsteb...@gmail.com > > <mailto: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/ > >> <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> > >> [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 > >> <https://en.wikipedia.org/wiki/CRIME> > >> _______________________________________________ > >> TLS mailing list > >> TLS@ietf.org <mailto:TLS@ietf.org> > >> https://www.ietf.org/mailman/listinfo/tls > >> <https://www.ietf.org/mailman/listinfo/tls> > > _______________________________________________ > > TLS mailing list > > TLS@ietf.org <mailto:TLS@ietf.org> > > https://www.ietf.org/mailman/listinfo/tls > > <https://www.ietf.org/mailman/listinfo/tls> > > _______________________________________________ > TLS mailing list > TLS@ietf.org <mailto:TLS@ietf.org> > https://www.ietf.org/mailman/listinfo/tls > <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
