Subject: [Plus] Supporting connection tracking and basic diagnostics: a minimal PLUS

From: Brian Trammell <[email-masked]>
Date: Fri, 9 Dec 2016 12:55:15 +0100

Greetings, all,

We were sitting around a whiteboard yesterday, thinking about (1) how to implement the signals required to drive the state machine outlined in the -plus-statefulness-01 draft, and (2) how to provide on-path diagnosability as we're discussing in the thread on Juho's blog post. Indeed, we think these two use cases are by far the most important for PLUS, in that they provide equivalent-to-TCP support for basic operations and troubleshooting practices for encrypted, UDP-encapsulated transports like QUIC, and one could implement either of them in QUIC directly without much disruption.

We came up with two implementation sketches, both of which use the same header fields to drive the association and confirmation signals as well as basic measurability.

The simpler one is pretty much the design Jana alluded to in his previous message. It looks kind of like TCP on the wire, and has basically the same properties.It uses three header fields: a connection ID which appears in packets of both directions and is chosen by the connection initiator; a packet serial number (PSN) whose initial value in each direction is chosen randomly by the sender (like the TCP sequence number, and as under discussion for QUIC) and is incremented by one for each packet sent regardless of content or lack thereof (like the QUIC packet number); and a maximum packet serial echo, which is the highest packet number received by the sender before a packet was sent.

This provides an association signal on the initial echo of the initiator's PSN, and a confirmation signal on the initiator's initial echo of the responder's PSN -- just like the ack numbers on the SYN/ACK and ACK legs of the TCP handshake. The connection ID here simply provides additional bits of protection against completely off-path attempts to force the state machine to tick over. Note there's no need for SYN or ACK flags -- the association and confirmation signals continually demonstrate that each side has seen packets from the other side.

A stop signal is considered authentic if it has a correct connection ID and a plausible PSN. This is path-verifiable, but provides no protection against on-path or path-side injection attacks against state on middleboxes (though, note that since even unencrypted headers are authenticated, the endpoint can always detect an attempt to inject a stop). A variation of the mechanism described in statefulness-01 would use a two-way stop signal: a stop is only considered valid along the path if one endpoint sends a stop signal in reply to the other endpoint's stop signal. This would make the path-side injection much harder to perform: in order to remove state on a given middlebox (presuming said middlebox isn't stupid about accepting packets from anywhere), the attacker would need to be able to inject packets on the interfaces facing both endpoints.

One-point measurement of the PSN and echo streams gives you two-sided RTT and upstream loss and reordering. Coordinated two-point analysis gives you a lot more. As noted, though, two-point analysis is far more complex.

This approach has the advantage of being extremely simple (it meets the "someone with wireshark could reverse-engineer this in an hour or so" requirement), and very close to what's there in QUIC right now. If implemented with a small number of possible header layouts (preferably one) the wire image could be trivially offloaded to hardware.

It all of the disadvantages as SEQ/ACK tracking in TCP, and of resistance to off-path meddling that TCP sequence numbers do, though it does give better RTT indication on lossy links (since the echo is always the max packet number, not the highest continuous ack), and two-side stop is better than RST at resisting path-side attacks. The definition of "plausible" next PSN or "plausible" echo when seen at a midpoint device is fuzzy, which could lead to difficult to debug problems with middleboxes that try to drop packets with implausible values (as some state-tracking TCP firewalls do now).

