Gapless Optimitisk ACK Attack Mitigation

[mikkelfj]

Since packet numbers are potententially becoming gapless with the introduction of encrypted packet numbers, it would be beneficial to also remove gaps in optimistic ACK mitigation.
While such gaps can be small, there is currently nothing preventing them from being large either.
Also, implementations might be tempted to not implement this defence until it becomes a problem.

Therefore I propose a different mitigation that requires 1 defence bit (or entropy bit) stored with each transmitted packet number. This defence bit could be that last bit of the authentication tag, i.e. something the receiver is trivially aware of but which also handle handshake packets (hence an encrypted packet number bit would not work well if those packet numbers are not encrypted).

An ACK frame includes the defence bit associated with the largest ACK'ed packet number. This could be done by assigning two packet types types to the ACK frame, e.g. 0x0d and 0x0e with the LSB of the packet type corresponding to the defence bit.

Internally a packet number is only 62 bits, so the defence bit can be stored in a 64-bit number, but there is no space for it variable length fields such as largest acknowledged, hence the extra ACK frame type.

See also
#1030

[marten-seemann]

We already had something like this entropy bit in gQUIC, until it was removed in favor of packet number gaps.
I think this was a good decision, since the entropy bit was quite painful to implement. I don’t see any problem with small packet number gaps, since this is exactly the same pattern a receiver would see on a lossy connection.

[mikkelfj]

Note that the last bit of the auth tag is not entirely unpredictable to the recipient, so there could be an attack path by guessing the exact content of early packets, ACK those optimistically and drive up bandwidth estimates, but any random mofication of packet content would mitigate this.

[mikkelfj]

We already had something like this entropy bit in gQUIC,

But the sender needs to either track omitted packets, or the entropy bit, so that is the same. The receiver can encode the packet number internally as 2*real-packetnumber + entropy-bit to achieve the same thing.

Link quality estimates also become more reliable as there is no unpredictable implementation dependent loss.

[mikkelfj]

And, the ACK block lengths are not getting artificially fragmented.

[mikkelfj]

Actually it is simpler: The receiver only needs to record the defence bit for the largest received packet number and OR it with the ACK frame type. The sender needs to record the defence bit for anything above largest ACK'ed, but in return don't have to remember which packets were sent. This can be a simple bitmap.

[mikkelfj]

If the sender do not want the burden of tracking entropy because there is not realistic attack vector for the use case, the sender can just accept either ACK frame without verifying. This is equivalent to not sending random gaps, and as mentioned, the overhead for the receiver is minimal.

[kazuho]

Personally, I prefer a protocol that enables you to implement ACK attack detection by using a deterministic function instead of recording the information that has been sent.

With gaps, that is possible, for example by using a keyed hash. Assuming that the hash function (H) returns a 32-byte output, you can implement a function like below that checks if a given packet number is represents a gap.

// one gap for every 256 packets
bool pn_is_gap(const uint8 *key, uint64_t pn) {
    uint8_t hash[32] = H(key, pn / 256 / 32);
    return hash[pn / 256 % 32] == pn % 256;
}

Note that for contiguous ACKs the gap check using a modified version of the function can become very efficient, since you can cache and reuse the result of the hash function.

If we are going to switch to a gapless approach, I would prefer having the possibility of generating the entropy at the sender (by using a deterministic function like the one above) and sending it, instead of using some bits that happen to be sent (e.g. the last bit of the AEAD tag).

[ianswett]

As Marten mentioned, GQUIC had this and got rid of it in favor of gaps, which are much less work to implement. We considered only echoing one bit back from the largest acked, but that doesn't protect against cases when a peer is only receiving a tiny fraction of the packets being sent, so it didn't seem worth the complexity.

The forthcoming PATH_CHALLENGE and PATH_RESPONSE can be used to prevent the optimistic ack attack for cases one is concerned about it.

Even without adding anything to QUIC or using PATH_CHALLENGE/RESPONSE OR creating gaps, I don't believe it's any more vulnerable to the optimistic ack attack than TCP is.

