[Search] [txt|xml|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
HTTPbis                                                        K. Morgan
Internet-Draft                                              C. Brunhuber
Intended status: Standards Track                                    IAEA
Expires: December 4, 2014                                   June 2, 2014


                EZFLATE: Token-based DEFLATE Compression
                      draft-morgan-ezflate-00

Abstract

   This specification defines EZFLATE, a token-based DEFLATE compression
   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
   <http://lists.w3.org/Archives/Public/ietf-http-wg/>.

   Working Group information can be found at
   <http://tools.ietf.org/wg/httpbis/>;

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
   Provisions Relating to IETF Documents



Morgan & Brunhuber      Expires December 4, 2014                [Page 1]


Internet-Draft                   EZFLATE                       June 2014


   (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.  Compression Attacks . . . . . . . . . . . . . . . . . . . . . . 3
     2.1.  CRIME . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
     2.2.  BREACH  . . . . . . . . . . . . . . . . . . . . . . . . . . 4
   3.  Tokenization  . . . . . . . . . . . . . . . . . . . . . . . . . 4
     3.1.  "Take a Bite out of CRIME"  . . . . . . . . . . . . . . . . 4
     3.2.  Delimiters & Tokenization Methods . . . . . . . . . . . . . 5
       3.2.1.  Method 1: Keep Delimiters as Separate Tokens  . . . . . 5
       3.2.2.  Method 2: Keep Delimiters with Preceding Token  . . . . 5
       3.2.3.  Method 3: Keep Delimiters with Succeeding Token . . . . 6
     3.3.  Tokenization Rules  . . . . . . . . . . . . . . . . . . . . 6
   4.  EZFLATE Compression Algorithm Details . . . . . . . . . . . . . 6
   5.  Security Considerations . . . . . . . . . . . . . . . . . . . . 8
   6.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . 9
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . . . 9
     7.1.  Normative References  . . . . . . . . . . . . . . . . . . . 9
     7.2.  Informative References  . . . . . . . . . . . . . . . . . . 9
























Morgan & Brunhuber      Expires December 4, 2014                [Page 2]


Internet-Draft                   EZFLATE                       June 2014


1.  Introduction

   DEFLATE [DEFLATE] is one of the most widely used compression
   mechanisms.  It forms the basis of ZIP [ZIP], GZIP [GZIP] and ZLIB
   [ZLIB].  However, DEFLATE poses a security vulnerability when
   messages comprised of secret and attacker-controlled data are
   delivered through a secure communication channel, as demonstrated by
   the CRIME [CRIME] and BREACH [BREACH] attacks.

   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).

   The first paragraph of Section 4, "Compression algorithm details", in
   RFC 1951 explicitly states that the "deflate" format is not tied to
   any particular algorithm.  To quote, it says, "While it is the intent
   of this document to define the 'deflate' compressed data format
   without reference to any particular compression algorithm, the format
   is related to the compressed formats produced by LZ77 ... it is
   strongly recommended that the implementor of a compressor follow the
   general algorithm presented here ... [however] a compressor need not
   follow it in order to be compliant [DEFLATE]."

   This document describes EZFLATE, a token-based DEFLATE _algorithm_.
   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.  In other
   words, LZ77 tuples must not reference partial matches, neither
   smaller nor longer, occurring in a previous block.

2.  Compression Attacks

2.1.  CRIME

   SPDY [SPDY] used DEFLATE [DEFLATE] to compress redundant HTTP
   [HTTP-p1] headers.  The CRIME [CRIME] attack exploited DEFLATE to
   guess secret information contained in the HTTP request headers (e.g.
   "Cookies").  Since DEFLATE looks for matches character-by-character,
   the attackers were able to guess the secret one character at a time.
   Each failed guess resulted in a compressed block of size n.  Correct
   guesses resulted in a compressed block of size m < n.  For example,
   consider the following sample HTTP requests (taken from [CRIME]):







Morgan & Brunhuber      Expires December 4, 2014                [Page 3]


Internet-Draft                   EZFLATE                       June 2014


   Attacker guesses the first character is 'a':

   GET /twid=a
   Host: twitter.com
   User-Agent: Chrome
   Cookie: twid=secret

   ... (more guesses) ...

   Attacker guesses the first character is 's':

   GET /twid=s
   Host: twitter.com
   User-Agent: Chrome
   Cookie: twid=secret

   After guessing 's' is the first character of the secret, the attacker
   sees a corresponding increase in compression (i.e. decrease in
   length) indicating the guess is correct.  The procedure is repeated
   until the entire secret is revealed.

   Although this is a brute-force attack of sorts, the average number of
   guesses required to extract a secret is considerably lower, and
   therefore tractable, thanks to being able to guess character by
   character.  If the number of possible characters is 256, then on
   average it will require 128 guesses per character to make a correct
   guess.  An n-character secret then only requires, on average, n * 128
   guesses to discover the secret.  For example, a 12-character secret
   requires 12 * 128 = 1,536 guesses.  In many cases the set of possible
   characters is smaller than 256, reducing the search space even more!

2.2.  BREACH

   While CRIME exploited SPDY (and TLS compression too), BREACH [BREACH]
   exploited compression of HTTP _response bodies_.  The mechanism of
   BREACH is similar to CRIME with slightly different details, therefore
   a detailed review of BREACH will not be given here.

3.  Tokenization

3.1.  "Take a Bite out of CRIME"

   Taking a "bite out of crime" requires more than a security dog named
   McGruff [MCGRUFF].  EZFLATE fights CRIME by using token matching,
   rather than character-by-character matching, to make the search space
   for an attacker equivalent to a full brute-force attack.  At that
   point there are easier ways to execute the brute-force attack.




Morgan & Brunhuber      Expires December 4, 2014                [Page 4]


Internet-Draft                   EZFLATE                       June 2014


   As stated in Section 1, the key feature of the 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) if the current token and referenced
   token exactly match in length _and_ octet values.  By selecting
   appropriate tokenization rules, potential attackers are forced to
   guess n-character secrets n characters at a time rather than one
   character at a time.  Taking the example from Section 2.1, a 12-
   character secret has a search space of 2^12 * 8 = 2^96 =
   79,228,162,514,264,337,593,543,950,336 possible secrets (of course,
   on average it would "only" take an attacker half that many guesses to
   discover the secret by brute force).  Even a Base64-encoded 12-
   character secret has a search space of 64^12 =
   4,722,366,482,869,645,213,696 possible secrets.

