[TLS] A Cryptographic Analysis of the TLS 1.3 Handshake Protocol Candidates

[Felix Günther]

Dear all,

In a recent work, we analyzed the ephemeral Diffie--Hellman-based
handshake protocol in two drafts of TLS 1.3 which were available at the
time of our research project in May: draft-ietf-tls-tls13-05 as well as
the variant proposal draft-ietf-tls-tls13-dh-based
(https://github.com/ekr/tls13-spec/blob/ietf92_materials/draft-ietf-tls-tls13-dh-based.txt).
 At this point in time, these have been integrated into the latest draft
08.

Our research paper will be published at the ACM Conference on Computer
and Communications Security (CCS 2015) in October; a full version is now
available in the IACR Cryptology ePrint Archive
(https://eprint.iacr.org/2015/914). We show that, for both drafts, the
full and resumption handshakes achieve the main goal of providing secure
authenticated key exchange in a "multi-stage" setting using a game-based
approach toward provable security (in the style of Bellare and Rogaway).

On a high level, this means that the handshakes establish record layer
keys, resumption keys, and exporter keys that look random to an
adversary. This holds with sessions that run concurrently and if the
adversary controls the whole network, is able to corrupt the long-term
secret keys of other parties, and allowed to reveal keys established in
other sessions, thus providing quite strong security guarantees for
practice. Moreover, we show that even leakage of record layer or
exporter keys in the same handshake session do not compromise each
other's security.
Our results hold based on standard cryptographic assumptions, namely
collision resistance of hash functions, unforgeability of signatures,
pseudorandomness of the key derivation function, and the Decisional
Diffie--Hellman assumption, and without resorting to an idealized model
such as the random oracle model.

Before sharing some technical insights and comments arising from our
work, let us shortly state precisely the scope of our work:
 * TLS 1.3 of course is still a work in progress, hence our analysis is
inevitably limited to the draft specifications at the time of writing
and should hence be considered as a contribution to the ongoing
discussion rather than a definitive analysis of TLS 1.3.
 * Our work focuses on the full and resumption handshakes, but does not
capture 0-RTT handshakes which were still un(der)specified at the time
of writing.
 * We do not analyze the record layer protocol (which is outside of the
scope of this work, and has been worked on by others), but rather follow
a compositional approach by showing that the full handshake securely
composes with any symmetric-key protocol. Extending this result to
encompass also the (non-forward-secret) resumption handshake is left for
future work due to a technicality in the compositional framework that
depends on forward secrecy.

Our main comments can be summarized as follows (see Section 3 of our
paper for a more detailed version):

 1. Soundness of key separation
Using separate keys for the encryption of handshake messages and
application data (compared with previous versions of TLS that encrypted
the Finished messages using the session key) allows the protocol to
achieve standard key secrecy/indistinguishability notions using standard
cryptographic assumptions (i.e., DDH rather than PRF-ODH).

 2. Key independence
The key schedule which derives each output key (in particular the
two traffic keys) through an application of the key derivation function
with a unique label/info input allows us to prove that these keys are
computationally independent: neither is affected by the other's
compromise. This in particular contributes to the compositional approach
of treating the (security of the) handshake and record layer separately.

 3. Session hash in online signatures
Including the full transcript/session hash in the CertificateVerify
signature makes the security proof easier and contributes to
establishing security based on standard assumptions.

 4. Encryption of handshake messages
The handshake traffic key is secure against passive adversaries and
hence encryption within the handshake can indeed increase privacy. We
confirm that this approach does not have negative effects on the main
key secrecy/indistinguishability goal of the key exchange.


While our paper addresses older drafts (draft-05 and draft-dh), we
expect that our analysis of the full handshake in draft-dh can be
adapted to cover the full handshake in the latest draft-08 version. As
the handshake stabilizes, we hope to update our work. At this point in
time, we hope that our analysis can provide some cryptographic insights
for the so-far achieved and further development of TLS 1.3.

We welcome your comments and suggestions.

Benjamin Dowling, Marc Fischlin, Felix Günther, and Douglas Stebila
(Queensland University of Technology and Technische Universität Darmstadt)

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Choice of Additional Data Computation

[Felix Günther]

Hi,

Sorry for chiming in with delay (thanks @Chris for pinging me); I'm not
following the list very closely, feel free to additionally CC me in case.


First of all, let me make sure I correctly understand that
 * "on-the-wire header" is what's exemplified in Fig. 4 of the draft
 * "pseudo-header" would be a superset, esp. including full epoch, full
sequence number, length, connection ID, ... -- what else?

Further, I understand there is _no_ unique mapping from pseudo-header to
on-the-wire header (as the latter may be compressed in different ways).

The latter, to me, suggests that authenticating the pseudo-header alone
may not be sufficient. It would at least allow on-path modifications to
the on-the-wire header, which I don't expect is intended.


As for the current authentication of the on-the-wire header: We [1] did
an analysis of the record layer of DTLS 1.3 (and QUIC) in which
 + we establish confidentiality, integrity and robustness ("correct
operation under adversarial manipulation")
 + of the record layer deprotecting packets with encoded/abbreviated
sequence numbers to payload fragments
 + under an adversary that can arbitrarily tamper with the packets (in
particular truncate ciphertext, i.e., modify lengths)
 + based on standard AEAD security.

However, our work did not consider
 - epochs or key updates (analysis under one key only)
 - the full header (only model encoded sequence number entering the AAD)
[- processing of payload fragments into the actual multiplexed data
streams (as in the TLS-related models Chris mentioned [2,3]; this only
applies to QUIC's application interface, and arguably is beyond the
cryptographic operations).]


Our analysis supports the arguments that:

 1) The length is implicitly authenticated through the ciphertext itself
-- tampering with the ciphertext, in particular its length, will make
AEAD decryption fail.

 2) The full sequence number is implicitly authenticated through the
nonce -- decoding the wrong sequence number will (offset by the IV)
yield a different nonce, leading AEAD decryption to fail.


As said, we didn't consider connection IDs or epochs, but for both I'm wary:

 3) Implicit connection IDs clearly aren't authenticated. I'm not sure I
