Re: [TLS] 0RTT freshness test does not work well when delays are in minutes

[Christian Huitema]

On 1/10/2024 10:20 PM, Martin Thomson wrote:

On Thu, Jan 11, 2024, at 15:45, Christian Huitema wrote:

Good for you. Not all implementations do that. It is hard for me to
blame them, because the 10 seconds recommendation is justified by for
"clients on the Internet", and delays larger than 1 or maybe 2 seconds
are quite rare on the "Earthian" Internet that we have today. Given that
complexity is the enemy of security, I certainly understand why some
implementations keep it simple.

I consider it necessary for reliability purposes.  If you don't at least try to 
account for RTT, you are skewing any window anti-replay window you have.


Yes, but the relation between delays and variance is rather complex. On
the current Internet, a good bit of delay variance comes from congestion
control protocols pushing ever more data until queues overflow -- but
better congestion control or using modern AQM in front of the bottleneck
can take care of that.

Keep in mind that a lot of these exchanges won't have had much data exchanged 
on the connection at the time.  So a lot of the variance from self-induced 
congestion won't come into play.  That's not to say that you won't be affected 
by what others are doing or other active connections though.  And of course, 
your space networks have other more interesting factors pushing delays in all 
directions.


Plus, how exactly does one test this kind of "variable delay" code?

Time is just another input to your program, right?


The more I think of it, the more I believe the solution may be some kind
of plug-in in the TLS implementation. Let the application that requires
the extra complexity deal with it, develop and test the adequate plug-in.

I don't think that there is much need for active code, just configuration.  
Maybe I'm missing something though.


If an implementation does not want to deal with the extra complexity, 
then having a way to plug in some extra code for a specific scenario 
makes sense...


-- Christian Huitema

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

Re: [TLS] 0RTT freshness test does not work well when delays are in minutes

[Martin Thomson]

On Thu, Jan 11, 2024, at 15:45, Christian Huitema wrote:
> Good for you. Not all implementations do that. It is hard for me to 
> blame them, because the 10 seconds recommendation is justified by for 
> "clients on the Internet", and delays larger than 1 or maybe 2 seconds 
> are quite rare on the "Earthian" Internet that we have today. Given that 
> complexity is the enemy of security, I certainly understand why some 
> implementations keep it simple.

I consider it necessary for reliability purposes.  If you don't at least try to 
account for RTT, you are skewing any window anti-replay window you have.

> Yes, but the relation between delays and variance is rather complex. On 
> the current Internet, a good bit of delay variance comes from congestion 
> control protocols pushing ever more data until queues overflow -- but 
> better congestion control or using modern AQM in front of the bottleneck 
> can take care of that. 

Keep in mind that a lot of these exchanges won't have had much data exchanged 
on the connection at the time.  So a lot of the variance from self-induced 
congestion won't come into play.  That's not to say that you won't be affected 
by what others are doing or other active connections though.  And of course, 
your space networks have other more interesting factors pushing delays in all 
directions.

> Plus, how exactly does one test this kind of "variable delay" code?

Time is just another input to your program, right?

> The more I think of it, the more I believe the solution may be some kind 
> of plug-in in the TLS implementation. Let the application that requires 
> the extra complexity deal with it, develop and test the adequate plug-in.

I don't think that there is much need for active code, just configuration.  
Maybe I'm missing something though.

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

Re: [TLS] 0RTT freshness test does not work well when delays are in minutes

[Christian Huitema]

On 1/10/2024 7:00 PM, Martin Thomson wrote:

On Thu, Jan 11, 2024, at 11:07, Christian Huitema wrote:

One first problem with this code is that implementations may or may not
have an estimate of the RTT when they are issuing the ticket. In theory
the server could measure the RTT by comparing the send time of the
server first flight and the arrival time of the client's second flight,
but that's extra complexity and implementations may well skip that test.


This seems like a pretty easy thing to measure.  It's what I implemented for 
NSS.  I don't think that you should assume that people won't do that.