3.2.  Delimiters & Tokenization Methods

   The classic tokenization method splits an arbitrary-length octet
   string by a subset of octets that act as "delimiters".  The result is
   typically a set of octet strings with the delimiter octets omitted.

   In the likely case where full reconstruction of the original octet
   string is desired, the delimiters obviously cannot be omitted.  There
   are three different choices, outlined below, for keeping the
   delimiters.  Each has their advantages and disadvantages.  The best
   method for a particular data type can be discovered by experimenting.
   Note also that a sequence of consecutive delimiters are treated as a
   single unit.

3.2.1.  Method 1: Keep Delimiters as Separate Tokens

   The first tokenization method simply keeps the delimiter(s) as
   separate tokens.  For example, consider the following string of ASCII
   text to be tokenized by white space and puncuation.

   ASCII string to be tokenized:

                   "The quick; brown fox."

   Resulting token set after Method 1:

                   { "The", " ", "quick", "; ", "brown", " ", "fox", "." }

3.2.2.  Method 2: Keep Delimiters with Preceding Token

   The second tokenization method keeps the delimiter(s) with the token
   which immediately precedes the delimiter(s).




Morgan & Brunhuber      Expires December 4, 2014                [Page 5]


Internet-Draft                   EZFLATE                       June 2014


   Resulting token set after Method 2:

                   { "The ", "quick; ", "brown ", "fox." }

3.2.3.  Method 3: Keep Delimiters with Succeeding Token

   The third tokenization method keeps the delimiter(s) with the token
   which immediately succeeds the delimiter(s).

   Resulting token set after Method 2:

                   { "The", " quick", "; brown", " fox", "." }

