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