amplification attack using Retry and VN triggered by coalesced Initial packets

[marten-seemann]

An Initial packet can be made pretty small, if I counted correctly the smallest size for a valid Initial is 18 bytes. That means that if I coalesce 67 of these packets, I can fill up one UDP datagram that fulfills the minimum size requirement of 1200 byte.

A naive server implementation might first split the coalesced packet into those 67 QUIC packets, decide that it wants to do address validation and then send a Retry packet for every one of them. Considering that a token will be at least around 40 bytes long (if the server is using authenticated encryption), and that there's UDP and IP overhead, that's a nice amplification factor in itself already, in addition to the fact that the attacker just converted a single large datagram into a lot of small datagrams.
I'm not sure if this is covered by the text yet. We say that

Prior to validating the client address, servers MUST NOT send more than three times as many bytes as the number of bytes they have received.

However, since the retries are supposed to be stateless, it's not clear how this would work.

The same applies to Version Negotiation packets. With the coalesced packet described above, a single packet could be used to elicit the sending of 67 VN packets. We currently have some text that a server MAY limit the number of VN packets it sends, but unless we come up with a better defense against this attack, I think we'll need stronger language here.

[nibanks]

I agree this could be a problem if an implementation processes each packet completely independently such as the following text requires:

The receiver of coalesced QUIC packets MUST individually process each QUIC packet and separately acknowledge them, as if they were received as the payload of different UDP datagrams.

I think the best way to handle this would be to add some text that specifically states that if a server sends a Retry or VN in response to a QUIC packet, the rest of the UDP payload should be discarded.

[ianswett]

@nibanks Discarding the rest of the UDP payload sounds wise to me.

[marten-seemann]

A client might combine two Initial packets of different versions into one datagram in order to save the round trip penalty associated with VN. This wouldn't work if the server decides to drop the rest of the packet after sending the VN packet.

[dtikhonov]

So this hypothetical client does not care that the server might create two connections. Perhaps we should not allow such scenario.

[nibanks]

I agree with @dtikhonov. I don't think we should allow/encourage that scenario. Send two different UDP datagrams if you really want to do that as a client.

[marten-seemann]

If we want to forbid that behavior, there's no need to coalesce two QUIC packets with the same encryption level. Maybe an easy fix would be prohibit that in general.
This would also mean that all coalesced QUIC packets must have the same QUIC version.

[nibanks]

Depending on how an implementation implements packet coalescing on the send side, I could see an implementation padding a UDP datagram with a padding-only Initial packet that follows the Initial packet with the crypto data.

[marten-seemann]

