Subject: Unrecoverable loss pattern

From: Marten Seemann <[email-masked]>
Date: Sun, 25 Feb 2018 14:25:52 +0000

I’ve been playing around with QUIC loss recovery and in my tests I’m
encountering one specific loss pattern which it seems impossible to recover
from. It's pretty rare, because there are a couple of conditions that must
be fulfilled for it to occur:

1. Client and server perform the handshake, no packets are lost so far.
Client and server both arrive at the CONNECTED state, and the server
receives all ACKs for handshake packets it sent. The client receives ACKs
for all handshake packets except for the one containing the FINISHED
message is lost (the packet containing the ACK for the FINISHED is lost).
2. The client starts using 1-RTT keys, and it sends two packets: First, a
packet only containing an ACK, and then a packet containing stream data
(e.g. a request). The request packet is then lost.
3. The server receives the ACK in the 1-RTT packet, and it stops accepting
unencrypted packets according to 6.1.2 of the TLS draft. It doesn’t
generate an ACK in response, since the packet only contained an ACK.
4. The client is now missing acknowledgements for two packets: the
(unencrypted) packet containing the FINISHED message, and the (1-RTT)
packet containing the request. It runs its loss recovery algorithm (
*OnLossDetectionAlarm*), and since there is one outstanding handshake
packet, it retransmit all outstanding handshake packets.

Now we’ve run into a situation we can’t recover from: The server won’t even
open packet sent as a retransmission (since these packets are unencrypted,
and arrive after it already received a 1-RTT packet), and the client will
never retransmit the request packet. Furthermore, the server won't send any
other packets, since it's just waiting for a request from the client.

I think the solution for this is to also retransmit 1-RTT packets in a case
like this. Can we just apply the normal retransmission rules in
*OnLossDetectionAlarm*, even if there are still handshake packets
outstanding?

---

From: Nick Banks <[email-masked]>
Date: Sun, 25 Feb 2018 16:52:02 +0000

Perhaps 6.1.2 should be changed just to say the server must continue to process unprotected packets until all the handshake packets are received, and remove the part about receiving an ACK that acknowledges its handshake messages?

- Nick

From: QUIC <[email-masked]> On Behalf Of Marten Seemann
Sent: Sunday, February 25, 2018 6:26 AM
To: QUIC WG <[email-masked]>
Subject: Unrecoverable loss pattern

I’ve been playing around with QUIC loss recovery and in my tests I’m encountering one specific loss pattern which it seems impossible to recover from. It's pretty rare, because there are a couple of conditions that must be fulfilled for it to occur:

1. Client and server perform the handshake, no packets are lost so far. Client and server both arrive at the CONNECTED state, and the server receives all ACKs for handshake packets it sent. The client receives ACKs for all handshake packets except for the one containing the FINISHED message is lost (the packet containing the ACK for the FINISHED is lost).
2. The client starts using 1-RTT keys, and it sends two packets: First, a packet only containing an ACK, and then a packet containing stream data (e.g. a request). The request packet is then lost.
3. The server receives the ACK in the 1-RTT packet, and it stops accepting unencrypted packets according to 6.1.2 of the TLS draft. It doesn’t generate an ACK in response, since the packet only contained an ACK.
4. The client is now missing acknowledgements for two packets: the (unencrypted) packet containing the FINISHED message, and the (1-RTT) packet containing the request. It runs its loss recovery algorithm (OnLossDetectionAlarm), and since there is one outstanding handshake packet, it retransmit all outstanding handshake packets.

Now we’ve run into a situation we can’t recover from: The server won’t even open packet sent as a retransmission (since these packets are unencrypted, and arrive after it already received a 1-RTT packet), and the client will never retransmit the request packet. Furthermore, the server won't send any other packets, since it's just waiting for a request from the client.

I think the solution for this is to also retransmit 1-RTT packets in a case like this. Can we just apply the normal retransmission rules in OnLossDetectionAlarm, even if there are still handshake packets outstanding?

---