fully understood the concept, but this sounds like a bad idea.

 4) I slightly disagree with "epochs determine the key" (true) as, what
I understand is, an argument that "the full epoch is implicitly
authenticated by using the right key", at least in its absoluteness. My
*guess* would be that, due to the key schedule, this argument comes down
to the probability of keys colliding (which is anyway to be avoided, so
probably fine). Still, from a security analysis point of view, showing
security with key updates might be easier if the (full) epoch was
authenticated as part of the AAD.


So, overall I guess my tendency would be to authenticate both what's on
the wire and the reconstructed context. At least from a crypto
perspective, this would be the safest bet. But again, this is
extrapolating beyond what our analyses cover, hence just my two cents.

Best,
Felix


[1] Marc Fischlin, Felix Günther, Christian Janson. Robust Channels:
Handling Unreliable Networks in the Record Layers of QUIC and DTLS.
Preprint for QUIPS 2020 Workshop at https://felixguenther.info/Q20_RC.pdf

[2] Marc Fischlin, Felix Günther, Giorgia Azzurra Marson, Kenneth G.
Paterson. Data Is a Stream: Security of Stream-Based Channels.
https://eprint.iacr.org/2017/1191

[3] Christopher Patton, Thomas Shrimpton. Partially Specified Channels:
The TLS 1.3 Record Layer without Elision. https://eprint.iacr.org/2018/634


On 2020-04-27 02:13 +0200, Martin Thomson  wrote:
> A few of the submissions to QUIPS addressed this question for QUIC (which has 
> a similar construction to DTLS) and concluded that this was broadly OK.  What 
> changes is the degree to which we rely on the strength of the AEAD for 
> prevention of spoofing.
> 
> (I'm sorry, but I can't find the paper that was most directly applicable, 
> perhaps Felix can help out.  https://eprint.iacr.org/2020/114.pdf does a 
> pretty good job, though it is a broader treatment.)



signature.asc
Description: OpenPGP digital signature
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Choice of Additional Data Computation

[Felix Günther]

Hi,

