This specification defines the format and compression of HTTP header fields in HTTP/2. The compression is based on EZFLATE, which is a token-based DEFLATE algorithm for secure compression within encrypted communication channels.

Editorial Note (To be removed by RFC Editor)

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

1. Introduction

[TODO: A significant portion of text the 'introduction' and 'security considerations' sections, is completely lifted from the HPACK Internet Draft; re-write or give credit somehow.]

In HTTP/1.1 (see [HTTP-p1]), header fields are encoded without any form of compression. As web pages have grown to include dozens to hundreds of requests, the redundant header fields in these requests now measurably increase latency and unnecessarily consume bandwidth (see [PERF1] and [PERF2]).

SPDY [SPDY] initially addressed this redundancy by compressing header fields using the DEFLATE format [DEFLATE], which proved very effective at efficiently representing the redundant header fields. However, that approach exposed a security risk as demonstrated by the CRIME attack (see [CRIME]).

A key observation of the CRIME and BREACH attacks is that they exploited the DEFLATE algorithm as described in RFC 1951 [DEFLATE], not the DEFLATE format (also described in RFC 1951).

EZFLATE [EZFLATE], is a token-based DEFLATE compression algorithm for secure compression within encrypted communication channels. The key feature of the EZFLATE algorithm (and primary difference to the algorithm described in RFC 1951), is that LZ77 <length, backward distance> tuples may only reference a duplicated token (octet string) occurring in a previous block, up to 32K input bytes before, if the current token exactly matches in length and octet values. As shown in Section 3.1, "Take a Bite out of CRIME", of [EZFLATE], this forces potential CRIME-like attackers to guess n-character secrets n characters at a time rather than one character at a time, making the search space no worse than a full brute-force attack.

This document defines 1) the formatting of HTTP/2 header fields, and 2) how EZFLATE is used to compress HTTP/2 header fields. Finally, this document also includes implementation recommendations.

In HTTP/1.1 [HTTP-p1] headers are defined as field-name, field-value pairs (see Section 3.2, "Header Fields" of [HTTP-p1]). The field-name and field-value are separated from each other by a single ':' character followed by optional whitespace. Each pair is separated by the two octet sequence CRLF (carriage return, line feed). The end of the header block is marked by an empty line followed by CRLF.

In HTTP/2, the headers are still field-name, field-value pairs except that each are length-prefixed octet strings to simplify parsing. In other words, the field-name and field-value are separately length-prefixed. In this way no separator is necessary between the field-name and field-value and no separator is necessary between consecutive pairs. The end of the header block is naturally defined as the end of a HTTP/2 HEADERS or PUSH_PROMISE frame with the END_HEADERS flag set [HTTP2].

Each field-name and field-value are encoded as an ASN.1 octet string [X.208-88][X.209-88]. This simply means the octets which compose a field-name or field-value are length-prefixed with a variable-length integer which indicates the exact number of octets composing the original field-name or field-value.

For ASN.1 encoded octet-strings, the length prefix is composed of at least a single octet, and optionally N additional octets, where N is exactly specified by the first octet as follows. If the length of the octets to be length-prefixed is less than 0x80 (128), then only a single octet is required for the length prefix and so the length-prefix octet is encoded as exactly the length (big endian) of the octets to be length-prefixed. If the length of the octets to be length-prefixed is greater than or equal to 0x80 (128), then the most significant bit of the first length-prefix octet is set (i.e. 0x80), and the remaining 7 bits specify the number of additional octets N (big endian) which will be added to encode the length, as an unsigned integer (big endian), of the octets to be length-prefixed .

2.1. ASN.1 Octet String Examples

The following are examples of computing the length prefix for converting various octet strings to ASN.1 octet strings.

2.1.1. Example 1 (length 15)

The ASCII string "accept-encoding" is to be converted to an ASN.1 octet string. The length of the string is 15 octets. Since 15 is less than 128, the length prefix is simply a single octet with the value 15 (0x0f).

2.1.2. Example 2 (length 33)

The ASCII string "gzip;q=1.0, identity;q=0.5, *;q=0" is to be converted to an ASN.1 octet string. The length of the string is 33 octets. Since 33 is less than 128, the length prefix is simply a single octet with the value 33 (0x21).

