Network Working Group                                         M. Thomson
Internet-Draft                                                   Mozilla
Intended status: Standards Track                        January 28, 2016
Expires: July 31, 2016


                   Merkle Integrity Content Encoding
                       draft-thomson-http-mice-00

Abstract

   This memo introduces a content-coding for HTTP that provides
   progressive integrity for message contents.  This integrity
   protection can be evaluated on a partial representation, allowing a
   recipient to process a message as it is delivered while retaining
   strong integrity protection.  The integrity protection can optionally
   be authenticated with a digital signature.

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 July 31, 2016.

Copyright Notice

   Copyright (c) 2016 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
   (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




Thomson                   Expires July 31, 2016                 [Page 1]


Internet-Draft                    MICE                      January 2016


   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Notational Conventions  . . . . . . . . . . . . . . . . .   3
   2.  The "mi-sha256" HTTP Content Encoding . . . . . . . . . . . .   3
     2.1.  Content Encoding Structure  . . . . . . . . . . . . . . .   4
     2.2.  Validating Integrity Proofs . . . . . . . . . . . . . . .   5
   3.  The MI HTTP Header Field  . . . . . . . . . . . . . . . . . .   6
     3.1.  MI Header Field Parameters  . . . . . . . . . . . . . . .   6
   4.  Examples  . . . . . . . . . . . . . . . . . . . . . . . . . .   7
     4.1.  Simple Example  . . . . . . . . . . . . . . . . . . . . .   7
     4.2.  Signature Example . . . . . . . . . . . . . . . . . . . .   7
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .   8
     5.1.  Message Truncation  . . . . . . . . . . . . . . . . . . .   8
     5.2.  Algorithm Agility . . . . . . . . . . . . . . . . . . . .   9
   6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   9
     6.1.  The "mi-sha256" HTTP Content Encoding . . . . . . . . . .   9
     6.2.  MI Header Field . . . . . . . . . . . . . . . . . . . . .   9
     6.3.  The HTTP MI Parameter Registry  . . . . . . . . . . . . .  10
       6.3.1.  p parameter . . . . . . . . . . . . . . . . . . . . .  10
       6.3.2.  keyid parameter . . . . . . . . . . . . . . . . . . .  10
       6.3.3.  p256ecdsa parameter . . . . . . . . . . . . . . . . .  10
       6.3.4.  rs parameter  . . . . . . . . . . . . . . . . . . . .  11
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  11
     7.1.  Normative References  . . . . . . . . . . . . . . . . . .  11
     7.2.  Informative References  . . . . . . . . . . . . . . . . .  12
   Appendix A.  Acknowledgements . . . . . . . . . . . . . . . . . .  12
   Appendix B.  FAQ  . . . . . . . . . . . . . . . . . . . . . . . .  12
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  13

1.  Introduction

   Integrity protection for HTTP content is often necessary.  HTTPS
   [RFC2818] is the most common form of integrity protection deployed,
   but that requires a direct TLS [RFC5246] connection to a host.
   However, additional integrity protection is often desirable.  This
   might be for additional protection against failures (e.g., [SRI]) or
   because content needs to traverse multiple HTTPS-protected exchanges.

   This document describes a "mi-sha256" content-encoding (see
   Section 2) that embeds a progressive, hash-based integrity check
   based on Merkle Hash Trees [MERKLE].  This integrity scheme
   optionally supports including a digital signature over the integrity
   value.




Thomson                   Expires July 31, 2016                 [Page 2]


Internet-Draft                    MICE                      January 2016


   The means of conveying the root proof used by this content encoding
   will depend on the requirements for deployment.  This document
   defines an MI header field (see Section 3) that can carry an
   integrity proof or signatures over the proof.

1.1.  Notational Conventions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

2.  The "mi-sha256" HTTP Content Encoding

   A Merkle Hash Tree [MERKLE] is a structured integrity mechanism that
   collates multiple integrity checks into a tree.  The leaf nodes of
   the tree contain data (or hashes of data) and non-leaf nodes contain
   hashes of the nodes below them.

   A balanced Merkle Hash Tree is used to efficiently prove membership
   in large sets (such as in [RFC6962]).  However, in this case, a
   right-skewed tree is used to provide a progressive integrity proof.
   This integrity proof is used to establish that a given record is part
   of a message.

   The hash function used for "mi-sha256" content encoding is SHA-256
   [FIPS180-4].  The integrity proof for all records other than the last
   is the hash of the concatenation of the record, the integrity proof
   of all subsequent records, and a single octet with a value of 0x1:

      proof(r[i]) = r[i] || proof(r[i+1]) || 0x1

   The integrity proof for the final record is the hash of the record
   with a single octet with a value 0x0 appended:

      proof(r[last]) = r[last] || 0x0

   Figure 1 shows the structure of the integrity proofs for a message
   that is split into 4 blocks: A, B, C, D).  As shown, the integrity
   proof for the entire message (that is, "proof(A)") is derived from
   the content of the first block (A), plus the value of the proof for
   the second and subsequent blocks.