From: Marten Seemann <[email-masked]>
Date: Sun, 25 Feb 2018 17:02:03 +0000

I don’t think this will fix the problem. All handshake packets (sent by the
server) were received by the client and acknowledged (in the first 1-RTT
packet sent by the client).

On Mon 26. Feb 2018 at 00:52, Nick Banks <[email-masked]> wrote:

> Perhaps 6.1.2 should be changed just to say the server must continue to
> process unprotected packets until all the handshake packets are received,
> and remove the part about receiving an ACK that acknowledges its handshake
> messages?
>
>
>
> - Nick
>
>
>
> *From:* QUIC <[email-masked]> *On Behalf Of * Marten Seemann
> *Sent:* Sunday, February 25, 2018 6:26 AM
> *To:* QUIC WG <[email-masked]>
> *Subject:* Unrecoverable loss pattern
>
>
>
> Now we’ve run into a situation we can’t recover from: The server won’t
> even open packet sent as a retransmission (since these packets are
> unencrypted, and arrive after it already received a 1-RTT packet), and the
> client will never retransmit the request packet. Furthermore, the server
> won't send any other packets, since it's just waiting for a request from
> the client.
>
>
>
> I think the solution for this is to also retransmit 1-RTT packets in a
> case like this. Can we just apply the normal retransmission rules in

---

From: Nick Banks <[email-masked]>
Date: Sun, 25 Feb 2018 17:51:44 +0000

Why not? Since the server didn’t get the last handshake packet, it will continue to process unprotected packets. So, when the client retransmits the last handshake message in an unprotected packet, the server processes it. Then everything should continue as usual.

Sent from my Windows 10 phone
[HxS - 15254 - 16.0.9029.2104]

________________________________
From: Marten Seemann <[email-masked]>
Sent: Sunday, February 25, 2018 9:02:03 AM
To: Nick Banks
Cc: QUIC WG
Subject: Re: Unrecoverable loss pattern

I don’t think this will fix the problem. All handshake packets (sent by the server) were received by the client and acknowledged (in the first 1-RTT packet sent by the client).

On Mon 26. Feb 2018 at 00:52, Nick Banks <[email-masked]<mailto:[email-masked]>> wrote:
Perhaps 6.1.2 should be changed just to say the server must continue to process unprotected packets until all the handshake packets are received, and remove the part about receiving an ACK that acknowledges its handshake messages?

- Nick

From: QUIC <[email-masked]<mailto:[email-masked]>> On Behalf Of Marten Seemann
Sent: Sunday, February 25, 2018 6:26 AM
To: QUIC WG <[email-masked]<mailto:[email-masked]>>
Subject: Unrecoverable loss pattern

---

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Feb 2018 09:47:39 +1100

I assume that this is the language you refer to:

   A server MUST process ACK frames in unprotected packets
   until the TLS handshake is reported as complete, or it receives an
   ACK frame in a protected packet that acknowledges all of its
   handshake messages.

That talks about ACK frames, not Finished.

On Mon, Feb 26, 2018 at 1:25 AM, Marten Seemann <[email-masked]> wrote:
> for all handshake packets except for the one containing the FINISHED message
> is lost (the packet containing the ACK for the FINISHED is lost).
> unencrypted packets according to 6.1.2 of the TLS draft. It doesn’t generate
> an ACK in response, since the packet only contained an ACK.
> (unencrypted) packet containing the FINISHED message, and the (1-RTT) packet
> containing the request. It runs its loss recovery algorithm
> (OnLossDetectionAlarm), and since there is one outstanding handshake packet,
> it retransmit all outstanding handshake packets.
>
> OnLossDetectionAlarm, even if there are still handshake packets outstanding?
>
>

---

From: Marten Seemann <[email-masked]>
Date: Mon, 26 Feb 2018 00:58:45 +0000