On 2020-05-15 22:04 +0200, Eric Rescorla  wrote:
> Actually, the full epoch is included in the overall sequence number and
> hence used to generate the nonce.
> 
> https://tools.ietf.org/html/draft-ietf-tls-dtls13-37#section-4
> 
> Does that help?

Sorry, I forgot about reading this difference in how the record sequence
number is constructed in DTLS (vs. TLS, and also QUIC). Yes, this should
effectively separate the nonce spaces between the different epochs /
epoch keys, and implicitly authenticate the epoch through the nonce.

Cheers,
Felix

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Choice of Additional Data Computation

[Felix Günther]

Hi,

On 2020-05-06 08:00 +0200, Hanno Becker  wrote:
>> The latter, to me, suggests that authenticating the pseudo-header alone
>> may not be sufficient. It would at least allow on-path modifications to
>> the on-the-wire header, which I don't expect is intended.
> 
> Can we go a bit into this? As mentioned in the original thread
> https://mailarchive.ietf.org/arch/msg/tls/VK9e6fA9jdQVFc6tQNWNO8OThU8/ 
> there are some (arguable) considerations of why it has practical benefits 
> to not cryptographically bind the header _format_ to the record.
> 
> Those considerations, however, are secondary to security considerations,
> so they didn't surface here so far.
> 
> Could we therefore clarify:
> 
> Are there any _security_ concerns arising from the modifiability of the
> header format assuming the underlying pseudo-header is bound via AEAD?

This will depend on what security you want to aim at. Clearly, if
non-malleability of headers is a goal, then yes.

More generally, cryptographic models of secure communication channels
would carve out "a ciphertext" (in quotes, as its not only the AEAD
ciphertext) from the spec. Now, it's always a modeling choice what this
ciphertext should include. A reasonable and natural choice for DTLS
would be to include the full on-the-wire header. Integrity would then
require that any modification of that header leads to the ciphertext
being rejected.
At the minimum, one would need to include all cryptographically relevant
information (esp. epoch, sequence number) enabling decryption, but then
singling those out from the wire format feels a little odd.

Hence, I would say that a natural cryptographic security notion most
likely suggests full on-the-wire header authentication. But again, it
all comes down to what's the goal.


> I don't see one so far, but might miss something. In my head, once the
> logical 
> data is authenticated, the entire on-the-wire header merely degrades to
> a 'hint' 
> to the receiver as to what the logical header data is, the precise form
> of which
> is entirely irrelevant.

This depends on the perspective. For analyzing channel security, it is
often conceptually easier to follow a modular approach that combines
confidentiality under passive attacks (usually straightforward) and
integrity of ciphertexts under active attacks. The latter means: no
modification of the ciphertext on the wire is permitted (in contrast to
plaintext integrity, demanding only that no modifications to the payload
can be made). This argument hence indeed relies on headers not being
malleable.

Our security analysis [1] for example models that the decision logic of
whether receiver should be accepting a certain next packet must be
decidable from the transcript of sent and received packets so far
(publicly, without internal keys or state).
Whether this would still work with a malleable 'hint' to the logical
header I don't know. Not saying this can't work, but our analysis
doesn't speak to that.


> Would you expect a change in proof complexity when switching
> to explicit length and sequence number authentication in the AEAD?

Length: no.
Sequence number (and epoch): only minor, as it merely obviates one level
of indirection (authentication via the nonce input).


Cheers,
Felix

[1] Marc Fischlin, Felix Günther, Christian Janson. Robust Channels:
Handling Unreliable Networks in the Record Layers of QUIC and DTLS.
Preprint for QUIPS 2020 Workshop at https://felixguenther.info/Q20_RC.pdf

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Choice of Additional Data Computation

[Felix Günther]

Hi,

