[TLS]Re: I-D Action: draft-ietf-tls-hybrid-design-10.txt

[Peter C <[e-mail]>]

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 <[e-mail]>
> Sent: Tuesday, August 13, 2024 10:51 AM
> To: Peter C <[e-mail]>; Marc Fischlin <marc.fischlin@tu-
> darmstadt.de>
> Cc: [e-mail]
> 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 <[e-mail]> 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
> 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 <[e-mail]>
> >> Sent: Friday, August 2, 2024 2:05 PM
> >> To: Peter C <[e-mail]>; Marc Fischlin <marc.fischlin@tu-
> >> darmstadt.de>
> >> Cc: [e-mail]
> >> Subject: Re: [TLS]Re: I-D Action: draft-ietf-tls-hybrid-design-10.txt
> >>
> >> [You don't often get email from [e-mail]. 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
> >>
> 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 <[e-mail]> 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 <[e-mail]>
> >>>> Sent: Monday, July 29, 2024 4:40 PM
> >>>> To: [e-mail]
> >>>> Subject: [TLS]Re: I-D Action: draft-ietf-tls-hybrid-design-10.txt
> >>>>
> >>>> [You don't often get email from [e-mail]. 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%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 -- [e-mail]
> >>>> To unsubscribe send an email to [e-mail]