3.3.  Tokenization Rules

   Note that EZFLATE is agnostic to tokenization methods and delimiter
   sets.  Appropriate tokenization rules and delimiter sets depend on
   the type of data to be compressed.  For a particular data type, a
   global set of generally applicable tokenization rules ought to be
   selected if at all possible.  This makes it easier for decompressors
   to verify, if desired, that the compressed data conforms to the rules
   and delimiter sets.  However, specialized rules might be necessary
   for special cases, particularly cases which might negatively affect
   security.  The selection of appropriate rules and delimiter sets for
   a particular data type is beyond the scope of this document.

4.  EZFLATE Compression Algorithm Details

   The EZFLATE algorithm, described in this Section, is simply an
   alternate to the algorithm described in Section 4 of [DEFLATE], it is
   not intended to replace that algorithm, which provides better
   general-purpose compression.

   The compressor MUST always operates on a single token (octet string).
   The compressor uses a chained hash table to find duplicated tokens.
   Any hash function may be used and the hash function may operate on
   the entire octet string or any subset.  The compressor also uses a
   separate "length table" to track the token lengths for each position
   in the input window.  At any given point during compression, let T be
   the next token at position P with length L (not necessarily all
   different octets, of course).  First, the compressor computes the
   hash value of the token T and updates the hash table with the hash
   value of T and updates the "length table" with L at position P. Next,
   the compressor examines the hash chain for the token T. If the chain
   is empty, the compressor simply emits the L literal octets of T. If
   the hash chain is not empty, this indicates that the token T (or, if
   there was a hash collision, some other octet string with the same
   hash value) has occurred recently.  The compressor follows the hash



Morgan & Brunhuber      Expires December 4, 2014                [Page 6]


Internet-Draft                   EZFLATE                       June 2014


   chain to find the first entry within the current window which has
   length L (stored in the length table) and is octet-for-octet
   equivalent to the L octets in T. If an exact match is found, the
   compressor may emit a LZ77 <length, backward distance> tuple, where
   the length is L and the backward distance is the position of the
   current token minus the position of the exactly matching token.  If
   no exact match is found, the compressor simply emits the L literal
   octets of T.

   Just as stated in Section 4 of [DEFLATE], "the compressor searches
   the hash chains starting with the most recent [octet] strings, to
   favor small distances and thus take advantage of the Huffman encoding
   [HUFF].  The hash chains are singly linked.  There are no deletions
   from the hash chains; the algorithm simply discards matches that are
   too old.  To avoid a worst-case situation, very long hash chains are
   arbitrarily truncated at a certain length, determined by a run-time
   parameter."

   To improve overall compression, the compressor may optionally defer
   emitting a match in order to find a longer match that is a
   consecutive sequence of matching tokens.  After a set of one or more
   matches with positions Pm ...  Pn have been found for the current
   token T1 at position P1 with length L1, the compressor may defer
   emitting the match and examine the next token T2 to determine if that
   token appears at any of the positions Pm + L1 ...  Pn + L1, i.e.
   directly after any of the matches for T1.  It is critical to note
   that the same rules apply for checking matches of T2 at positions Pm
   + L1 ...  Pn + L1 as if the compressor were finding matches for T2
   using the hash chain.  In particular the length of a given token at
   position Pi + L1 must be equal to L2 _and_ be octet-for-octet
   equivalent to the L2 octets in T2.  The compressor reduces the set of
   matching positions in Pm ...  Pn to only include those which had an
   exact match for T2 at a given position Pi + L1.  If one or more
   matches remains, the process is repeated until either the set of
   deferred matches cannot be extended by the next token or the length
   of the next token is such that the overall length of the match would
   exceed the maximum length of a match (258 octets) allowed by the
   DEFLATE format (see Section 3.2.5 of [DEFLATE]).  Note that the
   compressor must keep enough information about the currently deferred
   match(es), that once the final match is found the total length and
   backward distance are known or can be computed.  Once the set of
   matches cannot be extended any longer, the compressor returns to the
   normal process of searching for matches using the hash table.

   Just as stated in Section 4 of [DEFLATE], "the compressor terminates
   a block when it determines that starting a new block with fresh trees
   would be useful, or when the block size fills up the compressor's
   block buffer."



Morgan & Brunhuber      Expires December 4, 2014                [Page 7]


