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.

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

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.

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

• Name: mi-sha256
• Description: A Merkle Hash Tree based content encoding that provides progressive integrity.
• 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.

• Field name: MI
• Protocol: HTTP
• Status: Standard
• Reference: this specification
• Notes:

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:

• Parameter Name: The name of the parameter.
• Purpose: A brief description of the purpose of the parameter.
• 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

• Parameter Name: p
• Purpose: The value of the integrity proof for the first record.
• Reference: this document

6.3.2. keyid parameter

• Parameter Name: keyid
• Purpose: An identifier for the key that is used for signature over the integrity proof for the first record.
• Reference: this document

6.3.3. p256ecdsa parameter

• Parameter Name: p256ecdsa
• Purpose: An ECDSA signature using P-256 over the integrity proof for the first record.
• Reference: this document

6.3.4. rs parameter

• Parameter Name: rs
• Purpose: The size of the records used for progressive integrity protection.
• Reference: this document

7. References

7.1. Normative References

[FIPS180-4]	Department of Commerce, National., "NIST FIPS 180-4, Secure Hash Standard", March 2012.
[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.
[RFC4648]	Josefsson, S., "The Base16, Base32, and Base64 Data Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006.
[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.
[RFC7230]	Fielding, R. and J. Reschke, "Hypertext Transfer Protocol (HTTP/1.1): Message Syntax and Routing", RFC 7230, DOI 10.17487/RFC7230, June 2014.
[RFC7231]	Fielding, R. and J. Reschke, "Hypertext Transfer Protocol (HTTP/1.1): Semantics and Content", RFC 7231, DOI 10.17487/RFC7231, June 2014.
[RFC7233]	Fielding, R., Lafon, Y. and J. Reschke, "Hypertext Transfer Protocol (HTTP/1.1): Range Requests", RFC 7233, DOI 10.17487/RFC7233, June 2014.
[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", Internet-Draft draft-ietf-httpbis-encryption-encoding-00, December 2015.
[RFC2818]	Rescorla, E., "HTTP Over TLS", RFC 2818, DOI 10.17487/RFC2818, May 2000.
[RFC5246]	Dierks, T. and E. Rescorla, "The Transport Layer Security (TLS) Protocol Version 1.2", RFC 5246, DOI 10.17487/RFC5246, August 2008.
[RFC6962]	Laurie, B., Langley, A. and E. Kasper, "Certificate Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013.
[SRI]	Akhawe, D., Braun, F., Marier, F. and J. Weinberger, "Subresource Integrity", W3C CR , November 2015.

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?
   
   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