Re: [TLS] [EXTERNAL] [CFRG] X-Wing: the go-to PQ/T hybrid KEM?
Bas Westerbaan <bas@cloudflare.com> Thu, 11 January 2024 13:08 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 7B790C14F5F5 for <tls@ietfa.amsl.com>; Thu, 11 Jan 2024 05:08:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.095
X-Spam-Level:
X-Spam-Status: No, score=-2.095 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_FONT_LOW_CONTRAST=0.001, HTML_MESSAGE=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_NONE=0.001, T_SCC_BODY_TEXT_LINE=-0.01, T_SPF_HELO_TEMPERROR=0.01, 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 hn94-caY1xFE for <tls@ietfa.amsl.com>; Thu, 11 Jan 2024 05:08:08 -0800 (PST)
Received: from mail-ed1-x52d.google.com (mail-ed1-x52d.google.com [IPv6:2a00:1450:4864:20::52d]) (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 B215AC1CAF44 for <tls@ietf.org>; Thu, 11 Jan 2024 05:07:06 -0800 (PST)
Received: by mail-ed1-x52d.google.com with SMTP id 4fb4d7f45d1cf-55745901085so6729947a12.0 for <tls@ietf.org>; Thu, 11 Jan 2024 05:07:06 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google09082023; t=1704978425; x=1705583225; darn=ietf.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=adNX+Gs/E6tf7MAxsFh3cMLe0mnAMo+SA1C8UulF7rA=; b=aR6JOhsXP/9yNR6DYP+aBkjcDbkGyD8ikyqKQpupbLM0ZGIulRKtZln+slLvfvOuME RketF0qCAKVTrVbYNVlX+uJPracJ4FkoqsVSwzxYZ34CDrefaHhyYpQRQ7wYnjYSku/y zwN4dnT/gDFEry0M3RnikBm65BFEEqyep/mTv/FjBFL+OqIpJjrjUWFEon4xHjNMQy6M LwYXlF3QvF3ztiC+xvn7jrOuJIKcJk+rxrHKr+T5QZTkiaRzWUNws32Dx/uUEo1Qc9CC rPK3zI1MJRjH4lXcayzykMKEpKr2catYD4lQxevg+OIj9hIcoMSz4GRALOkKFGr0a7u8 A4dQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1704978425; x=1705583225; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=adNX+Gs/E6tf7MAxsFh3cMLe0mnAMo+SA1C8UulF7rA=; b=rwe8lCMeWLBGdrvXPta6A0+SiwlnBQ+zBcZte+XvB/JHgxgxHlAXauyI0DrHH9g/ei eC+R4tapXKrjUhB9dyPKAg+ghwuJwQoYfCaza5gqMjspB3DM3eSra3pisNHXhm6HTC+v f8HoOeEhva7OZdmwuya6tFXXBVhsb0FG2ZpIU7vZ8zV6AgqphK9bT4nK2aT13tfWZt6B TlZHGouRI5Ow5AGofPOcuqtzEr5DY0LVEpEwHtaxuePmFN12xTQtZyGd11fdJEPw9vJ7 EBPWHJ4d6iHuUWtOorwB2f/ND4LZ4aWQXDYBRtaqzxSAXuBYASSxdHl+8cwP6MaTwCBJ befg==
X-Gm-Message-State: AOJu0Ywgj4lo9bPNjETDHn7GFH8Pb01Nm0z9nCZQTQCKlFYkhUYnVexj nJtu7sZKLj3N0AHzNimCYWXK7bOam8bsSumYT45vyqgyfc9BAg==
X-Google-Smtp-Source: AGHT+IHQj1pwcBCglcg0zAdCm1bCVCSawjkTgqAPdJXXcRRh3qxC6rVKRI9PQhmievKRUPA3Uz1Mm6oAcQa0LzAkxLs=
X-Received: by 2002:a50:ec8e:0:b0:555:204a:beb3 with SMTP id e14-20020a50ec8e000000b00555204abeb3mr633832edr.59.1704978425064; Thu, 11 Jan 2024 05:07:05 -0800 (PST)
MIME-Version: 1.0
References: <CAMjbhoWZxsLFH6yBc0hdx3t3SohurXGkfMzouoxGXM92HBR_dw@mail.gmail.com> <CH0PR11MB5739F6307E16B3B6A01BFBFA9F692@CH0PR11MB5739.namprd11.prod.outlook.com>
In-Reply-To: <CH0PR11MB5739F6307E16B3B6A01BFBFA9F692@CH0PR11MB5739.namprd11.prod.outlook.com>
From: Bas Westerbaan <bas@cloudflare.com>
Date: Thu, 11 Jan 2024 14:06:54 +0100
Message-ID: <CAMjbhoWysgatzqy1uR+4qx1mVHW8wbn6KvPuD5z79w_6+bueRw@mail.gmail.com>
To: Mike Ounsworth <Mike.Ounsworth=40entrust.com@dmarc.ietf.org>
Cc: IRTF CFRG <cfrg@irtf.org>, "<tls@ietf.org>" <tls@ietf.org>, Deirdre Connolly <durumcrustulum@gmail.com>, "karo@cupdev.net" <karo@cupdev.net>
Content-Type: multipart/alternative; boundary="00000000000060a391060eab396c"
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/1QGG0KjW2OwPKLQjsqiRb1g1Qro>
Subject: Re: [TLS] [EXTERNAL] [CFRG] 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: Thu, 11 Jan 2024 13:08:13 -0000
> Speaking for myself (not for my co-authors), this feels like friendly, > complementary work to draft-ounsworth-cfrg-kem-combiners; > I agree. > We could consider adding a section with concrete instantiations, and the > first one would be X-Wing š (followed by ML-KEM + P-256, Brainpool, and > RSA variants). > > > > I guess that leads to the following question: @Bas Westerbaan > <bas=40cloudflare.com@dmarc.ietf.org>, @Deirdre Connolly > <durumcrustulum@gmail.com>, Peter, would you be open to merging X-Wing > into the generic combiner draft, or is there value in it being standalone? > X-Wing explicitly trades genericity for simplicity. We will not get such a simple and efficient construction if it is the instantiation of an easy-to-use generic construction. Best, Bas > > --- > > *Mike* Ounsworth > > > > *From:* CFRG <cfrg-bounces@irtf.org> *On Behalf Of *Bas Westerbaan > *Sent:* Wednesday, January 10, 2024 2:14 PM > *To:* IRTF CFRG <cfrg@irtf.org>; <tls@ietf.org> <tls@ietf.org> > *Cc:* karo@cupdev.net > *Subject:* [EXTERNAL] [CFRG] X-Wing: the go-to PQ/T hybrid KEM? > > > > 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 > > 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/ > <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-Y-JP2DY$> > Proof: https://eprint.iacr.org/2024/039 > <https://urldefense.com/v3/__https:/eprint.iacr.org/2024/039__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-Xl0zY2C$> > [1] Full name X25519Kyber768Draft00. > https://datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/ > <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-bUDJTlz$> > [2] Full name SecP256r1Kyber768Draft00. > https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-kyber/ > <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-kyber/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-cpge9_6$> > [3] > https://blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html > <https://urldefense.com/v3/__https:/blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-X2cJwvg$> > https://twitter.com/bwesterb/status/1734586155868287457 > <https://urldefense.com/v3/__https:/twitter.com/bwesterb/status/1734586155868287457__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-agVitjD$> > [4] https://datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/ > <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-axrezMz$> > [5] https://link.springer.com/chapter/10.1007/978-3-319-76578-5_7 > <https://urldefense.com/v3/__https:/link.springer.com/chapter/10.1007/978-3-319-76578-5_7__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-U_tyIdl$> > [6] > https://datatracker.ietf.org/doc/draft-westerbaan-cfrg-hpke-xyber768d00/ > <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-westerbaan-cfrg-hpke-xyber768d00/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-V-p_aAA$> > [7] https://datatracker.ietf.org/doc/draft-ounsworth-cfrg-kem-combiners/ > <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-ounsworth-cfrg-kem-combiners/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-bx4gLTn$> > [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