Subject: [TLS] Gaps in specification of DTLS 1.3 state machine

From: Hanno Becker <[email-masked]>
Date: Wed, 4 Mar 2020 14:19:22 +0000

Hi,

[TL;DR]
The DTLS 1.3 spec (draft 34) doesn't fully describe the retransmission state
machine in the case of post-handshake messages, which requires clarification.
For example, is it allowed to send multiple post-handshake messages without
waiting for ACKs for the previous ones? If so, how is the retransmission
state machine modeled for sender and receiver in this case?
I'll describe and assess a few possible options, but I don't know the best
answer, and so this post is mostly a request for discussion, hopefully
resulting in some common understanding and clarification of the spec.

Details:

The following cases need addressing:
a) Is it allowed to send multiple post-handshake messages (e.g., multiple session
   tickets) without waiting for ACKs for the previous ones? If so, how is the
   retransmission state machine modeled for sender and receiver in this case?
b) How should simultaneous sending/receiving of post-handshake messages be handled?
   The current retransmission state machine doesn't allow sending and receiving
   at the same time.

Some thoughts on a) first:

The spec mentions that post-handshake messages are treated as single-message flights.
As such, the sender would enter WAITING state after sending the post-handshake message,
and move to FINISHED on receipt of the corresponding ACK. This, however, forbids sending
another post-handshake message in between, since sending isn't allowed in WAITING state.

Option A: Fork state machine

One could circumvent this by 'forking' the retransmission state machine for post-handshake
messages, i.e. declaring their semantics as if there were multiple independent state machines
for each outstanding post-handshake message. This essentially degrades the DTLS' ACK scheme
to a per-message acknowledgement.

I believe that such an approach is not in the spirit of the rest of the protocol and moreover
significantly increases complexity and thereby comes at the danger of slower adoption and/or bugs.
Moreover, it will significantly harden efforts for formal verification, which should be considered
in light of previous efforts on TLS 1.3.

Option B: Don't allow multiple post-handshake messages

Forcing implementations to await an ACK before sending the next post-handshake message is a theoretical
option which would allow to stick to the existing state machine. However, this significantly increases
the latency of, say, the delivery of multiple session tickets, which is a valid use case. This is therefore
not a convincing option, either.

Option C: Merge consecutive post-handshake messages into a single flight.

Another approach would be to treat multiple post-handshake messages as a single flight on the sender.
That is, when the sender is in state WAITING after sending the first post-handshake message, and the
user request to send another one, it moves into SENDING and then back into WAITING as usual, appending
the new post-handshake message to the (so-far single-message) flight.

How would that be handled on the receiver side?

That's not entirely clear because a basic property of the TLS handshake that DTLS leverages now no longer
holds: Namely, that both sides implicitly know and agree on the bounds of flights. Here, multiple post-
handshake messages would be treated as a single flight on the sender, but the receiver doesn't know
when the flight is over. How should this be handled?

This is to be explored further. One way to address this would be the following:

Option D: Add an 'end-of-flight' signal to handshake messages to allow dynamic-length flights.

Recall that the handshake logic must inform the retransmission state machine about when a flight
is over in the main handshake, allowing the state machine to transition accordingly. This signal,
however, isn't explicitly conveyed to the receiver, because the receiver can figure it out for
himself.

As mentioned, this isn't true anymore for batched post-handshake messages.

One simple way to deal with is to add an explicit 'end-of-flight' bit in the handshake header
which informs the receiver about when a flight is over, in those situations where it's not
clear from the context.

This would allow to keep a single retransmission state-machine as-is while allowing for
batched post-handshake messages such as multiple session tickets. Moreover, such a signal
would be trivial to implement because it's already implicit in the main handshake.

For the wire-format, we can discuss different options, but that's an orthogonal question
to the issue of finding the correct conceptual approach.

Happy to hear everyone's thoughts. It would be great if we could come up with some
precise description of the state machine evolution for post-handshake messages that
is both simple and supports batched post-handshake messages.

Best,
Hanno
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 05 Mar 2020 10:32:45 +1100

Option A please.  Multiple state machines.

It's unavoidable in any case.  If you generate your own post-handshake message and then have to respond to post-handshake authentication, there will be two concurrent exchanges.  We already require acknowledgment for both request and response in a two-way exchange.  Since 2 is a member of the third class of numbers (0, 1, ∞), we might as well deal with the full implications of that.

Handling this is fairly simple though.  We can recommend limiting to only one active transmission at a time.  And if implementations have an especially low tolerance for concurrency they can close connections.