@Nick: The server did get all handshake packets, please see 1. in my
description. It's the server's ACK for the FINISHED message that is lost,
not the FINISHED message itself.
@Martin: Yes, it is, but I don't think there's anything problematic about
the language in this paragraph. Since the server received ACKs for all the
handshake messages it sent, it makes sense to not open unencrypted packets
any more.

On Mon, Feb 26, 2018 at 6:47 AM Martin Thomson <[email-masked]>
wrote:

> message
> generate
> packet
> even
> case

---

From: Christian Huitema <[email-masked]>
Date: Sun, 25 Feb 2018 17:19:52 -0800

On 2/25/2018 4:58 PM, Marten Seemann wrote:

> description. It's the server's ACK for the FINISHED message that is
> lost, not the FINISHED message itself.
> @Martin: Yes, it is, but I don't think there's anything problematic
> about the language in this paragraph. Since the server received ACKs
> for all the handshake messages it sent, it makes sense to not open
> unencrypted packets any more.

See https://github.com/quicwg/base-drafts/issues/829 and
https://github.com/quicwg/base-drafts/issues/1018 for  discussion of
related issues.

Picoquic manages these issues by handling "ACK of ACK". Normally, it
will send ACK frames that acknowledge all packets received so far,
potentially with a long list of ACK ranges. So if an ACK is lost, the
next ACK will repeat the information that it carried. The list is only
pruned when an "ACK of ACK" is received.

In your example, if the FINISHED message is not acknowledged, the client
will retransmit the stream zero data containing the FINISHED message in
a new Handshake packet. The server will have to send an ACK of that
packet, and the ACK range will also cover the previous packet. There is
no problem for sending that ACK. You cannot acknowledge a protected
packet in a clear text message, but nothing prevents you from
acknowledging clear text packets in protected messages.

-- Christian Huitema

---

From: Marten Seemann <[email-masked]>
Date: Mon, 26 Feb 2018 01:30:51 +0000

The problem is that the server will not open the unencrypted packet
containing the retransmission of the FINISHED, since it already completed
the handshake AND received ACKs for all its handshake packets. We *could*
fix this problem by making the server accept unencrypted packets
indefinitely, but this comes with a whole range of problems of
man-on-the-side attacks.

On Mon, Feb 26, 2018 at 9:20 AM Christian Huitema <[email-masked]>
wrote:

> Picoquic manages these issues by handling "ACK of ACK". Normally, it will
> send ACK frames that acknowledge all packets received so far, potentially
> with a long list of ACK ranges. So if an ACK is lost, the next ACK will
> repeat the information that it carried. The list is only pruned when an
> "ACK of ACK" is received.
>
> will retransmit the stream zero data containing the FINISHED message in a
> new Handshake packet. The server will have to send an ACK of that packet,
> and the ACK range will also cover the previous packet. There is no problem
> for sending that ACK. You cannot acknowledge a protected packet in a clear
> text message, but nothing prevents you from acknowledging clear text
> packets in protected messages.
>
>
> -- Christian Huitema
>

---

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Feb 2018 13:07:46 +1100

Yes, this is a real issue.  It arises because the packet that would
normally trigger loss detection for the request packet (the ACK for
the Finished) never gets sent because the server believes the client
to be quiescent.  The server believes that because it discards the
cleartext packets that it receives.

Client sends ...., Finished, ACK, Y. Then Y is lost.  Server
acknowledges up to Finished, but this acknowledgment is lost. Client
detects loss of the Finished.  It does this on a timer, because if the
server was sending data, the client would receive the ACK for the
Finished and things would work out.

If the handshake wasn't special, the client would send Finished again
using the 1-RTT keys, and this wouldn't be a problem.  But in this
case it resends Finished in a new packet and the server throws that
away.  The client never does TLP or RTO for Y.  See
<https://quicwg.github.io/base-drafts/draft-ietf-quic-recovery.html#rfc.section.3.4.7.4>
for that algorithm.

