[TLS] X-Wing: the go-to PQ/T hybrid KEM?
Bas Westerbaan <bas@cloudflare.com> Wed, 10 January 2024 20:14 UTC
Return-Path: <bas@cloudflare.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 01758C14CE5D for <tls@ietfa.amsl.com>; Wed, 10 Jan 2024 12:14:07 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.104
X-Spam-Level:
X-Spam-Status: No, score=-2.104 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=cloudflare.com
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id d9_xkVdkfHoM for <tls@ietfa.amsl.com>; Wed, 10 Jan 2024 12:14:02 -0800 (PST)
Received: from mail-lj1-x22f.google.com (mail-lj1-x22f.google.com [IPv6:2a00:1450:4864:20::22f]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E4064C14CE33 for <tls@ietf.org>; Wed, 10 Jan 2024 12:14:02 -0800 (PST)
Received: by mail-lj1-x22f.google.com with SMTP id 38308e7fff4ca-2cd0f4f306fso54963951fa.0 for <tls@ietf.org>; Wed, 10 Jan 2024 12:14:02 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google09082023; t=1704917641; x=1705522441; darn=ietf.org; h=cc:to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=YfLq93q55TlT4Y/KckGUr4cQsn9yCwW3GzmUKf04mh0=; b=TMTHkKXNPcHIwa/ILohgP+NVr+9pP/+MFZsCRevVZesalis3t46+n0NNL3NXzVVkKb v9aTgLi36VC6zY2HL3cBANUBnfCESSqB3yjyvisVCTS5PfIS/LUlEqf/HR3iGgVb33Aq wjCbiZRLumMB8i7hSRaqBAmhKBY+tvXESmMXvTgS6hYk72rzdfk3e8l2/fScGHCy9ewg c8HzHUMNLK1LRpEDoozyl90bY2UQbjZfbmhdzlobUMHGRHtllcJ3hcwjZRpPKmnX/yeg Wh0EnFurFtRZ+bM1lFWuKIOWEL6qzUQNdoCMAFCguYurwp6X6ws+oGhWV2d9yW0qQDMP CDDQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1704917641; x=1705522441; h=cc:to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=YfLq93q55TlT4Y/KckGUr4cQsn9yCwW3GzmUKf04mh0=; b=YHRzfA1ToC9XKxLYiyPSEIsNZ4oGUOt6OQLUPs1AUlUcRqE7bt1y6hpjsJrLbjMvC9 WNdPu7Lb1YoqizLUNI7VHm3uByjZw44hvd6ytBJ5k7MqsUVqc7/IbNz5yADlfBeUJ/7M IzgjqYhbEcO2U1DLLwVpNeYUK3lN/U4clhxDclq+97z3IJ0sVfnfMaNDX/OUIiLb5qxK xQLtpb7kiBh3rP22dUCe/Jue5qY6Lg6M+DrPWkQ/qKPLRmSrq4muHkXjOj5GfCdno+n4 qKRmzHiPfuHAO7Lo5cpgO81FUVBdKwbvFoOQYrcqHy4uueUvipBBCATxHxsGv+90EbXz XllQ==
X-Gm-Message-State: AOJu0YxqddzwJcJUeP1dx2AD5wvccvA6Lvzzg/MmqGSZywKelgX0Nj8P S7Q1ODA7czWSIi9gT9POmeYtKFxGH3crxI3GS7QbBJ9FpPwX/w==
X-Google-Smtp-Source: AGHT+IEWzXjBeVyhbaEVWHcifZLHz1rPphMhB6EkFx0J2oXJce2X2heQtYideUSLbtnhKFdXc8cLxOwbwt89tNsw1+I=
X-Received: by 2002:a2e:9e01:0:b0:2cd:4c1e:fdcb with SMTP id e1-20020a2e9e01000000b002cd4c1efdcbmr47833ljk.93.1704917640700; Wed, 10 Jan 2024 12:14:00 -0800 (PST)
MIME-Version: 1.0
From: Bas Westerbaan <bas@cloudflare.com>
Date: Wed, 10 Jan 2024 21:13:49 +0100
Message-ID: <CAMjbhoWZxsLFH6yBc0hdx3t3SohurXGkfMzouoxGXM92HBR_dw@mail.gmail.com>
To: IRTF CFRG <cfrg@irtf.org>, "<tls@ietf.org>" <tls@ietf.org>
Cc: Deirdre Connolly <durumcrustulum@gmail.com>, Peter Schwabe <peter@cryptojedi.org>, karo@cupdev.net, mbb@fc.up.pt
Content-Type: multipart/alternative; boundary="00000000000058d568060e9d12eb"
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/m3zApMjm9Z9Naf3uTAY-M3mi7BI>
Subject: [TLS] X-Wing: the go-to PQ/T hybrid KEM?
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.39
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, 10 Jan 2024 20:14:07 -0000
Dear tls and cfrg working groups, With ML-KEM (née Kyber) expected to be finalized this year, it’s time to revisit the question of which PQ/T hybrid KEMs to standardize, and which to recommend. # Status quo For TLS at the time of writing there are two PQ/T hybrids registered: X25519Kyber768 [1] and P256Kyber768 [2]. The former has been deployed widely [3]. Both are instances of the hybrid-design draft [4], which use the simple combiner ss_ECC || ss_Kyber, which is suitable for TLS, but not for other applications such as HPKE, as it’s not IND-CCA2 robust [5]. For HPKE, there is a different KEM called X25519Kyber768 [6], which uses a different combiner that mixes in the X25519 ephemeral key, by using HPKE’s DHKEM construction instead of raw X25519. There is also the ounsworth-kem-combiners I-D [7] that informed by [5] proposes the generic combiner KDF( counter || ct1 || ss1 || ct2 || ss2 || fixedInfo, outputBits ) >From a security standpoint that would be suitable for HPKE and TLS. To TLS it is somewhat unattractive as it requires hashing the typically large PQ ciphertexts, and adds some extra hashing in the conversion of the ECDH into a KEM. On the other hand, for TLS it would be nice to have a KEM that is also suitable for HPKE, as HPKE is used in ECH. >From a usability perspective, ounsworth-kem-combiners requires the user to make several choices: which KEMs and in particular which method to use to turn ECDH into a KEM, which security levels, which KDF, etc. # The proposal: X-Wing Let us introduce X-Wing [0]. The goal of X-Wing is to be *the* go-to PQ/T hybrid KEM for the majority of use cases (including TLS and HPKE): no need to make choices, or understand the subtleties. X-Wing aims for 128-bit security, and for that combines the time-tested X25519 with ML-KEM-768 [8]. X-Wing uses the combiner SHA3-256( xwing-label || ss_ML-KEM || ss_X25519 || ct_X25519 || pk_X25519 ) Here ss_X25519 is the plain X25519 shared secret; ct_X25519 is the ephemeral public key; xwing-label a 6-byte label. Note that it doesn’t hash in the ML-KEM ciphertext. For a generic KEM one cannot leave out the ciphertext, but in the case of ML-KEM we can, assuming we can model SHA3/SHAKE as a random oracle. This is proven in [0]. The gist is that FO transform in ML-KEM makes it “ciphertext collision resistant”: even if the underlying lattice problem is broken, it’s infeasible to create from one ciphertext another different ciphertext with the same shared secret. # Not final We would love to hear your input: X-Wing is not final. For one, ML-KEM itself might still change (presumably only in minor ways) before final standardization. We think the CFRG would be a good venue to standardize X-Wing — do you concur? Best, Bas, Deirdre, Karolin, Manuel, Peter PS. We want to mention explicitly that we see value in the kem-combiners and hybrid-design drafts as generic safe methods to construct hybrids for those use cases where X-Wing would not suffice. [0] Spec: https://datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/ Proof: https://eprint.iacr.org/2024/039 [1] Full name X25519Kyber768Draft00. https://datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/ [2] Full name SecP256r1Kyber768Draft00. https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-kyber/ [3] https://blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html https://twitter.com/bwesterb/status/1734586155868287457 [4] https://datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/ [5] https://link.springer.com/chapter/10.1007/978-3-319-76578-5_7 [6] https://datatracker.ietf.org/doc/draft-westerbaan-cfrg-hpke-xyber768d00/ [7] https://datatracker.ietf.org/doc/draft-ounsworth-cfrg-kem-combiners/ [8] Following earlier deployment of X25519Kyber768, despite targeting 128 bits, we use ML-KEM-768 instead of ML-KEM-512 to hedge against advances in lattice attacks.
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein
- [TLS] X-Wing: the go-to PQ/T hybrid KEM? Bas Westerbaan
- Re: [TLS] [EXTERNAL] [CFRG] X-Wing: the go-to PQ/… Mike Ounsworth
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Bas Westerbaan
- Re: [TLS] [EXTERNAL] [CFRG] X-Wing: the go-to PQ/… Bas Westerbaan
- Re: [TLS] [EXTERNAL] [CFRG] X-Wing: the go-to PQ/… Mike Ounsworth
- Re: [TLS] [EXTERNAL] Re: [CFRG] X-Wing: the go-to… Mike Ounsworth
- Re: [TLS] [EXTERNAL] Re: [CFRG] X-Wing: the go-to… Bas Westerbaan
- Re: [TLS] [EXTERNAL] [CFRG] X-Wing: the go-to PQ/… Bas Westerbaan
- Re: [TLS] [CFRG] [EXTERNAL] X-Wing: the go-to PQ/… Peter C
- Re: [TLS] [CFRG] [EXTERNAL] X-Wing: the go-to PQ/… Mike Ounsworth
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Kampanakis, Panos
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Deirdre Connolly
- Re: [TLS] X-Wing: the go-to PQ/T hybrid KEM? Filippo Valsorda
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Salz, Rich
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Sophie Schmieg
- Re: [TLS] [EXT] Re: [CFRG] X-Wing: the go-to PQ/T… Blumenthal, Uri - 0553 - MITLL
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Orie Steele
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Scott Fluhrer (sfluhrer)
- Re: [TLS] X-Wing: the go-to PQ/T hybrid KEM? Martin Thomson
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein
- Re: [TLS] X-Wing: the go-to PQ/T hybrid KEM? Watson Ladd
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Jack Grigg
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Bas Westerbaan
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Bas Westerbaan
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Ilari Liusvaara
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Eric Rescorla
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Ilari Liusvaara
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Peter Schwabe
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Peter Schwabe
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… Natanael
- Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KE… D. J. Bernstein