Re: [TLS] Combining Secrets in Hybrid Key Exchange in TLS 1.3

[Nimrod Aviram <[e-mail]>]

Hi David,

> we assume the KDF is collision-resistant.
Agreed that the current key schedule relies on this. Appendix E.1.1 also
states
we assume the underlying hash function to be collision resistant.

> the proposed construction is dramatically more involved than what's in
the draft
Agreed. Another option is to omit the expanding function F:
combined_key = H(HMAC(key=H(k1), data=2||k2) xor HMAC(key=H(k2),
data=1||k1))
We hypothesize this weakened construction is also secure, but we don't
expect to
be able to prove this. This seems like a cheap way to add defense-in-depth.
At least, there is no clear technique for attacking this.

> I think it should be motivated by a clear story for
> what properties we assume from primitives across the protocol, rather than
> a point fix to one part.
This is certainly a reasonable position, but I'd like to offer a counter
argument:
When analyzing (non-hybrid) TLS 1.3 in its entirety, the current risk seems
relatively benign. If SHA256 collisions are found, then an attacker that can
establish multiple PSKs of their choice with another party can cause two
sessions with two different PSKs to share the same early_secret.
But this seems benign: When the resumption secret serves as the PSK, it can
not
be chosen by the attacker. And if the PSK is communicated out of band and
the
attacker can control it, this seems to imply some existing (misguided)
trust in
the attacker.

However, when PQ KEMs are used, this opens the door to more "standard"
attack
scenarios. Assuming the client dictates the encapsulated key, the attacker
has
a direct avenue for injecting crafted material into the KDF. This is
similar to
RSA key exchange, and this technique (in its general form) has been used in
the
past:
https://blog.cryptographyengineering.com/2014/04/24/attack-of-week-triple-handshakes-3shake/

So my position is similar to what you said about fixed DH keys: This is not
ideal, it might be tolerable in some scenarios but not okay in others,
especially if we can do better. And we should take this opportunity, before
hybrid key exchange is deployed, to do better.




On Fri, 3 Sept 2021 at 01:51, David Benjamin <[e-mail]> wrote:

> Regarding the TLS 1.3 proof, I recall some discussion around
> collision-resistance and PSK binders, with the result that we assume the
> KDF is collision-resistant.
>
> The paragraph that begins "The PSK binder value forms a binding" in
> Appendix E.1:
> https://datatracker.ietf.org/doc/html/rfc8446#appendix-E.1
> The second paragraph in Appendix E.1.1:
> https://datatracker.ietf.org/doc/html/rfc8446#appendix-E.1.1
>
> Though I'm not as familiar with the details of all the proofs here and may
> be misinterpreting this. Perhaps someone more familiar could chime in?
>
> APOP doesn't seem relevant here because we're only concatenating
> fixed-length values. (Indeed the whole construction in the draft assumes
> each KEM's output size is fixed. Otherwise concatenation isn't injective.
> This is a fine assumption because a KEM with variable-length output can
> cause other troubles, per the Raccoon attack.) I think that means there is
> no room to shift lengths around and try to target individual bytes.
>
> Of course, that doesn't mean there aren't other attacks. But the proposed
> construction is dramatically more involved than what's in the draft. If
> it's the way to go, I think it should be motivated by a clear story for
> what properties we assume from primitives across the protocol, rather than
> a point fix to one part.
>
> On Thu, Sep 2, 2021 at 4:32 PM Blumenthal, Uri - 0553 - MITLL <
> [e-mail]> wrote:
>
>> The APOP attack demonstrates that concatenating secrets may be dangerous,
>> as a general cryptographic practice.
>>
>>
>>
>> I disagree with the word “general” here.
>>
>>
>>
>> As to the TLS KDF, if future SHA256 cryptanalysis results in collisions,
>>
>>
>>
>> Since (if memory serves me) KDF is HMAC-based, rather than merely
>> SHA-based – it won’t matter from the security point of view whether SHA256
>> will or will not show collisions.
>>
>>
>>
>> This likely violates the security proof for TLS 1.3, in and of itself.
>>
>>
>>
>> I don’t think so.
>>
>>
>>
>> A similar violation of the security guarantee seems to arise when using
>> hybrid key exchange with a PQ KEM.
>>
>>
>>
>> I absolutely don’t think so.
>>
>>
>>
>> Or if that's what you're asking: As we write, we are unaware of a way to
>> apply the APOP attack to the TLS KDF.
>>
>>
>>
>> Excellent, thanks! I concur here.
>>
>>
>>
>> We view this as an opportunity to defend-in-depth against such issues,
>> while the document is not yet finalized.
>>
>>
>>
>> I think we’re OK as-is.
>>
>>
>>
>>
>>
>> On Wed, 1 Sept 2021 at 23:34, Blumenthal, Uri - 0553 - MITLL <
>> [e-mail]> wrote:
>>
>> How does the described AOAP attack apply to TLS KDF?
>>
>>
>>
>> --
>>
>> Regards,
>>
>> Uri
>>
>>
>>
>> *There are two ways to design a system. One is to make is so simple there
>> are obviously no deficiencies.*
>>
>> *The other is to make it so complex there are no obvious deficiencies.*
>>
>> *
>>                                                                                                                    -
>> C. A. R. Hoare*
>>
>>
>>
>>
>>
>> *From: *TLS <[e-mail]> on behalf of Nimrod Aviram <
>> [e-mail]>
>> *Date: *Wednesday, September 1, 2021 at 15:58
>> *To: *"<[e-mail]>" <[e-mail]>
>> *Cc: *Eylon Yogev <[e-mail]>, Ilan Komargodski <
>> [e-mail]>, Benjamin Dowling <[e-mail]>, Eyal
>> Ronen <[e-mail]>
>> *Subject: *[TLS] Combining Secrets in Hybrid Key Exchange in TLS 1.3
>>
>>
>>
>> (This note is also available on Github
>> <https://github.com/nimia/kdf_public#readme> for ease of reading.)
>>
>>
>>
>> This note identifies a possible security problem in the "Hybrid key
>> exchange in
>> TLS 1.3" document, stemming from how cryptographic secrets are combined.
>> In
>> short: constructions that concatenate secrets are vulnerable when the
>> underlying
>> hash function is not collision-resistant. We are unaware of a full attack
>> that leverages the underlying problem. However, we view this as an
>> opportunity
>> to defend-in-depth against such issues, while the document is not yet
>> finalized.
>> We propose a new construction that seems robust to this potential issue,
>> and we
>> are in the process of writing a technical report that includes a full
>> security
>> proof.
>>
>> # Concatenating Secrets May Be Dangerous
>>
>> The APOP attack (see appendix for a brief description) demonstrates that
>> concatenating secrets to potentially attacker-controlled input might be
>> dangerous. Currently, the "Hybrid key exchange in TLS 1.3" document uses
>> secret
>> concatenation as the preferred way to combine secrets. (This was an
>> understandable design choice given how little this issue has been
>> studied.)
>>
>> We recommend a defense-in-depth approach against this potential issue. We
>> should
>> not concede to an attacker even the ability to cause a collision in an
>> internal
>> state of the key schedule. Moreover, this part of TLS is likely
>> particularly
>> amenable to ossification: Whatever we standardize will likely persist for
>> 5-10
>> years. (We do note that TLS mixes in the client and server nonces, so
>> additional
>> offensive techniques would be required to exploit this for a full attack.)
>>
>> We note that concatenation is also used in the "TLS 1.3 Extended Key
>> Schedule"
>> document.
>>
>> # Our proposed construction
>>
>> We have identified an alternative construction that we believe could
>> provide
>> defense-in-depth against this issue. We are in the process of writing a
>> technical report that includes a full security proof.
>> The required assumptions on the hash function appear to be much milder
>> than
>> collision resistance; instead, we likely only need
>> multi-preimage-resistance:
>> Essentially, requiring only that computing preimages for multiple images
>> is
>> hard.
>>
>> The construction is:
>> combined_key = H(HMAC(key=H1(k1), data=2||F(k2)) xor HMAC(key=H2(k2),
>> data=1||F(k1)))
>> where || denotes concatenation, H denotes the underlying hash function,
>> and:
>> H1(k) = H('derive1' || k)
>> H2(k) = H('derive2' || k)
>> F is defined as follows:
>> Let m denote the input to F. We split m into blocks, according to the
>> block size
>> of H:
>> m = m1||m2||...||mn
>> Let j~=3 denote an “expanding factor” (the value chosen for j in practice
>> depends on how strong an assumption we want to rely on; we expect 3 to be
>> enough).
>> Then
>> 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)
>>
>> This construction is cheap to calculate and would be used only in the key
>> schedule, which is not a bottleneck for TLS performance.
>>
>> # Adding another layer to the TLS key schedule may also be problematic
>>
>> Another strategy for mixing secrets is to add the second secret to
>> another layer
>> of the TLS key schedule. This strategy is already used to mix a PSK and
>> an ECDHE
>> secret in TLS 1.3, as well as in AuthKEM, and it was also considered for
>> the
>> Hybrid key exchange document. This strategy is vulnerable as well to
>> collisions
>> in the underlying hash function, and we propose using one secure
>> construction
>> for mixing secrets.
>>
>> Consider a standard PSK+ECDHE TLS 1.3 handshake. Then
>> handshake_secret = HKDF_Extract(IKM=ECDHE_secret,
>> salt=Derive_Secret(early_secret))
>> early_secret = HKDF_Extract(IKM=PSK, salt=000)
>> HKDF_Extract(IKM, salt) = HMAC(k=salt, data=IKM)
>>
>> Therefore, early_secret = HMAC(k=000, data=PSK).
>> Assume a non-collision-resistant hash function. Then an attacker that can
>> establish multiple PSKs of their choice with another party can cause two
>> sessions with two different PSKs to share the same early_secret. If the
>> other
>> party reuses ECDH(E) values, the attacker can also cause the
>> handshake_secret to
>> be identical.
>>
>> Furthermore,
>> Client_Handshake_Traffic_Secret =
>>   HMAC(k=Handshake_Secret, data=Label||H(ClientHello...ServerHello))
>> If the attacker is the server, and the hash function allows for
>> chosen-prefix
>> collisions, the attacker can choose two ServerHello messages such that
>> for two
>> different ClientHello messages, H(ClientHello...ServerHello) is identical.
>> This leads to identical values for an actual key output of the key
>> schedule,
>> Client-Handshake-Traffic-Secret (if the client reuses an ECDH(E) value,
>> or in a
>> hypothetical PQ TLS, which uses a KEM and the server chooses the
>> encapsulated
>> key).
>>
>> We note that the full version of the HKDF paper explicitly disclaims
>> security in
>> the presence of attacker-controlled entropy. Also, note that by
>> definition, a
>> KEM allows one party to control the secret.
>>
>> # Appendix: The APOP Attack
>>
>> APOP is an old challenge-response protocol used in email, relevant here
>> because
>> it demonstrates the attack well. Broadly, in APOP the challenger sends a
>> challenge, and the responder needs to respond with:
>> MD5(challenge || password)
>> where || denotes concatenation.
>>
>> The attacker wants to e.g. test whether the password starts with 'a'. They
>> pick an MD5 collision x, y such that MD5(x) = MD5(y) and both x and y end
>> with
>> 'a'. They wait for the client to connect in two different sessions, and
>> send
>> x[:-1] and y[:-1] as the challenges, where [:-1] denotes removing the
>> last byte
>> from a string. If the password starts with 'a', and the MD5 blocks align,
>> then
>> the response will be the same for both challenges. The attacker can
>> therefore
>> test a single guess for the starting byte with two sessions, and learn
>> that byte
>> after at most 512 sessions. See [1], [2].
>>
>> best wishes,
>> Nimrod Aviram, Benjamin Dowling, Ilan Komargodski, Kenny Paterson, Eyal
>> Ronen, Eylon Yogev
>>
>> References:
>> [1] Practical key-recovery attack against APOP, an MD5-based
>> challenge-response authentication. Leurent, Gaetan.
>>
>> [2] Practical Password Recovery on an MD5 Challenge and Response.
>> Sasaki, Yu and Yamamoto, Go and Aoki, Kazumaro.
>>
>>
>>
>> _______________________________________________
>> TLS mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/tls
>>
>