Huffman table hacking tool

This tool calculates tricky canonical huffman histogram, which is able to trigger OOB (Out Of Band) write for vulnerable libwebp library (i.e. libwebp <= 1.3.1). This vulnerability is known as CVE-2023-4863 or CVE-2023-41064. We can overflow the pre-allocated huffman table by at most 132 entries.

The rationale is that libwebp assumes the huffman histogram contained in each webp image is well formated. That is, the decoding tree must be a complete tree. With this assumption, the libwebp group took advantage of an enough tool to estimate the maximum memory size to build the decoding huffman table (a powerful structure to decode canonical huffman codes rapidly). However, hackers are able to construct an incomplete tree to go beyond this memory limit and thus overflow the pre-allocated memory.

This hacking tool was created by adjusting enough with incomplete tree support.

Compile the code using command below:

gcc -o NotEnough ./main.c

For a huffman table with 40-symbol, 8-bit root table and maximum depth being 15, the maximum number of table entries is 410. However, by constructing an incomplement tree, the number of table entries could be 542. Try the command below:

./NotEnough 40 8 15

An example of such trees is as below:

Note that we pruned the branches with no leaves for brief.

You can then use the craft tool to construct an effective webp image to overflow dwebp tool (version <= 1.3.1). Change the huffman code histogram code_lengths_counts[4] to {0, 1, 0, 0, 0, 0, 0, 0, 0, 3, 5, 9, 17, 1, 1, 3} accordingly, and rebuild the tool:

vim craft.c    # Change huffman code histogram accordingly, i.e. about line 495.
gcc -o craft craft.c
./craft -o bad_542.webp

Please check @benhawkes's blog to have a better idea of CVE-2023-4863.