Internet-Draft                   EZFLATE                       June 2014


   A token T with length L less than the minimum length of a match (3
   octets) allowed by the DEFLATE format (see Section 3.2.5 of
   [DEFLATE]) is processed by simply updating the "length table" and
   emiting the L literal octets.  These short tokens should, however,
   participate in extending deferred matches.  The same matching rules
   apply as for matching tokens in all other situations, namely the
   length of the potentially matching token stored in the "length table"
   must be equal to L and the L octets of the stored token must be
   octet-for-octet equivalent to the L octets in T.

   Note that the formatting rules and static/dynamic Huffman encoding
   rules in RFC 1951 [DEFLATE], apply to any implementation of the
   EZFLATE algorithm described here.

5.  Security Considerations

   Care must be taken when implementing deferred matching such that
   checking for matches of the current token against the octets
   immediately following the deferred set of matches not only checks for
   octet equivalency, but length equivalency as well.  If the length is
   not also checked, an attacker would be able to perform character-by-
   character guessing by injecting the token immediately preceding the
   secret, which in many cases may be a known identifier.

   [TODO: A lot of the remaining text is completely lifted from the
   HPACK Internet Draft; re-write or give credit somehow.]

   An EZFLATE compressor can still 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, users of an EZFLATE
   compressor SHOULD use non-compressed DEFLATE blocks (see Section
   3.2.4 of [DEFLATE]) disable compression of any low-entropy secrets
   which could be put at risk by a brute-force attack.

   There is currently no known threat taking advantage of the use of a
   fixed Huffman encoding.  A study has shown that using a fixed Huffman
   encoding table created an information leakage, however this same
   study concluded that an attacker could not take advantage of this



Morgan & Brunhuber      Expires December 4, 2014                [Page 8]


Internet-Draft                   EZFLATE                       June 2014


   information leakage to recover any meaningful amount of information
   (see [PETAL]).

6.  Acknowledgements

   Roberto Peon and Herve Ruellan.

7.  References

7.1.  Normative References

   [DEFLATE]  Deutsch, P., "DEFLATE Compressed Data Format Specification
              version 1.3", RFC 1951, May 1996.

7.2.  Informative References

   [BREACH]   Gluck, Y., "BREACH: REVIVING THE CRIME ATTACK", July 2013,
              <http://breachattack.com/resources/
              BREACH%20-%20SSL,%20gone%20in%2030%20seconds.pdf>.

   [CRIME]    Rizzo, J. and T. Duong, "The CRIME Attack",
              September 2012, <https://docs.google.com/a/twist.com/
              presentation/d/
              11eBmGiHbYcHR9gL5nDyZChu_-lCa2GizeuOfaLU2HOU/
              edit#slide=id.g1eb6c1b5_3_6>.

   [GZIP]     Deutsch, P., "GZIP file format specification version 4.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.

   [HUFF]     Huffman, D., "A Method for the Construction of Minimum
              Redundancy Codes", Proceedings of the Institute of Radio
              Engineers Volume 40, Number 9, pp. 1098-1101,
              September 1952, <http://ieeexplore.ieee.org/xpl/
              articleDetails.jsp?arnumber=4051119>.

   [MCGRUFF]  McGruff, M., "About McGruff", 2014,
              <http://www.ncpc.org/about/about-mcgruff>.

   [PETAL]    Tan, J. and J. Nahata, "PETAL: Preset Encoding Table
              Information Leakage", April 2013, <http://www.pdl.cmu.edu/
              PDL-FTP/associated/CMU-PDL-13-106.pdf>.

   [SPDY]     Belshe, M. and R. Peon, "SPDY Protocol",



Morgan & Brunhuber      Expires December 4, 2014                [Page 9]


Internet-Draft                   EZFLATE                       June 2014


              draft-mbelshe-httpbis-spdy-00 (work in progress),
              February 2012.

   [ZIP]      Katz, P., ".ZIP File Format Specification",
              September 2012,
              <http://www.pkware.com/documents/casestudies/APPNOTE.TXT>.

   [ZLIB]     Deutsch, P., "ZLIB Compressed Data Format Specification
              version 3.3", RFC 1950, May 1996.

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 10]