On Thu, Mar 5, 2020, at 01:19, Hanno Becker wrote:
>  IMPORTANT NOTICE: The contents of this email and any attachments are 
> confidential and may also be privileged. If you are not the intended 
> recipient, please notify the sender immediately and do not disclose the 
> contents to any other person, use it for any purpose, or store or copy 
> the information in any medium. Thank you. 
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Hanno Becker <[email-masked]>
Date: Thu, 5 Mar 2020 07:00:08 +0000

Thanks Martin for your thoughts.

>  It's unavoidable in any case.  If you generate your own post-handshake message and
> then have to respond to post-handshake authentication, there will be two concurrent
> exchanges.

Yes that's an instance of the second question b) which the post didn't further go into.

I'm not yet convinced that this situation unavoidably creates the need for duplicating state machines, though, and think that if possible we should avoid it for the sake of implementation simplicity.

Moreover, even if it is acceptable that state machines should be duplicated, it isn't clear (to me) how to logically separate them because they're all tied together by the use of the same global handshake sequence number. This creates non-trivial ambiguities like the following:

Imagine after the handshake the server requests post-handshake authentication while, simultaneously, the client initiates a key update. When the server receives the KeyUpdate, it assumes from the handshake sequence number that it is the reply to his CertificateRequest, and only when inspecting the type of the handshake message it'll notice the mismatch. Usually, a type mismatch would be treated as a protocol violation and lead to failure of the connection, while here, we'd need the server to drop the message or notice that it should fork a new state machine.

Note that this problem already exists, albeit in less prominent form, in DTLS 1.2, where both sides may simultaneously trigger a renegotiation.

Thinking about it, it seems that the way to make this work is to segregate the part of the retransmission state machine which establishes in-order delivery via handshake sequence numbers, and to have the duplicated contexts one level higher. When a handshake message comes in, it would be trial-fed into all existing contexts, either until one of them accepts it after checking type and content, or potentially leading to the forking of a new context.

However, this asynchronous nature of handling multiple post-handshake messages is in conflict with the serialized nature of the handshake transcript used e.g. in the CertificateVerify message:

Imagine a post-handshake client authentication to happen interwoven with another post-handshake message from client to server. When the client writes the CertificateVerify, that would require the transcript of the entire handshake up until the CertificateVerify message. Assuming this should include all post-handshake messages, not just those belonging to the client authentication, this may lead to the situation where the server receives a CertificateVerify message with a transcript it cannot validate because it hasn't yet received all other authentication-independent post-handshake messages that went into the transcript.

Maybe I'm overcomplicating things, but as it stands it seems to me that the above are serious issues to be further discussed and clarified even if we accept state machine duplication.

Happy to hear your thoughts.

Cheers,
Hanno
________________________________
From: TLS <[email-masked]> on behalf of Martin Thomson <[email-masked]>
Sent: Wednesday, March 4, 2020 11:32 PM
To: [email-masked] <[email-masked]>
Subject: Re: [TLS] Gaps in specification of DTLS 1.3 state machine

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 5 Mar 2020 06:45:26 -0800

Hanno,

I do think you are overcomplicating things somewhat.