2.1.3. Example 3 (length 128)

The string of octets 0x00 0x01 ... 0x7d 0x7f is to be converted to an ASN.1 octet string. The number of octets is 128. Since 128 equals 128, the first octet of the length prefix has the most significant bit set to indicate the length prefix is longer than one octet. The remaining seven bits encode the number of additional octets necessary to represent the value 128 as a big endian unsigned integer. Since encoding 128 requires one octet, the seven remaining bits encode the value 1 (0x01). The second octet encodes the value 128 (0x80).

2.1.4. Example 4 (length 258)

The string of octets 0x00 0x01 ... 0xfe 0xff 0x00 0x01 is to be converted to an ASN.1 octet string. The number of octets is 258. Since 258 is greater than 128, the first octet of the length prefix has the most significant bit set to indicate the length prefix is longer than one octet. The remaining seven bits encode the number of additional octets necessary to represent the value 258 as a big endian unsigned integer. Since encoding 258 requires two octets, the seven remaining bits encode the value 2 (0x02). The second and third octets encode the value 258 (0x01 0x02).

3. EZFLATE Tokenization Rules

EZFLATE is itself agnostic to tokenization methods and delimiter sets. Appropriate tokenization rules and delimiter sets depend on the type of data to be compressed. For HTTP/2 header data, each field-name and field-value are tokenized separately.

3.1. Header Name Tokenization

Since header field names are typically static, it is not beneficial to tokenize field names. Therefore field names are fed to the EZFLATE compressor as a single token, including the ASN.1 length prefix.

3.2. Header Value Tokenization

	      { ' ', '\t', ';', ',' }

Figure 1

Field values, on the other hand, have varying values of staticity ranging from very static (e.g. :scheme, user-agent) to semi-static (e.g. accept, accept-encoding) to very dynamic (e.g. :path, date). Field values MAY be tokenized with following set of delimiters:

Special token delimiters for header values containing a path:

	      { '/', '?', '&', '=' }

Figure 2

The ASN.1 length prefix MAY be treated as a delimiter and therefore treated as a separate token.

Finally, note that per Section 3.2 of [EZFLATE], a sequence of consecutive delimiters are to be treated as a single unit (e.g. as one token). For examle, see Figure 3 and Figure 4, where the consecutive delimiter characters ',' and ' ', are treated as a single token ", ".

3.3. Tokenization Example

The following is an example of converting an HTTP header name-value pair into ASN.1 length prefixed octet strings (see Section 2 and then tokenizing the octet string based on the tokenization rules.

accept-encoding: gzip;q=1.0, identity;q=0.5, *;q=0

The following header is to be encoded: Section 2.1.1 and Section 2.1.1).

Hex dump of the header converted to ASN.1 octet strings:

0000000 0f61 6363 6570 742d | 656e 636f 6469 6e67 | .accept-encoding
0000010 2167 7a69 703b 713d | 312e 302c 2069 6465 | !gzip;q=1.0, ide
0000020 6e74 6974 793b 713d | 302e 352c 202a 3b71 | ntity;q=0.5, *;q
0000030 3d30                |                     | =0

Hex dump of the header name token:

0000000 0f61 6363 6570 742d | 656e 636f 6469 6e67 | .accept-encoding

Token 1:

0000010 2167 7a69 70        |                     | !gzip

Token 2:

0000010             3b      |                     |      ;

Token 3:

0000010                713d | 312e 30             |       q=1.0

Token 4:

0000010                     |        2c 20        |            ,

Figure 3

Token 5:

0000010                     |             69 6465 |              ide
0000020 6e74 6974 79        |                     | ntity

Token 6:

0000020             3b      |                     |      ;

Token 7:

0000020                713d | 302e 35             |       q=0.5

Token 8:

0000020                     |        2c 20        |            ,

Figure 4

Token 9:

0000020                     |             2a      |              *

Token 10:

0000020                     |                3b   |               ;

Token 11:

0000020                     |                  71 |                q
0000030 3d30                |                     | =0