On 2020-05-17 07:35 +0200, Hanno Becker  wrote:
> So, we're here at the moment:
> (1) Only the CID issue really _needs_ fixing somehow.
> (2) Other header fields are currently authenticated through a mixture of
> AAD, nonce, and implicit properties of the AEAD,
> and proof complexity doesn't seem to grow significantly because of that
> non-uniformity (the latter was slightly in doubt
> so far for epoch authentication, but Ekr's remark clarifies that it
> isn't actually the case). 
> (3) No security issues with the proposed alternative -- uniformly
> pseudo-header based AAD -- have been raised yet.
> (4) Non-security arguments for a pseudo-header AAD have been proposed,
> e.g. network bandwidth reduction.
> Those aren't discussed until the question of security reaches some clarity.
> 
> Felix, could you give some input on (3) as detailed in my last post? 

Our security analysis doesn't speak to (3) --- I added some more
detailed remarks in reply to your last post. Cearly, you wouldn't
achieve the same security definition (as headers are intentionally
malleable). Whether that's a problem or not depends on the goal, and if
you can indeed prove the corresponding, to-be-formalized security
statements.


Cheers,
Felix

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] PR #493: Multiple concurrent tickets

[Felix Günther]

Hi,

On 06/06/2016 11:53 +0200, Antoine Delignat-lavaud wrote:
> Le 2016-06-04 16:51, Eric Rescorla a écrit :
>> I wanted to call out to cryptographers/analysts that this formalizes
>> the existing practice (going back to RFC 5077) of having multiple
>> ticket values tied to the same basic secret (though less so with 1.3
>> because tickets issued on connection N+1 don't have the same RMS as
>> those on connection N). If there is a problem with this, that would be
>> good to know.
> 
> Looking at the pull request, I don't think it will have much impact on
> the protocol analysis given that it doesn't introduce any adversarial
> capability that wasn't already present before. If anything, your change
> may enable a proof of session unlinkability for well-behaved clients
> connecting to honest servers, under a number of restrictions.

I agree with Antoine that I don't expect multiple ticket values for the
same cryptographic key to have a (negative) impact on the/our security
results. As the ticket value is, through ClientHello, part of the
handshake hash, hence flowing into the key derviation, separate ticket
values should "domain-separate" the keys established from the same RMS.

And yes, might be one can establish some form of cryptographic
session/handshake unlinkability for honest client-server communication.

Cheers,
Felix



signature.asc
Description: OpenPGP digital signature
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Consensus call for keys used in handshake and data messages

[Felix Günther]

I also prefer (2).

Cheers,
Felix

On 14/06/2016 14:45 +0200, Cas Cremers wrote:
> It is not quite as simple as saying "(1) makes proofs more complicated"
> since it depends on what you are trying to prove.
> 
> (1) makes some styles of standard AKE property proofs (key secrecy,
> authentication) harder
> (2) might make some privacy proofs harder
> 
> Given that the proof-effort has mostly focused on secrecy and
> authentication properties, one can argue for (2).
> However, some proof styles can still work out in (1), so it is not such
> a clear choice.
> 
> Over time, I've changed my mind, and I now prefer (2) (since we don't
> have full detail on any privacy proofs) as long as the content-type
> essentially boils down to a single bit of information (which key we are
> using) and nothing else.
> 
> FWIW,
> 
> Cas
> 
> 
> On Tue, Jun 14, 2016 at 1:12 PM, Hannes Mehnert  > wrote:
> 
> On 13/06/2016 21:27, Daniel Kahn Gillmor wrote:
> > On Mon 2016-06-13 15:00:03 -0400, Joseph Salowey wrote:
> >> 1. Use the same key for handshake and application traffic (as in the
> >> current draft-13)
> >>
> >  > or
> >>
> >> 2. Restore a public content type and different keys
> >
> > Given this choice, i prefer (1).
> 
> FWIW, I prefer (1) as well
> 
> 
> hannes
> 
> ___
> TLS mailing list
> TLS@ietf.org 
> https://www.ietf.org/mailman/listinfo/tls
> 
> 
> 
> 
> ___
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
> 



signature.asc
Description: OpenPGP digital signature
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Adding an additional step to exporters

[Felix Günther]

Hi Martin,

just to clarify: you add an additional HKDF.Expand step, not
HKDF.Extract, right?

You mentioned extract in the email and PR text, but in code it's a
second expand---which makes sense, as only expand allows to add context
(here: label).

Cheers,
Felix