Good for you. Not all implementations do that. It is hard for me to 
blame them, because the 10 seconds recommendation is justified by for 
"clients on the Internet", and delays larger than 1 or maybe 2 seconds 
are quite rare on the "Earthian" Internet that we have today. Given that 
complexity is the enemy of security, I certainly understand why some 
implementations keep it simple.





In theory, the client could compensate the clients_ticket_age to include
the RTT, but that's risky. If the client is connecting to a server
implementation that does adjust the ticket creation time, the adjusted
client time will be found larger than the current time at the server.
Servers may well test for that, reject the ticket and fall back to 1RTT.


Compensating for the RTT estimate is possible (again, I can attest to this 
being easy to implement), but the problem is that you also need to account for 
a larger RTT variance when RTT increases.  For that, it is not so easy as the 
more obvious mechanisms for tracking anti-replay need to be globally 
configured, not driven by per-connection parameters.  If you have clients with 
1s RTTs coexisting with those that have RTTs measured in minutes, the 
configuration needs to be different.

See 
https://searchfox.org/mozilla-central/rev/b1a029fadaaabb333d8139f9ec3924a20c0c941f/security/nss/lib/ssl/sslexp.h#187-194
 (which doesn't talk about RTT variance, but it should).


Yes, but the relation between delays and variance is rather complex. On 
the current Internet, a good bit of delay variance comes from congestion 
control protocols pushing ever more data until queues overflow -- but 
better congestion control or using modern AQM in front of the bottleneck 
can take care of that. In space, I am more concerned about delay 
variation over time, since everything is either in some orbit or falling 
through space at considerable speed. Plus I see dreams of building 
networks of space relays, which implies variable paths between two 
points. So the RTT at the time the ticket is issued may differ from the 
RTT when the ticket is used by quite a bit.


And then, as you point out, larger tolerance means loosening the 
freshness test a lot. Might be much better to rely on Bloom filters or 
similar solutions.


Plus, how exactly does one test this kind of "variable delay" code?



If you know about a population of clients with high variance, you can build 
allowances in, but I don't have a general solution.  However, allowing for that 
variance comes with a cost in terms of state space, especially if you have to 
allow for high connection rates.


The more I think of it, the more I believe the solution may be some kind 
of plug-in in the TLS implementation. Let the application that requires 
the extra complexity deal with it, develop and test the adequate plug-in.


-- Christian Huitema

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

Re: [TLS] 0RTT freshness test does not work well when delays are in minutes

[Martin Thomson]

On Thu, Jan 11, 2024, at 11:07, Christian Huitema wrote:
> One first problem with this code is that implementations may or may not 
> have an estimate of the RTT when they are issuing the ticket. In theory 
> the server could measure the RTT by comparing the send time of the 
> server first flight and the arrival time of the client's second flight, 
> but that's extra complexity and implementations may well skip that test.

This seems like a pretty easy thing to measure.  It's what I implemented for 
NSS.  I don't think that you should assume that people won't do that.

> In theory, the client could compensate the clients_ticket_age to include 
> the RTT, but that's risky. If the client is connecting to a server 
> implementation that does adjust the ticket creation time, the adjusted 
> client time will be found larger than the current time at the server. 
> Servers may well test for that, reject the ticket and fall back to 1RTT.

Compensating for the RTT estimate is possible (again, I can attest to this 
being easy to implement), but the problem is that you also need to account for 
a larger RTT variance when RTT increases.  For that, it is not so easy as the 
more obvious mechanisms for tracking anti-replay need to be globally 
configured, not driven by per-connection parameters.  If you have clients with 
1s RTTs coexisting with those that have RTTs measured in minutes, the 
configuration needs to be different.

See 
https://searchfox.org/mozilla-central/rev/b1a029fadaaabb333d8139f9ec3924a20c0c941f/security/nss/lib/ssl/sslexp.h#187-194
 (which doesn't talk about RTT variance, but it should).

If you know about a population of clients with high variance, you can build 
allowances in, but I don't have a general solution.  However, allowing for that 
variance comes with a cost in terms of state space, especially if you have to 
allow for high connection rates.

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

Re: [TLS] 0RTT freshness test does not work well when delays are in minutes

[Stephen Farrell]

Hiya,

Interesting question...

On 11/01/2024 00:07, Christian Huitema wrote:

I am wondering what the proper fix should be.


I don't know the answer (or if there's one answer) but
suspect that it may be better to first explore various
scenarios (as you've kinda kicked off with forwarding to
the deepspace list) and then come back to TLS implementers
with an ask based on some of those.

I also suspect that one'd need to use some kind of callback
that e.g. can query ephemeris data, as a number of scenarios
would involve RTTs that vary significantly over time, but
adding such callbacks to implementations could be dangerous
in more typical Internet environments.

Lastly, I'd guess that replay of early_data for applications
in some deepspace scenarios would be so dangerous that one'd
be better to not use early_data but rather to export a key and
then use that with an application that itself knows how to handle
replayed data. So maybe exploring ways to use key exporters is
also something to consider, rather than using early_data. (For
cases where new deepspace applications are developed that want
to use TLS.)

Cheers,
S.


OpenPGP_0xE4D8E9F997A833DD.asc
Description: OpenPGP public key


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

[TLS] 0RTT freshness test does not work well when delays are in minutes

[Christian Huitema]

There is interest in using TLS 1.3 and QUIC for communication in space 
-- partly for reason such as "reusing off the shelf components". But 
this is not the typical Internet environment. The transmission delays 
can be very long: a few seconds between Earth and Moon, from a few 
minutes to tens of minutes between Earth and Mars. 0RTT is a great fit 
for these scenarios -- one really wants to not wait another RTT before 
sending data. But we do have a problem, because of the ways 
implementations implement anti-replay of resumption tickets using the 
"freshness tests" defined in section 8.3 of RFC8446.


The code is described as:

adjusted_creation_time = creation_time + estimated_RTT

expected_arrival_time = adjusted_creation_time + clients_ticket_age

If the expected_arrival_time is too far back in time, the session may be 
resumed, but 0RTT should be disabled. The recommended value for the that 
test "for clients on the Internet" is "on the order of ten seconds".


One first problem with this code is that implementations may or may not 
have an estimate of the RTT when they are issuing the ticket. In theory 
the server could measure the RTT by comparing the send time of the 
server first flight and the arrival time of the client's second flight, 
but that's extra complexity and implementations may well skip that test.


In theory, the client could compensate the clients_ticket_age to include 
the RTT, but that's risky. If the client is connecting to a server 
implementation that does adjust the ticket creation time, the adjusted 
client time will be found larger than the current time at the server. 
Servers may well test for that, reject the ticket and fall back to 1RTT.


There is a secondary issue when delays are not just long but also 
variable. That could happen if the session is resumed on a different 
path, which could well be minutes shorter or longer than the original 
path over which the ticket was received. If the delays are shorter and 
the server adjusted for the longer delays, the expected_arrival_time 
will be before the current time at the server, and the sanity check will 
reject the ticket. If the delays are longer, the freshness test will fail.


I am wondering what the proper fix should be.

-- Christian Huitema

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

Re: [TLS] [EXTERNAL] [CFRG] X-Wing: the go-to PQ/T hybrid KEM?

[Mike Ounsworth]

Thanks for this work!

 

Speaking for myself (not for my co-authors), this feels like friendly, 
complementary work to draft-ounsworth-cfrg-kem-combiners; X-Wing could be 
viewed as a profile of ounsworth-kem-combiners that optimizes around the 
security properties of ML-KEM.

 

Bas makes a good point that ounsworth-kem-combiners is not by itself 
implementable because it does not provide concrete instantiations. We could 
consider adding a section with concrete instantiations, and the first one would 
be X-Wing 😊 (followed by ML-KEM + P-256, Brainpool, and RSA variants).

 

I guess that leads to the following question:  
 @Bas Westerbaan,  
 @Deirdre Connolly, Peter, would you be open 
to merging X-Wing into the generic combiner draft, or is there value in it 
being standalone?

 

---

Mike Ounsworth

 

From: CFRG  On Behalf Of Bas Westerbaan
Sent: Wednesday, January 10, 2024 2:14 PM
To: IRTF CFRG ;  
Cc: k...@cupdev.net
Subject: [EXTERNAL] [CFRG] X-Wing: the go-to PQ/T hybrid KEM?

 

Dear tls and cfrg working groups, With ML-KEM (née Kyber) expected to be 
finalized this year, it’s time to revisit the question of which PQ/T hybrid 
KEMs to standardize, and which to recommend. # Status quo For TLS at the time 
of writing there 



Dear tls and cfrg working groups,

With ML-KEM (née Kyber) expected to be finalized this year, it’s time to 
revisit the question of which PQ/T hybrid KEMs to standardize, and which to 
recommend.

# Status quo

For TLS at the time of writing there are two PQ/T hybrids registered: 
X25519Kyber768 [1] and P256Kyber768 [2]. The former has been deployed widely 
[3]. Both are instances of the hybrid-design draft [4], which use the simple 
combiner ss_ECC || ss_Kyber, which is suitable for TLS, but not for other 
applications such as HPKE, as it’s not IND-CCA2 robust [5].

For HPKE, there is a different KEM called X25519Kyber768 [6], which uses a 
different combiner that mixes in the X25519 ephemeral key, by using HPKE’s 
DHKEM construction instead of raw X25519.

There is also the ounsworth-kem-combiners I-D [7] that informed by [5] proposes 
the generic combiner

  KDF( counter || ct1 || ss1 || ct2 || ss2 || fixedInfo, outputBits )

>From a security standpoint that would be suitable for HPKE and TLS. To TLS it 
>is somewhat unattractive as it requires hashing the typically large PQ 
>ciphertexts, and adds some extra hashing in the conversion of the ECDH into a 
>KEM. On the other hand, for TLS it would be nice to have a KEM that is also 
>suitable for HPKE, as HPKE is used in ECH.

>From a usability perspective, ounsworth-kem-combiners requires the user to 
>make several choices: which KEMs and in particular which method to use to turn 
>ECDH into a KEM, which security levels, which KDF, etc.

# The proposal: X-Wing

Let us introduce X-Wing [0]. The goal of X-Wing is to be *the* go-to PQ/T 
hybrid KEM for the majority of use cases (including TLS and HPKE): no need to 
make choices, or understand the subtleties.

X-Wing aims for 128-bit security, and for that combines the time-tested X25519 
with ML-KEM-768 [8]. X-Wing uses the combiner

  SHA3-256( xwing-label || ss_ML-KEM || ss_X25519 || ct_X25519 || pk_X25519 )

Here ss_X25519 is the plain X25519 shared secret; ct_X25519 is the ephemeral 
public key; xwing-label a 6-byte label. Note that it doesn’t hash in the ML-KEM 
ciphertext. For a generic KEM one cannot leave out the ciphertext, but in the 
case of ML-KEM we can, assuming we can model SHA3/SHAKE as a random oracle. 
This is proven in [0]. The gist is that FO transform in ML-KEM makes it 
“ciphertext collision resistant”: even if the underlying lattice problem is 
broken, it’s infeasible to create from one ciphertext another different 
ciphertext with the same shared secret.

# Not final

We would love to hear your input: X-Wing is not final. For one, ML-KEM itself 
might still change (presumably only in minor ways) before final 
standardization. We think the CFRG would be a good venue to standardize X-Wing 
— do you concur?

Best,

Bas, Deirdre, Karolin, Manuel, Peter


PS. We want to mention explicitly that we see value in the kem-combiners and 
hybrid-design drafts as generic safe methods to construct hybrids for those use 
cases where X-Wing would not suffice.


[0] Spec: https://datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/ 

 
Proof: https://eprint.iacr.org/2024/039 

 
[1] Full name X25519Kyber768Draft00. 
https://datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/ 

[TLS] X-Wing: the go-to PQ/T hybrid KEM?

[Bas Westerbaan]

Dear tls and cfrg working groups,

With ML-KEM (née Kyber) expected to be finalized this year, it’s time to
revisit the question of which PQ/T hybrid KEMs to standardize, and which to
recommend.

# Status quo

For TLS at the time of writing there are two PQ/T hybrids registered:
X25519Kyber768 [1] and P256Kyber768 [2]. The former has been deployed
widely [3]. Both are instances of the hybrid-design draft [4], which use
the simple combiner ss_ECC || ss_Kyber, which is suitable for TLS, but not
for other applications such as HPKE, as it’s not IND-CCA2 robust [5].

For HPKE, there is a different KEM called X25519Kyber768 [6], which uses a
different combiner that mixes in the X25519 ephemeral key, by using HPKE’s
DHKEM construction instead of raw X25519.

There is also the ounsworth-kem-combiners I-D [7] that informed by [5]
proposes the generic combiner

  KDF( counter || ct1 || ss1 || ct2 || ss2 || fixedInfo, outputBits )

>From a security standpoint that would be suitable for HPKE and TLS. To TLS
it is somewhat unattractive as it requires hashing the typically large PQ
ciphertexts, and adds some extra hashing in the conversion of the ECDH into
a KEM. On the other hand, for TLS it would be nice to have a KEM that is
also suitable for HPKE, as HPKE is used in ECH.

>From a usability perspective, ounsworth-kem-combiners requires the user to
make several choices: which KEMs and in particular which method to use to
turn ECDH into a KEM, which security levels, which KDF, etc.

# The proposal: X-Wing

Let us introduce X-Wing [0]. The goal of X-Wing is to be *the* go-to PQ/T
hybrid KEM for the majority of use cases (including TLS and HPKE): no need
to make choices, or understand the subtleties.

X-Wing aims for 128-bit security, and for that combines the time-tested
X25519 with ML-KEM-768 [8]. X-Wing uses the combiner

  SHA3-256( xwing-label || ss_ML-KEM || ss_X25519 || ct_X25519 || pk_X25519
)

Here ss_X25519 is the plain X25519 shared secret; ct_X25519 is the
ephemeral public key; xwing-label a 6-byte label. Note that it doesn’t hash
in the ML-KEM ciphertext. For a generic KEM one cannot leave out the
ciphertext, but in the case of ML-KEM we can, assuming we can model
SHA3/SHAKE as a random oracle. This is proven in [0]. The gist is that FO
transform in ML-KEM makes it “ciphertext collision resistant”: even if the
underlying lattice problem is broken, it’s infeasible to create from one
ciphertext another different ciphertext with the same shared secret.

# Not final

We would love to hear your input: X-Wing is not final. For one, ML-KEM
itself might still change (presumably only in minor ways) before final
standardization. We think the CFRG would be a good venue to standardize
X-Wing — do you concur?

Best,

Bas, Deirdre, Karolin, Manuel, Peter


PS. We want to mention explicitly that we see value in the kem-combiners
and hybrid-design drafts as generic safe methods to construct hybrids for
those use cases where X-Wing would not suffice.


[0] Spec: https://datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/
Proof: https://eprint.iacr.org/2024/039
[1] Full name X25519Kyber768Draft00.
https://datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/
[2] Full name SecP256r1Kyber768Draft00.
https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-kyber/
[3]
https://blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html
https://twitter.com/bwesterb/status/1734586155868287457
[4] https://datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/
[5] https://link.springer.com/chapter/10.1007/978-3-319-76578-5_7
[6] https://datatracker.ietf.org/doc/draft-westerbaan-cfrg-hpke-xyber768d00/
[7] https://datatracker.ietf.org/doc/draft-ounsworth-cfrg-kem-combiners/
[8] Following earlier deployment of X25519Kyber768, despite targeting 128
bits, we use ML-KEM-768 instead of ML-KEM-512 to hedge against advances in
lattice attacks.
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls