[TLS] Combining Secrets in Hybrid Key Exchange in TLS 1.3
Nimrod Aviram <nimrod.aviram@gmail.com> Wed, 01 September 2021 19:56 UTC
Return-Path: <nimrod.aviram@gmail.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 99D973A17FE for <tls@ietfa.amsl.com>; Wed, 1 Sep 2021 12:56:52 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id v-0bGFkZBaZQ for <tls@ietfa.amsl.com>; Wed, 1 Sep 2021 12:56:50 -0700 (PDT)
Received: from mail-qv1-xf29.google.com (mail-qv1-xf29.google.com [IPv6:2607:f8b0:4864:20::f29]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9CBF83A1803 for <tls@ietf.org>; Wed, 1 Sep 2021 12:56:49 -0700 (PDT)
Received: by mail-qv1-xf29.google.com with SMTP id z2so522890qvl.10 for <tls@ietf.org>; Wed, 01 Sep 2021 12:56:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:from:date:message-id:subject:to:cc; bh=z/SYDP7rOcM+8ZLm2zApr9JlwaMz3X+SCiU4Z0BfRnQ=; b=Qzx2Sjm2oJPV1k1vAw6DFIIAlLqrU5rpU0TYpkaISxb5cMS5+DLBZIr7GvnJVTKH7B lpvfbXY+ePZCu/hGYrgRcJ0/IGJRbbpXw8YVPPhagp8rOpiokYNQgwb1RDiWPfHguX88 GZkN2ZJ28qDkP6QJSdiHaBw89pIvP4cjdyZ82t/xa6muVE7yQhqALGS5sYtkFissIpkf 5Veiq50kMpYOpmiYfQiDXRQ5jfh/ZN7YC0ZPOq9WDtilEkTJUldMRzs6+xklmNm34jHG DbrAUhQgyKKY2aPZMp/hLX6YaxSTJZF3t3JI5BLTwRwBJ8YGTkC8yrzuWmy3jKDCLovZ TT8g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc; bh=z/SYDP7rOcM+8ZLm2zApr9JlwaMz3X+SCiU4Z0BfRnQ=; b=BYEUWJ4G3TiVx1+yAJnVMP7VynzhH9MUagChLIeqSBFnDdjmd6GHsjlU5NLcEeHMuQ LRBcUf1bX7Mx/N+yQ/0XUfUwdbHzbdBOqwIr8hDPo2KcsSG4jIK6HInSkRMMb0xTzI/7 jycHW+BGUd9SokTYll6aJ2j711qMp3kf+5Jzlfl+MqhLOl9vJaJFnW9ppp7l+B8k/MwW wJjJYIRh62cy4VzChV4oUl+DZA7FrJKvt58glfK1bkioK4ZIQIX1HdZHicVbX9A696w3 ZIRPamUWFpsHpjUoWCkhWnm75EVN8ReMy8jOXt0fTjvch0FHNve11Yhj2DAyxXAZ2T4b wZiw==
X-Gm-Message-State: AOAM532sf+Z4F0DJ4wZzgSqYuAbTX2avob2NXAwlxzbgc94e1Uo0hT9n BBJ0v1TJ6EozI8xz0egVK/nTrE9aQdlKtQsXVSCtQ6w1MGUCzA==
X-Google-Smtp-Source: ABdhPJyYFyLIYhuZfSmphGQAFTzN2Du6Uj1ZfeMzOJQpPw9rMNoWNpDoHfp2DASddKliWqVfBzu183kxHtK+vI+TXMc=
X-Received: by 2002:a0c:cd86:: with SMTP id v6mr1546761qvm.26.1630526206796; Wed, 01 Sep 2021 12:56:46 -0700 (PDT)
MIME-Version: 1.0
From: Nimrod Aviram <nimrod.aviram@gmail.com>
Date: Wed, 01 Sep 2021 22:56:35 +0300
Message-ID: <CABiKAoTOVqDucNuyJeH6VzJQdygpT7yAiA-V=+jLBCpfw+Ru4w@mail.gmail.com>
To: "<tls@ietf.org>" <tls@ietf.org>
Cc: Eylon Yogev <eylony@gmail.com>, Ilan Komargodski <ilankom10@gmail.com>, Benjamin Dowling <b.dowling@sheffield.ac.uk>, Paterson Kenneth <kenny.paterson@inf.ethz.ch>, Eyal Ronen <er@eyalro.net>
Content-Type: multipart/alternative; boundary="0000000000005a668f05caf477b3"
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/F4SVeL2xbGPaPB2GW_GkBbD_a5M>
Subject: [TLS] Combining Secrets in Hybrid Key Exchange in TLS 1.3
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 01 Sep 2021 19:56:53 -0000
(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] Combining Secrets in Hybrid Key Exchange in… Nimrod Aviram
- Re: [TLS] Combining Secrets in Hybrid Key Exchang… Blumenthal, Uri - 0553 - MITLL
- Re: [TLS] Combining Secrets in Hybrid Key Exchang… Nimrod Aviram
- Re: [TLS] Combining Secrets in Hybrid Key Exchang… Dan Brown
- Re: [TLS] Combining Secrets in Hybrid Key Exchang… Blumenthal, Uri - 0553 - MITLL
- Re: [TLS] Combining Secrets in Hybrid Key Exchang… David Benjamin
- Re: [TLS] Combining Secrets in Hybrid Key Exchang… Nimrod Aviram
- Re: [TLS] Combining Secrets in Hybrid Key Exchang… Nimrod Aviram
- Re: [TLS] Combining Secrets in Hybrid Key Exchang… Nimrod Aviram