Subject: Re: [quicwg/base-drafts] Packet number skipping and entropy (#305)

From: Martin Thomson <[email-masked]>
Date: Fri, 05 May 2017 06:35:20 -0700

I think that @mikkelfj has it right here, the notion that we might somehow gain some signal from skipping packets is a roundabout way of doing this.  We could be far more direct and add an ARE_YOU_THERE frame.  ARE_YOU_THERE would contain some randomness and could be used to solicit a YES_I_AM frame that echoes that randomness, thereby providing that it was successfully received.  We probably want that for #161 anyhow.  Then we can do away with this slightly dodgy language.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/305#issuecomment-299466054

---

From: MikkelFJ <[email-masked]>
Date: Fri, 05 May 2017 07:39:15 -0700

Just to be clear - my comment was also a request for a guarantee that sequence numbers do not have large unnatural gaps such that packets with unexpected gaps can be rejected early. Otherwise such gaps can be exploided by maliciously inserting gaps to harm a poorly implemented end-point and consequently end-points must implement logic to protect against this, for example using comparatively slow balanced search trees instead of linear buffers.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/305#issuecomment-299482690

---

From: janaiyengar <[email-masked]>
Date: Fri, 05 May 2017 18:51:37 -0700

You definitely do not want to disallow large gaps in sequence spaces, since large BDPs can have large gaps. 

QUIC packet numbers are different from TCP sequence numbers in that the receiver handles these cases, allowing servers to do interesting things with packet numbers. There are server architectures that can use this to good effect, but splitting sending of different objects over different packet number spaces.

I don't see the DoS here, BTW -- this is the data receiver, meaning that it's getting data from the server. How do you DoS by adding a gap in packet number? Gaps needs to be handled at the receiver and the size of the gap does not help really, since it's not like you're allocating a bitmap for packet numbers (if you are, you really shouldn't be.) Bear in mind that any gaps that are reported or state at the receiver with a large gap in it only lasts for 1 RTT, after which the receiver can discard this state entirely. I would strongly encourage you to write code that does not assume sequential packet numbers. Sequential shoukd be the common case, but the receiver shouldn't collapse on large gaps.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/305#issuecomment-299608391

---

From: janaiyengar <[email-masked]>
Date: Fri, 05 May 2017 19:01:30 -0700

@martinthomson Using a packet number jump isn't a hack -- it's a design principle and we should use it to good effect. The packet number was designed to be separate from everything else. The client associates no particular semantic with gaps -- note that the receiver does not assume *anything* about gaps, except that they need to be reported. Gaps are ultimately for the sender to manage. And once the receiver is certain that the sender has heard about the gap, it stops reporting them. All this allows a sender to freely use packet number space in innovative ways, including this one.

Further, remember that for a DDoS towards a victim, you need a large number of such connections, and the attacked has to guess the jump correctly for *all* these connections. For a large enough jump, that's diminishing probabilities.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/305#issuecomment-299608882

---

From: MikkelFJ <[email-masked]>
Date: Fri, 05 May 2017 23:19:39 -0700

> You definitely do not want to disallow large gaps in sequence spaces, since large BDPs can have large gaps.

This is not what I am a saying - you can have gaps associated with the number of expected packets in flight, and it can be large - but you need to allocated state for all these packets one way or another. Sometimes it can be done compactly as run length encoded maps etc., but the point is that it is bounded and controllable, and that violating sequences beyond that can easily be rejected. So I am suggesting that the sender is not permitted to issue unnecessary gaps. (Connection migration might be an exception).

> QUIC packet numbers are different from TCP sequence numbers in that the receiver handles these cases, allowing servers to do interesting things with packet numbers. There are server architectures t…

But still limited by the connection flow control window. Again I'm not arguing against gaps as long as all sequences are being used timely - but it is a good point that you should not require packets to be transmitted in sequence.

> I don't see the DoS here, BTW -- this is the data receiver, meaning that it's getting data from the server.

You cannot make any assumptions on who is sending what, and who is hostile. The classic http client/server model is just one use case, and even here massive data volumes can flow both ways.

> How do you DoS by adding a gap in packet number? Gaps needs to be handled at the receiver and the size of the gap does not help really, since it's not like you're allocating a bitmap for packet numbers (if you are, you really shouldn't be.)

The DoS is preventable - the point is that it forces the implementation to take preventative measures. For example some part of the Linux Kernel is using an AVL tree instead of a hash (as I understand) because hash tables are vulnerable to collision attacks. So the possibility of DoS is a burden on quality implementations and a real concern for lesser implementations. As I recall a study showed many vulnerabilities in DNS name lookups.

The attack on a quality implementation still exists because you design data such every packet requires a distance to the next packet. For example an binary search tree node typically requires 3x8 bytes, and more for interval handling so at least 32 bytes. When ranges fall in line, a single node can handle several sequences but if not you use that much space. For 1 million packets in flight that is 32MB which is not enough for a serious DoS attack, especially since the sender must provide data to feed the attack. But the implementatation still needs to take its precautions. If you could allocate a bitmap for 1 million packets, you would only need  125K to track which packets have been seen already. This also impacts cache performance and overall system load. Even if the binary interval tree was lucky to handle more dense ranges, it likely couldn't achieve the same density as a bitmap, especially if the bitmap is clustered - meaning that ranges for all ones can be collapsed. You can get clever and mix binary search trees and bitmaps for arbitrary ranges, but it is much more complex and likely not done in the typical implementation you will see.

So overall, no it is not a DoS attack if handled correctly, but it is an extra burden on the implemtation.

> Bear in mind that any gaps that are reported or state at the receiver with a large gap in it only lasts for 1 RTT, after which the receiver can discard this state entirely.

For 1 RTT you can draft a sequence space spanning 2^31 values, but you are right that it does limit the effectiveness of an attack. And as far as I can see (not 100% sure) you cannot limit this to 1 RTT because an attacker is not required to submit timely ACKs' and the receiver cannot reasonable discard state after 1 RTT if it on average expects lazy ACK's.

> I would strongly encourage you to write code that does not assume sequential packet numbers. Sequential shoukd be the common case, but the receiver shouldn't collapse on large gaps.

Absolutely - I just saying that it would be much simpler to implement effective guards when the spec provides stronger contraints on valid ranges.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/305#issuecomment-299619140