Thomson                   Expires July 31, 2016                 [Page 3]


Internet-Draft                    MICE                      January 2016


       proof(A)
         /\
        /  \
       /    \
      A    proof(B)
            /\
           /  \
          /    \
         B    proof(C)
                /\
               /  \
              /    \
             C    proof(D)
                    |
                    |
                    D

           Figure 1: Proof structure for a message with 4 blocks

   The final encoded message is formed from the first record, followed
   by an arbitrary number of tuples of the integrity proof of the next
   record and then the record itself.  Thus, in Figure 1, the body is:

      A || proof(B) || B || proof(C) || C || proof(D) || D

   A message that has a content length less than or equal to the content
   size does not include any inline proofs.  The proof for a message
   with a single record is simply the hash of the body plus a trailing
   zero octet.

2.1.  Content Encoding Structure

   In order to produce the final content encoding the content of the
   message is split into equal-sized records.  The final record can
   contain less than the defined record size.

   The default record size for the "mi-sha256" content encoding is 4096
   octets.  This refers to the length of each data block.  The MI header
   field MAY contain an "rs" parameter that describes a different record
   size.

   The final encoded stream comprises of a record ("rs" octets in
   length), followed by the proof for the following record (32 octets).
   This allows a receiver to validate and act upon each record after
   receiving the proof that follows it.  The final record is not
   followed by a proof.





Thomson                   Expires July 31, 2016                 [Page 4]


Internet-Draft                    MICE                      January 2016


   Note:  This content encoding increases the size of a message by 32
      octets times the length of the message divided by the record size,
      rounded up, less one.  That is, 32 * (ceil(length / rs) - 1).

   Constructing a message with the "mi-sha256" content encoding requires
   processing of the records in reverse order, inserting the proof
   derived from each record before that record.

   This structure permits the use of range requests [RFC7233].  However,
   to validate a given record, a contiguous sequence of records back to
   the start of the message is needed.

2.2.  Validating Integrity Proofs

   A receiver of a message with the "mi-sha256" content-encoding applied
   first attempts to acquire the integrity proof for the first record.
   If the MI header field is present, a value might be included there.

   Then, the message is read into records of size "rs" (based on the
   value in the MI header field) plus 32 octets.  For each record:

   1.  Hash the record using SHA-256 with a single octet appended.  All
       records other than the last have an octet with value 0x1
       appended, and the last record (which will be between 1 and "rs"
       octets in length) has an octet with value 0x0 appended.

   2.  For the first record:

       1.  If a signature is known for the integrity proof for the first
           record and the receiver is configured to validate a signature
           for this message, then the signature is validated with the
           output of the hash as the signed message.  If this check
           passes, then the signature applies to the entire message if
           subsequent checks succeed.

       2.  If the integrity proof for the first record is known, the
           integrity check passes if the output of SHA-256 is identical
           to the known value.

       3.  If an integrity proof for the first record is not available,
           treat the message as not having integrity protection.

   3.  For all other records, check if the output of SHA-256 is equal to
       the expected value, then the integrity check passes.  The
       expected value is the last 32 octets of the previous record.

   If an integrity check fails, the message SHOULD be discarded and the
   exchange treated as an error unless explicitly configured otherwise.



Thomson                   Expires July 31, 2016                 [Page 5]


Internet-Draft                    MICE                      January 2016


   For clients, treat this as equivalent to a server error; servers
   SHOULD generate a 400 status code.  However, if the integrity proof
   for the first record is not known, this check SHOULD NOT fail unless
   explicitly configured.