@nibanks Why would you do that? If an implementation is not capable of using QUIC PADDING for some reason (and I can't think of any reason why this would pose an insurmountable challenge), it can just pad the rest of the UDP packet directly. There's no need to use a second Initial packet.

[martinthomson]

The fix of "one Retry per UDP datagram" seems about right to me.

[marten-seemann]

@martinthomson Why do we need to allow multiple packets of the same encryption level in one UDP datagram? I can't see a single use case for this, but I see a lot of ways this can be used in malicious ways.
We introduced coalesced packets to reduce HoL blocking on encryption level changes, not to give senders the ability to stuff 67 packets into a single datagram.

Proposed text:

A sender MUST NOT coalesce multiple packets with the same encryption level into a single datagram. Receiver SHOULD ignore any subsequent packets that have the same encryption level as any of the previous packets in the datagram.

[kazuho]

@marten-seemann I am not sure if having a MUST requirement that cannot be enforced by the peer is a good idea (note: it cannot be enforced by the peer because a middlebox can stitch valid QUIC packets to compose a QUIC datagram).

Therefore my preference goes to what @martinthomson suggests.

[marten-seemann]

@kazuho We already have a MUST requirement for coalesced packets:

Senders MUST NOT coalesce QUIC packets for different connections into a single UDP datagram. Receivers SHOULD ignore any subsequent packets with a different Destination Connection ID than the first packet in the datagram.

Both requirements cannot be enforced in the sense that the connection is closed. However, they are enforced in the sense that the incorrect packets are dropped, so there's no motivation whatsoever for an endpoint to misbehave.

[kazuho]

@marten-seemann That's true. Thank you for pointing that out.

OTOH, I am still not convinced that we should disallow senders from coalescing QUIC packets of same type.

We need to maintain state while parsing the datagram (to not let each of enclosed packets generate a Retry), regardless of the approach we adopt. Therefore, I do not see benefit in disallowing coalescence, while the downside would be that it makes difficult to stitch a fake QUIC packet in front of the datagram to help PMTUD (as of -17, we do not have "reserved" packet types).

[marten-seemann]

We need to maintain state while parsing the datagram (to not let each of enclosed packets generate a Retry)

State is exactly what I'm concerned about. I'd like to avoid allocating state for 67 QUIC packets due to a single datagram. With my proposed requirement, you can at most have 4 QUIC packets per datagram.
Not sending more than a single Retry or a single VN packet per datagram gets trivial if we introduce this requirement, since you already detect duplicate Initials when parsing, not just when handling packets.

Therefore, I do not see benefit in disallowing coalescence, while the downside would be that it makes difficult to stitch a fake QUIC packet in front of the datagram to help PMTUD (as of -17, we do not have "reserved" packet types).

I haven't implemented PMTUD yet, and as far as I can see, the PMTU section doesn't say anything about coalesced packets. To increase the packet size you're supposed to fill packets with PING or PADDING frames. I assume you don't want to do this, and you want to use coalesced packets instead. What's the advantage of that approach? It seems like you just add a bunch of corner case to your code (since then there's a range of packet sizes you can't reach, because you have to add a whole QUIC header).

[kazuho]

State is exactly what I'm concerned about. I'd like to avoid allocating state for 67 QUIC packets due to a single datagram. With my proposed requirement, you can at most have 4 QUIC packets per datagram.

I do not get the same numbers.

With @martinthomson's approach, an endpoint needs one boolean when parsing a datagram. The value is flipped when you send a Retry, and prohibits the rest of the packets belonging to the same boolean from issuing another Retry.

With your proposal, an endpoint needs to maintain at least four booleans to detect if any of the packets have been seen more than once in a datagram.

Therefore, I think that @martinthomson's approach requires less state.

I haven't implemented PMTUD yet, and as far as I can see, the PMTU section doesn't say anything about coalesced packets.

In Kista, we discussed about prepending long header packets (that do not authenticate) that contain enough information for the load balancer to forward ICMP response to the server.

[ianswett]

I think I prefer the suggestion of @marten-seemann of not allowing two packets with the same encryption levels in a datagram. Given you can't change CID, the only other purpose of multiple packets would be to supply different versions. I had been assuming all QUIC packets in a datagram have a single version. If we want to allow that, I think we should explicitly decide that.

If we want to allow that, I think we need to both add a rule about sending one Retry per datagram and a rule about what to do with the rest of the QUIC packets in the datagram once you send a Retry. Presumably you should drop/ignore them as @nibanks suggested?

[nibanks]

I am in agreement with @kazuho here. I don't see a need to limit the type or number of QUIC packets in a datagram. In my implementation that would just increase the state and complexity.

I also don't think we need to support different QUIC versions in the same datagram. Push the little bit of extra work to the client in this case, and have it send different datagrams instead. Perhaps we should explicitly disallow this scenario in the spec.

[DavidSchinazi]

The current text on coalescing packets is:

Senders MUST NOT coalesce QUIC packets for different connections into a single UDP datagram. Receivers SHOULD ignore any subsequent packets with a different Destination Connection ID than the first packet in the datagram.

We could solve this amplification attack by changing that quote to Destination Connection ID or Version, and add text like: If a server receives a coalesced QUIC packet that causes it to send a Retry or Version Negotiation packet, the server MUST silently drop all subsequent coalesced packets in this UDP datagram. This has the advantage of not limiting the type or number of coalesced packets.

[mikkelfj]

Currently coalescing only makes sense in early packets, but as a general concept I don't like forcing ordering on processing independent packets because it affects concurrency design.

Since the problem relates to stateless transmission there is only the datagram to latch onto as a substitute for state and this sort of requires ordering as @DavidSchinazi suggests.

If instead we require that a VN or Retry can only be sent if it is triggered by the very first QUIC packet in a datagram then we avoid most of the ordering. A recommendation could be to silently drop further packets, but not require it. What could go wrong if subsequent packets were to be processed (keeping in mind that it will cause a stateful transition of successful)?

[DavidSchinazi]

@mikkelfj I didn't suggest enforcing ordering. Whichever packets causes sending Retry/VN causes all subsequent packets to be dropped. I don't see having the third packet trigger a Retry as an an issue.

[mikkelfj]

@DavidSchinazi even if there is no strict ordering, there is still coordination. And reading you text verbatim you also require the first Reset / VN triggering packet to win.

For the sake of argument assume packets were coalesced in the general case. A single preprocessor locates packet boundaries and pushes each packet to a queue handled by several processing units which picks a packet whenever it is available for processing. Suddenly one of these processors wants to emit a Reset. It then has to signal all other processors that they should stop doing what they are doing if they happen to be processing the same datagram. Furthermore, the processor must figure out if there is another processor also wanting to send a VN or Reset on the same datagram, and if so, if it is earlier in the datagram such that the correct winner can be identified.

In praxis such complexity would not be implemented as long as coalescing only happens during handshake, but it illustrates that ordering constraints are difficult when introducing concurrency in processing.

[DavidSchinazi]

@mikkelfj Ah I see, I thought you meant requiring/enforcing in which order packets are sent, but you meant that now the order in which they are sent matters when it didn't used to. I agree with you, and I see how this could be an issue for some implementations.

Another solution would be to prohibit sending Retry/VN in response to packets that are smaller than 601 bytes (the idea behind the number 601=1200/2+1 is that if well-behaved clients always pad their largest long header it should meet this requirement).

[mikkelfj]

I was about to suggest that VN / Retry could only be sent if the QUIC packet had at least 1200 bytes, but that goes against the idea of using coalesced packets. I'm not sure that 600 bytes is much better because it limits how much you can send in a second coalesced package when you want to stay below the minimum PMTU.

By requiring that only the first QUIC packet in a datagram can trigger VN / Retry you avoid these problems, and I can't imagine a reasonable case where you want to coalesce packets in a way where later packets actually trigger a VN / Retry.

One could also add that coalesced packets must belong to the same logical connection or connection attempt and that an implementation MAY ignore part or all of the packets in a datagram that does not conform (without requiring this to be enforced because that could get complex fast).

[ianswett]

@DavidSchinazi I think a tweak to your previous suggestion is probably best here: "If a server receives a coalesced QUIC packet that causes it to send a Retry or Version Negotiation packet, the server SHOULD silently drop all subsequent coalesced packets in this UDP datagram.

[kazuho]

@ianswett

"If a server receives a coalesced QUIC packet that causes it to send a Retry or Version Negotiation packet, the server SHOULD silently drop all subsequent coalesced packets in this UDP datagram.

That sounds a bit odd to me, because IIRC we decided in #1514 that servers can buffer 0-RTT packets when sending a Retry. Recommending a server to drop a 0-RTT packet that was coalesced to an Initial packet will have a negative impact to servers that choose such a strategy.

I still think that the best text is "one Retry per UDP datagram" suggested by @martinthomson. It allows the behavior you suggested with more freedom.

[mikkelfj]

Is there any case where it a VN / Retry would reasonably be triggered after the first packet in a datagram? If not, why not simply restrict VN / Retry to the first packet?

[kazuho]

Is there any case where it a VN / Retry would reasonably be triggered after the first packet in a datagram?

I do not think such a case exists, because a QUIC packet belonging to different connections are never coalesced, and because v1 requires every packet of a connection to use the same version number^1/.

Therefore, I agree that endpoints can restrict VN / Retry to the first packet. It might be a good idea to clarify that.

Though I am not sure if that should be the normative requirement. IMO, the requirement is that a server MUST NOT send too many (possible no more than one) datagram in response. The way you describe is one way of achieving that.

1: Theoretically, v2 could use a datagram consisting of v1 Initial and v2 long header packet, but I am not sure if we need to allow that kind of design.

[mikkelfj]

If it is normative it would prevent certain reorderings of packets that receivers would otherwise need to consider, however little sense such reorderings make.

[janaiyengar]

Please reopen the issue if you think this ought to be discussed further, especially in Tokyo.