You can't process handshake messages out of sequence even if they are
received out of sequence (this is, of course, also the case in TLS,
it's just that the resequencing happens at the TCP layer). You have to
either drop out of order messages or buffer them. Yes, this is
somewhat irritating, but as you demonstrate below, it's inherent
in the design of post-handshake messages even if each side is
only allowed to initiate one transaction at a time.

It might be useful to explain this in the text, but I don't think
anything else is needed.

-Ekr

On Wed, Mar 4, 2020 at 11:00 PM Hanno Becker <[email-masked]> wrote:

> I'm not yet convinced that this situation unavoidably creates the need for
> duplicating state machines, though, and think that if possible we should
> avoid it for the sake of implementation simplicity.
>
> Moreover, even if it is acceptable that state machines should be
> duplicated, it isn't clear (to me) how to logically separate them because
> they're all tied together by the use of the same global handshake sequence
> number. This creates non-trivial ambiguities like the following:
>
> Imagine after the handshake the server requests post-handshake
> authentication while, simultaneously, the client initiates a key update.
> When the server receives the KeyUpdate, it assumes from the handshake
> sequence number that it is the reply to his CertificateRequest, and only
> when inspecting the type of the handshake message it'll notice the
> mismatch. Usually, a type mismatch would be treated as a protocol violation
> and lead to failure of the connection, while here, we'd need the server to
> drop the message or notice that it should fork a new state machine.
>
> Note that this problem already exists, albeit in less prominent form, in
> DTLS 1.2, where both sides may simultaneously trigger a renegotiation.
>
> Thinking about it, it seems that the way to make this work is to segregate
> the part of the retransmission state machine which establishes in-order
> delivery via handshake sequence numbers, and to have the duplicated
> contexts one level higher. When a handshake message comes in, it would be
> trial-fed into all existing contexts, either until one of them accepts it
> after checking type and content, or potentially leading to the forking of a
> new context.
>
> However, this asynchronous nature of handling multiple post-handshake
> messages is in conflict with the serialized nature of the handshake
> transcript used e.g. in the CertificateVerify message:
>
> Imagine a post-handshake client authentication to happen interwoven with
> another post-handshake message from client to server. When the client
> writes the CertificateVerify, that would require the transcript of the
> entire handshake up until the CertificateVerify message. Assuming this
> should include all post-handshake messages, not just those belonging to the
> client authentication, this may lead to the situation where the server
> receives a CertificateVerify message with a transcript it cannot validate
> because it hasn't yet received all other authentication-independent
> post-handshake messages that went into the transcript.
>
> Maybe I'm overcomplicating things, but as it stands it seems to me that
> the above are serious issues to be further discussed and clarified even if
> we accept state machine duplication.
>
> ------------------------------
> *From:* TLS <[email-masked]> on behalf of Martin Thomson <
> [email-masked]>
> *Sent:* Wednesday, March 4, 2020 11:32 PM
> *To:* [email-masked] <[email-masked]>
> *Subject:* Re: [TLS] Gaps in specification of DTLS 1.3 state machine
>
> It's unavoidable in any case.  If you generate your own post-handshake
> message and then have to respond to post-handshake authentication, there
> will be two concurrent exchanges.  We already require acknowledgment for
> both request and response in a two-way exchange.  Since 2 is a member of
> the third class of numbers (0, 1, ∞), we might as well deal with the full
> implications of that.
>
> Handling this is fairly simple though.  We can recommend limiting to only
> one active transmission at a time.  And if implementations have an
> especially low tolerance for concurrency they can close connections.
>
> > https://www.ietf..org/mailman/listinfo/tls
> <https://www.ietf.org/mailman/listinfo/tls>
> >
>
> contents to any other person, use it for any purpose, or store or copy the
> information in any medium. Thank you.

---

From: "Christopher Wood" <[email-masked]>
Date: Wed, 11 Mar 2020 06:37:51 -0700

Thanks for raising this issue and for the discussion, folks!

Given that endpoints *process* handshake messages in sequence, thereby preventing any out-of-order processing issues raised earlier on this thread, the chairs think no further action is needed to address this comment.

Thanks,
Chris, on behalf of the chairs

On Thu, Mar 5, 2020, at 6:45 AM, Eric Rescorla wrote:
> it's just that the resequencing happens at the TCP layer).. You have to
> anything else is needed..
> 
> -Ekr
> 
> > *From:* TLS <[email-masked]> on behalf of Martin Thomson <[email-masked]>
> >  > https://www.ietf..org/mailman/listinfo/tls <https://www.ietf.org/mailman/listinfo/tls>
> >  >
> >

---

From: Hanno Becker <[email-masked]>
Date: Wed, 11 Mar 2020 14:36:05 +0000

Thanks Eric, Martin and Chris for your input!

For the record: I withdraw my claim that there's an issue with handshake message reordering
and the transcript, as already pointed out by Eric and Chris. I also don't see any other issues
at the moment with what appears to be the preferred model of duplicated state machines
that would require technical changes to the specification.

However, I do believe that the duplication of state machines is non-trivial enough to merit
explicit mentioning in the specification. In particular, if I understand things correctly, it appears
that it increases the implicit interface between the handshake logic 'layer' (which should be
as similar to that for TLS 1.3 implementations as possible) and the underlying 'messaging' layer,
including the retransmission state machine: For example, the retransmission state machine cannot
infer which handshake message belongs to which state machine on its own on the basis of handshake
metadata. Instead, this information needs to be provided by the handshake logic after inspecting the
message content. As a concrete example, one can consider multiple CertificateRequest messages
being sent from Server to Client. When the Client responds to one of them, it is only on parsing
of the certificate request context that it becomes clear which state machine the message belongs to.
Hence, in a nutshell, while for the main handshake the signaling between handshake logic layer
and messaging layer is confined to indicating when a flight or handshake is over, the duplication
of state machines seems to add complexity by requiring to add a signal indicating which state
machine an incoming message belongs to. Similarly, when sending messages, it needs to be
indicated which state machine they belong to.

Overall, I believe that it would be beneficial if the abstract model for the retransmission state
machine - including the state machine duplication for post-handshake messages - received
some more attention and (potentially formal) analysis.

Cheers,
Hanno
________________________________
From: TLS <[email-masked]> on behalf of Christopher Wood <[email-masked]>
Sent: Wednesday, March 11, 2020 1:37 PM
To: [email-masked] <[email-masked]>
Subject: Re: [TLS] Gaps in specification of DTLS 1.3 state machine

Thanks,