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

[Felix Günther <[e-mail]>]

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 <[e-mail]> 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 <[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]