Felix, Thank you for your reply and sorry for taking so long to respond.
I do realise that you are not arguing via IND-CCA security. I was trying to use the hybrid KEM setting as (I thought) a simpler way of illustrating my point. Clearly that didn't work! Nevertheless, in your setting the presence of the PQ component still means that you need to adapt the PRF-ODH assumption and choose a way of simulating the handshake secret computation that avoids invalid queries to the adapted PRF-ODH oracle. Further, even if it is not phrased terms of IND-CCA security, it is still true that PRF-ODH by itself is not enough to guarantee that the handshake secrets will be indistinguishable from random if, for example, they can be directly observed by the adversary. (Of course, that's outside of the TLS security model.) Consequently, if you are not assuming anything about the security of the PQ KEM, then the indistinguishability of the traffic keys (not just their distinctness) must depend on the traffic key derivation including the ciphertext in the transcript. This feels to me like a significant change from the existing proof and while I believe it's probably true, I don't think it's obvious. Best, Peter > -----Original Message----- > From: Felix Günther <m...@felixguenther.info> > Sent: 05 September 2024 09:25 > To: Peter C <pete...@ncsc.gov.uk> > Cc: Marc Fischlin <marc.fisch...@tu-darmstadt.de>; TLS List <tls@ietf.org> > Subject: [TLS] Re: [TLS]Re: I-D Action: draft-ietf-tls-hybrid-design-10.txt > > Hi Peter, > > I think there's a misunderstanding. My response to your original > question on what assumption one needs to make on the PQ KEM to be able > to reuse the argument in [DOWLING] was "none", in the following sense: > If you're _only_ after the classic security shown in [DOWLING], then > there's no additional assumption needed. That is, I think the [DOWLING] > result can be adapted to hold, assuming the DH component is strong. > > Note that this argument is _not_ via IND-CCA security of some combiner > KEM, but following the current proof. That is, relying directly on > PRF-ODH and then key derivation (which includes the transcript, and > hence also the possibly modified PQ KEM ciphertext), ensuring separated > keys. > > > It seems you understood my response as "the [DOWLING] results hold with > a combiner KEM". That's indeed _not_ the case, in particular because > this result doesn't use a KEM/IND-CCA type assumption, so one can't hope > to just plug in such assumption for the result to still go through. > > And I agree with your assessment, that a K = KDF(ss_pq || ss_ec) KEM > combiner step would itself not achieve IND-CCA security. As you write, > one could modify the PQ ciphertext without changing ss_pq, violating > that property. (This is in line with [GIACON] including the ciphertexts > in the key derivation.) Even then, the raw ss_ec is not an IND-CCA KEM > secret. So showing results based on KEM assumptions here requires > working out more analysis details. > > I hope this clarifies things a little? > > Best, > Felix > > On 2024-08-20 13:02 +0200, Peter C <pete...@ncsc.gov.uk> wrote: > > Felix, > > > > I definitely don't understand something here, so I have tried to abstract > > things slightly to try to illustrate why I think there might still be an > > issue. > > I'm reasonably (but not completely) confident that I haven't abstracted > > away anything significant. Apologies if I've missed something important. > > > > Consider the PQ/ECDH hybrid KEM where the KEM combiner is > > K = KDF(ss_pq || ss_ec). I think you are essentially arguing that an > > adversary A that breaks the IND-CCA2 security of the hybrid KEM can > > be converted into an adversary B that breaks something like PRF-ODH > > security for the ECDH component. > > > > IND-CCA2 is the usual notion. PRF-ODH might need a little explanation > > in this case. I think it needs to be along the following lines: > > > > - The adversary selects ss*_pq for the challenger. > > > > - The challenger chooses an ECDH key pair (sk*_ec, pk*_ec) and > > "ciphertext" ct*_ec, and computes K*_0 = KDF(ss*_pq || ss*_ec) with > > the corresponding ECDH shared secret ss*_ec. The challenger also > > chooses a random K*_1 and sets K* = K_b for a random bit b. > > > > - The adversary is given the public key pk*_ec, ciphertext ct*_ec, and > > key K*, and can query an oracle with (ss_pq, ct_ec) =/= (ss*_pq, > > ct*_ec) > > to get K = KDF(ss_pq || ss_ec). > > > > I agree that adversary B can embed a PRF-ODH challenge into an IND-CCA2 > > challenge for adversary A. B chooses a PQ key pair (sk*_pq, pk*_pq) and > > ciphertext ct*_pq, computes the PQ shared secret ss*_pq and uses ss*_pq > > to request pk*_ec, ct*_ec and K* from the PRF-ODH challenger. The > > corresponding IND-CCA2 challenge will be the public key (pk*_pq, pk*_ec), > > ciphertext (ct*_pq, ct*_ec) and key K*. > > > > I also agree that B can simulate (to some extent) the decapsulation oracle. > > Given a query (ct_pq, ct_ec) =/= (ct*_pq, ct*_ec) from A, B uses sk*_pq to > > compute the PQ shared secret ss_pq, queries the PRF-ODH oracle with > > (ss_pq, ct_ec) and returns the response to A. In the case of a query > > (ct_pq, ct*_ec) where ct_pq =/= ct*_pq but ss_pq = ss*_pq, B can indeed > > identify this and adjust, say, by returning the challenge key K*. > > > > I think the issue is that by handling invalid PRF-ODH queries in this way, > > adversary B may not be able to use adversary A to break PRF-ODH. If the > > PQ KEM is appropriately weak, then a perfectly reasonable approach to > > breaking IND-CCA2 for the hybrid KEM is to find a second PQ ciphertext > > ct_pq =/= ct*_pq that encapsulates the same PQ shared secret ss*_pq > > and query the decapsulation oracle with (ct_pq, ct*_ec) to see if it returns > > the challenge key K* or not. In the simulation above, it will always return > > K* and so A will always conclude that it is the real key, regardless of the > > PRF-ODH challenger's choice of b. > > > > The difference between this and X25519 equivalent public keys is that > > it is easy to identify the equivalent public keys so both the PRF-ODH and > > IND-CCA2 games can be adjusted to exclude their use in oracle queries. > > This is essentially the same as requiring public key validation. I don't > > believe it's possible to modify the IND-CCA2 game to block equivalent > > PQ ciphertexts in the same way and even if you could I think it would be > > a significant deviation from the usual security notion. > > > > Sorry for all the details. Hopefully, it's clear enough! > > > > Best, > > > > Peter > > > > > >> -----Original Message----- > >> From: Felix Günther <m...@felixguenther.info> > >> Sent: Tuesday, August 13, 2024 10:51 AM > >> To: Peter C <pete...@ncsc.gov.uk>; Marc Fischlin <marc.fischlin@tu- > >> darmstadt.de> > >> Cc: tls@ietf.org > >> Subject: Re: [TLS]Re: I-D Action: draft-ietf-tls-hybrid-design-10.txt > >> > >> Hi Peter, > >> > >> For a broken PQ KEM it could indeed be easy to have distinct ciphertexts > >> decapsulate to the same shared secret. I don't think this affects the > >> (EC)DH result holding up though, from how the proof would go in my > head. > >> > >> In the PRF-ODH/random oracle step of deriving HS from DHE and ss, the > >> reduction embeds a DH challenge in DHE. It needs to check for DH shares > >> trivially colliding with the DH challenge (unknown to the reduction), > >> which it can do. For the shared secret input ss, it would perform KEM > >> key generation and encapsulation itself (as there's no challenge to > >> embed here), so it can compute ss itself. > >> Put differently: the reduction would indeed have access to the KEM > >> private key, and hence can detect same shared secrets. > >> > >> Best, > >> Felix > >> > >> On 2024-08-12 14:03 +0200, Peter C <pete...@ncsc.gov.uk> wrote: > >>> Felix, > >>> > >>> I'm not completely sure I understand what you are suggesting, > >>> but I think it might not be quite as straightforward as that. > >>> > >>> In general, if the PQ KEM is not secure then the HS can fail to be > >>> indistinguishable from random: fixing the ECDH components of > >>> the hybrid key shares and choosing distinct PQ KEM component > >>> ciphertexts that encapsulate the same PQ shared secret will give the > >>> same HS. As an example, consider ML-KEM where the re-encryption > >>> check is skipped and malformed ciphertexts are never (implicitly) > >>> rejected. In that case, it is trivial to modify ciphertexts without > >>> changing the encapsulated shared secret, but I suspect it would be > >>> hard to reliably detect equivalent ciphertexts without having access > >>> to the ML-KEM private key. > >>> > >>> My guess is that this can be avoided if you assume that the PQ KEM > >>> satisfies something along the lines of ciphertext second preimage > >>> resistance from the X-Wing paper > >> > (https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fia.cr%25 > 25 > >> > 2F2024%2F039&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7Cb7ce7a0ed243 > >> > 413e0cd008dcbb7d77c7%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C > >> > 0%7C638591394753320161%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wL > >> > jAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C% > >> > 7C&sdata=1UMZm9CTSN8uN%2BZGGYk15U3WPiXpz26qBJ50jv48Eko%3D&res > >> erved=0). It is also > >>> entirely possible that I'm missing something obvious and a different > >>> part of the proof rules this out. > >>> > >>> Best, > >>> > >>> Peter > >>> > >>>> -----Original Message----- > >>>> From: Felix Günther <m...@felixguenther.info> > >>>> Sent: Friday, August 2, 2024 2:05 PM > >>>> To: Peter C <pete...@ncsc.gov.uk>; Marc Fischlin <marc.fischlin@tu- > >>>> darmstadt.de> > >>>> Cc: tls@ietf.org > >>>> Subject: Re: [TLS]Re: I-D Action: draft-ietf-tls-hybrid-design-10.txt > >>>> > >>>> [You don't often get email from m...@felixguenther.info. Learn why this > is > >>>> important at https://aka.ms/LearnAboutSenderIdentification ] > >>>> > >>>> Hi Peter, > >>>> > >>>> If your question is about what assumption the PQ KEM you still need to > >>>> make in case it's not IND-CCA secure anymore and you want to fall back > >>>> to [DOWLING] for the (EC)DH result, I think the answer is: none. > >>>> (Beyond ensuring unambiguous encoding of KDF inputs, as the draft > >>>> mandates through fixed-length shared secrets etc.) > >>>> > >>>> You would then be treating HKDF.Extract as a random oracle (which for > >>>> PRF-ODH security is the take-away from [ > >>>> > >> > https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fia.cr%252 > 52 > >> 52 > >>>> > >> > F2017%2F517&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7C56886bf3e45f4c > >>>> > >> > 711da808dcb2f3c83a%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C0% > >>>> > >> > 7C638582007420625450%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjA > >>>> > >> > wMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C60000%7C%7 > >>>> > >> > C%7C&sdata=%2BRlEU5oghUgBNo4lKyP5qIjVaARVHCq69n2P%2B50ZDMo%3 > >>>> D&reserved=0 ]), > >>>> where the IKM input is augmented with the (possibly > >>>> adversary-controlled) KEM shared secret. But the encoding would > ensure > >>>> that the argument wrt. ECDH would still apply. > >>>> > >>>> Cheers, > >>>> Felix > >>>> > >>>> > >>>> PS: Sorry for the prior double posting; we were under the impression > >>>> that Marc's first email didn't get delivered to the list. > >>>> > >>>> On 2024-08-01 11:38 +0200, Peter C <pete...@ncsc.gov.uk> wrote: > >>>>> Marc and Felix, > >>>>> > >>>>> Thank you both for your replies. > >>>>> > >>>>> I can see how this will work for NIST P-256 and X25519 - it is > >>>>> straightforward to detect the equivalent public and adjust the > >>>>> output of the simulator accordingly - and I also agree that it is > >>>>> not a significant change to the PRF-ODH assumption. > >>>>> > >>>>> Have you thought how this transfers across to the hybrid key > >>>>> exchange in draft-ietf-tls-hybrid-design? Do you know what > >>>>> assumption, if any, you need to make on the PQ KEM to be > >>>>> able to reuse the argument in [DOWLING]? > >>>>> > >>>>> Thanks, > >>>>> > >>>>> Peter > >>>>> > >>>>>> -----Original Message----- > >>>>>> From: Marc Fischlin <marc.fisch...@tu-darmstadt.de> > >>>>>> Sent: Monday, July 29, 2024 4:40 PM > >>>>>> To: tls@ietf.org > >>>>>> Subject: [TLS]Re: I-D Action: draft-ietf-tls-hybrid-design-10.txt > >>>>>> > >>>>>> [You don't often get email from marc.fisch...@tu-darmstadt.de. Learn > >> why > >>>>>> this is important at https://aka.ms/LearnAboutSenderIdentification ] > >>>>>> > >>>>>> Dear all, > >>>>>> > >>>>>> Douglas and the other "TLS co-authors" discussed this briefly, but I > >>>>>> think that Douglas is offline for the next couple of days and asked me > >>>>>> if I could answer on behalf of the authors. > >>>>>> > >>>>>> It is indeed true that the PRF-ODH assumption, as stated, wouldn't be > >>>>>> comaptible with the usage of the x-coordinate. One needs to be a > little > >>>>>> bit more careful in this case, disallowing the adversary to flip signs > >>>>>> of curve points. This has been done for example in a paper about the > >>>>>> security of Bluetooth which I co-authored, where the x-coordinate is > >>>>>> also used to derive keys. There we adapted the definition accordingly > >>>>>> (Section 4.1 in > >>>> > >> > https://eprint.i/ > %2F&data=05%7C02%7Cpeter.c%40ncsc.gov.uk%7C10f67053bc814e8eeb5908 > dccd846b09%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C0%7C638611 > 215811934623%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJ > QIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata= > WL0SOmM3s1aM%2BvLANg8ZzZqS%2Fx%2FAkF2FC1D4%2Fr0U9y0%3D&rese > rved=0 > >> > %2F&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7Cb7ce7a0ed243413e0cd00 > >> > 8dcbb7d77c7%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C0%7C63859 > >> > 1394753339561%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLC > >> > JQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=r > >> IjaJxk4fNPxrvrW8%2FqEu15ej2G518Nve6iaNCiywhs%3D&reserved=0 > >>>> > >> > acr.org%2F2021%2F1597.pdf&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7C5 > >>>> > >> > 6886bf3e45f4c711da808dcb2f3c83a%7C14aa5744ece1474ea2d734f46dda64a > >>>> > >> > 1%7C0%7C0%7C638582007420635222%7CUnknown%7CTWFpbGZsb3d8eyJ > >>>> > >> > WIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7 > >>>> > >> > C60000%7C%7C%7C&sdata=JMYMT3Tf5UyBBAFiV9fIQB3KKfMbmtBlubkPItW > >>>> YTZY%3D&reserved=0 of this Asiacrypt > >>>>>> 2021 paper). I don't think that this makes the assumption less > >>>>>> plausible, only more annoying to deal with in the proofs. > >>>>>> > >>>>>> We have also checked that with the modifcation above the TLS proofs > >> goes > >>>>>> through as before, one only needs to repeat the extracted key in > >>>>>> executions which have the same x-coordinate (instead of the same > DH > >>>>>> values as so far). > >>>>>> > >>>>>> Hope this helps to clarify. Let me know if you need more details. > >>>>>> > >>>>>> Marc Fischlin > >>>>>> > >>>>>> _______________________________________________ > >>>>>> TLS mailing list -- tls@ietf.org > >>>>>> To unsubscribe send an email to tls-le...@ietf.org > > _______________________________________________ > TLS mailing list -- tls@ietf.org > To unsubscribe send an email to tls-le...@ietf.org _______________________________________________ TLS mailing list -- tls@ietf.org To unsubscribe send an email to tls-le...@ietf.org
