Hpack 阅读笔记
抽象
该规范定义了HPACK，HPACK的压缩格式 有效地表示要在HTTP / 2中使用的HTTP标头字段。
解决问题
该规范定义了HPACK，这是一种新型压缩机，它消除了冗余标头字段，将漏洞限制为已知安全性攻击，并且在受限条件下使用时具有有限的内存要求环境。
关键术语
标头字段：名称/值对。名称和值都是视为八位字节的不透明序列。 动态表：动态表是一个表，将存储的标头字段与索引值相关联。这个桌子是动态且特定于编码或解码上下文。 静态表：静态表是一个表，静态地将经常出现的标头字段与索引值。该表是有序的，只读的，始终可以访问，并且可以在所有编码或解码之间共享上下文。 标头列表：标头列表是标头字段的有序集合联合编码，并且可以包含重复的标头字段。HTTP / 2标头中包含的标头字段的完整列表块是标题列表。 标头字段表示形式：标头字段可以表示为编码形式，可以是文字形式或索引形式。 标头块：标头字段表示形式的有序列表，解码时会产生完整的标头列表。
索引表
HPACK使用两个表将标头字段与索引相关联。的静态表是预定义的，并且包含通用表标头字段（其中大多数带有空值）。动态表是动态的，编码器可以使用它来在编码的标题列表中重复的索引标题字段。 这两个表合并为一个地址空间，用于定义索引值。
索引地址空间
索引严格大于静态表的长度动态表中的元素的长度减去静态表以找到动态表中的索引。 索引严格大于两个表的长度之和必须视为解码错误。
头字段表示处理
定义了获取报头列表的头块的处理过程在这一部分。以确保解码成功生成一个报头列表时，解码器必须遵守以下规则。
头块中包含的所有头字段表示都是按照它们出现的顺序进行处理。
indexed表示形式需要执行以下操作： 对应于任一项中所引用条目的标题字段静态表或动态表被附加到解码后标头列表。 动态表中未添加的文字表示形式需要采取以下措施： 头字段被附加到解码后的标头列表中。 动态表的文字表示形式需要执行以下操作： 标头字段被附加到解码后的标头列表中。 头字段插入到动态内容的开头表。此插入可能导致驱逐先前的动态表中的条目。
计算表大小
动态表的大小是其表项大小的总和。 条目的大小是其名称长度的总和（以八位字节为单位），其值的长度（以八位字节为单位）和32。 条目的大小是使用其名称的长度和值，不应用任何霍夫曼编码。
动态表大小更改时的逐出
每当减小动态表的最大大小时，条目从动态表的末尾逐出，直到动态表小于或等于最大大小。
添加新条目时将条目逐出
在将新条目添加到动态表之前，逐出条目从动态表的末尾到动态表的大小小于或等于（最大大小-新条目大小）或直到表是空的。如果新条目的大小小于或等于最大大小，该条目将添加表中。这不是错误尝试添加一个大于最大大小的条目；一个尝试添加大于最大大小的条目导致表清空所有现有条目并生成一个空表。 新条目可以引用动态表中的条目名称将此新条目添加到动态广告素材中时将被逐出表。请注意实现，以免删除如果引用条目已从动态表中逐出，则引用名称表，然后插入新条目。
整数表示
整数用于表示名称索引，标头字段索引或字符串长度。整数表示可以从一个八位位组。为了优化处理，整数表示总是在八位字节的末尾结束。 整数分为两部分：前缀填充当前八位位组和可选的八位位组列表，如果整数值不适合前缀的位数前缀（称为N）是整数表示的参数。 如果整数值足够小，即严格小于2 ^ N-1，它被编码在N位前缀内。
否则，将前缀的所有位设置为1，并将值设置为使用一个或多个八位位组的列表对减少了2 ^ N-1的位进行编码。每个八位位组的最高有效位用作延续 标志：除列表中的最后一个八位字节外，其值均设置为1。八位位组的其余位用于编码减少的值。
代码示例：
字符串文字表示
头字段名称和头字段值可以表示为字符串文字。字符串文字被编码为直接编码字符串文字的八位字节或使用霍夫曼代码。
字符串文字表示形式包含以下字段： H：一位标志H，指示是否字符串是霍夫曼编码的。 字符串长度：用于编码字符串的八位字节数文字，编码为带有7位前缀的整数。 字符串数据：字符串文字的编码数据。如果H为0，那么编码后的数据就是字符串文字的原始八位位组。如果H为'1'，则编码数据为Huffman编码字符串字面量。 使用霍夫曼编码的字符串文字使用霍夫曼代码。编码后的数据是对应于的每个八位位组的代码的按位串联字符串文字。 由于霍夫曼编码的数据并不总是以八位字节为边界，在其后插入一些填充，直到下一个八位位组边界。至防止将此填充误解为字符串的一部分文字，代码的最高有效位对应于使用EOS（字符串结尾）符号。 解码时，编码数据末尾的不完整代码为被视为填充和丢弃。填充严格更长超过7位必须视为解码错误。填充不对应于EOS代码的最高有效位 符号必须被视为解码错误。霍夫曼编码的字符串包含EOS符号的文字必须被视为解码错误。
文字标题字段表示
文字标头字段表示形式包含文字标头字段值。标头字段名称以文字形式或通过以下方式提供从静态表或现有表中引用现有表项动态表。 本规范定义了文字头字段的三种形式表示形式：有索引，无索引，从不索引。
带增量索引的文字标题字段
具有增量索引表示的文字标头字段结果是将头字段附加到解码的头列表中，并且将其作为新条目插入动态表。
具有增量索引表示的文字标头字段从“ 01” 2位模式开始。
没有索引的文字标题字段
没有索引表示的文字标头字段会导致将标题字段附加到已解码的标题列表，而无需更改动态表。
没有索引表示形式的文字标头字段以'0000'4位模式。
文字头字段从不索引
文字标头字段永不索引表示形式导致将标题字段附加到已解码的标题列表，而无需更改动态表。
文字标头字段永不索引的表示形式以'0001'4位模式。
动态表大小更新
动态表格大小更新从“ 001” 3位模式开始，然后是新的最大尺寸，以整数表示，带有5位前缀。 新的最大尺寸必须小于或等于限制由协议使用HPACK确定。超过此值限制必须视为解码错误。在HTTP / 2中，此限制为SETTINGS_HEADER_TABLE_SIZE参数的最后一个值（请参见从解码器收到并确认的通过编码器。 减小动态表的最大大小可能会导致条目被驱逐。
适用于HPACK和HTTP
HPACK可以缓解但不能完全阻止仿照通过强制猜测以匹配整个标头字段来实现CRIME [ CRIME ]值而不是单个字符。攻击者只能学习猜测是否正确，因此将其简化为蛮力 猜测标题字段的值。 因此，恢复特定标头字段值的可行性取决于值的熵。结果，具有高价值的不太可能成功恢复。但是，价值低的参数仍然脆弱。 这种性质的攻击有可能在任何两个相互之间的时间不信任的实体控制放置的请求或响应到单个HTTP / 2连接上。如果共享HPACK压缩器允许一个实体向动态表中添加条目，而另一个实体访问这些条目，则可以了解表的状态。 来自互不信任实体的请求或响应发生以下情况时，中介者： 在单个连接上将来自多个客户端的请求发送到原始服务器，或从多个原始服务器获取响应并将其放置在与客户端的共享连接。 Web浏览器还需要假设请求是在相同的不同Web来源的连接是相互建立的不信任的实体。
twitter hpack
关键代码：
Encoder.java
/**
* Encode the header field into the header block.
*/
public void encodeHeader(OutputStream out, byte[] name, byte[] value, boolean sensitive) throws IOException {
// If the header value is sensitive then it must never be indexed
if (sensitive) {
int nameIndex = getNameIndex(name);
encodeLiteral(out, name, value, IndexType.NEVER, nameIndex);
return;
}
// If the peer will only use the static table
if (capacity == 0) {
int staticTableIndex = StaticTable.getIndex(name, value);
if (staticTableIndex == -1) {
int nameIndex = StaticTable.getIndex(name);
encodeLiteral(out, name, value, IndexType.NONE, nameIndex);
} else {
encodeInteger(out, 0x80, 7, staticTableIndex);
}
return;
}
int headerSize = HeaderField.sizeOf(name, value);
// If the headerSize is greater than the max table size then it must be encoded literally
if (headerSize > capacity) {
int nameIndex = getNameIndex(name);
encodeLiteral(out, name, value, IndexType.NONE, nameIndex);
return;
}
HeaderEntry headerField = getEntry(name, value);
if (headerField != null) {
int index = getIndex(headerField.index) + StaticTable.length;
// Section 6.1\. Indexed Header Field Representation
encodeInteger(out, 0x80, 7, index);
} else {
int staticTableIndex = StaticTable.getIndex(name, value);
if (staticTableIndex != -1) {
// Section 6.1\. Indexed Header Field Representation
encodeInteger(out, 0x80, 7, staticTableIndex);
} else {
int nameIndex = getNameIndex(name);
if (useIndexing) {
ensureCapacity(headerSize);
}
IndexType indexType = useIndexing ? IndexType.INCREMENTAL : IndexType.NONE;
encodeLiteral(out, name, value, indexType, nameIndex);
if (useIndexing) {
add(name, value);
}
}
}
}
Decode.java
/**
* Decode the header block into header fields.
*/
public void decode(InputStream in, HeaderListener headerListener) throws IOException {
while (in.available() > 0) {
switch (state) {
case READ_HEADER_REPRESENTATION:
byte b = (byte) in.read();
if (maxDynamicTableSizeChangeRequired && (b & 0xE0) != 0x20) {
// Encoder MUST signal maximum dynamic table size change
throw MAX_DYNAMIC_TABLE_SIZE_CHANGE_REQUIRED;
}
if (b < 0) {
// Indexed Header Field
index = b & 0x7F;
if (index == 0) {
throw ILLEGAL_INDEX_VALUE;
} else if (index == 0x7F) {
state = State.READ_INDEXED_HEADER;
} else {
indexHeader(index, headerListener);
}
} else if ((b & 0x40) == 0x40) {
// Literal Header Field with Incremental Indexing
indexType = IndexType.INCREMENTAL;
index = b & 0x3F;
if (index == 0) {
state = State.READ_LITERAL_HEADER_NAME_LENGTH_PREFIX;
} else if (index == 0x3F) {
state = State.READ_INDEXED_HEADER_NAME;
} else {
// Index was stored as the prefix
readName(index);
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
}
} else if ((b & 0x20) == 0x20) {
// Dynamic Table Size Update
index = b & 0x1F;
if (index == 0x1F) {
state = State.READ_MAX_DYNAMIC_TABLE_SIZE;
} else {
setDynamicTableSize(index);
state = State.READ_HEADER_REPRESENTATION;
}
} else {
// Literal Header Field without Indexing / never Indexed
indexType = ((b & 0x10) == 0x10) ? IndexType.NEVER : IndexType.NONE;
index = b & 0x0F;
if (index == 0) {
state = State.READ_LITERAL_HEADER_NAME_LENGTH_PREFIX;
} else if (index == 0x0F) {
state = State.READ_INDEXED_HEADER_NAME;
} else {
// Index was stored as the prefix
readName(index);
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
}
}
break;
case READ_MAX_DYNAMIC_TABLE_SIZE:
int maxSize = decodeULE128(in);
if (maxSize == -1) {
return;
}
// Check for numerical overflow
if (maxSize > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
setDynamicTableSize(index + maxSize);
state = State.READ_HEADER_REPRESENTATION;
break;
case READ_INDEXED_HEADER:
int headerIndex = decodeULE128(in);
if (headerIndex == -1) {
return;
}
// Check for numerical overflow
if (headerIndex > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
indexHeader(index + headerIndex, headerListener);
state = State.READ_HEADER_REPRESENTATION;
break;
case READ_INDEXED_HEADER_NAME:
// Header Name matches an entry in the Header Table
int nameIndex = decodeULE128(in);
if (nameIndex == -1) {
return;
}
// Check for numerical overflow
if (nameIndex > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
readName(index + nameIndex);
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
break;
case READ_LITERAL_HEADER_NAME_LENGTH_PREFIX:
b = (byte) in.read();
huffmanEncoded = (b & 0x80) == 0x80;
index = b & 0x7F;
if (index == 0x7f) {
state = State.READ_LITERAL_HEADER_NAME_LENGTH;
} else {
nameLength = index;
// Disallow empty names -- they cannot be represented in HTTP/1.x
if (nameLength == 0) {
throw DECOMPRESSION_EXCEPTION;
}
// Check name length against max header size
if (exceedsMaxHeaderSize(nameLength)) {
if (indexType == IndexType.NONE) {
// Name is unused so skip bytes
name = EMPTY;
skipLength = nameLength;
state = State.SKIP_LITERAL_HEADER_NAME;
break;
}
// Check name length against max dynamic table size
if (nameLength + HEADER_ENTRY_OVERHEAD > dynamicTable.capacity()) {
dynamicTable.clear();
name = EMPTY;
skipLength = nameLength;
state = State.SKIP_LITERAL_HEADER_NAME;
break;
}
}
state = State.READ_LITERAL_HEADER_NAME;
}
break;
case READ_LITERAL_HEADER_NAME_LENGTH:
// Header Name is a Literal String
nameLength = decodeULE128(in);
if (nameLength == -1) {
return;
}
// Check for numerical overflow
if (nameLength > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
nameLength += index;
// Check name length against max header size
if (exceedsMaxHeaderSize(nameLength)) {
if (indexType == IndexType.NONE) {
// Name is unused so skip bytes
name = EMPTY;
skipLength = nameLength;
state = State.SKIP_LITERAL_HEADER_NAME;
break;
}
// Check name length against max dynamic table size
if (nameLength + HEADER_ENTRY_OVERHEAD > dynamicTable.capacity()) {
dynamicTable.clear();
name = EMPTY;
skipLength = nameLength;
state = State.SKIP_LITERAL_HEADER_NAME;
break;
}
}
state = State.READ_LITERAL_HEADER_NAME;
break;
case READ_LITERAL_HEADER_NAME:
// Wait until entire name is readable
if (in.available() < nameLength) {
return;
}
name = readStringLiteral(in, nameLength);
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
break;
case SKIP_LITERAL_HEADER_NAME:
skipLength -= in.skip(skipLength);
if (skipLength == 0) {
state = State.READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
}
break;
case READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX:
b = (byte) in.read();
huffmanEncoded = (b & 0x80) == 0x80;
index = b & 0x7F;
if (index == 0x7f) {
state = State.READ_LITERAL_HEADER_VALUE_LENGTH;
} else {
valueLength = index;
// Check new header size against max header size
long newHeaderSize = (long) nameLength + (long) valueLength;
if (exceedsMaxHeaderSize(newHeaderSize)) {
// truncation will be reported during endHeaderBlock
headerSize = maxHeaderSize + 1;
if (indexType == IndexType.NONE) {
// Value is unused so skip bytes
state = State.SKIP_LITERAL_HEADER_VALUE;
break;
}
// Check new header size against max dynamic table size
if (newHeaderSize + HEADER_ENTRY_OVERHEAD > dynamicTable.capacity()) {
dynamicTable.clear();
state = State.SKIP_LITERAL_HEADER_VALUE;
break;
}
}
if (valueLength == 0) {
insertHeader(headerListener, name, EMPTY, indexType);
state = State.READ_HEADER_REPRESENTATION;
} else {
state = State.READ_LITERAL_HEADER_VALUE;
}
}
break;
case READ_LITERAL_HEADER_VALUE_LENGTH:
// Header Value is a Literal String
valueLength = decodeULE128(in);
if (valueLength == -1) {
return;
}
// Check for numerical overflow
if (valueLength > Integer.MAX_VALUE - index) {
throw DECOMPRESSION_EXCEPTION;
}
valueLength += index;
// Check new header size against max header size
long newHeaderSize = (long) nameLength + (long) valueLength;
if (newHeaderSize + headerSize > maxHeaderSize) {
// truncation will be reported during endHeaderBlock
headerSize = maxHeaderSize + 1;
if (indexType == IndexType.NONE) {
// Value is unused so skip bytes
state = State.SKIP_LITERAL_HEADER_VALUE;
break;
}
// Check new header size against max dynamic table size
if (newHeaderSize + HEADER_ENTRY_OVERHEAD > dynamicTable.capacity()) {
dynamicTable.clear();
state = State.SKIP_LITERAL_HEADER_VALUE;
break;
}
}
state = State.READ_LITERAL_HEADER_VALUE;
break;
case READ_LITERAL_HEADER_VALUE:
// Wait until entire value is readable
if (in.available() < valueLength) {
return;
}
byte[] value = readStringLiteral(in, valueLength);
insertHeader(headerListener, name, value, indexType);
state = State.READ_HEADER_REPRESENTATION;
break;
case SKIP_LITERAL_HEADER_VALUE:
valueLength -= in.skip(valueLength);
if (valueLength == 0) {
state = State.READ_HEADER_REPRESENTATION;
}
break;
default:
throw new IllegalStateException("should not reach here");
}
}
}
HuffmanEncoder.java
/**
* Compresses the input string literal using the Huffman coding.
*
* @param out the output stream for the compressed data
* @param data the string literal to be Huffman encoded
* @param off the start offset in the data
* @param len the number of bytes to encode
* @throws IOException if an I/O error occurs. In particular,
* an <code>IOException</code> may be thrown if the
* output stream has been closed.
*/
public void encode(OutputStream out, byte[] data, int off, int len) throws IOException {
if (out == null) {
throw new NullPointerException("out");
} else if (data == null) {
throw new NullPointerException("data");
} else if (off < 0 || len < 0 || (off + len) < 0 || off > data.length || (off + len) > data.length) {
throw new IndexOutOfBoundsException();
} else if (len == 0) {
return;
}
long current = 0;
int n = 0;
for (int i = 0; i < len; i++) {
int b = data[off + i] & 0xFF;
int code = codes[b];
int nbits = lengths[b];
current <<= nbits;
current |= code;
n += nbits;
while (n >= 8) {
n -= 8;
out.write(((int) (current >> n)));
}
}
if (n > 0) {
current <<= (8 - n);
current |= (0xFF >>> n); // this should be EOS symbol
out.write((int) current);
}
}
/**
* Returns the number of bytes required to Huffman encode the input string literal.
*
* @param data the string literal to be Huffman encoded
* @return the number of bytes required to Huffman encode <code>data</code>
*/
public int getEncodedLength(byte[] data) {
if (data == null) {
throw new NullPointerException("data");
}
long len = 0;
for (byte b : data) {
len += lengths[b & 0xFF];
}
return (int) ((len + 7) >> 3);
}
HuffmanDecoder.java
/**
* Decompresses the given Huffman coded string literal.
*
* @param buf the string literal to be decoded
* @return the output stream for the compressed data
* @throws IOException if an I/O error occurs. In particular,
* an <code>IOException</code> may be thrown if the
* output stream has been closed.
*/
public byte[] decode(byte[] buf) throws IOException {
ByteArrayOutputStream baos = new ByteArrayOutputStream();
Node node = root;
int current = 0;
int bits = 0;
for (int i = 0; i < buf.length; i++) {
int b = buf[i] & 0xFF;
current = (current << 8) | b;
bits += 8;
while (bits >= 8) {
int c = (current >>> (bits - 8)) & 0xFF;
node = node.children[c];
bits -= node.bits;
if (node.isTerminal()) {
if (node.symbol == HpackUtil.HUFFMAN_EOS) {
throw EOS_DECODED;
}
baos.write(node.symbol);
node = root;
}
}
}
while (bits > 0) {
int c = (current << (8 - bits)) & 0xFF;
node = node.children[c];
if (node.isTerminal() && node.bits <= bits) {
bits -= node.bits;
baos.write(node.symbol);
node = root;
} else {
break;
}
}
// Section 5.2\. String Literal Representation
// Padding not corresponding to the most significant bits of the code
// for the EOS symbol (0xFF) MUST be treated as a decoding error.
int mask = (1 << bits) - 1;
if ((current & mask) != mask) {
throw INVALID_PADDING;
}
return baos.toByteArray();
}
private static void insert(Node root, int symbol, int code, byte length) {
// traverse tree using the most significant bytes of code
Node current = root;
while (length > 8) {
if (current.isTerminal()) {
throw new IllegalStateException("invalid Huffman code: prefix not unique");
}
length -= 8;
int i = (code >>> length) & 0xFF;
if (current.children[i] == null) {
current.children[i] = new Node();
}
current = current.children[I];
}
Node terminal = new Node(symbol, length);
int shift = 8 - length;
int start = (code << shift) & 0xFF;
int end = 1 << shift;
for (int i = start; i < start + end; i++) {
current.children[i] = terminal;
}
}
附录
静态表定义
静态表包含一个预定义的标头字段的固定列表。 静态表是根据最常见的标题字段创建的由流行的网站使用，另外还有特定于HTTP / 2的信息伪头字段。对于标题具有一些频繁值的字段，为每个字段添加了一个条目这些频繁的价值观对于其他标题字段，添加了一个条目具有空值。 表列出了构成静态对象的预定义头字段表并给出每个条目的索引。
Huffman Code
表中的每一行均定义用于表示符号的代码： sym：要表示的符号。它是一个十进制值八位位组，可能以ASCII表示形式开头。一个特定符号“ EOS”用于指示字符串的结尾文字。 位编码：符号的霍夫曼编码，表示为以2为基的整数，在最高有效位（MSB）上对齐。 十六进制代码：符号的霍夫曼代码，表示为十六进制整数，在最低有效位（LSB）上对齐。 len：代表符号的代码的位数。
