[openpgp] Re: WG: BSI view on KEM combiners
"D. J. Bernstein" <djb@cr.yp.to> Sat, 14 September 2024 18:22 UTC
Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1C35AC151534 for <openpgp@ietfa.amsl.com>; Sat, 14 Sep 2024 11:22:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.905
X-Spam-Level:
X-Spam-Status: No, score=-1.905 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, UNPARSEABLE_RELAY=0.001, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no
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 oMRabiWSdiQR for <openpgp@ietfa.amsl.com>; Sat, 14 Sep 2024 11:22:05 -0700 (PDT)
Received: from salsa.cs.uic.edu (salsa.cs.uic.edu [131.193.32.108]) by ietfa.amsl.com (Postfix) with SMTP id 0A53FC15152D for <openpgp@ietf.org>; Sat, 14 Sep 2024 11:22:04 -0700 (PDT)
Received: (qmail 6133 invoked by uid 1010); 14 Sep 2024 18:22:03 -0000
Received: from unknown (unknown) by unknown with QMTP; 14 Sep 2024 18:22:03 -0000
Received: (qmail 7221 invoked by uid 1000); 14 Sep 2024 18:21:54 -0000
Date: Sat, 14 Sep 2024 18:21:54 -0000
Message-ID: <20240914182154.7219.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: openpgp@ietf.org
In-Reply-To: <CAMm+Lwj1+O1whL1Xf_ZypD9t8rQ5TAmG9Z4O9V3VWFk=dN7VGA@mail.gmail.com>
Message-ID-Hash: NJVVL2AUBTFLPZ2UIAN7FOFBL23WFZ4U
X-Message-ID-Hash: NJVVL2AUBTFLPZ2UIAN7FOFBL23WFZ4U
X-MailFrom: djb-dsn2-1406711340.7506@cr.yp.to
X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; header-match-openpgp.ietf.org-0; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header
X-Mailman-Version: 3.3.9rc4
Precedence: list
Subject: [openpgp] Re: WG: BSI view on KEM combiners
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
Archived-At: <https://mailarchive.ietf.org/arch/msg/openpgp/3h3el8sKSu4eVpp1WL4mhuGM9UY>
List-Archive: <https://mailarchive.ietf.org/arch/browse/openpgp>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Owner: <mailto:openpgp-owner@ietf.org>
List-Post: <mailto:openpgp@ietf.org>
List-Subscribe: <mailto:openpgp-join@ietf.org>
List-Unsubscribe: <mailto:openpgp-leave@ietf.org>
Phillip Hallam-Baker writes: > What is it about combining KEM and ECC outputs that is supposed to be so > difficult that HKDF does not already address it? Sure, 99% of the real-world problem that combiners are supposed to address is solved by simply upgrading from "ECDH session key" to "hash of ECDH session key and KEM session key", with any of the usual hash functions. (Similarly, checking an ECC signature and a PQ signature deals with 99% of the problem for signatures.) However, there are security arguments for having an ECDH+KEM combiner hash the full transcript: not just the session keys but also the KEM ciphertext, the KEM public key, and both of the ECDH public keys. For example, if there's a severe IND-CCA2 attack against the KEM in which a modified ciphertext produces the same session key, then simply hashing the two session keys isn't IND-CCA2 even when ECDH is unbroken, so what happens to a protocol relying on IND-CCA2? Many protocols turn out to be ok, but do we really want to spend time re-analyzing a bunch of protocols and dealing with the cases where there _is_ a problem? With transcript hashing, breaking IND-CCA2 clearly requires breaking ECDH _and_ the KEM. https://eprint.iacr.org/2021/708 and https://eprint.iacr.org/2021/1351 include arguments for hashing at least a prefix of the public key. Having a KEM combiner that includes the ECDH public key and KEM public key as extra inputs means that people don't have to worry about the possibility of problems here. The arguments in these papers are weak, but the counterarguments are weak too. Once one has settled on what to hash, there are further engineering questions about the hashing details and about which system component should be responsible for each part of the hashing. As an example of why this is tricky: * KEMs vary in whether they include their own hashing of ciphertexts and of public keys. * Kyber said that for "robustness" it was hashing "the entire transcript" to make Kyber "as robust and misuse-resilient as possible". However, NIST then (for unclear reasons) dropped Kyber's ciphertext hashing. * X-Wing uses a combiner that (for speed) omits ciphertext hashing. But X-Wing also uses specifically Kyber-768, and has a security analysis claiming that Kyber is still doing something _tantamount_ to ciphertext hashing, maybe at a 2^128 security level. This puts unnecessary load on security reviewers, and I think it'll turn out to be fragile. I would just have the combiner hash the transcript so that we don't have to worry about whether KEMs are aiming for something beyond IND-CCA2 and don't have to worry about whether protocols are secure with less hashing. But there's a specific claim that extra hashing would cost Google "millions of dollars/CO2 emissions/energy"; there's a claim that failing outside the Kyber context is a positive feature; etc. One can't expect CFRG to have an easy decision here. ---D. J. Bernstein
- [openpgp] WG: BSI view on KEM combiners Ehlen, Stephan
- [openpgp] BSI view on KEM combiners Kris Kwiatkowski
- [openpgp] Re: WG: BSI view on KEM combiners D. J. Bernstein
- [openpgp] Re: WG: BSI view on KEM combiners D. J. Bernstein
- [openpgp] Re: WG: BSI view on KEM combiners D. J. Bernstein
- [openpgp] Re: WG: BSI view on KEM combiners Daniel Huigens
- [openpgp] Re: WG: BSI view on KEM combiners Ehlen, Stephan
- [openpgp] Re: WG: BSI view on KEM combiners Daniel Huigens
- [openpgp] Re: WG: BSI view on KEM combiners Ehlen, Stephan
- [openpgp] Re: WG: BSI view on KEM combiners Daniel Huigens
- [openpgp] Re: WG: BSI view on KEM combiners Falko Strenzke
- [openpgp] Re: WG: BSI view on KEM combiners Daniel Huigens
- [openpgp] Re: WG: BSI view on KEM combiners Falko Strenzke
- [openpgp] Re: WG: BSI view on KEM combiners Daniel Huigens
- [openpgp] Re: WG: BSI view on KEM combiners Paul Wouters
- [openpgp] Re: WG: BSI view on KEM combiners Paul Wouters
- [openpgp] Re: WG: BSI view on KEM combiners Paul Wouters
- [openpgp] Re: WG: BSI view on KEM combiners Falko Strenzke
- [openpgp] Re: WG: BSI view on KEM combiners Paul Wouters
- [openpgp] Re: WG: BSI view on KEM combiners Phillip Hallam-Baker
- [openpgp] Re: WG: BSI view on KEM combiners Phillip Hallam-Baker
- [openpgp] Re: WG: BSI view on KEM combiners Phillip Hallam-Baker