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

From: Nimrod Aviram <[email-masked]>
Date: Wed, 1 Sep 2021 22:56:35 +0300

(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.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 1 Sep 2021 20:34:06 +0000

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 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.

dangerous. Currently, the "Hybrid key exchange in TLS 1.3" document uses secret

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.

collision resistance; instead, we likely only need multi-preimage-resistance:

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)

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.

APOP is an old challenge-response protocol used in email, relevant here because

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.

---

From: Nimrod Aviram <[email-masked]>
Date: Thu, 2 Sep 2021 23:16:50 +0300

The APOP attack demonstrates that concatenating secrets may be dangerous,
as a general cryptographic practice.
As to the TLS KDF, if future SHA256 cryptanalysis results in collisions, 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.
This likely violates the security proof for TLS 1.3, in and of itself.
A similar violation of the security guarantee seems to arise when using
hybrid key exchange with a PQ KEM.

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.
We view this as an opportunity to defend-in-depth against such issues,
while the document is not yet finalized.

On Wed, 1 Sept 2021 at 23:34, Blumenthal, Uri - 0553 - MITLL <[email-masked]>
wrote:

> *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
>
>
>

---

From: Dan Brown <[email-masked]>
Date: Thu, 2 Sep 2021 20:28:57 +0000

Dear Nimrod and team:

How does your concern compare to Campagna and Petcher’s report

https://eprint.iacr.org/2020/1364

which has security proofs for concatenation-based KDF?

(Maybe a detailed discussion is better suited to CFRG?)

Best regards,

 Dan

From: TLS <[email-masked]> On Behalf Of Nimrod Aviram
Sent: Wednesday, September 1, 2021 3:57 PM
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*readme__;Iw!!COg3wY07Hnb7!5OmIbV58bG3VGtwYOI1gL73xJz_hfm6BqfyKoWRKT25K7-yOj4ziPAfkU9BCeC0$>  for ease of reading.)

The construction is: 

Furthermore, 

best wishes,

References: 

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 2 Sep 2021 20:31:53 +0000

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.

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:

--

Regards,

Uri

                                                                                                                                     -  C. A. R. Hoare

The construction is: 

Furthermore, 

best wishes,

References:

---

From: David Benjamin <[email-masked]>
Date: Thu, 2 Sep 2021 18:51:22 -0400

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 <
[email-masked]> wrote:

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

---

From: Nimrod Aviram <[email-masked]>
Date: Fri, 3 Sep 2021 14:25:48 +0300

Hi Dan,

The assumptions for the ETSI proofs don't match the scenario we're
considering, but are rather stronger.
We assume the adversary gets to control some part of the secret
concatenation (e.g. when KEMs are used), and that honest parties may re-use
secrets (e.g. when static ECDH is used).
The ETSI proofs model HKDF either as a random oracle, or as a weakly secure
KDF.

In particular, they use two assumptions to model HKDF in the ETSI
constructions:

1. HKDF is modelled as a random oracle, which is inherently
collision-resistant. Specifically, each random oracle takes a query tuple
(s, r, c), where s is keying material, r is salt and c is context values,
and returns a random bit string if the query is not entirely equal to a
previous query value. The HKDF paper does not claim security in the
presence of attacker-controlled entropy [1], so this assumption seems
rather strong.

2. HKDF is modelled as a weakly secure KDF. In this assumption, both the
secret value s and the salt r are randomly selected, and (r,a) is given to
the adversary, where a is a description of the secret space that s is drawn
from. The adversary is allowed to specify a context value c and an output
length, and has to distinguish the output from the KDF from a random string
of the same length. The adversary is not allowed to query the KDF more than
once. Note that for the purposes of Cascade KDF, the secret value s is the
concatenation of all secrets output from the hybrid KEM, and they seem to
assume one of which is IND-CPA secure.

In either case, the adversary is not able to inject KEM ciphertexts or
secrets.

(I am mostly relaying here an explanation by my colleague Ben Dowling,
thanks Ben :-)
best,
Nimrod

[1] https://eprint.iacr.org/2010/264.pdf, starting from the bottom of page
8.

On Thu, 2 Sept 2021 at 23:29, Dan Brown <[email-masked]> wrote:

> *From:* TLS <[email-masked]> *On Behalf Of *Nimrod Aviram
> *Sent:* Wednesday, September 1, 2021 3:57 PM
> *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
>
>
>
> <https://urldefense.com/v3/__https:/github.com/nimia/kdf_public*readme__;Iw!!COg3wY07Hnb7!5OmIbV58bG3VGtwYOI1gL73xJz_hfm6BqfyKoWRKT25K7-yOj4ziPAfkU9BCeC0$>
> for ease of reading.)
>
>
>
> ------------------------------
> This transmission (including any attachments) may contain confidential
> information, privileged material (including material protected by the
> solicitor-client or other applicable privileges), or constitute non-public
> information. Any use of this information by anyone other than the intended
> recipient is prohibited. If you have received this transmission in error,
> please immediately reply to the sender and delete this information from
> your system. Use, dissemination, distribution, or reproduction of this
> transmission by unintended recipients is not authorized and may be unlawful.
>

---

From: Nimrod Aviram <[email-masked]>
Date: Fri, 3 Sep 2021 15:33:39 +0300

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
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.

---

From: Nimrod Aviram <[email-masked]>
Date: Mon, 6 Sep 2021 20:07:10 +0300

I'd like to understand your position better.

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://datatracker.ietf.org/doc/html/rfc8446#appendix-E.1.1
"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