Questions

• What is the code signing requirement?
• How does the kalloc heap allocator work?

Background

Huffman Trees & Tables

Huffman trees are used to compress data into just symbols, and the symbol lengths instead of transmitting the full binary codes. This is done via the following process:

1. Symbols are sorted by code length (shortest first), then by symbol value (lexicographical order)
2. The first code is all zeros (e.g. 00) of the correct length.
3. Each next code is incremented by 1 and left-shifted when the code length increases.

Example:

Lets say we have the following symbols and their lengths:

Symbol A: length 2
Symbol B: length 3
Symbol C: length 3

Then this would be translated to the following:

A: 00
B: 010
C: 011

Why? The first symbol always starts with all 0’s of the correct length. So since A is of length 2, then it is represented by 2 0’s. Then we add 1, which turns it to 01 and then left shift 010. Then we add 1 for every next symbol of the same length. The tree for this data would look like:

Notice how the parent nodes don’t actually represent anything, and the leaf nodes hold the symbols / bits representations. There is one more important thing to note that is relevant to the vulnerability. There are rules that must be followed in order for this to be a valid Huffman tree.

1. Every symbol in the alphabet should appear exactly once as a leaf.
2. No extra leaves just dangling off the tree with no symbol assigned.
3. The shorter codes CANNOT be at a lower level than the longer codes.
4. No code must be a prefix for ANY other code.
1. So for example, since we already have a 00 code, then we cannot have 001, 0011, 00101, etc.
5. There is limited space determined by the combination of short and long codes.

The last point is important because it should make you realize that code length determines depth, and depth determines the number of available slots. At depth n you have at most $2^n$ slots. So now imagine what happens if some system assumes that it will receive a valid tree, but instead receives a tree with 100 symbols of length 2. To help visualize this, lets take a look at a set of invalid code lengths:

[A:1, B:2, C:2, D:3, E:3]

Take a moment to try and figure out why this is invalid.

.

.

.

So lets start by assigning bits to these lengths:

A: 0
B: 10
C: 11
D: INVALID (11 + 1 = 00 and then left shift = 000)
E: N/A

So we see that D gets an overflow, and then the shorter codes prefix it (A prefixes 000 ).

Here is another invalid tree: [A:1, B:2, C:3, D:3, E:3]

A: 0
B: 10
C: 110
D: 111
E: INVALID (111 + 1 = 000 because overflow)

And no, E cannot get assigned 101 because the process of adding 1 and then left shifting MUST be followed for every proceeding symbol. You can’t jump around and assign arbitrary bit patterns. 101 would come before 110, but we already used 110 and 111 for C and D so we can ONLY keep going forward, not back (AOT reference?).

However, the vulnerable code does not use trees, they use tables (because its apparently faster). So lets translate these concepts to this new structure. The table starts with determining how many “root bits” we want. The more root bits, the more entries there will be in this tree. Why? Because more bits means more possible values: $2^n$ remember?

So as an example lets take a look at a table with 8 root bits:

root_table[8] -> size = 2^3 = 8 entries

The index of the entries would then be:

000
001
010
011
100
101
110
111

Here’s where things get a bit tricky. Only codes of length <= root_bits can be resolved directly in this table. Anything longer must be resolved in a second, third, fourth, etc, table. If the codes length is exactly root_bits then it can be resolved directly in the table. If its shorter, then it gets replicated across multiple entries (I’ll explain what this means in a bit).

Lets look at a few examples:

LONGER THAN root_bits:

Lets say we have root_bits = 3 and the code: 1001110 (so length is 7).

The first 3 bits of this are 100, which is all that can fit in our table. So the entry at 100 will now contain a pointer to a second level table. The next 4 bits can now be used to index into this second order table.

SHORTER THAN root_bits:

Now lets say we have a symbol assigned to code 00 (so length is 2). Since this is shorter than root_bits then it is bound to be a prefix to some of the entries (000 , 001 ). So these two entries will point to this symbol. So basically shorter codes are filled in anywhere where they prefix the longer code.

Simple right?

Again Again Again Again Again

So now we understand that if we use shorter root bits, with super long code lengths, then we can create pointers into many second / third / etc level tables. This means allocating memory for these tables, creating pointers to them, etc. How does this actually happen in the code?

First Steps

WEBP File format

+------------------+
| RIFF Header      |
|  - "RIFF"        |
|  - File Size     |
|  - "WEBP"        |
+------------------+
| VP8L Chunk Header|
|  - "VP8L"        |
|  - Chunk Size    |
+------------------+
| VP8L Image Data  |
|  - Signature     |
|  - Image Header  |
|  - Transform(s)  |
|  - Huffman Trees |
|  - Pixel Data    |
+------------------+

I then asked ChatGPT to build me a script to generate a minimal .webp file so I could begin testing. This is what it came up with:

from struct import pack

# === RIFF HEADER ===
riff_header = b'RIFF'
# Placeholder size for now, will be updated later
riff_header += pack('<I', 0)  # Chunk size
riff_header += b'WEBP'

# === VP8L Chunk ===
vp8l_chunk = b'VP8L'
# Placeholder size for now, will be updated later
vp8l_chunk += pack('<I', 0)

# === VP8L BITSTREAM START ===

# 1 byte: signature + version + width/height bits
# 0x2f = 0b00101111 → signature bits + has alpha + simple format
vp8l_bitstream = b'\x2f'

# 4 bytes: width/height + reserved
vp8l_bitstream += pack('<I', 0x00000000)  # Fake for now

# Combine everything
image = bytearray()
image.extend(riff_header)
image.extend(vp8l_chunk)
image.extend(vp8l_bitstream)

# Fix sizes
file_size = len(image) - 8
vp8l_size = len(vp8l_bitstream)

image[4:8] = pack('<I', file_size)
image[16:20] = pack('<I', vp8l_size)

# Write to file
with open("minimal.webp", "wb") as f:
    f.write(image)

• The Huffman meta table will determine the depth of the tree based on the longest code length code length. (very confusing, took me a while to understand)
• For example, if the code length code length uses at most the length 4, then the huffman tree will have at most a depth of 4

WebP Analysis

Links to vulnerable code:

• vp8l_dec.c

• huffman_utils.c

huffman_tables = (HuffmanCode*)WebPSafeMalloc(num_htree_groups * table_size,                                            sizeof(*huffman_tables));

• this line was removed from vpl8_dec.c in the ReadHuffmanCodes function
• -429,16 +434,15 @@
• table_size is defined as: const int table_size = kTableSize[color_cache_bits];
• color_cache_bits is a parameter passed into the function
• kTableSize is an array of fixed sizes:

#define FIXED_TABLE_SIZE (630 * 3 + 410)
static const uint16_t kTableSize[12] = {
  FIXED_TABLE_SIZE + 654,
  FIXED_TABLE_SIZE + 656,
  FIXED_TABLE_SIZE + 658,
  FIXED_TABLE_SIZE + 662,
  FIXED_TABLE_SIZE + 670,
  FIXED_TABLE_SIZE + 686,
  FIXED_TABLE_SIZE + 718,
  FIXED_TABLE_SIZE + 782,
  FIXED_TABLE_SIZE + 912,
  FIXED_TABLE_SIZE + 1168,
  FIXED_TABLE_SIZE + 1680,
  FIXED_TABLE_SIZE + 2704
};