3.  The MI HTTP Header Field

   The MI HTTP header field describes the message integrity content
   encoding(s) that have been applied to a payload body, and therefore
   how those content encoding(s) can be removed.

   The MI header field uses the extended ABNF syntax defined in
   Section 1.2 of [RFC7230] and the "parameter" rule from [RFC7231]:

     MI = #mi_params
     mi_params = [ parameter *( ";" parameter ) ]

   If the payload is encoded more than once (as reflected by having
   multiple content-codings that use the message integrity header
   field), each application of the content encoding is reflected in the
   MI header field in the order in which they were applied.

   The MI header MAY be omitted if the sender intends for the receiver
   to acquire the integrity proof for the first record by other means.

3.1.  MI Header Field Parameters

   The following parameters are used in validating content encoded with
   the "mi-sha256" content encoding:

   p: The "p" parameter carries an integrity proof for the first record
      of the message.  This provides integrity for the entire message
      body.  This value is encoded using Base 64 Encoding with URL and
      Filename Safe Alphabet (Section 5 of [RFC4648]) with no padding.

   p256ecdsa:  The "p256ecdsa" parameter carries an ECDSA signature over
      the integrity proof for the first record of the message using
      P-256 [FIPS186] encoded as defined in [X9.62] then further encoded
      using Base 64 Encoding with URL and Filename Safe Alphabet
      (Section 5 of [RFC4648]) with no padding.  If the receiver is
      expected to validate this signature, the "p" parameter MAY be
      ignored and omitted.  Note that this document doesn't describe how
      a receiver might determine that a particular key is acceptable.
      The input to the signature is the UTF-8 encoded string "MI:
      p256ecdsa", a single zero-valued octet, and the integrity proof
      for the first record.  That is:

     SignInput = "MI: p256ecdsa" || 0x0 || proof(r[0])



Thomson                   Expires July 31, 2016                 [Page 6]


Internet-Draft                    MICE                      January 2016


   Multiple values of this parameter might be provided.  If the "keyid"
   parameter is used to identify a key for each of these, the first
   "keyid" parameter to precede the "p256ecdsa" parameter is used.

   keyid:  The "keyid" parameter optionally identifies the key that was
      used to generate a signature.

   rs:  The "rs" parameter contains a positive decimal integer that
      describes the record size in octets.  This value MUST be greater
      than 0.  If the "rs" parameter is absent, the record size defaults
      to 4096 octets.

4.  Examples

4.1.  Simple Example

   The following example contains a short message.  This contains just a
   single record, so there are no inline integrity proofs, just a single
   value in a MI header field.

   HTTP/1.1 200 OK
   MI: p=dcRDgR2GM35DluAV13PzgnG6-pvQwPywfFvAu1UeFrs
   Content-Length: 41

   When I grow up, I want to be a watermelon

4.2.  Signature Example

   The following example includes a signature over the integrity proof
   for the first record.  The public key for the signer is included in a
   Crypto-Key header field [I-D.ietf-httpbis-encryption-encoding] using
   the uncompressed form [X9.62].  The example shows the value for the
   integrity proof in the MI header field, but this could be omitted if
   the client anticipates that the server will verify the signature.

















Thomson                   Expires July 31, 2016                 [Page 7]


Internet-Draft                    MICE                      January 2016


   PUT /test HTTP/1.1
   Host: example.com
   Crypto-Key: keyid=x;
               p256ecdsa=BIy6-8mZ48aKJpB54By_dK0pTv94s86yIVef6JhEC_bS
                         Q-AnXQMX1oYG9dmCeezgJsmzQo52qJbfJEzIXpZiBSA
   MI: rs=16;
       p=IVa9shfs0nyKEhHqtB3WVNANJ2Njm5KjQLjRtnbkYJ4;
       p256ecdsa=3pXnQrynYwnAW2T86MHel0bd6VgidWdQgb4SPGbxGGo
                 vemyiAdgNx5cKYkNSgz4c3vSGFt6_UoF2GLhWRePJeA
   Content-Length: 105

   When I grow up,
   OElbplJlPK-Rv6JNK6p5_515IaoPoZo-2elWL7OQ60A
   I want to be a w
   iPMpmgExHPrbEX3_RvwP4d16fWlK4l--p75PUu_KyN0
   atermelon

   The example shows the same message as above, but with a smaller
   record size (16 octets).  This results in two integrity proofs being
   included in the representation.

   Since the inline integrity proofs contain non-printing characters,
   these are shown here using the Base 64 Encoding with URL and Filename
   Safe Alphabet [RFC4648] with new lines between the original text and
   integrity proofs.  Note that there is a single trailing space (0x20)
   on the first line.

   The MI and Crypto-Key header fields are split across several lines to
   fit formatting constraints.

