HTTPbis K. Morgan Internet-Draft C. Brunhuber Intended status: Standards Track IAEA Expires: December 4, 2014 June 2, 2014 H2EZ: HTTP/2 Header Compression draft-morgan-http2-header-compression-00 Abstract 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) Discussion of this draft takes place on the HTTPBIS working group mailing list (ietf-http-wg@w3.org), which is archived at . Working Group information can be found at ; Status of This Memo 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 Internet-Draft will expire on December 4, 2014. Copyright Notice Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Morgan & Brunhuber Expires December 4, 2014 [Page 1] Internet-Draft H2EZ June 2014 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. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Detailed Header Format . . . . . . . . . . . . . . . . . . . . 3 2.1. ASN.1 Octet String Examples . . . . . . . . . . . . . . . 4 2.1.1. Example 1 (length 15) . . . . . . . . . . . . . . . . 4 2.1.2. Example 2 (length 33) . . . . . . . . . . . . . . . . 4 2.1.3. Example 3 (length 128) . . . . . . . . . . . . . . . . 5 2.1.4. Example 4 (length 258) . . . . . . . . . . . . . . . . 5 3. EZFLATE Tokenization Rules . . . . . . . . . . . . . . . . . . 6 3.1. Header Name Tokenization . . . . . . . . . . . . . . . . . 6 3.2. Header Value Tokenization . . . . . . . . . . . . . . . . 6 3.3. Tokenization Example . . . . . . . . . . . . . . . . . . . 7 3.4. Sub-Tokenization . . . . . . . . . . . . . . . . . . . . . 9 3.4.1. Sub-Tokenization Example 1 (1292 octet token) . . . . 9 3.4.2. Sub-Tokenization Example 2 (516 octet token) . . . . . 9 3.4.3. Sub-Tokenization Example 3 (259 octet token) . . . . . 10 4. Security Considerations . . . . . . . . . . . . . . . . . . . 10 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.1. Normative References . . . . . . . . . . . . . . . . . . . 10 6.2. Informative References . . . . . . . . . . . . . . . . . . 11 Morgan & Brunhuber Expires December 4, 2014 [Page 2] Internet-Draft H2EZ June 2014 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 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. 2. Detailed Header Format 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 Morgan & Brunhuber Expires December 4, 2014 [Page 3] Internet-Draft H2EZ June 2014 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). Hex dump of the resulting ASN.1 octet string: 0000000 0f61 6363 6570 742d | 656e 636f 6469 6e67 | .accept-encoding 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 Morgan & Brunhuber Expires December 4, 2014 [Page 4] Internet-Draft H2EZ June 2014 single octet with the value 33 (0x21). Hex dump of the resulting ASN.1 octet string: 0000000 2167 7a69 703b 713d | 312e 302c 2069 6465 | !gzip;q=1.0, ide 0000010 6e74 6974 793b 713d | 302e 352c 202a 3b71 | ntity;q=0.5, *;q 0000020 3d30 | | =0 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). Hex dump of the resulting ASN.1 octet string: 0000000 8180 0001 0203 0405 | 0607 0809 0a0b 0c0d | ................ 0000010 0e0f 1011 1213 1415 | 1617 1819 1a1b 1c1d | ................ 0000020 1e1f 2021 2223 2425 | 2627 2829 2a2b 2c2d | .. !"#$%&'()*+,- 0000030 2e2f 3031 3233 3435 | 3637 3839 3a3b 3c3d | ./0123456789:;<= 0000040 3e3f 4041 4243 4445 | 4647 4849 4a4b 4c4d | >?@ABCDEFGHIJKLM 0000050 4e4f 5051 5253 5455 | 5657 5859 5a5b 5c5d | NOPQRSTUVWXYZ[\] 0000060 5e5f 6061 6263 6465 | 6667 6869 6a6b 6c6d | ^_`abcdefghijklm 0000070 6e6f 7071 7273 7475 | 7677 7879 7a7b 7c7d | nopqrstuvwxyz{|} 0000080 7e7f | | ~. 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). Morgan & Brunhuber Expires December 4, 2014 [Page 5] Internet-Draft H2EZ June 2014 Hex dump of the resulting ASN.1 octet string: 000000 8201 0200 0102 0304 | 0506 0708 090a 0b0c | ................ 000010 0d0e 0f10 1112 1314 | 1516 1718 191a 1b1c | ................ 000020 1d1e 1f20 2122 2324 | 2526 2728 292a 2b2c | ... !"#$%&'()*+, 000030 2d2e 2f30 3132 3334 | 3536 3738 393a 3b3c | -./0123456789:;< 000040 3d3e 3f40 4142 4344 | 4546 4748 494a 4b4c | =>?@ABCDEFGHIJKL 000050 4d4e 4f50 5152 5354 | 5556 5758 595a 5b5c | MNOPQRSTUVWXYZ[\ 000060 5d5e 5f60 6162 6364 | 6566 6768 696a 6b6c | ]^_`abcdefghijkl 000070 6d6e 6f70 7172 7374 | 7576 7778 797a 7b7c | mnopqrstuvwxyz{| 000080 7d7e 7f80 8182 8384 | 8586 8788 898a 8b8c | ................ 000090 8d8e 8f90 9192 9394 | 9596 9798 999a 9b9c | ................ 0000a0 9d9e 9fa0 a1a2 a3a4 | a5a6 a7a8 a9aa abac | ................ 0000b0 adae afb0 b1b2 b3b4 | b5b6 b7b8 b9ba bbbc | ................ 0000c0 bdbe bfc0 c1c2 c3c4 | c5c6 c7c8 c9ca cbcc | ................ 0000d0 cdce cfd0 d1d2 d3d4 | d5d6 d7d8 d9da dbdc | ................ 0000e0 ddde dfe0 e1e2 e3e4 | e5e6 e7e8 e9ea ebec | ................ 0000f0 edee eff0 f1f2 f3f4 | f5f6 f7f8 f9fa fbfc | ................ 000100 fdfe ff00 01 | | ................ 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 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: { ' ', '\t', ';', ',' } Figure 1 Additionally, the set of headers { ":path", "location", "content- location" } MAY instead be tokenized with the following set of delimiters: Morgan & Brunhuber Expires December 4, 2014 [Page 6] Internet-Draft H2EZ June 2014 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. The following header is to be encoded: accept-encoding: gzip;q=1.0, identity;q=0.5, *;q=0 First the field-name and field-value are converted to ASN.1 octet strings by adding the appropriate length prefixes (see 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 Next, the length-prefixed header name is taken as a single token. Hex dump of the header name token: 0000000 0f61 6363 6570 742d | 656e 636f 6469 6e67 | .accept-encoding Finally, the length-prefixed header value is tokenized according to the rules in Section 3. The following is a hex dump of each of the eleven tokens. Morgan & Brunhuber Expires December 4, 2014 [Page 7] Internet-Draft H2EZ June 2014 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 | ; Morgan & Brunhuber Expires December 4, 2014 [Page 8] Internet-Draft H2EZ June 2014 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) A token T, 1292 octets in length, is to be sub-tokenized. 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 Thus there are six sub-tokens. The first four sub-tokens are 258 octets in length. The final two sub-tokens are 130 octets in length. 3.4.2. Sub-Tokenization Example 2 (516 octet token) A token T, 516 octets in length, is to be sub-tokenized. N = (516 + 257) / 258 = 773 / 258 = 2 R = 516 L1 = R - R / 2 = 258 L2 = R / 2 = 258 Thus there are two sub-tokens. The two sub-tokens are 258 octets in Morgan & Brunhuber Expires December 4, 2014 [Page 9] Internet-Draft H2EZ June 2014 length. 3.4.3. Sub-Tokenization Example 3 (259 octet token) A token T, 259 octets in length, is to be sub-tokenized. N = (259 + 257) / 258 = 516 / 258 = 2 R = 259 L1 = R - R / 2 = 130 L2 = R / 2 = 129 Thus there are two sub-tokens. The length of the first sub-token is 130 octets. The length of the second sub-token is 129 octets. 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 Herve Ruellan. 6. References 6.1. Normative References [EZFLATE] Morgan, K. and C. Brunhuber, "EZFLATE: Token-based DEFLATE Compression", draft-morgan-ezflate (work in progress), June 2014. [X.208-88] CCITT, "Recommendation X.208: Specification of Abstract Syntax Notation One (ASN.1)", January 1998. Morgan & Brunhuber Expires December 4, 2014 [Page 10] Internet-Draft H2EZ June 2014 [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., Ed. and J. Reschke, Ed., "Hypertext Transfer Protocol (HTTP/1.1): Message Syntax and Routing", draft-ietf-httpbis-p1-messaging-26 (work in progress), February 2014. [HTTP2] Belshe, M., Peon, R., and M. Thomson, Ed., "Hypertext Transfer Protocol version 2", draft-ietf-httpbis-http2-10 (work in progress), February 2014. [SPDY] Belshe, M. and R. Peon, "SPDY Protocol", draft-mbelshe-httpbis-spdy-00 (work in progress), 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 Morgan & Brunhuber Expires December 4, 2014 [Page 11]