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 protected]>: > 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 protected]> > 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 <[email protected]> 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 <[email protected]> >> 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 >> >> [email protected] >> >> https://www.ietf.org/mailman/listinfo/tls >> > _______________________________________________ >> > TLS mailing list >> > [email protected] >> > https://www.ietf.org/mailman/listinfo/tls >> >> _______________________________________________ >> TLS mailing list >> [email protected] >> https://www.ietf.org/mailman/listinfo/tls >> > _______________________________________________ > TLS mailing list > [email protected] > https://www.ietf.org/mailman/listinfo/tls > > > _______________________________________________ > TLS mailing list > [email protected] > https://www.ietf.org/mailman/listinfo/tls >
_______________________________________________ TLS mailing list [email protected] https://www.ietf.org/mailman/listinfo/tls
