HTML Subresource Integrity

Posted Jul 3, 2016 9:46 UTC (Sun) by oever (guest, #987)
In reply to: HTML Subresource Integrity by ianmcc
Parent article: HTML Subresource Integrity

This is what the BitTorrent protocol does. It's not too popular for browsing yet. There is more attention for the distributed web lately, so it might become more popular.

Using checksums for block is a nice suggestion for the next version of SRI.

to post comments

HTML Subresource Integrity

Posted Jul 4, 2016 9:20 UTC (Mon) by hkario (subscriber, #94864) [Link] (3 responses)

problem is, that if you want to verify only part of the file, you need to have the _whole_ Merkle tree, not only the root node, to do that

and a whole Merkle tree for 4KiB fragments of a 1MiB file is 8KiB long (using SHA-256, double that for SHA-512)

HTML Subresource Integrity

Posted Jul 5, 2016 15:34 UTC (Tue) by nybble41 (subscriber, #55106) [Link] (2 responses)

> problem is, that if you want to verify only part of the file, you need to have the _whole_ Merkle tree, not only the root node, to do that

You don't necessarily need the whole Merkle tree, if it's organized properly. You just need the root and the siblings of the nodes on the path to the block you want. For example:

Root
|-- A0
|...|-- B0
|...|...|-- C0
|...|...|...|-- D0
|...|...|...|...|-- E0
|...|...|...|...|...|-- Block 0
|...|...|...|...|...\-- Block 1
|...|...|...|...\-- E1
|...|...|...|...|...|-- Block 2
|...|...|...|...|...\-- Block 3
|...|...|...\-- D1 (elided)
|...|...\-- C1 (elided)
|...\-- B1 (elided)
\-- A1 (elided)

The value of each node is a hash of its immediate children. A six-level binary tree can describe up to 2^6=64 blocks (or 256 KiB at 4 KiB per block), but to verify block 0 you only need the hashes of the root, A1, B1, C1, D1, E1, and block 1, for a total of 7 hashes (224 bytes of SHA-256). The intermediate hashes stand in for the parts which weren't downloaded, so in general the more complete subtrees you download the fewer hashes you need. If you download the entire file you only need to know the root hash.

HTML Subresource Integrity

Posted Jul 7, 2016 8:59 UTC (Thu) by hkario (subscriber, #94864) [Link] (1 responses)

the suggestion was so that the browser can do partial rendering as soon as the data is read, that means you need all the leaf nodes as the browser will want to update the rendering each time a new chunk is downloaded and checksummed

By writing 8KiB I meant exactly 8192 bytes of data i.e. only the leaf nodes.

In general yes, if getting parts of the tree requires less time (latency) than downloading the data, you don't need the full Merkle tree, but that doesn't assume that the whole point of using it is to reduce latency.

HTML Subresource Integrity

Posted Jul 7, 2016 16:57 UTC (Thu) by nybble41 (subscriber, #55106) [Link]

> the suggestion was so that the browser can do partial rendering as soon as the data is read

Sorry, I wasn't looking at the bigger picture, just the statement that one needs the full Merkle tree to verify part of a file. If you want to download the full file while verifying each part as its received then you will need (almost) the full Merkle tree.

Still, it isn't necessary to download the Merkle tree in full before you can start verifying the data. You could stream the hashes from the Merkle tree in the order that they'll be needed to verify each block, e.g.:

(the root hash is already known from the SRI attribute)
Fetch A1, B1, C1, D1, E1, H(Block 1), and Block 0
Compute H(Block 0)
Compute E0 = H(H(Block 0)|H(Block 1))
Compute D0 = H(E0|E1)
Compute C0 = H(D0|D1)
Compute B0 = H(C0|C1)
Compute A0 = H(B0|B1)
Verify H(A0|A1) = root hash
Fetch Block 1
Verify H(Block 1)
Fetch H(Block 3) and Block 2
Compute H(Block 2)
Verify H(H(Block 2)|H(Block 3)) = E1
Fetch Block 3
Verify H(Block 3)
Fetch E3, H(Block 5), and Block 4
Compute H(Block 4)
Compute E2 = H(H(Block 4)|H(Block 5))
Verify H(E2|E3) = D1
Fetch Block 5
Verify H(Block 5)
etc.

The expectation is that the hashes would be provided in this order in a separate file alongside the content. With this approach you can verify each block as it's downloaded. Even better, to do so you only need to download the hashes for the odd-numbered blocks and intermediate nodes; the even-numbered hashes can be computed from the content under the assumption that the even-numbered nodes are downloaded and verified first within each subtree. For larger files this should cut the number of downloaded hashes almost in half.