Brotli Stale Table Read

Klaas van Schelven
Klaas van Schelven; October 28 - 4 min read | tags: Security

Looking into the origins of HTTP2Shell, I came across a guard that raises an interesting question: why was it added in the first place? And what does it say about the security of the versions of Brotli before HTTP2Shell? Spoiler: it says that those were vulnerable too, but in a different way.

To see why, it helps to know the four pieces that make the HTTP2Shell RCE chain possible, as detailed in the Mozilla bug:

  1. The decoder assumes the metablock’s 16 MiB output-size limit also bounds the number of distance symbols.
  2. Zero-output commands invalidate that assumption
  3. A guard returning BROTLI_FALSE by means of error-code, whereas that value is interpreted as “not enough input”.
  4. The decoder’s streaming retry loop keeps buffering input and retrying, overflowing its eight-byte buffer.

Http2Shell gets introduced

The first point in time where the four issues came together was in this February 26, 2018 commit titled “New feature: Large Window Brotli”.

It both lowered the initial block-counter value from 2^28 to 2^24, and introduced the single-block-type guard in the block-switch decoder. That latter bit is the one that’s most relevant here:

if (max_block_type <= 1) {
  return BROTLI_FALSE;
}

But why was it added in the first place? Presumably, to avoid reaching the subsequent code, which would try to read switching tables that aren’t constructed when there is only one block type:

block_type = ReadSymbol(type_tree, br);
s->block_length[tree_type] = ReadBlockLength(len_tree, br);

For reference, piece of code that makes it so that the switching tables aren’t constructed looks like this:

if (s->num_block_types[s->loop_counter] < 2) {
  s->loop_counter++;
  break;
}

In other words, it is a guard against reading uninitialized or stale (more on that later) switching tables.

Post-HTTP2Shell, we understand that this guard can be reached by virtue of exploiting steps 1 & 2, i.e. by counting down the single-block-type counter to zero using zero-output commands.

This means that the same first two steps from the HTTP2Shell chain can be used to reach the guard, and in versions before Brotli 1.0.3, reaach the code where there is no guard.

Thus, we can reach the code the guard was supposed to protect against: the reading of uninitialized or stale switching tables.

Out of bounds reads

So what if the switching tables are not constructed? It means that the decoder will read either uninitialized memory, or attacker-controlled switching tables.

The first case happens when the decoder is called with a metablock that has only one block type, and the switching tables are not yet constructed because there were no previous metablocks with more than one block type. In that case, the decoder will read uninitialized memory. In Brotli 1.0.2, the storage for both sets of switching tables is allocated together using BROTLI_ALLOC. The default allocator calls malloc, which does not initialize the memory.

The second case (when there are stale, attacker-controlled switching tables) happens when the decoder is called with a metablock that has only one block type, but there were previous metablocks with more than one block type. In that case, the decoder will read stale switching tables from the previous metablocks.

Those switching tables can be put there by an attacker as part of the previous metablocks. They will be validated by the decoder, but only in the context of those previous metablocks, but not in the context of the current metablock. That means, for example, that they can contain symbols that select nonexistent types in the current metablock. Those invalid indices then cause out-of-bounds reads from the context map.

Turning that into something exploitable is left as an exercise to the historically inclined reader (Brotli 1.0.3 was released 8 years ago). I’m just here to point out that out-of-bounds reads are “generally bad”.

So what?

This is interesting (to me) at at least a few levels:

First, the fact that a guard against out-of-bounds reads was itself a puzzle-piece in the HTTP2Shell chain. Something something frying pan, something something fire.

Did they know?

Second, the question of what was known at the time.

Did the developer realize that zero-output commands could exhaust the supposedly inexhaustible counter, and add the check for that reason?

That would seem quite odd: the very same commit actually lowered the initial block-counter value from 2^28 to 2^24, which would seem to indicate their mental model was that there would never be more distance symbols than the output size limit.

But if they did not doubt those assumptions, why was the extra check added? General defensiveness? Tools flagging it? Something else?

If they knew

If they did know the counter could reach zero, why not opt for a more direct fix?

Not actually counting down a counter for a block-switch when there is only one block type, for example, seems like a much more straightforward mental model than trying to come up with a “good enough” value for infinity.

Affected versions

Finally, how long does this go back?

The unchecked table read is present in every tagged Brotli release before 1.0.3, including the earliest, 0.1.0. Those versions use a larger counter than the present value of 2^24, but zero-output commands can still exhaust it.

Also see: HTTP2Shell Timeline and Bye Bye Brotli? Google’s Compression Library Is a Security Mess.