3.4. Sub-Tokenization

The DEFLATE [DEFLATE] format has a fixed maximum length of 258 octets for matches (see Section 3.2.5 of [DEFLATE]). As such, tokens with length L greater than 258 octets SHOULD be sub-tokenized into sub-tokens as follows. The number of sub-tokens N MUST be N = (L + 257) / 258 (integer division). If N > 2, the first N - 2 sub-tokens MUST be 258 octets in length. In all cases, the final two sub-tokens MUST have length greater than or equal to 129 (258 / 2). Let R be the remaining length for the final two tokens. The length of the first remaining token is L[N - 1] = R - R / 2 and the length of the second remaining token is L[N] = R / 2 (where the index is 1..N). Alternatively, tokens with length L greater than 258 octets may simply be emitted as literals.

Consider the following examples:

3.4.1. Sub-Tokenization Example 1 (1292 octet token)

N  = (1292 + 257) / 258 = 1549 / 258 = 6
L1 = 258
L2 = 258
L3 = 258
L4 = 258
R  = 1292 - 4 * 258 = 260
L5 = 260 - 260 / 2  = 130
L6 = 260 / 2        = 130

A token T, 1292 octets in length, is to be sub-tokenized.

3.4.2. Sub-Tokenization Example 2 (516 octet token)

N  = (516 + 257) / 258 = 773 / 258 = 2
R  = 516
L1 = R - R / 2 = 258
L2 = R / 2     = 258

A token T, 516 octets in length, is to be sub-tokenized.

3.4.3. Sub-Tokenization Example 3 (259 octet token)

N  = (259 + 257) / 258 = 516 / 258 = 2
R  = 259
L1 = R - R / 2 = 130
L2 = R / 2     = 129

A token T, 259 octets in length, is to be sub-tokenized.

4. Security Considerations

An EZFLATE compressor can act as an oracle to an attacker probing the compression context. However, the attacker can only find out if the guess of the entire token is correct or not.

Still, an attacker could take advantage of this limited information for breaking low-entropy secrets using a brute-force attack. A server usually has some protections against such brute-force attack. Here, the attack would target the client, where it would be harder to detect. The attack would be even more dangerous if the attacker is able to prevent the traffic generated by its brute-force attack from reaching the server.

To offer protection against such type of attacks, and endpoint MUST use non-compressed DEFLATE blocks (see Section 3.2.4 of [DEFLATE]) to prevent the compression of any header field whose value contains a secret which could be put at risk by a brute-force attack.

5. Acknowledgements

Roberto Peon and Hervé Ruellan.

6. References

6.1. Normative References

[EZFLATE]	Morgan, K. and C. Brunhuber, "EZFLATE: Token-based DEFLATE Compression", Internet-Draft draft-morgan-ezflate, June 2014.
[X.208-88]	CCITT, "Recommendation X.208: Specification of Abstract Syntax Notation One (ASN.1)", January 1998.
[X.209-88]	CCITT, "Recommendation X.209: Specification of Basic Encoding Rules for Abstract Syntax Notation One", January 1998.

6.2. Informative References

[CRIME]	Rizzo, J. and T. Duong, "The CRIME Attack", September 2012.
[DEFLATE]	Deutsch, P., "DEFLATE Compressed Data Format Specification version 1.3", RFC 1951, May 1996.
[HTTP-p1]	Fielding, R. and J. Reschke, "Hypertext Transfer Protocol (HTTP/1.1): Message Syntax and Routing", Internet-Draft draft-ietf-httpbis-p1-messaging-26, February 2014.
[HTTP2]	Belshe, M., Peon, R. and M. Thomson, "Hypertext Transfer Protocol version 2", Internet-Draft draft-ietf-httpbis-http2-10, February 2014.
[SPDY]	Belshe, M. and R. Peon, "SPDY Protocol", Internet-Draft draft-mbelshe-httpbis-spdy-00, February 2012.

Authors' Addresses

Keith Shearl Morgan International Atomic Energy Agency EMail: k.morgan@iaea.org

Christoph Brunhuber International Atomic Energy Agency EMail: c.brunhuber@iaea.org

Abstract