The second one replaces the packet number and the echo with a token and a nonce. The connection initiator chooses an initial random token and a nonce. The connection responder applies a function to the token and nonce to generate its own token, and chooses a random nonce. Each side generates a new token from the token and nonce it receives each time the token it receives changes. Like the simpler implementation, this one provides continual association and confirmation signals. It also provides one-point measurement of RTT, since the token change is an RTT-clocked signal. The RTT clock would also behave odd ways under high-reordering situations, and additional complexity (which involves remembering a few past tokens, but which we didn't work through) would be needed to fix that.

The token and nonce could be separate from an additional connection ID, or the connection ID and the token could be the same -- though this would require much more state to be kept everywhere in order to allow the connection ID to be useful for NAT rebinding and injection defense purposes.

The main advantage over the simpler approach is that the fuzziness around plausible PSNs and echoes goes away, as does the predictability of association and confirmation values after the initial connection establishment. However, it does not provide loss measurement without additional information, and it places more state and processing requirements on endpoints.

Either of these mechanisms could used together with a path-and-endpoint verifiable, on-path and side-path attack resistant stop signal: during connection setup each endpoint generates a random value, and exposes the result of the application of a hash function to that random value as its stop signal proof. To send a stop signal, it reveals the random value as a stop signal verification (this is the essence of PR#20 on QUIC). Any endpoint or on-path device can verify that the hash of the verification is the proof. Of course, devices that don't keep the proof value (or never saw it) can't verify it. The tradeoff here is additional complexity versus additional resistance against path-side injection meddling with state on middleboxes.

Simple packet number and echo signaling for association and confirmation signaling with two-way stop seems to us like a reasonable "minimal functionality set" at the moment.

Thoughts?

Cheers,

Brian and Mirja

---

From: Ian Swett <[email-masked]>
Date: Fri, 9 Dec 2016 10:40:53 -0500

I have been discussing the first option with people for a while, and
everyone has indicated it's relatively simple to implement, potentially
even in hardware, and provides quite a bit of extra useful information(RTT,
approximate bandwidth) over QUIC's status quo.

I believe packet numbers being in order makes the first case both easier to
implement and provides some valuable extra information(it's easy to infer
upstream loss and reordering), so I think it's definitely a better approach.

Also, given an equal number of bytes spent on the echo, I think they both
have about the same fuzziness properties.  For example, if 2 bytes were
used in the first case, assuming this echo must be monotonically
increasing, an ack or packet gap of over 65,000 packets would have to occur
for the signal to be misinterpreted.  If we're getting 65,000 packet gaps,
we might be outside the realm of QUIC's wire format to help you diagnose
your network issues, to put it mildly.

On Fri, Dec 9, 2016 at 6:55 AM, Brian Trammell <[email-masked]> wrote:

> Greetings, all,
>
> We were sitting around a whiteboard yesterday, thinking about (1) how to
> implement the signals required to drive the state machine outlined in the
> -plus-statefulness-01 draft, and (2) how to provide on-path diagnosability
> as we're discussing in the thread on Juho's blog post. Indeed, we think
> these two use cases are by far the most important for PLUS, in that they
> provide equivalent-to-TCP support for basic operations and troubleshooting
> practices for encrypted, UDP-encapsulated transports like QUIC, and one
> could implement either of them in QUIC directly without much disruption.
>
> We came up with two implementation sketches, both of which use the same
> header fields to drive the association and confirmation signals as well as
> basic measurability.
>
>
> The simpler one is pretty much the design Jana alluded to in his previous
> message. It looks kind of like TCP on the wire, and has basically the same
> properties.It uses three header fields: a connection ID which appears in
> packets of both directions and is chosen by the connection initiator; a
> packet serial number (PSN) whose initial value in each direction is chosen
> randomly by the sender (like the TCP sequence number, and as under
> discussion for QUIC) and is incremented by one for each packet sent
> regardless of content or lack thereof (like the QUIC packet number); and a
> maximum packet serial echo, which is the highest packet number received by
> the sender before a packet was sent.
>
> This provides an association signal on the initial echo of the initiator's
> PSN, and a confirmation signal on the initiator's initial echo of the
> responder's PSN -- just like the ack numbers on the SYN/ACK and ACK legs of
> the TCP handshake. The connection ID here simply provides additional bits
> of protection against completely off-path attempts to force the state
> machine to tick over. Note there's no need for SYN or ACK flags -- the
> association and confirmation signals continually demonstrate that each side
> has seen packets from the other side.
>
> A stop signal is considered authentic if it has a correct connection ID
> and a plausible PSN. This is path-verifiable, but provides no protection
> against on-path or path-side injection attacks against state on middleboxes
> (though, note that since even unencrypted headers are authenticated, the
> endpoint can always detect an attempt to inject a stop). A variation of the
> mechanism described in statefulness-01 would use a two-way stop signal: a
> stop is only considered valid along the path if one endpoint sends a stop
> signal in reply to the other endpoint's stop signal. This would make the
> path-side injection much harder to perform: in order to remove state on a
> given middlebox (presuming said middlebox isn't stupid about accepting
> packets from anywhere), the attacker would need to be able to inject
> packets on the interfaces facing both endpoints.
>
> One-point measurement of the PSN and echo streams gives you two-sided RTT
> and upstream loss and reordering. Coordinated two-point analysis gives you
> a lot more. As noted, though, two-point analysis is far more complex.
>
> This approach has the advantage of being extremely simple (it meets the
> "someone with wireshark could reverse-engineer this in an hour or so"
> requirement), and very close to what's there in QUIC right now. If
> implemented with a small number of possible header layouts (preferably one)
> the wire image could be trivially offloaded to hardware.
>
> It all of the disadvantages as SEQ/ACK tracking in TCP, and of resistance
> to off-path meddling that TCP sequence numbers do, though it does give
> better RTT indication on lossy links (since the echo is always the max
> packet number, not the highest continuous ack), and two-side stop is better
> than RST at resisting path-side attacks. The definition of "plausible" next
> PSN or "plausible" echo when seen at a midpoint device is fuzzy, which
> could lead to difficult to debug problems with middleboxes that try to drop
> packets with implausible values (as some state-tracking TCP firewalls do
> now).
>
>
> The second one replaces the packet number and the echo with a token and a
> nonce. The connection initiator chooses an initial random token and a
> nonce. The connection responder applies a function to the token and nonce
> to generate its own token, and chooses a random nonce. Each side generates
> a new token from the token and nonce it receives each time the token it
> receives changes. Like the simpler implementation, this one provides
> continual association and confirmation signals. It also provides one-point
> measurement of RTT, since the token change is an RTT-clocked signal. The
> RTT clock would also behave odd ways under high-reordering situations, and
> additional complexity (which involves remembering a few past tokens, but
> which we didn't work through) would be needed to fix that.
>
> The token and nonce could be separate from an additional connection ID, or
> the connection ID and the token could be the same -- though this would
> require much more state to be kept everywhere in order to allow the
> connection ID to be useful for NAT rebinding and injection defense purposes.
>
> The main advantage over the simpler approach is that the fuzziness around
> plausible PSNs and echoes goes away, as does the predictability of
> association and confirmation values after the initial connection
> establishment. However, it does not provide loss measurement without
> additional information, and it places more state and processing
> requirements on endpoints.
>
>
> Either of these mechanisms could used together with a path-and-endpoint
> verifiable, on-path and side-path attack resistant stop signal: during
> connection setup each endpoint generates a random value, and exposes the
> result of the application of a hash function to that random value as its
> stop signal proof. To send a stop signal, it reveals the random value as a
> stop signal verification (this is the essence of PR#20 on QUIC). Any
> endpoint or on-path device can verify that the hash of the verification is
> the proof. Of course, devices that don't keep the proof value (or never saw
> it) can't verify it. The tradeoff here is additional complexity versus
> additional resistance against path-side injection meddling with state on
> middleboxes.
>
>
> Simple packet number and echo signaling for association and confirmation
> signaling with two-way stop seems to us like a reasonable "minimal
> functionality set" at the moment.
>
> Thoughts?
>
> Cheers,
>
> Brian and Mirja
>
>
> _______________________________________________
> Plus mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/plus
>
>

---

From: Tommy Pauly <[email-masked]>
Date: Sat, 10 Dec 2016 16:35:22 -0800

I agree with Ian that the first option is probably easier and more viable as a solution. The second option is attractive in how it makes the association and confirmation values less predictable, and thus more trustworthy. However, the extra state required to debug and reconstruct the flow does seem too high if want wide adoption.

When we are looking at the first option, you mentioned strategies to avoid on-path injection attacks of stops. Is there any attack that could be made regarding the PSN? If the attacker can modify PSN values or inject packets with higher PSN values in either direction, what side effects can we see? I'm assuming that the endpoints themselves will be able to validate the authenticity of the fields, but could a middle box that is trying to monitor the plausible-ness of the PSN get thrown off? Or does it only ever adjust its plausibility window when it sees a PSN acknowledged? (To that end, if an acknowledgment value is faked, what does that do?)

—Tommy

> On Dec 9, 2016, at 7:40 AM, Ian Swett <[email-masked]> wrote:
> 
> I have been discussing the first option with people for a while, and everyone has indicated it's relatively simple to implement, potentially even in hardware, and provides quite a bit of extra useful information(RTT, approximate bandwidth) over QUIC's status quo.
> 
> I believe packet numbers being in order makes the first case both easier to implement and provides some valuable extra information(it's easy to infer upstream loss and reordering), so I think it's definitely a better approach.
> 
> Also, given an equal number of bytes spent on the echo, I think they both have about the same fuzziness properties.  For example, if 2 bytes were used in the first case, assuming this echo must be monotonically increasing, an ack or packet gap of over 65,000 packets would have to occur for the signal to be misinterpreted.  If we're getting 65,000 packet gaps, we might be outside the realm of QUIC's wire format to help you diagnose your network issues, to put it mildly. 
> 
> 
> 
> On Fri, Dec 9, 2016 at 6:55 AM, Brian Trammell <[email-masked] <mailto:[email-masked]>> wrote:
> Greetings, all,
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/plus <https://www.ietf.org/mailman/listinfo/plus>
> 
>

---

From: "Christian Huitema" <[email-masked]>
Date: Sat, 10 Dec 2016 22:33:35 -0800

On Saturday, December 10, 2016 4:35 PM, Tommy Pauly wrote:
>
> I agree with Ian that the first option is probably easier and more viable as a 
> solution. The second option is attractive in how it makes the association and 
> confirmation values less predictable, and thus more trustworthy. However, 
> the extra state required to debug and reconstruct the flow does seem too high
> if want wide adoption.

I too think that the first option is more practical. I am a bit concerned that the "token" suggested in the second option does not have any link to the mechanism of the transport protocol. That means lazy implementation could take their sweet time and "rotate the token" once in a blue moon, making it seriously unfit for RTT assessment. 

In the first option, the echo is the "last seen sequence number" that would otherwise be carried in the ACK frame. If we move it out of the ACK frame and into the header, then we have pretty much a guarantee that applications will do it right. I like that. I also like that the scheme does not make the "connection start" special, and works just as well after a rerouting or a NAT state change.

OTOH, there is going to be a "feature interaction" between this sequence+echo scheme and the senders' strategy of skipping some sequence numbers in order to verify that the recipients are not making up ACKS. The intermediate boxes will have no way to distinguish between a packet number voluntarily skipped by the sender, and a packet loss between the sender and the middlebox. I hope this won't affect the "wireshark diagnostics" too much.

> When we are looking at the first option, you mentioned strategies to avoid on-path
> injection attacks of stops. 

I like the "two ways stop". It definitely increases the robustness. Also, sending the sequence number and last seen in "clear text" solves the "guess the sequence number" issue for the "rebooted server." Maybe we can use EKR's scheme after all.

> ... Is there any attack that could be made regarding the PSN? If the attacker can modify 
> PSN values or inject packets with higher PSN values in either direction, what side effects
> can we see? I'm assuming that the endpoints themselves will be able to validate the
> authenticity of the fields, but could a middle box that is trying to monitor the 
> plausible-ness of the PSN get thrown off? Or does it only ever adjust its plausibility
> window when it sees a PSN acknowledged? (To that end, if an acknowledgment
> value is faked, what does that do?)

That's a very good observation, and in fact it applies to current QUIC as well. A man-on-the side can inject a series of plausible packets before the sender does. The "real" packets coming from the sender will repeat packet numbers that are 'already seen'. A middlebox that is too clever might drop those in an attempt to "remove duplicates." We can always say that middleboxes should not try to be too clever, but that's a bit like saying that the bubonic plague should be nicer...

-- Christian Huitema

---

From: Ian Swett <[email-masked]>
Date: Sun, 11 Dec 2016 09:51:06 -0500

On Sun, Dec 11, 2016 at 1:33 AM, Christian Huitema <[email-masked]>
wrote:

> I too think that the first option is more practical. I am a bit concerned
> that the "token" suggested in the second option does not have any link to
> the mechanism of the transport protocol. That means lazy implementation
> could take their sweet time and "rotate the token" once in a blue moon,
> making it seriously unfit for RTT assessment.
>
> In the first option, the echo is the "last seen sequence number" that
> would otherwise be carried in the ACK frame. If we move it out of the ACK
> frame and into the header, then we have pretty much a guarantee that
> applications will do it right. I like that. I also like that the scheme
> does not make the "connection start" special, and works just as well after
> a rerouting or a NAT state change.
>
> OTOH, there is going to be a "feature interaction" between this
> sequence+echo scheme and the senders' strategy of skipping some sequence
> numbers in order to verify that the recipients are not making up ACKS. The
> intermediate boxes will have no way to distinguish between a packet number
> voluntarily skipped by the sender, and a packet loss between the sender and
> the middlebox. I hope this won't affect the "wireshark diagnostics" too
> much.
>

We could specify that if a peer wants to skip packet numbers, it should be
by more than 256, assuming 256 packet gaps are rare(which they are, though
they do happen).    Or some other known approach that is relatively simple
to identify.

> I like the "two ways stop". It definitely increases the robustness. Also,
> sending the sequence number and last seen in "clear text" solves the "guess
> the sequence number" issue for the "rebooted server." Maybe we can use
> EKR's scheme after all.
>
> That's a very good observation, and in fact it applies to current QUIC as
> well. A man-on-the side can inject a series of plausible packets before the
> sender does. The "real" packets coming from the sender will repeat packet
> numbers that are 'already seen'. A middlebox that is too clever might drop
> those in an attempt to "remove duplicates." We can always say that
> middleboxes should not try to be too clever, but that's a bit like saying
> that the bubonic plague should be nicer...
>
>
Agreed.  Since QUIC does not reuse packet numbers, the only times a
middlebox would expect to see duplicate PSNs is if the network duplicates
them(insanely rare) or if there is an attack.  In both cases, the best
course of action is to do nothing and not remove duplicates, since only
endpoints know which packets are valid, so there is no practical incentive
for a middlebox to do that.  That being said, this and many other points
may need to be documented to reduce the chances of someone trying to be
clever.

---

From: "Christian Huitema" <[email-masked]>
Date: Sun, 11 Dec 2016 08:47:05 -0800

On Sunday, December 11, 2016 6:51 AM, Ian Swett wrote:
> On Sun, Dec 11, 2016 at 1:33 AM, Christian Huitema <mailto:[email-masked]> wrote:
>> ...OTOH, there is going to be a "feature interaction" between this sequence+echo scheme and 
>> the senders' strategy of skipping some sequence numbers in order to verify that the recipients
>> are not making up ACKS. The intermediate boxes will have no way to distinguish between a 
>> packet number voluntarily skipped by the sender, and a packet loss between the sender and
>> the middlebox. I hope this won't affect the "wireshark diagnostics" too much.
>
> We could specify that if a peer wants to skip packet numbers, it should be by more than 256,
> assuming 256 packet gaps are rare(which they are, though they do happen).    Or some other 
> known approach that is relatively simple to identify.

If you make it easier to identify, then you defeat the purpose of the packet skipping. Suppose a bad receiver, intent on setting a DOS attack. Its strategy is to ACK as quickly as possible, regardless of losses. The sender detects ACK of packets that were not sent, and aborts the connection. But if the skipping is easy to detect by middleboxes, it is also easy to detect by the bad receiver, which will suspend its ACK everything strategy if it detects a test...

-- Christian Huitema

---

From: Ian Swett <[email-masked]>
Date: Sun, 11 Dec 2016 12:08:18 -0500

Good point, though they'd only know it afterwards.  At which point the
connection would be torn down.

I'm not sure it's critical the receiver is unaware they're being tested or
not.  And if the connection is suddenly torn down, presumably they'll
realize they were being tested anyway?

On Sun, Dec 11, 2016 at 11:47 AM, Christian Huitema <[email-masked]>
wrote:

> If you make it easier to identify, then you defeat the purpose of the
> packet skipping. Suppose a bad receiver, intent on setting a DOS attack.
> Its strategy is to ACK as quickly as possible, regardless of losses. The
> sender detects ACK of packets that were not sent, and aborts the
> connection. But if the skipping is easy to detect by middleboxes, it is
> also easy to detect by the bad receiver, which will suspend its ACK
> everything strategy if it detects a test...
>
> -- Christian Huitema
>
>
>
>
>

---

From: Brian Trammell <[email-masked]>
Date: Mon, 12 Dec 2016 10:44:19 +0100

hi Ian,

> On 09 Dec 2016, at 16:40, Ian Swett <[email-masked]> wrote:
> 

Indeed.

However, there are two issues to consider here:

(1) ways in which the PSN/echo can fail in terms of exposing information for measurement. Agreed, 16 bits is more than enough here.

(2) ways in which the PSN/echo can fail in terms of exposing information for on-path state maintenance, and this is the fuzziness I was referring to. On further consideration, it's not clear to me this is all that important, though: if you have sufficient bits in the connection ID (and the connection ID appears on each packet), then the additional bits of resistance to off path injection window plausibility checks give you probably aren't worth the effort.

(You do need plausible values for PKT and ECHO on close bits, but since the close packet should be the last packet in sequence in each direction, there's no fuzziness in the window at all).

Cheers,

Brian

---

From: Brian Trammell <[email-masked]>
Date: Mon, 12 Dec 2016 11:07:29 +0100

hi Christian, all,

> On 11 Dec 2016, at 07:33, Christian Huitema <[email-masked]> wrote:
> 
> I too think that the first option is more practical.

Having had a weekend to think a bit more about both of them, I'll add my voice to this chorus.

> I am a bit concerned that the "token" suggested in the second option does not have any link to the mechanism of the transport protocol. That means lazy implementation could take their sweet time and "rotate the token" once in a blue moon, making it seriously unfit for RTT assessment.

There are other ways in which the RTT assessment can go awry. You need a little more state (and, on path, an extra addition) to do RTT measurement with the first option, but it has the advantage over its TCP counterpart that the packet number *always* increments, even for ACKs, and the echo number is always the max packet number seen, so you can get good upstream RTT component measurements even if all the client sends is ACKs.

> In the first option, the echo is the "last seen sequence number" that would otherwise be carried in the ACK frame. If we move it out of the ACK frame and into the header, then we have pretty much a guarantee that applications will do it right. I like that.

Well, to be fair, the first option also allows two endpoints running a private transport protocol to collude to lie to the path about their RTT by agreeing to manipulate echo numbers. I'm not sure it's either possible or useful to prevent that, though.

> I also like that the scheme does not make the "connection start" special, and works just as well after a rerouting or a NAT state change.

That was a hard requirement of our design exercise. It's also the main problem I can see with the revealed-hash stop signal: you need to send the proof value somewhen, and the exposure of that proof is a special "connection start", unless it is exposed periodically (which comes with a cost in overhead).

> I like the "two ways stop". It definitely increases the robustness. Also, sending the sequence number and last seen in "clear text" solves the "guess the sequence number" issue for the "rebooted se…

The two-way stop and the revealed-hash stop are independent, so you could also do both if you wanted to.

> That's a very good observation, and in fact it applies to current QUIC as well. A man-on-the side can inject a series of plausible packets before the sender does. The "real" packets coming from the…

This might be an argument for recommending against plausibility checks for middleboxes for anything other than the two-way stop. Unlike with TCP, in any case they cannot assume anything about window dynamics based upon assumed knowledge of the reliability or congestion control schemes in place. Whether this recommendation would be widely followed is a different question.

Since the endpoints should be able to detect a middlebox-injected packet (at least as long as there's a requirement that *every* packet have an (encrypted) transport header above the common unencrypted header, which, IMO, there is), really these attacks are all about middleboxes messing with each other. If the endpoint can always detect, then it can also close and attempt to reinitiate, or at least throw up a "your network is messing with you" error.

Cheers,

Brian