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

[Douglas Stebila <[e-mail]>]

Hi Peter,

I agree that if you assume that the PQ KEM is broken, then [GIACON] and [BINDEL] don't apply since ECDH-as-a-KEM is not IND-CCA2 secure.  I don't fully follow your argument on why it's not possible to fall back on [DOWLING] -- in other words, just resort back to the original security proof of ECDH in TLS 1.3.  

I did see your subsequent email about the tweaking that one can do for NIST P-256 and X25519 due to compressed formats leading to mathematically equivalent points.  If it was the case that this tweakability resulted in hybrid key exchange having a problem (either a security problem or just a proof problem) when the PQ KEM is broken, then I think that would also imply that this tweakability leads to a problem in plain old ECDH key exchange in TLS 1.3.  In other words, I think your argument implies that the [DOWLING] proof doesn't apply to TLS 1.3 ECDH key exchange because the point encodings used for X25519 and NIST P-256 don't satisfy dual-snPRF-ODH.  Which may be true, but it would imply a bigger scope of concerns than just hybrid key exchange.

Now, it is the case that the HKDF.Expand portions of the key schedule include the transcript hash and thus the ECDH public keys, so any of these tweaks would, at the HKDF.Expand point, lead to different hash values.  This suggests to me that if one needed to adapt the proof, I'd start by treating HKDF.Extract and HKDF.Expand as a single monolithic operation involving the shared secrets and the transcripts.  In the random oracle model, this results in hashing everything in, which I guess would provide enough rigidity to prevent any such attacks, similar to the argument in X-Wing.

So if I am correctly interpreting your argument about point formats leading to a proof doubt, I think the path forward would be to revisit the original [DOWLING] proof in light of groups that don't satisfy dual-snPRF-ODH due to tweakability of point formats, possibly addressing this by treating HKDF.Extract and HKDF.Expand monolithically, and try to cover both the original ECDH and the hybrid questions at the same time.

Douglas


