Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7B82AC14F748 for ; Mon, 29 Jul 2024 08:07:00 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -7.104 X-Spam-Level: X-Spam-Status: No, score=-7.104 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, RCVD_IN_DNSWL_HI=-5, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-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=gmail.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 TfuAH0UlbQnO for ; Mon, 29 Jul 2024 08:06:56 -0700 (PDT) Received: from mail-yw1-x1131.google.com (mail-yw1-x1131.google.com [IPv6:2607:f8b0:4864:20::1131]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature ECDSA (P-256) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id F10BEC169412 for ; Mon, 29 Jul 2024 08:06:55 -0700 (PDT) Received: by mail-yw1-x1131.google.com with SMTP id 00721157ae682-64b417e1511so22723887b3.3 for ; Mon, 29 Jul 2024 08:06:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722265615; x=1722870415; darn=irtf.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=gvTxoC7UixZKUVS/4N6Y4oYj50qAKsSZftSA1jRm/+M=; b=c8X7hAZoTJ/nr6y5lpEsPLa45jS8oAmbTLeUaHSzmhiojq8diGmT3lGDdSAdYEZ84l GlgQMWLZ5wXJJe6hNXB8DC10PdD+NOrtXH53AKascU/dXQftflsqB2y/xXxaRz7LR+sY Q7SxvdT1Jhg1wKAHPoR/luIOUjzUoYoVniWPYL9TKjJhliX56zZBxqH9RHqYzxoWHWpT EH7rVz7YCF4M8JiH3RZK+BezCUI0h9lPj48uitfreOgPU2b6nKbYPjfJHrHksVB1JvUi Fo5PmMQ9jj1zgKLrnkDSM1kONRKHidcJKqrafuMFFHIczmNLkYlWpqg1ZdVbmayG9qsz QcLw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722265615; x=1722870415; 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=gvTxoC7UixZKUVS/4N6Y4oYj50qAKsSZftSA1jRm/+M=; b=qnE+OBMCAWhclxehEpxqcHMJUp/aG2NceoOxteDw0Aqsu2JfiTyfMxMdJyg4Q6uuAh SEHhlYpt+s6ZzWMfGx7JkXquiUH6Qam0FvhE+geaHh5Tld8/7ya2o3rN63+VJSZmKrI5 g8iRQCv2JeFUZXm0Zpuvk3mHdcXeawhzSGAyxg8W/jcQ6a3GqXqwPJaD0VOU36vvsbAE G/7DSePwqlwymXCr17ScnwC2uuuoqFFPMxfPDDMxJcLV5uuXcIR5ZTNxQeQkZ2n6dlyk Gr9yVrz9KrHATOiKZxl9DqFnzQ1ZjsAqzZp/SyAJ/10Aaa7/eKGuY8FnVn0HzmHJrV6t KySA== X-Forwarded-Encrypted: i=1; AJvYcCV+ZmtrcDuwT8WJy01UjxxGmPycUWkdefAD+Z0HL5nUuYWPFSBsWcCYBfXTiTFh0JUZQhJay9F5Mi7S20aA X-Gm-Message-State: AOJu0YzYLZudGlEZdvncdg3TbA+KXZwzluRVkcfDAgUK8am/Y1c5NzIa rHjFU4S49VDUmZDW5UJ6NnEpkPKDUxhub9eDnVbOM6U5VKWykXrN5cmrrEPdrz7aQJeCvu7pi8z GRKoREXSE8FjP1TDS5KEiF+SAMfQ= X-Google-Smtp-Source: AGHT+IFHCz1u9LOGMrPofAkyHPxmEzTTZi/IePdmeNCZHRcaMKF2qhatSF3YQpHnq8EhlVtH3XLqJIuF43qAeq1zU9s= X-Received: by 2002:a05:690c:7307:b0:64b:9f5f:67b2 with SMTP id 00721157ae682-67a09596465mr104543257b3.31.1722265614831; Mon, 29 Jul 2024 08:06:54 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Cas Cremers Date: Mon, 29 Jul 2024 17:06:38 +0200 Message-ID: To: Peter C Content-Type: multipart/alternative; boundary="0000000000002e56f2061e643675" Message-ID-Hash: GIZXV3V4VL5T5KHAZLISKJP2LBL4CDGO X-Message-ID-Hash: GIZXV3V4VL5T5KHAZLISKJP2LBL4CDGO X-MailFrom: cas.cremers@gmail.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; header-match-cfrg.irtf.org-0; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: CFRG X-Mailman-Version: 3.3.9rc4 Precedence: list Subject: =?utf-8?q?=5BCFRG=5D_Re=3A_DHKEM_binding_properties?= List-Id: Crypto Forum Research Group Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --0000000000002e56f2061e643675 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Peter, while you directed the email to Deirdre, we think it may be a good point to chime in here as the original authors of https://eprint.iacr.org/2023/1933: TL;DR: Yes, DH-KEM is probably not MAL secure. This is not because of an API mismatch but because it does not explicitly check for well-formed key material. Our API models real-world KEM usage. The =E2=80=98trivial attacks= =E2=80=99 we =E2=80=98block=E2=80=99 in our paper are degenerate cases in our properties= , we will update the wording. Let us first address some points, before going to the API. 1. Deirdre's Slides: Checking Deirdre's backup slides, there seem to be some relics from earlier talks. We no longer conjecture MAL properties but provide a proof for LEAK in the ROM (for DH-KEM and other KEMs). 2. Previous Paper Versions: We've checked, and the previous versions of the paper are available to us on IACR as expected: https://eprint.iacr.org/archive/versions/2023/1933 MAL-Binding and API Choices We agree that MAL claims need careful interpretation. As mentioned, we no longer conjecture these properties for any KEM implementation. This change is not due to our API choice differing from the real-world API, but because these properties can only be achieved if the KEM implementation verifies the well-formedness of the supplied key material. For example, a KEM implementation might check whether the hash of the public key stored inside the secret key is correct. Without these checks, a MAL adversary could alter the stored hash to break binding. More details can be found in Section 3 of [this paper](https://eprint.iacr.org/2024/523.pdf). Next, we will elaborate on our API choices, why they differ from the real-world API, and why we believe this is necessary. Let=E2=80=99s recall the intuition behind our binding properties: Given a shared secret, a public key, or a ciphertext, two KEM operations which use (or result in) this value, should with overwhelming probability also produce equal values for one (or more) of the other parameters. Note, that we did not include the private key here, as during a KEM exchange, only one of the parties knows the private key. As an example, given a shared secret, any two KEM operations that result in this shared secret must also agree on the used public key. In our paper, this property is called X-K-PK, where X can be different threat models. If we now want to formally write down such a property, we have to refer to the public key of a KEM. However, the previous KEM.Decaps API does not allow us to do this because the public key does not appear in it =E2=80=93 = even though KEM.Decaps uses the public key internally. This is only possible because in the real-world the public key (or a hash of it) is usually stored inside of the secret key. To allow us to formally state properties which include the public key over KEM.Decaps, we thus added the public key to the KEM.Decaps API. We want to stress that this is only a syntactic change which we believe to be necessary to state our properties. First, we acknowledge that 'trivial attacks' was a poor word choice (originating in crypto literature tradition). The =E2=80=98trivial attacks= =E2=80=99 we =E2=80=98block=E2=80=99 are not actual attacks, but =E2=80=98degenerate=E2= =80=99 cases in our property definition that would lead to a property which is not achievable for any KEM. Any changes we made to the real-world API, and assumptions we placed on it were only made to formally write down our properties. We believe our API models real-world KEM usage and we will update the eprint with better wording. Additionally, our API changes alone do not 'block' any behavior. The behavior is 'blocked' by our assumption that the KEM.Decaps algorithm uses the explicitly supplied public key instead of extracting it from the secret key. This assumption is necessary; without it, our binding properties depend on a parameter that might never be used, resulting in a useless, unachievable property for any KEM. Dismissing X-BIND-PK, CT-K You correctly note that our dismissal X-BIND-PK, CT-K is not justified for implicitly rejecting KEMs in the context of MAL. This is an artifact of an earlier version, as pointed out to us previously by Dennis Jackson. Our next eprint update will fix this. Of course, ideally, our binding properties would be independent of the API choice. If we were to redesign the KEM API from scratch, we would probably neither use the academic definitions nor the current real-world APIs, all of which have their drawbacks. Also, if we were to redesign KEMs with what we know now, we would probably only recommend explicitly rejecting KEMs. Best regards, Niklas, Alex, and Cas On Mon, Jul 29, 2024 at 3:51=E2=80=AFPM Peter C wrote: > Deirdre, > > > > > > DHKEM is MAL-BIND-K-CT and MAL-BIND-K-PK secure as analyzed > > > > in the symbolic model=E2=80=9D and cite Cremers et al (https://ia.cr/= 2023/1933 > ). > > > > > This was an error from previous slide decks, those properties are > modelled > > > in Tamarin and tested with several protocols to see if attacks showed u= p > > > when the KEMs used in protocols such as Kyber-AKE have varying binding > > > properties. The eprint version seems to be weird (all the previous > versions > > > are 404'ing?) so I've attached the version I have in my archive as it > has lots > > > more material, case studies, and short proofs for different KEMs about > their > > > binding properties (as written, vs as in practice, but still) > > > > Thanks for the clarification and a copy of the earlier version. > > > > > > As specified in RFC 9180, DHKEM is not MAL-BIND-K-PK secure because > > > > DHKEM.Decaps recomputes the public key from the private key. To > achieve > > > > MAL-BIND-K-PK, I think the public key needs to be provided as input t= o > > > > DHKEM.Decaps and used in the KDF instead of the recomputed > > > > > Fair enough. Either way, we get much stronger BIND properties from the > > > default HPKE construction DH-KEM than swapping DH-KEM out for say > > > Classic McEliece, which is IND-CCA secure but gets us zero binding to t= he > > > PK, not even HON, and which earlier drafts of HPKE would have protected > > > against, but no longer does. > > > > Classic McEliece is not HON-BIND-CT-K or HON-BIND-CT-PK since it is > > implicitly rejecting. It is not HON -BIND-K-PK or HON -BIND-K, CT-PK by > > Grubbs et al (https://ia.cr/2021/708). For one of the parameter sets, it > is > > not even HON-BIND-K-CT or HON-BIND-K, PK-CT if the implementation > > does not check the ciphertext padding bits (see =E2=80=9CIND-CCA2 for enc= odings=E2=80=9D > in https://classic.mceliece.org/mceliece-rationale-20221023.pdf). > > > > > Relatedly, depending on how thing like Kyber/ML-KEM are implemented and > > > used in practice, we may rarely get MAL-BIND security in practice if th= e > encaps > > > keys are only partially used in the interior KDF, or other shenanigans > (see the > > > 'Kemmy Schmidt' note for more fun: https://eprint.iacr.org/2024/523.pdf= ). > We > > may cover ourselves by including everything in the higher protocol key > schedule > > anyway (like TLS 1.3) but in HPKE we don't do that. LEAK-BIND may be > sufficient > > and achievable in practice for general KEM usages but since HPKE is > supposed > > to be a pretty bulletproof building block (and basically is for DH-KEM) > it would be > > > even nicer to change HPKE to be as bulletproof for other KEM cipher > suites, or > > > whatever action actually results in users getting security in > deployments without > > having to do this bespoke analyst themselves every time. > > > > Again, I think any MAL-BIND-P-Q claims need to be interpreted very > carefully as > > they can work in a very different way to their HON- or LEAK- > counterparts. For > > example, Cremers et al dismiss X-BIND-PK, CT-K on the basis that =E2=80= =9Cif > Decaps is > > deterministic, this is trivally true=E2=80=9D, but that only holds for HO= N- and > LEAK-. An > > implicitly rejecting KEM will not be MAL-BIND-PK, CT-K if malformed publi= c > keys > > can be used to cause decapsulation failures. > > > > Peter > > > > > > _______________________________________________ > CFRG mailing list -- cfrg@irtf.org > To unsubscribe send an email to cfrg-leave@irtf.org > --0000000000002e56f2061e643675 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Peter,

while you directed the email to Deirdre, = we think it may be a good point to chime in here as the original authors of= https://eprint.iacr.org/2023= /1933:

TL;DR: Yes, DH-KEM is probably not MAL secure. This is no= t because of an API mismatch but because it does not explicitly check for w= ell-formed key material. Our API models real-world KEM usage. The =E2=80=98= trivial attacks=E2=80=99 we =E2=80=98block=E2=80=99 in our paper are degene= rate cases in our properties, we will update the wording.

Let us fir= st address some points, before going to the API.
1. Deirdre's Slides= : Checking Deirdre's backup slides, there seem to be some relics from e= arlier talks. We no longer conjecture MAL properties but provide a proof fo= r LEAK in the ROM (for DH-KEM and other KEMs).
2. Previous Paper Version= s: We've checked, and the previous versions of the paper are available = to us on IACR as expected: https://eprint.iacr.org/archive/versions/2023/1933
MAL-Binding and API Choices
We agree that MAL claims need careful inte= rpretation. As mentioned, we no longer conjecture these properties for any = KEM implementation. This change is not due to our API choice differing from= the real-world API, but because these properties can only be achieved if t= he KEM implementation verifies the well-formedness of the supplied key mate= rial. For example, a KEM implementation might check whether the hash of the= public key stored inside the secret key is correct. Without these checks, = a MAL adversary could alter the stored hash to break binding. More details = can be found in Section 3 of [this paper](https://eprint.iacr.org/2024/523.pdf).

Next, we = will elaborate on our API choices, why they differ from the real-world API,= and why we believe this is necessary.

Let=E2=80=99s recall the intu= ition behind our binding properties:
Given a shared secret, a public key= , or a ciphertext, two KEM operations which use (or result in) this value, = should with overwhelming probability also produce equal values for one (or = more) of the other parameters. Note, that we did not include the private ke= y here, as during a KEM exchange, only one of the parties knows the private= key.
As an example, given a shared secret, any two KEM operations that = result in this shared secret must also agree on the used public key. In our= paper, this property is called X-K-PK, where X can be different threat mod= els.

If we now want to formally write down such a property, we have = to refer to the public key of a KEM. However, the previous KEM.Decaps API d= oes not allow us to do this because the public key does not appear in it = =E2=80=93 even though KEM.Decaps uses the public key internally. This is on= ly possible because in the real-world the public key (or a hash of it) is u= sually stored inside of the secret key.
To allow us to formally state pr= operties which include the public key over KEM.Decaps, we thus added the pu= blic key to the KEM.Decaps API. We want to stress that this is only a synta= ctic change which we believe to be necessary to state our properties.
First, we acknowledge that 'trivial attacks' was a poor word choi= ce (originating in crypto literature tradition). The =E2=80=98trivial attac= ks=E2=80=99 we =E2=80=98block=E2=80=99 are not actual attacks, but =E2=80= =98degenerate=E2=80=99 cases in our property definition that would lead to = a property which is not achievable for any KEM. Any changes we made to the = real-world API, and assumptions we placed on it were only made to formally = write down our properties. We believe our API models real-world KEM usage a= nd we will update the eprint with better wording.
Additionally, our API = changes alone do not 'block' any behavior. The behavior is 'blo= cked' by our assumption that the KEM.Decaps algorithm uses the explicit= ly supplied public key instead of extracting it from the secret key. This a= ssumption is necessary; without it, our binding properties depend on a para= meter that might never be used, resulting in a useless, unachievable proper= ty for any KEM.

Dismissing X-BIND-PK, CT-K
You correctly note tha= t our dismissal X-BIND-PK, CT-K is not justified for implicitly rejecting K= EMs in the context of MAL. This is an artifact of an earlier version, as po= inted out to us previously by Dennis Jackson. Our next eprint update will f= ix this.

Of course, ideally, our binding properties would be indepen= dent of the API choice. If we were to redesign the KEM API from scratch, we= would probably neither use the academic definitions nor the current real-w= orld APIs, all of which have their drawbacks. Also, if we were to redesign = KEMs with what we know now, we would probably only recommend explicitly rej= ecting KEMs.

Best regards,

Niklas, Alex, and Cas


On Mon, Jul 29, 2024 at 3:51=E2=80=AFPM Peter C <Peter.C=3D40ncsc.gov.uk@dmarc.ietf.org> wr= ote:

Deirdre,

=C2=A0<= /span>

> >=C2=A0DHKEM = is MAL-BIND-K-CT and MAL-BIND-K-PK secure as analyzed<= /p>

> > in the symb= olic model=E2=80=9D and cite Cremers et al (https://ia.cr/= 2023/1933).

=C2=A0<= /span>

> This=C2=A0was an= error from previous slide decks, those properties are modelled

> in Tamarin and t= ested with several protocols to see if attacks showed up

> when the KEMs us= ed in protocols such as Kyber-AKE have varying binding=

> properties. The = eprint version seems to be weird (all the previous versions

> are 404'ing?= ) so I've attached the version I have in my archive as it has lots

> more material, c= ase studies, and short proofs for different KEMs about their<= /span>

> binding properti= es (as written, vs as in practice, but still)=C2=A0

=C2=A0<= /span>

Thanks for the clarif= ication and a copy of the earlier version.

=C2=A0<= /span>

> > As specifie= d in RFC 9180, DHKEM is not MAL-BIND-K-PK secure because

> > DHKEM.Decap= s recomputes the public key from the private key.=C2=A0 To achieve

> > MAL-BIND-K-= PK, I think the public key needs to be provided as input to

> > DHKEM.Decap= s and used in the KDF instead of the recomputed=C2=A0<= /p>

=C2=A0<= /span>

> Fair enough. Eit= her way, we get much stronger BIND properties from the=

> default HPKE con= struction DH-KEM than swapping DH-KEM out for say

> Classic McEliece= , which is IND-CCA secure but gets us zero binding to the

> PK, not even HON= , and which earlier drafts of HPKE would have protected

> against, but no = longer does.

=C2=A0<= /span>

Classic McEliece is n= ot HON-BIND-CT-K or HON-BIND-CT-PK since it is

implicitly rejecting.= =C2=A0 It is not HON -BIND-K-PK or HON -BIND-K, CT-PK by

Grubbs et al (https://ia.cr/2021/708).= =C2=A0 For one of the parameter sets, it is

not even HON-BIND-K-C= T or HON-BIND-K, PK-CT if the implementation

does not check the ci= phertext padding bits (see =E2=80=9CIND-CCA2 for encodings=E2=80=9D
in https://classic.mceliece.org/mceliece-rationale-20221023= .pdf).

=C2=A0<= /span>

> Relatedly, depen= ding on how thing like Kyber/ML-KEM are implemented and

> used in practice= , we may rarely get MAL-BIND security in practice if the encaps

> keys are only pa= rtially used in the interior KDF, or other shenanigans (see the

> 'Kemmy Schmi= dt' note for more fun:=C2=A0https://eprint.iacr.org/2024/523.pdf). We
> may cover ourselves by including everything in the higher protocol key= schedule
> anyway (like TLS 1.3) but in HPKE we don't do that. LEAK-BIND may = be sufficient
> and achievable in practice for general KEM usages but since HPKE is su= pposed
> to be a pretty bulletproof building block (and basically is for DH-KEM= ) it would be

> even nicer to ch= ange HPKE to be as bulletproof for other KEM cipher suites, or

> whatever action = actually results in users getting security in deployments without
> having to do this bespoke analyst themselves every time.=

=C2=A0<= /span>

Again, I think any MA= L-BIND-P-Q claims need to be interpreted very carefully as

they can work in a ve= ry different way to their HON- or LEAK- counterparts.=C2=A0 For

example, Cremers et a= l dismiss X-BIND-PK, CT-K on the basis that =E2=80=9Cif Decaps is=

deterministic, this i= s trivally true=E2=80=9D, but that only holds for HON- and LEAK-.=C2=A0 An<= u>

implicitly rejecting = KEM will not be MAL-BIND-PK, CT-K if malformed public keys

can be used to cause = decapsulation failures.

=C2=A0<= /span>

Peter

=C2=A0<= /span>

=C2=A0

_______________________________________________
CFRG mailing list -- cfr= g@irtf.org
To unsubscribe send an email to cfrg-leave@irtf.org
--0000000000002e56f2061e643675--