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

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

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://ia.cr/2024/039)  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
>> 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/
>> 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]