In practice, even if we switch to a gapless approach, nothing prevents implementations from creating gaps for this purpose and I suspect some will. And if we're encrypting packet numbers, the one reason I know of for removing gaps(middleboxes trying to track upstream reordering and loss) disappears.

[mikkelfj]

I'm fine with PATH_CHALLENGE if it does the job and if we can get rid of gaps as a recommended mode of operation, even if it cannot be prevented. If the challenge works it is much simpler solution since you only have to do very limited bookkeeping.

If peers choose to introduce gaps regardless, it is much easier to drop or down-priorititize a misbehaving endpoint. If gaps are generally permitted you either have to allow arbitrary gaps way beond reasonable loss profiles which makes the entire migration gap avoidance pointless, or you have to define what is a reasonable gap profile, which is messy.

[MikeBishop]

If you want to catch a peer doing early ACKs, there has to be something that they can only learn from having seen the packets at the time they're sending the ACK. The entropy bit gives you that, but is hard to implement. Skipping packets gives you that, because if they don't know when you skip they'll give themselves away. PATH_CHALLENGE doesn't give you that, because it's not bound to the ACK.

The problem with PATH_CHALLENGE for this scenario is that the ACK and the PATH_RESPONSE don't have to arrive at the same time. So if the other side is ACK'ing packets that you sent before they've actually arrived in an effort to build up the window, you won't detect it -- the ACK looks legitimate.

Now, if they ACK a packet that gets dropped, they'll get caught (eventually, when the timer runs out, assuming the implementation checks whether a packet has been ACK'd when a PATH_CHALLENGE times out) -- but even without doing anything, that will result in missing stream data, which is likely to bite the receiver eventually anyway.

I'm indifferent to which ACK-bound mechanism we use to guard against this -- if we've been told by implementers that packet gaps are easier than entropy bits, let's stick with that. But using a mechanism not bound to the ACK doesn't buy us much we don't already have.

[huitema]

As Kazuho points out, it is possible to write a keyed pseudo random function, "shall I skip sending sequence number X", and tune it for whatever skip probability you want. The same function can be used when receiving acks, to detect "should someone really ack sequence number X". That means the "ack skipping" test is really easy to implement. The entropy test, not so much.

[mikkelfj]

I'm aware of the pseudo random hash approach to skipping, and if wasn't because it required on-wire changes or gaps, I would have suggested it too. It can be done gapless by randomly sending an ACK token frame in packets that would otherwise have been gaps which avoids packet header flags.

Although the hash based testing is fairly simple with gaps, storing a bit per transmitted packet is also easy, if not easier since you need a data structure for retransmission and ACK tracking anyway.

However, I do see the issue Ian mentions with false acknowledgements of lost packets. I'm not convinced that is a realistic attack scenario whereas opportunistic personal bandwidth prioritisation or DoS are demonstrated attacks. Even so, it would be great if the gapless approach could improve in this aspect without requiring the ACK frames to carry entropy for all ACK'ed packets, which I agree, is not ideal.

There are attacks on specific receivers index implementation of received packets which are easily defended with a gapless approach but with gaps it is hard to reject because any gap pattern could be valid even if far from a realistic network loss pattern.

[mikkelfj]

Failing to gain traction for a gapless approach, I would suggest an alternative gap based approach that uses something like Kazuhos hash in formalized manner in line with my comments placed in the quic-go issue: quic-go/quic-go#1149

Citing my mis-placed comment on that issue:

If such a function is formalized, with an unpredictable key, of course, it would remove a class of attacks on the receivers indexing of received packets, for example by simply dropping a connection if the index starts to use too much space per packet on average. It would also put a bound the gap size so large gap jumps are ruled out. This would alleviate some of my concerns regarding gaps.

[martinthomson]

Not seeing any concrete issue here (over those already open), closing this. If you have a proposal, please mail the list to explore the idea. Ideas that are more fully thought out can be expressed as pull requests.