The general case is a little worrying: as long as the Finished is
outstanding, the client will not repair loss from other packets (see
<https://quicwg.github.io/base-drafts/draft-ietf-quic-recovery.html#rfc.section.3.4.8>).

You might consider this failing to be a result of trying to compose
the various timers into a single alarm.  This wouldn't be a problem if
the RTO and TLP for ordinary packets proceeded as normal.  One extra
timer during the handshake isn't that much additional burden.  But
maybe there is a more elegant solution.

On Mon, Feb 26, 2018 at 12:30 PM, Marten Seemann
<[email-masked]> wrote:
>> https://github.com/quicwg/base-drafts/issues/1018 for  discussion of related
>> issues.
>>
>> repeat the information that it carried. The list is only pruned when an "ACK
>> of ACK" is received.
>>
>> text message, but nothing prevents you from acknowledging clear text packets
>> in protected messages.
>>
>>
>> -- Christian Huitema

---

From: Christian Huitema <[email-masked]>
Date: Sun, 25 Feb 2018 23:28:43 -0800

> cleartext packets that it receives.
We debated that with issue #1018
(https://github.com/quicwg/base-drafts/issues/1018). At the time, we saw
two options:

1) Allow the "finished" message to be transmitted in 1-RTT protected
packets. This was nixed because it seems to interfere with the formal
proofs of TLS 1.3.

2) Allow the server to accept retransmission of handshake packets
intermixed with 1-RTT protected packet. Clearly, this open a DOS attack,
as third parties can now inject such packets, consume packet numbers,
and possibly cause good data to be dropped.

I was not aware that the spec pushed a third alternative, to mandate
that the server to just drop handshake packets after receiving the first
copy of the finished message. As Marten says, that puts the client in a
bad position if the first ACK is lost and the server is silent after that.

The solution might be to send a "Finished received" frame in the
protected data flow, and require an ACK for that frame. That way, the
problem would really be solved.

-- Christian Huitema

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 26 Feb 2018 02:33:48 -0500

That is sort of a handshake of the handshake, but I like the idea.
Could that somehow extend to 0-RTT as a more general concept?

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Mon, 26 Feb 2018 02:36:57 -0500

Another thing:

The concept might be more general handover in path-migration, multi-path,
visible path specific sequence numbers, and rekeying.
Rather than having 7 or so different constructs, there might be an
underlying principle called handoff?

Kind Regards,
Mikkel Fahnøe Jørgensen

---

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Feb 2018 19:51:37 +1100

The issue in #1018 (as I understood it) was the fact that Finished
could be protected (and thereby authenticated), but it was not.  Not
having it protected makes it vulnerable to all sorts of attack.

This is different, it's not an attack, it's just an unfortunate
interaction between the loss recovery algorithms and the TLS mapping.

Other than running multiple timers as I suggested, you could also
force the server to respond to cleartext packets with a repeat of its
ACK.  It doesn't even have to look at what it received, it just plays
out the last ACK.  That's what we do in our DTLS 1.3 implementation.
It works.  The trick there is that once you have an ACK for the ACKs
that acknowledge the handshake you stop the special behaviour.

---

From: Christian Huitema <[email-masked]>
Date: Mon, 26 Feb 2018 10:44:51 -0800

> interaction between the loss recovery algorithms and the TLS mapping.

Actually, the issue was that allowing Finished to be repeated in clear
text allows for a DOS attack on the server. The spec changed to ignore
handshake packets after Finished is received once. That closes the DOS
issue, but it opens the "ACK of Finished" issue.
 
> that acknowledge the handshake you stop the special behaviour.
That was actually the first solution I thought off. That works too, but
there are two downsides. First, you get a "twitch trigger" -- send an
handshake packet, get the server to send an ACK. Not a very big deal,
but slightly annoying. Second, it relies not only on implementing ACK of
ACK, but also on triggering a special behavior for the ACK of the ACK of
the last handshake packet. Many implementations do ACK of ACK
management, but grafting a special case in that path is a bit tricky.
That was my thought process before proposing a simple one byte
"handshake complete" frame. The special frame is easier to integrate in
the receive processing.

-- Christian Huitema