Subject: Re: [TLS] [EXTERNAL] TLS Digest, Vol 206, Issue 12

From: Mike Ounsworth <[email-masked]>
Date: Thu, 9 Sep 2021 19:15:13 +0000

Nimrod,

>From this thread:
> 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.

A comparison with PBKDF2-HMAC-SHA1 seems apt as PBKDF2 has an HMAC at its core, though it uses the input as a key rather than as the message, so maybe is not directly comparable. I can't find a strong citation for this, but I believe PBKDF2-HMAC-SHA1 is still considered collision-resistant for inputs less than the block size of the hash function. (for inputs longer than the block size, there are fairly trivial ways to force collisions in PBKDF2, even with SHA256, but that's unrelated to the HMAC; see https://mathiasbynens.be/notes/pbkdf2-hmac).

There's also this quote from Thomas Pornin in 2011 (https://stackoverflow.com/questions/4938906/is-sha1-still-secure-for-use-as-hash-function-in-pbkdf2):

> None of the currently known weaknesses on SHA-1 has any impact on its security when used in HMAC, a fortiori when used in PBKDF2. For that matter, MD5 would be fine too (but not MD4).
> However, SHA-1 is not good for public relations: if, in 2011, you use SHA-1, then you must prepare yourself to have to justify that choice. On the other hand, SHA-256 is a fine "default function" and nobody will question it.

That's not direct proof that "KDF-HMAC-MD5 or KDF-HMAC-SHA1 are still good", but at least I'm not able to find any evidence to the contrary ...

---
Mike Ounsworth
Software Security Architect, Entrust

-----Original Message-----
From: TLS <[email-masked]> On Behalf Of [email-masked]
Sent: September 6, 2021 12:08 PM
To: [email-masked]
Subject: [EXTERNAL] TLS Digest, Vol 206, Issue 12

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

______________________________________________________________________
Send TLS mailing list submissions to
        [email-masked]

To subscribe or unsubscribe via the World Wide Web, visit
        https://urldefense.com/v3/__https://www.ietf.org/mailman/listinfo/tls__;!!FJ-Y8qCqXTj2!OJfu0Bw4RAJRNBaTWiveymI3ejCAhENdhuYiYHgrbCMekym94Kjx_qQ9grARj7oxn_y9$
or, via email, send a message with subject or body 'help' to
        [email-masked]

You can reach the person managing the list at
        [email-masked]

When replying, please edit your Subject line so it is more specific than "Re: Contents of TLS digest..."

Today's Topics:

   1. Re:  Combining Secrets in Hybrid Key Exchange in TLS 1.3
      (Nimrod Aviram)

----------------------------------------------------------------------

Message: 1
Date: Mon, 6 Sep 2021 20:07:10 +0300
From: Nimrod Aviram <[email-masked]>
To: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Cc: "<[email-masked]>" <[email-masked]>
Subject: Re: [TLS] Combining Secrets in Hybrid Key Exchange in TLS 1.3
Message-ID:
        <CABiKAoSi6KmF=[email-masked]>
Content-Type: text/plain; charset="utf-8"

I'd like to understand your position better.

> 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.
So, if I understand correctly, you argue that the text David Benjamin quoted from Appendix E.1 is wrong?
The second paragraph in Appendix E.1.1:
https://urldefense.com/v3/__https://datatracker.ietf.org/doc/html/rfc8446*appendix-E.1.1__;Iw!!FJ-Y8qCqXTj2!OJfu0Bw4RAJRNBaTWiveymI3ejCAhENdhuYiYHgrbCMekym94Kjx_qQ9grARjyN8Nzd2$
"This requires the underlying hash function to be collision resistant..."

Moreover, if it won?t matter from the security point of view whether SHA256 will or will not show collisions, then this implies that (hypothetically) switching from SHA256 to e.g. MD5 will not degrade security.
Is this your position? If so, could you please provide references that support this position, e.g. prove security under a non-CR hash function?

> I don?t think so.
If I understand correctly, you wrote this in response to me saying "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... This likely violates the security proof for TLS 1.3, in and of itself."
Is this what you're referring to? And I understand that you claim that an attacker achieving this would not violate any proven security property of TLS 1.3?

best,
Nimrod

On Thu, 2 Sept 2021 at 23:32, Blumenthal, Uri - 0553 - MITLL <[email-masked]>
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 <
> [email-masked]> 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 <[email-masked]> on behalf of Nimrod Aviram <
> [email-masked]>
> *Date: *Wednesday, September 1, 2021 at 15:58
> *To: *"<[email-masked]>" <[email-masked]>
> *Cc: *Eylon Yogev <[email-masked]>, Ilan Komargodski <
> [email-masked]>, Benjamin Dowling <[email-masked]>,
> Eyal Ronen <[email-masked]>
> *Subject: *[TLS] Combining Secrets in Hybrid Key Exchange in TLS 1.3
>
>
>
> (This note is also available on Github
> <https://urldefense.com/v3/__https://github.com/nimia/kdf_public*readm
> e__;Iw!!FJ-Y8qCqXTj2!OJfu0Bw4RAJRNBaTWiveymI3ejCAhENdhuYiYHgrbCMekym94
> Kjx_qQ9grARj5dfRKqq$ > 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||m
> 2)||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.
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://urldefense.com/v3/__https://mailarchive.ietf.org/arch/browse/tls/attachments/20210906/ac3cdfac/attachment.htm__;!!FJ-Y8qCqXTj2!OJfu0Bw4RAJRNBaTWiveymI3ejCAhENdhuYiYHgrbCMekym94Kjx_qQ9grARj7oVVWsG$ >

------------------------------

Subject: Digest Footer

_______________________________________________
TLS mailing list
[email-masked]
https://urldefense.com/v3/__https://www.ietf.org/mailman/listinfo/tls__;!!FJ-Y8qCqXTj2!OJfu0Bw4RAJRNBaTWiveymI3ejCAhENdhuYiYHgrbCMekym94Kjx_qQ9grARj7oxn_y9$

------------------------------

End of TLS Digest, Vol 206, Issue 12
************************************
Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.