On 23/02/2017 20:30 -0800, Martin Thomson wrote:
> https://github.com/tlswg/tls13-spec/pull/882 contains the longer description.
> 
> In short, the existence of an exporter secret threatens the forward
> secrecy of any exported secret.  This is a problem for QUIC and is
> likely to be a more general problem.
> 
> The proposed fix is small: separate exporters into two steps
> (extract+expand) where the first step allows for separation based on
> exporter type and the second on context.  That allows an endpoint to
> keep separate secrets for each exporter type and discard those that it
> no longer needs, thus gaining forward secrecy if it likes.
> 
> ___
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
> 

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Felix Günther]

Hi Peter,

We discussed this among the [DOWLING] authors; Douglas asked me to chime 
in here as he's offline the next couple of days.


It is indeed true that the PRF-ODH assumption, as stated in [DOWLING] 
and https://ia.cr/2017/517, wouldn't be compatible when using the 
x-coordinate only, or with clamping. One needs to be a little bit more 
careful in these cases, disallowing the PRF-ODH adversary to make 
queries on trivially colliding points (e.g., by flipping signs, or 
adding small-order points).


This has been done for example in a paper about the security of 
Bluetooth by Fischlin (co-author of [DOWLING]) and Sanina [ 
https://ia.cr/2021/1597 ], where the x-coordinate is also used to derive 
keys. There, they adapted the PRF-ODH definition accordingly (Section 
4.1). We don't think that this makes the assumption less plausible, only 
a bit more tedious to define and deal with in the proofs.


Concretely for TLS 1.3, the reduction to sn-PRF-ODH for Theorem 5.2 in 
Game B.2 would perform the relevant collision checks upon a modified 
g^v' received by the partner session, and use the same uniform random 
string as in the test session for such collisions. (The session hash in 
later key derivation steps still ensures they'll derive independent keys.)
This matches the PRF-ODH assumption with the restricted modifications as 
mentioned above; the TLS proof then goes through as before.



As for the PQ3 protocol also brought up in this, from a
quick glance similar arguments seem to apply: the PRF-ODH reductions
already check whether "the same V" is received, hence the collision
check can be added there, too.


Hope this helps to clarify.  We plan to update the eprint version 
https://ia.cr/2020/1044 of [DOWLING] accordingly.  Let us know if you 
need more details.


Best,
Felix  (with Ben, Douglas, Marc)


On 2024-07-26 00:19 +0200, Peter C 
 wrote:

Douglas,


It's not exactly due to the point formats, at least for X25519.  The RFC 7748
security considerations highlight that "for each public key, there are several
publicly computable public keys that are equivalent to it, i.e., they produce
the same shared secrets".  Assuming the early secret doesn't change, this
means equivalent public keys will produce the same handshake secrets and
the same master secrets.  The transcript hash does give you different
handshake traffic secrets and application traffic secrets, but I think that's 
too
late in the key schedule for [DOWLING].



The proof in [DOWLING] only aims to prove that the handshake traffic secrets
and application traffic secrets are secure, not that the handshake secrets and
master secrets are secure, so for that purpose it should be okay that the
transcript hash is incorporated a little later in the key schedule.


Sorry, I only meant that in Theorem 5.2 the dual-snPRF-ODH assumption is used
in Game B.2 to replace the handshake secret with a uniformly random value which
then allows the handshake traffic secrets to be replaced with uniformly random
values in Game B.3 using the PRF assumption on HKDF.Expand and the fact that
the labels are distinct.  Equivalent public keys mean that the handshake secret
is not indistinguishable from random and the proof fails at Game B.2.  The 
distinct
labels in Game B.3 only imply that the handshake traffic secrets will be 
different,
not that they are indistinguishable.

Peter
___
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

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

[Felix Günther]

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://ia.cr/2017/517 ]), 
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  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 
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.iacr.org/2021/1597.pdf 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

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

[Felix Günther]

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  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 
Sent: Friday, August 2, 2024 2:05 PM
To: Peter C ; Marc Fischlin 
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%7C6%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  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 
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.

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

[Felix Günther]

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  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ünthe