Tag: quic header compression design team

SMITH: Doctor, it hurts when I do this.
DALE: Don’t do that.

– Smith and Dale

This is the third article in the QUIC Header Compression Design Team series.

Introduction

To achieve the best header compression performance, it is tempting to have the compression protocol allow potential head-of-line blocking (HoLB). The idea is that HoLB will not occur most of the time, while the compression gain is significant. The first article of this series exposes priority inversion caused by HoLB and challenges the assertion that HoLB is rare. The second problem is that HoLB is a potential attack vector, wherein the decoder is tricked into using a lot of memory. One way to prevent such attack is to not read from the stream until the decoder can process the stream immediately. This approach creates a deadlock hazard. This problem is examined in this article.

Note on Terminology

If a header block B depends on an entry inserted by header block A, we say that B depends on A. Together, they are dependent header blocks.

Problem Statement

Writing dependent header blocks to stream out of order introduces the risk of a deadlock. There are two types of a deadlock.

Single-stream Deadlock

When dependent header blocks are written out of order to the same stream, the first header block cannot be parsed because it depends on the block that follows it.

Multiple-stream Deadlock

This type of deadlock happens when the out-of-order header block prevents the receiver from reading stream data that follows the header block. What makes it different from the regular HoLB case is that the sender cannot put the resolving header block onto the stream due to the limits imposed by the QUIC connection flow control.

Scenario 1: Resend After a Reset

One way a multi-stream deadlock can occur is when a header block must be resent after a stream reset. By the time the sender figures out that it needs to resend a header block, it may have filled all existing streams to the brim — which the receiver cannot drain — and is not allowed to stream more data.

Possible Mitigation: Don’t Fill Flow Control Window

One potential solution is always to leave some room in the connection flow control window. That is, leave at least the number of bytes required to resend all unacknowledged header blocks.

There are downsides to this approach:

1. It is not clear that the connection flow control window information is available at HTTP/QUIC level.
2. The code complexity of the HTTP/QUIC layer increases — the user code can no longer write directly to the stream. These calls must be intercepted at HTTP/QUIC layer to ensure that the threshold is not exceeded.
3. Most of the time, these are just wasted bytes that could otherwise be used. In other words, throughput suffers.
4. Not filling the connection window may prevent the peer from sending WINDOW_UPDATE, resulting in a stall.

Scenario 2: Out-of-order Write

In general, a multi-stream deadlock can occur any time dependent header blocks are written to different streams — consuming flow control credits — out of order. If header block B depends on header block A, but is written to stream first, it may happen that header block A can never be written: If the receiver does not process stream B because of its application protocol rules (in our case, the receiver is avoiding memory exhaustion attacks), it is possible that the connection flow control prevents the sender from sending more data.

Possible Mitigation: Don’t Do That

“Well, don’t do that, then!” – might one say. This is a sound point of view: since the problem is of the application’s own making, it is up to the application to solve it. Nevertheless, the deadlock risk bears being pointed out, as it affects how a QUIC/HTTP implementation may be designed. For example, if the stream interface offered by a QUIC implementation performs internal buffering, can the application make sure that data on one stream gets sent before dependent data on another stream?

Possible Mitigation: Make the Transport Do It

My initial report to the Design Team prompted Martin Thomson to share the finding on the common IETF QUIC WG Mailing list. The resulting thread is large and makes for an interesting read. It contains several ideas on how such deadlock could be prevented by the transport, either by making the current priority implications stricter; or by introducing extra transport rules, exceptions, or overrides of various sorts.

Summary

It is natural to write dependent header blocks to streams in order. Not doing so may result in a deadlock. In particular, resetting streams forces the encoder to write header blocks out of order. Hence, the encoder must address the possibility of a deadlock in some fashion.

P. S.

The “don’t do that” versus “let the transport solve it” discussion is likely to resume at the upcoming Interim Meeting (Jan 23 – 25) in Melbourne, Australia. Watch this space for updates.

Protocol designers underestimate
how badly people will implement
their designs.

– Adam Langley, Cryptographic Agility.

Abstract

Compression schemes that allow head-of-line blocking are targets for memory exhaustion attacks against the decoder. Detecting such an attack is not trivial. Without guidance, programmers are likely to produce vulnerable implementations. HoL blocking must either be prohibited at the protocol level or the attack mitigation mechanism must be specified explicitly in the compression specification. One way to avoid an attack is presented.

Introduction

In the previous article, we discussed how head-of-line blocking can cause priority inversion and vice versa. In the second part of the series, we will examine potential attacks made possible by head-of-line blocking.

Problem Statement

Head-of-line blocking causes the decoder to queue header blocks that cannot be decoded due to a missing dynamic entry. Under normal circumstances, this occurs because of packet loss or reordering. An adversary, however, may create this scenario artificially in order to get the decoder to queue data, thereby creating a denial-of-service attack.

Here, a simple recommendation that the decoder use a timer is insufficient. The decoder must decide how much data it is willing to buffer and for how long. In other words, it must be able to differentiate between an attack and a regular packet loss/reordering situation. An incorrect determination may mean allowing a server to be DoSed; err the other way, and a valid connection is aborted.

Sample Attack

The attacker’s strategy is simple: send header blocks that contain a reference to a non-existent dynamic entry:

The decoder cannot resolve a reference and has to wait — buffering data. More and more header block data is sent. To maximize the effect of the attack, the adversary may use more than one — potentially all — available streams.

Mitigation Strategies

Strategy 1: Simple Timer

The decoder may associate a simple timer with each stalled header block. A simple timer has to be quite conservative in order to eliminate false positives. During that time, the attacker writes more data to each of the header blocks in a round-robin fashion, perhaps even resolving the blocking entry to reset the decoder timer while introducing a new unresolved entry at the same time. The amount of data queued at the decoder grows and grows and the server is eventually hosed.

Strategy 2: Adaptive Timer

A conservative timer means that the attacker has plenty of time to write more blocking data. An adaptive timer aims to reduce that window by using recent network conditions for determining a smaller timeout value. Besides RTT, it may need information such as the current CWND as well as callbacks fired when packet loss or timeout is detected. (This is digging pretty deep into the transport.) Even then, the adaptive timer must take into account that data could be lost multiple times as well as the possibility that the peer retransmits lost packets after it sends new data.

This approach lessens the impact (although without further analysis I cannot state to what degree), but does not solve the problem. In addition, the possibility of a false positive grows.

Strategy 3: Application-Aided Attack Detection

The decoder does not know whether the headers it receives make sense to the application or whether they are just fluff the attacker uses to blow up its blocked queue. The application knows about the headers it uses and thus could be called upon to evaluate the headers’ fluff level, sort of like an email SPAM filter.

This idea is not workable:

1. While we (the IETF QUIC Working Group) do control the direction the transport layer takes, requiring all applications to provide extra logic to fight attacks is a non-starter.
2. The attacker may simply target an application with special header blocks that would pass the checks.

Strategy 4: Change Application Interface

It is possible to change the decoder API to require the application to receive out-of-order headers, allowing the decoder to queue just the unresolved references. This is not good enough, either:

1. The problem is just kicked upstairs — now the application must queue the data and decide when to abort the connection.
2. If an indexed-name/literal header representation is used, with the index being unresolved, the decoder still has to queue the whole header field.

Strategy 5: Unread Data From Stream

One can imagine requiring the stream interface to be able to revert a read; alternatively, a peeking functionality may be provided. Either will allow the decoder to leverage the underlying stream’s queuing functionality instead of doing its own: when an unresolved entry is encountered, push back some data (or the whole header block). The advantage of using the stream for this is that the amount of data in the stream is limited by that stream’s maximum as well as the connection’s overall maximum.

The first downside of this approach is that unreading may not always be possible, as the application must take off data from streams so that the connection can proceed.

When it is possible, this strategy effectively exchanges a memory exhaustion attack for processor exhaustion attack. One can imagine an attacker now switching to feeding the decoder resolved entries and new data with unresolved entries, forcing it to read, decode, and push back the data.

In addition, it is unclear whether the QUIC standard will require the transport layer to provide such functionality. (Consider, for instance, the implications of deferring sending a WINDOW_UPDATE frame while waiting for the application to “commit” to a read.)

No Way to Detect An Attack

None of the mitigation strategies above help the decoder to detect an attack in time. An odd (for some value of “odd”) sequence of incoming streams, header blocks, and dynamic table updates may be a perfectly valid use case. An attack detection mechanism built into the decoder must be sure that it is not going to break applications. Thus, one implementation may do it well and another may do it poorly. Chances are good that it is the protocol that will take the blame. One could add: for a good reason.

What This Means

Section 7: Security Considerations of RFC 7541 (HPACK) is five pages long — a quarter of the whole text! (Sans preamble, table of contents, and appendices). Obviously, the security of the header compression mechanism has been addressed thoroughly in the past.

It is apparent that the compression mechanism that we (the Design Team) eventually present to the Working Group must either preclude this type of attack at the protocol level or offer a robust attack detection and mitigation that can pass a security review.

There are two ways to address this:

1. 1. Not allow head-of-line blocking in the final proposal.
   2. Agree that the final compression proposal
      • limit HoL blocking in a quantifiable fashion and/or
      • include a robust attack detection mechanism.

Limiting HoL blocking in a quantifiable fashion means that the compression mechanism guarantees that the amount of data that has to be queued at the decoder does not exceed some threshold.

A robust attack-detection mechanism implies that it is possible to implement using standard programming techniques. It would be unreasonable to require that every decoder implement a sophisticated attack detection logic. (This would also be against the QUIC WG mandate that the decoder be simple.) In addition, the detection code must be relatively inexpensive (memory, CPU) to operate as part of the decoder.

Potential Solution: Defer Reading

One potential solution to this is to prefix header block data with information that would tell the decoder whether the header block could be processed in one shot given current decoder state. For example:

If the Update #X has not yet arrived, the decoder does not read any more from this stream. This leaves the headers in the transport. (This takes Strategy 5 one step further.) Such approach limits the amount of memory required by the decoder.

The downside to this approach is that not draining the streams promptly may prevent the transport from operating efficiently.

Summary

Allowing HoL blocking and requiring the decoder to queue data and wait until it can be decoded is a denial-of-service attack vector. The simplest way to prevent such attack is to not allow HoL blocking at all. Deferring reading from affected streams is likely feasible but requires further analysis. GitHub issue #1011 was opened to track this.