> On Jul 24, 2024, at 09:39, Peter C <[e-mail]> wrote:
> 
> Douglas,
> 
> The agenda for the TLS session is looking packed, and this is a very in-the-weeds comment, so I hope you don't mind me posting it to the list.  Happy to take any discussion off-list, if you'd prefer.
> 
> The draft-ietf-tls-hybrid-design security considerations currently say:
> 
>    The shared secrets computed in the hybrid key exchange should be
>    computed in a way that achieves the "hybrid" property: the resulting
>    secret is secure as long as at least one of the component key
>    exchange algorithms is unbroken. See [GIACON] and [BINDEL] for an
>    investigation of these issues.
> 
> If you assume the PQ KEM is IND-CCA2 secure, then I agree that [GIACON] and [BINDEL] imply that the derived traffic secrets will be indistinguishable from random and from each other.  The same is true if the KEM is only OW-CCA2 secure by Petcher-Campagna (https://ia.cr/2023/972)
> 
> If you assume the PQ KEM is broken, however, then [GIACON] and [BINDEL] do not apply since ECDH-as-a-KEM is not IND-CCA2 secure.  Similarly, Petcher-Campagna does not apply because ECDH is not OW-CCA2 secure.  Nor do I think it's possible to fall back on [DOWLING] since X25519 and NIST P-256 (as they are used in RFC 8446) do not satisfy the dual-snPRF-ODH assumption for any choice of KDF.  In this case, I don't believe the derived traffic secrets are guaranteed to be indistinguishable from random.
> 
> Flo raised similar points a couple of years ago which I don't think were fully addressed at the time.  I suspect this is just a security proof issue - the inclusion of the ciphertexts in the transcript hash should still protect against any actual attacks - and it's entirely possible that I've missed more recent results covering all of this.  If not, one easy solution might be to adopt the X-Wing approach and use
> 
>    concatenated_ss = pqkem_ss || ecdh_ss || ecdh_ct || ecdh_pk,
> 
> although this currently only works with ML-KEM.
> 
> Best,
> 
> Peter
> 
> 
>> -----Original Message-----
>> From: TLS <[e-mail]> On Behalf Of [e-mail]
>> Sent: Friday, April 5, 2024 9:24 PM
>> To: [e-mail]
>> Cc: [e-mail]
>> Subject: [TLS] I-D Action: draft-ietf-tls-hybrid-design-10.txt
>> 
>> Internet-Draft draft-ietf-tls-hybrid-design-10.txt is now available. It is a
>> work item of the Transport Layer Security (TLS) WG of the IETF.
>> 
>>   Title:   Hybrid key exchange in TLS 1.3
>>   Authors: Douglas Stebila
>>            Scott Fluhrer
>>            Shay Gueron
>>   Name:    draft-ietf-tls-hybrid-design-10.txt
>>   Pages:   24
>>   Dates:   2024-04-05
>> 
>> Abstract:
>> 
>>   Hybrid key exchange refers to using multiple key exchange algorithms
>>   simultaneously and combining the result with the goal of providing
>>   security even if all but one of the component algorithms is broken.
>>   It is motivated by transition to post-quantum cryptography.  This
>>   document provides a construction for hybrid key exchange in the
>>   Transport Layer Security (TLS) protocol version 1.3.
>> 
>>   Discussion of this work is encouraged to happen on the TLS IETF
>>   mailing list [e-mail] or on the GitHub repository which contains
>>   the draft:
>> https://github/.
>> com%2Fdstebila%2Fdraft-ietf-tls-hybrid-
>> design&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7Cec161933c97947c8a7e0
>> 08dc55ae8cd7%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C0%7C6384
>> 79455373796379%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiL
>> CJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata
>> =qNBE50aYk4woYCLUj6Rq1wMeFur63hP1MnHXDGihg80%3D&reserved=0.
>> 
>> The IETF datatracker status page for this Internet-Draft is:
>> https://datatra/
>> cker.ietf.org%2Fdoc%2Fdraft-ietf-tls-hybrid-
>> design%2F&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7Cec161933c97947c8
>> a7e008dc55ae8cd7%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C0%7C
>> 638479455373796379%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwM
>> DAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&s
>> data=kVBR6kDc19NDTnC1fRgVqJmTnZOQggzmWk7wHHcVKbI%3D&reserved=
>> 0
>> 
>> There is also an HTML version available at:
>> https://www.ie/
>> tf.org%2Farchive%2Fid%2Fdraft-ietf-tls-hybrid-design-
>> 10.html&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7Cec161933c97947c8a7e
>> 008dc55ae8cd7%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C0%7C638
>> 479455373796379%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAi
>> LCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdat
>> a=dcjY38cicBXU6ab7hnMalN1WTWqtQdhblMYu7xdzVT8%3D&reserved=0
>> 
>> A diff from the previous version is available at:
>> https://author/
>> -tools.ietf.org%2Fiddiff%3Furl2%3Ddraft-ietf-tls-hybrid-design-
>> 10&data=05%7C02%7CPeter.C%40ncsc.gov.uk%7Cec161933c97947c8a7e008d
>> c55ae8cd7%7C14aa5744ece1474ea2d734f46dda64a1%7C0%7C0%7C6384794
>> 55373952646%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQ
>> IjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=3ll
>> ZNYcqaixqUpU%2BhzzNOigFmuDlrA6CxCrIvyiG5HI%3D&reserved=0
>> 
>> Internet-Drafts are also available by rsync at:
>> rsync.ietf.org::internet-drafts
>> 
>> 
>> _______________________________________________
>> TLS mailing list
>> [e-mail]
>> https://www.ie/
>> tf.org%2Fmailman%2Flistinfo%2Ftls&data=05%7C02%7CPeter.C%40ncsc.gov.u
>> k%7Cec161933c97947c8a7e008dc55ae8cd7%7C14aa5744ece1474ea2d734f46
>> dda64a1%7C0%7C0%7C638479455373952646%7CUnknown%7CTWFpbGZsb3
>> d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%
>> 3D%7C0%7C%7C%7C&sdata=rFzF%2BExBIX03adggpWV4uxzcgfHR6Z0zCLamc
>> GZIX9o%3D&reserved=0