5.  Security Considerations

   The integrity of an entire message body depends on the means by which
   the integrity proof for the first record is protected.  If this value
   comes from the same place as the message, then this provides only
   limited protection against transport-level errors (something that TLS
   provides adequate protection against).

   Separate protection for header fields might be provided by other
   means if the first record retrieved is the first record in the
   message, but range requests do not allow for this option.

5.1.  Message Truncation

   This integrity scheme permits the detection of truncated messages.
   However, it enables and even encourages processing of messages prior
   to receiving an complete message.  Actions taken on a partial message
   can produce incorrect results.  For example, a message could say "I



Thomson                   Expires July 31, 2016                 [Page 8]


Internet-Draft                    MICE                      January 2016


   need some 2mm copper cable, please send 100mm for evaluation
   purposes" then be truncated to "I need some 2mm copper cable, please
   send 100m".  A network-based attacker might be able to force this
   sort of truncation by delaying packets that contain the remainder of
   the message.

   Whether it is safe to act on partial messages will depend on the
   nature of the message and the processing that is performed.

5.2.  Algorithm Agility

   A new content encoding type is needed in order to define the use of a
   hash function other than SHA-256.

   A new parameter name for the MI header field is needed to support new
   digital signature algorithms.

6.  IANA Considerations

6.1.  The "mi-sha256" HTTP Content Encoding

   This memo registers the "mi-sha256" HTTP content-coding in the HTTP
   Content Codings Registry, as detailed in Section 2.

   o  Name: mi-sha256

   o  Description: A Merkle Hash Tree based content encoding that
      provides progressive integrity.

   o  Reference: this specification

6.2.  MI Header Field

   This memo registers the "MI" HTTP header field in the Permanent
   Message Header Registry, as detailed in Section 3.

   o  Field name: MI

   o  Protocol: HTTP

   o  Status: Standard

   o  Reference: this specification

   o  Notes:






Thomson                   Expires July 31, 2016                 [Page 9]


Internet-Draft                    MICE                      January 2016


6.3.  The HTTP MI Parameter Registry

   This memo establishes a registry for parameters used by the "MI"
   header field under the "Hypertext Transfer Protocol (HTTP)
   Parameters" grouping.  The "Hypertext Transfer Protocol (HTTP) MI
   Parameters" registry operates under an "Specification Required"
   policy [RFC5226].

   Entries in this registry are expected to include the following
   information:

   o  Parameter Name: The name of the parameter.

   o  Purpose: A brief description of the purpose of the parameter.

   o  Reference: A reference to a specification that defines the
      semantics of the parameter.

   The initial contents of this registry are:

6.3.1.  p parameter

   o  Parameter Name: p

   o  Purpose: The value of the integrity proof for the first record.

   o  Reference: this document

6.3.2.  keyid parameter

   o  Parameter Name: keyid

   o  Purpose: An identifier for the key that is used for signature over
      the integrity proof for the first record.

   o  Reference: this document

6.3.3.  p256ecdsa parameter

   o  Parameter Name: p256ecdsa

   o  Purpose: An ECDSA signature using P-256 over the integrity proof
      for the first record.

   o  Reference: this document






Thomson                   Expires July 31, 2016                [Page 10]


Internet-Draft                    MICE                      January 2016


6.3.4.  rs parameter

   o  Parameter Name: rs

   o  Purpose: The size of the records used for progressive integrity
      protection.

   o  Reference: this document

7.  References

