Fast Huffman decoder accepts padding longer than 7 bits (RFC 7541 §5.2) and disagrees with the full decoder

[phongn]

Fast Huffman decoder accepts padding longer than 7 bits (RFC 7541 §5.2) and disagrees with the full decoder

Version: v2.3.5 (cf0f70d), but the relevant code is unchanged for years.

Summary

lshpack_dec_huff_decode (the LS_HPACK_USE_LARGE_TABLES fast decoder) accepts Huffman-encoded strings whose final symbol is followed by 8 or more bits of EOS-prefix (all-ones) padding. RFC 7541 §5.2 requires:

A padding strictly longer than 7 bits MUST be treated as a decoding error.

lshpack_dec_huff_decode_full correctly rejects these inputs, so the two decoders disagree on input validity. As a consequence, library behavior also differs by build configuration: with LS_HPACK_USE_LARGE_TABLES=0 (where lshpack_dec_huff_decode is #defined to the full decoder) the same byte sequence is rejected, while the default build accepts it.

The condition is reachable through the public decoding path (lshpack_dec_decode → hdec_dec_str → lshpack_dec_huff_decode), not just the internal function.

Mechanism

In lshpack_dec_huff_decode, the no-symbol tail case is handled strictly — if (idx == 0xFFFF && avail_bits < 8) goto end; only accepts all-ones remainders shorter than 8 bits. But when the post-loop lookup emits a final symbol, the remaining avail_bits can be 8–10 (the tail holds at most 15 bits and the shortest code is 5), and the final padding check accepts any all-ones remainder regardless of length:

    if (avail_bits > 0)
    {
        if (((1u << avail_bits) - 1) != (buf & ((1u << avail_bits) - 1)))
            return -1;  /* Not EOF as expected */
    }

The full decoder's FSM clears the accept flag once padding exceeds 7 bits, hence the disagreement.

Reproducer

Build from the ls-hpack source tree:

gcc -O2 -I. -Ideps/xxhash -DXXH_HEADER_NAME='"xxhash.h"' \
    repro.c lshpack.c deps/xxhash/xxhash.c -o repro

#include <stdio.h>

int lshpack_dec_huff_decode_full(const unsigned char *src, int src_len,
                                 unsigned char *dst, int dst_len);
int lshpack_dec_huff_decode(const unsigned char *src, int src_len,
                            unsigned char *dst, int dst_len);

static void
try_input(const unsigned char *src, int src_len)
{
    unsigned char dst[64];
    int full, fast, i;

    full = lshpack_dec_huff_decode_full(src, src_len, dst, sizeof(dst));
    fast = lshpack_dec_huff_decode(src, src_len, dst, sizeof(dst));
    printf("input:");
    for (i = 0; i < src_len; ++i)
        printf(" %02x", src[i]);
    printf("\n  full: %d, fast: %d", full, fast);
    if (fast >= 0)
        printf(", fast decoded: \"%.*s\"", fast, dst);
    printf("\n");
}

int
main(void)
{
    /* 32 bits of symbols ("Dj1D3") + 8 bits of all-ones padding. */
    static const unsigned char in1[] = { 0xbf, 0xd0, 0x37, 0xd9, 0xff };
    /* Longer example, also >7 bits of padding after the final symbol. */
    static const unsigned char in2[] = { 0xd9, 0x68, 0x63, 0x84, 0x4c,
                                         0xfe, 0x77, 0xa0, 0xbc, 0xc9, 0xff };
    try_input(in1, sizeof(in1));
    try_input(in2, sizeof(in2));
    return 0;
}

Output on v2.3.5:

input: bf d0 37 d9 ff
  full: -1, fast: 5, fast decoded: "Dj1D3"
input: d9 68 63 84 4c fe 77 a0 bc c9 ff
  full: -1, fast: 13, fast decoded: "Qu1bA23XvleYc"

Both inputs should be rejected (and are, by the full decoder).

Impact

No memory-safety impact — bounds are respected; this is a conformance/leniency issue. A compliant peer never produces such padding, but RFC 7541 makes rejection a MUST, and conformance suites test exactly this (e.g. h2spec's HPACK 5.2 case sends over-long padding and expects a COMPRESSION_ERROR — a server using the fast decoder will not error). The decoder-vs-decoder and build-config inconsistency seems undesirable independent of the RFC reading.

Suggested fix

Reject all-ones remainders of 8 or more bits in the final check:

    if (avail_bits > 0)
    {
        if (avail_bits >= 8
            || ((1u << avail_bits) - 1) != (buf & ((1u << avail_bits) - 1)))
            return -1;  /* Not EOF as expected */
    }

We validated this change against the full decoder differentially (exhaustive 1–3-byte inputs plus extensive seeded fuzzing): with the guard added, the two decoders agree on validity for every tested input. Apache Traffic Server carries this patch in its vendored copy: apache/trafficserver#13259.

🤖 Generated with Claude Code

[dtikhonov]

Fixed in #83 (v2.6.3)

[phongn]

Thanks! I meant to open an issue with ls-hpack, hence closing it immediately, but it looks like it applies here too.