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://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 <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
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/
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
