Subject: Re: [quicwg/base-drafts] Are random packet number skips still relevant for opportunistic ACK protection? (#1030)

From: Martin Thomson <[email-masked]>
Date: Mon, 01 Jan 2018 22:46:09 +0000 (UTC)

I think that the main defense here is explicit path verification.  I would prefer that we remove gaps entirely.  That also means changing the linkability defense, which I want to do for other reasons.

-- 
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/1030#issuecomment-354682392

---

From: Marten Seemann <[email-masked]>
Date: Thu, 04 Jan 2018 10:47:36 +0000 (UTC)

I realized that my comment 2 weeks ago is wrong.

The optimistic ACK attack in QUIC comes in two variants. The first is a traffic redirection attack against a third party, which can be solved by explicit path verification. The second is a resource exhaustion attack against the server.

-- 
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/1030#issuecomment-355252383

---

From: Martin Thomson <[email-masked]>
Date: Thu, 04 Jan 2018 22:34:09 +0000 (UTC)

How does a client mount that attack?  Do they send optimistic ACKs in order to get the server to open their congestion window and send more data?  Wouldn't that be a symmetric attack?

-- 
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/1030#issuecomment-355418502

---

From: MikkelFJ <[email-masked]>
Date: Thu, 04 Jan 2018 23:23:16 +0000 (UTC)

If the ACK is contained in a packet encrypted with the connection ID, the attacker must known the connection ID or guess 1/2^64. So effectively the attacker is able to listen to the transmission. How would path verification improve on this before the handshake is complete if the attacker can observe traffic and spoof the source?

-- 
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/1030#issuecomment-355428122

---

From: Marten Seemann <[email-masked]>
Date: Fri, 05 Jan 2018 02:04:21 +0000 (UTC)

@martinthomson: The client acks packets that is hasn't received. By doing so, the server will increase the congestion window for this connection and flood the network with packets. Packets will get lost, but since the client is just acking everything, none of those losses will be reported.

The only thing the client needs to take care of for this attack is to only ack packets that have actually been sent (and not any yet unsent packet numbers, since that would be connection error). This shouldn't be too hard, since the increase of the congestion window is predictable.

-- 
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/1030#issuecomment-355453544

---

From: Martin Thomson <[email-masked]>
Date: Fri, 05 Jan 2018 02:45:02 +0000 (UTC)

My point was that this is a symmetric attack.  A server can do the same to a client.

-- 
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/1030#issuecomment-355458912

---

From: Marten Seemann <[email-masked]>
Date: Fri, 05 Jan 2018 02:58:30 +0000 (UTC)

That's correct.

-- 
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/1030#issuecomment-355460600

---

From: MikkelFJ <[email-masked]>
Date: Fri, 05 Jan 2018 08:21:59 +0000 (UTC)

OK, I forgot part of the issue here. The connection ID protects against off path attacks.

The random gap protects against a malicious client or server that seeks to trick the peer into believing there is more bandwidth than what is available by ACK'ing too fast. This leads to congestion and denial of service of other peers, even without consuming any considerable resources at that attacked endpoint directly.

Could it work to include the spin bit in the ACK and thus get rid of random 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/1030#issuecomment-355497784

---

From: MikkelFJ <[email-masked]>
Date: Tue, 09 Jan 2018 09:59:31 +0000 (UTC)

If we cannot get rid of random skips, can we at least place a constraint such skipping dropping at most one random packet every 32 packets or so, or if insufficient, skip 1 random packet every four packets.

In the current formulation a skip may be up to 2^31 which doesn't really improve over smaller skips while smaller skips allow for more efficient and simpler data structures and supports trivial rejection of obviously incorrect packet numbers. With variable length packet numbers it also keeps that paket number representation small.

-- 
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/1030#issuecomment-356236632

---

From: Marten Seemann <[email-masked]>
Date: Tue, 09 Jan 2018 02:04:13 -0800

For optimistic ACK mitigation, it is sufficient to skip a single packet number. I don't see any advantage you would get from skipping more packet numbers at once. 

-- 
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/1030#issuecomment-356237866

---

From: janaiyengar <[email-masked]>
Date: Fri, 12 Jan 2018 14:16:29 -0800

@marten-seemann : This optimistic ack attack was one of the motivating reasons for entropy in the old GQUIC. We eventually agreed internally that this wasn't an interesting attack... looking through past work and asking around made it clear that this potential vector, which is present in TCP as well, wasn't interesting enough to be exploited.

But, as you note, a sender can always skip a packet number just to test. This doesn't have to be co-ordinated with the receiver, and it needs skipping only a single packet number.

-- 
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/1030#issuecomment-357369666

---

From: MikkelFJ <[email-masked]>
Date: Fri, 12 Jan 2018 14:18:05 -0800

But it is important that the spec limits the size of the jumps, otherwise an implementation must support arbitrarily large jumps.

-- 
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/1030#issuecomment-357370008

---

From: janaiyengar <[email-masked]>
Date: Fri, 12 Jan 2018 22:19:41 +0000 (UTC)

What implementation support is needed? ACK frames can encode arbitrarily large gaps. What other special code do you think you'd need for this situation?

-- 
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/1030#issuecomment-357370355

---

From: MikkelFJ <[email-masked]>
Date: Fri, 12 Jan 2018 14:23:30 -0800

I have two implementations, one using a bitmap and one using some sort of binary search. I'd much rather use the bitmap, but I can't if very second packet can jump 10000 packet numbers just for the heck of it.

-- 
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/1030#issuecomment-357371139

---

From: Nick Banks <[email-masked]>
Date: Fri, 12 Jan 2018 22:25:55 +0000 (UTC)

But you still have to handle arbitrarily large gaps from plain packet loss, right? Why is that any different?

-- 
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/1030#issuecomment-357371581

---

From: MikkelFJ <[email-masked]>
Date: Fri, 12 Jan 2018 22:30:25 +0000 (UTC)

The difference is that I have a very large, but finite bitmap, and that it can condense whereever all gaps are filled. The map needs to cover the packets in flight, which it can, but it can't handle randomly large gaps. Even with large losses, the bitmap is still very efficient up to the point where the connection is unusable due to losses.

-- 
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/1030#issuecomment-357372451

---

From: ianswett <[email-masked]>
Date: Fri, 12 Jan 2018 22:36:40 +0000 (UTC)

Whether or not we document this in the transport draft, skipping a packet number is a pretty viable option for implementations that want some protection.  So I'm ok with removing text relating to it, because we have other defenses, but I believe it's still perfectly valid for an implementation to close a connection if a packet number it has never sent is acknowledged.

-- 
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/1030#issuecomment-357373640

---

From: janaiyengar <[email-masked]>
Date: Fri, 12 Jan 2018 15:22:09 -0800

mikkelfj@ : An artificial limit on implementations is likely to be much larger than what you'd want to use for a BDP's worth of packets anyways, so you would likely still have to deal with packets that fall outside your bitmap. Given this would be the occasional case, isn't it easier to consider this to be the "slow path" in your implementation? That is, handle separately the case where the received packet falls outside your bitmap. I can't see how you'd implement something complete without having this code.

-- 
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/1030#issuecomment-357381526

---

From: MikkelFJ <[email-masked]>
Date: Fri, 12 Jan 2018 15:28:24 -0800

Oh absolutely, it isn't a dumb bitmap. There can be large gaps in it, but the assumption is that if one packets land there, more packets will follow shortly. It can be indexed - for example using a second level binary tree, or using a second level bitmap, or something else I haven't given a proper name,  but it cannot (efficiently) handle that every other packet is a large gap.

You could of course also generally have a slow path, but then you need two complete and efficient implementations because every other packet may still have a large gap. Every single one in fact.

-- 
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/1030#issuecomment-357382628