HPACK: Header Compression for HTTP/2
Extracted elements (29)
A static Huffman code derived from statistics over a large sample of HTTP headers is used rather than an adaptive code. This avoids the shared-context security risks of adaptive compression (as exploited by CRIME) while still providing useful compression gains.
HPACK was created to replace SPDY's use of DEFLATE for header compression, which was effective but exposed a security risk demonstrated by the CRIME attack. HPACK eliminates redundant header fields while limiting vulnerability to known security attacks and bounding memory requirements for constrained environments.
The encoder is solely responsible for deciding which header fields to insert into the dynamic table; the decoder executes the encoder's prescribed modifications without discretion. This asymmetry keeps decoders simple and enables wide interoperability.
The HPACK format is intentionally simple and inflexible to reduce the risk of interoperability or security issues due to implementation error. No extensibility mechanisms are defined; changes to the format are only possible by defining a complete replacement.
When used for bidirectional communication (e.g., HTTP/2), the encoding and decoding dynamic tables maintained by each endpoint are completely independent: the request and response dynamic tables are separate and must not be conflated.
A dynamic table size update MUST occur at the beginning of the first header block following a change to the maximum dynamic table size. When multiple size changes occur between header blocks, the smallest intermediate size MUST be signaled, followed by the final size (at most two updates).
An encoder MUST order header field representations in the header block according to their ordering in the original header list, and a decoder MUST order header fields in the decoded header list according to their ordering in the header block.
Duplicate entries in the dynamic table (entries with the same name and same value) MUST NOT be treated as an error by a decoder.
For Huffman-encoded strings: padding strictly longer than 7 bits MUST be treated as a decoding error; padding not corresponding to the MSBs of the EOS code MUST be treated as a decoding error; a Huffman-encoded string containing the EOS symbol MUST be treated as a decoding error.
Integer encodings that exceed implementation limits—in value or octet length—MUST be treated as decoding errors. Different limits may be set for each use of integers based on implementation constraints.
Intermediaries MUST NOT re-encode a value marked as never-indexed with a representation that would index it. If HPACK is used for re-encoding, the never-indexed literal representation MUST be used.
The dynamic table entry size is computed as: length of name in octets + length of value in octets + 32. The 32-octet overhead accounts for estimated per-entry structure cost (e.g., two 64-bit pointers and two 64-bit reference counts). Huffman encoding is not applied when calculating size.
The dynamic table is a per-context FIFO list of header fields maintained by both encoder and decoder, with the newest entry at the lowest index. It is initially empty, grows as header blocks are processed, and is bounded by a maximum size set by the protocol.
The static table (indices 1 to s) and dynamic table (indices s+1 to s+k) are combined into a single index address space. Indices strictly greater than the sum of both table lengths MUST be treated as a decoding error.
The static table is a predefined, read-only, ordered list of 61 common header fields (with index values 1–61), derived from the most frequent headers on popular web sites plus HTTP/2-specific pseudo-header fields. It is always accessible and may be shared across all encoding/decoding contexts.
An attacker may attempt to exhaust decoder memory. HPACK bounds both peak and steady-state memory: the dynamic table size is limited by the protocol (SETTINGS_HEADER_TABLE_SIZE in HTTP/2), and sequential processing of header fields limits transient memory use.
An attacker who can both inject headers into a compressed stream and observe the encoded lengths can probe the dynamic table state to confirm guesses about secret header values (a CRIME-style attack). HPACK mitigates this by requiring whole-field matches rather than character-by-character, but low-entropy values remain vulnerable.
Implementations can mitigate dynamic table probing by using never-indexed literals for sensitive header fields such as Cookie or Authorization, and may heuristically stop indexing a field that receives a large number of different values, limiting an attacker's ability to confirm guesses.
Implementations MUST set limits on integer values, integer encoded lengths, and string literal lengths to prevent large or maliciously crafted values from creating security weaknesses such as integer overflows or excessive memory allocation.
The attack is viable when two mutually distrustful entities share an HTTP/2 connection—e.g., an intermediary multiplexing requests from multiple clients toward an origin, or web origins on the same browser connection. In these cases, one entity may probe table entries inserted by another.
There is no currently known attack against HPACK's static Huffman encoding. A study (PETAL) found an information leakage from the static table but concluded an attacker could not recover meaningful information from it.
When the dynamic table maximum size is reduced, entries are evicted from the end (oldest entries) until the table size is within the new maximum. When a new entry is added, entries are evicted from the end until the table has room (size ≤ max − new entry size) or is empty; entries larger than the maximum size cause a complete table clear.
A dynamic table size update starts with the '001' 3-bit pattern followed by the new maximum size as a 5-bit-prefix integer. The new maximum size MUST be lower than or equal to the limit set by the protocol; a value exceeding this limit MUST be treated as a decoding error.
An indexed header field representation starts with a '1' bit followed by a 7-bit-prefix integer index. Index value 0 is not used and MUST be treated as a decoding error if encountered.
Integers are encoded with an N-bit prefix (N between 1 and 8). Values that fit in the prefix (< 2^N−1) are stored directly; larger values set the prefix to all 1s and encode the remainder in subsequent octets using a 7-bit base-128 varint with continuation flags in the MSB.
Literal header field never-indexed starts with the '0001' 4-bit pattern. The representation is identical in structure to 'without indexing' but signals that intermediaries MUST use this same representation when re-encoding, preventing compression of sensitive values.
Literal header field with incremental indexing starts with the '01' 2-bit pattern and uses a 6-bit-prefix index for the name (or 0 + literal name). The field is appended to the decoded header list and inserted at the beginning of the dynamic table.
Literal header field without indexing starts with the '0000' 4-bit pattern and uses a 4-bit-prefix index for the name. The field is appended to the decoded header list but does not modify the dynamic table.
String literals are encoded with a 1-bit Huffman flag (H), a 7-bit-prefix integer giving the byte length, and then the raw or Huffman-encoded string data. Padding after Huffman-encoded data uses the MSBs of the EOS symbol code.