7.1.  Normative References

   [FIPS180-4]
              Department of Commerce, National., "NIST FIPS 180-4,
              Secure Hash Standard", March 2012,
              <http://csrc.nist.gov/publications/fips/fips180-4/
              fips-180-4.pdf>.

   [FIPS186]  National Institute of Standards and Technology (NIST),
              "Digital Signature Standard (DSS)", NIST PUB 186-4 , July
              2013.

   [MERKLE]   Merkle, R., "A Digital Signature Based on a Conventional
              Encryption Function", International Crytology Conference -
              CRYPTO , 1987.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <http://www.rfc-editor.org/info/rfc2119>.

   [RFC4648]  Josefsson, S., "The Base16, Base32, and Base64 Data
              Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006,
              <http://www.rfc-editor.org/info/rfc4648>.

   [RFC5226]  Narten, T. and H. Alvestrand, "Guidelines for Writing an
              IANA Considerations Section in RFCs", BCP 26, RFC 5226,
              DOI 10.17487/RFC5226, May 2008,
              <http://www.rfc-editor.org/info/rfc5226>.

   [RFC7230]  Fielding, R., Ed. and J. Reschke, Ed., "Hypertext Transfer
              Protocol (HTTP/1.1): Message Syntax and Routing",
              RFC 7230, DOI 10.17487/RFC7230, June 2014,
              <http://www.rfc-editor.org/info/rfc7230>.






Thomson                   Expires July 31, 2016                [Page 11]


Internet-Draft                    MICE                      January 2016


   [RFC7231]  Fielding, R., Ed. and J. Reschke, Ed., "Hypertext Transfer
              Protocol (HTTP/1.1): Semantics and Content", RFC 7231,
              DOI 10.17487/RFC7231, June 2014,
              <http://www.rfc-editor.org/info/rfc7231>.

   [RFC7233]  Fielding, R., Ed., Lafon, Y., Ed., and J. Reschke, Ed.,
              "Hypertext Transfer Protocol (HTTP/1.1): Range Requests",
              RFC 7233, DOI 10.17487/RFC7233, June 2014,
              <http://www.rfc-editor.org/info/rfc7233>.

   [X9.62]    ANSI, "Public Key Cryptography For The Financial Services
              Industry: The Elliptic Curve Digital Signature Algorithm
              (ECDSA)", ANSI X9.62 , 1998.

7.2.  Informative References

   [I-D.ietf-httpbis-encryption-encoding]
              Thomson, M., "Encrypted Content-Encoding for HTTP", draft-
              ietf-httpbis-encryption-encoding-00 (work in progress),
              December 2015.

   [RFC2818]  Rescorla, E., "HTTP Over TLS", RFC 2818,
              DOI 10.17487/RFC2818, May 2000,
              <http://www.rfc-editor.org/info/rfc2818>.

   [RFC5246]  Dierks, T. and E. Rescorla, "The Transport Layer Security
              (TLS) Protocol Version 1.2", RFC 5246,
              DOI 10.17487/RFC5246, August 2008,
              <http://www.rfc-editor.org/info/rfc5246>.

   [RFC6962]  Laurie, B., Langley, A., and E. Kasper, "Certificate
              Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013,
              <http://www.rfc-editor.org/info/rfc6962>.

   [SRI]      Akhawe, D., Braun, F., Marier, F., and J. Weinberger,
              "Subresource Integrity", W3C CR , November 2015,
              <https://w3c.github.io/webappsec-subresource-integrity/>.

Appendix A.  Acknowledgements

   David Benjamin and Erik Nygren both separately suggested that
   something like this might be valuable.

Appendix B.  FAQ

   1.  Why not include the first proof in the encoding?





Thomson                   Expires July 31, 2016                [Page 12]


Internet-Draft                    MICE                      January 2016


       The requirements for the integrity proof for the first record
       require a great deal more flexibility than this allows for.
       Transferring the proof separately is sometimes necessary.
       Separating the value out allows for that to happen more easily.

   2.  Why do messages have to be processed in reverse to construct
       them?

       The final integrity value, no matter how it is derived, has to
       depend on every bit of the message.  That means that there are
       three choices: both sender and receiver have to process the whole
       message, the sender has to work backwards, or the receiver has to
       work backwards.  The current form is the best option of the
       three.  The expectation is that this will be useful for content
       that is generated once and sent multiple times, since the onerous
       backwards processing requirement can be amortized.

Author's Address

   Martin Thomson
   Mozilla

   Email: martin.thomson@gmail.com




























Thomson                   Expires July 31, 2016                [Page 13]