an oversight in the Bao security argument: security relies on the chunk counter

[oconnor663]

Antonio Marcedone and Balachandar Kesavan have reported a mistake in the Bao security argument related to seeking. The security argument can be repaired without any changes to Bao, so this mistake is not a vulnerability, but nonetheless it was a significant flaw in my reasoning. It indicates that I need to look carefully for similar mistakes and ultimately formalize the security argument into a proof.

Here's my summary of their report. Consider a 2 KiB file whose BLAKE3/Bao tree looks like this:

      root
      /  \
chunk_a  chunk_b

Now imagine an attacker tries to construct the following invalid tree representing a 3 KiB file:

          root
          /  \
     parent  chunk_b
      /  \
chunk_c  chunk_d

Here the attacker has kept nodes root and chunk_b the same, but they've replaced chunk_a with some new, arbitrary 2 KiB subtree. Note that the attacker cannot make the CV of the new parent node match the old CV of chunk_a, which is still the left half of the unchanged root node, so this tree cannot be a valid Bao encoding. (A collision on any of these CV's would mean that BLAKE3 itself was broken.)

However, suppose the attacker presents this invalid encoding with a length header of 3072 (3*1024), claims that it matches the original root hash, and invites the victim to seek to the start of the final chunk (content offset 2048). In this case the victim will read only the nodes root and chunk_b. The security question is, will these nodes validate? If so, the attacker will have successfully tricked the victim into validating content bytes that differ from the original input. (The bytes in question were present in the original but at a different offset, and the victim would also validate an incorrect total length for the file.)

In fact, thankfully, chunk_b will not validate. The root node will, because its CV/hash doesn't directly depend on the total input length. But chunk_b will not, because moving it to a new position in the tree changes the value of its chunk counter a.k.a. the t parameter to the compression function.

This is all well and good...but I never actually considered the chunk counter when I wrote Bao's security argument. In fact, an earlier version of Bao didn't include chunk counters at all and was broken in this case. The chunk counter was added later, for unrelated reasons. See also Zooko's original suggestion and section 7.5 of the BLAKE3 paper. So what we have here is a pretty dramatic oversight in the design, where I missed an important class of attacks, but I got lucky and didn't get burned.

The generalized version of this attack exploits the fact that that traversing the right face of the tree comes with some ambiguity about the size of the left subtrees that we're "skipping over". The number of parent nodes in the path from the root to the rightmost chunk is equal to the number of 1-bits in the binary representation of the rightmost chunk index (i.e. the total number of chunks minus one), and an attacker in this scenario has to preserve the number of nodes in that path, but which 1-bits those nodes represent is potentially ambiguous. In the case above the attacker tries to pass off chunk index 0b1 (1) as chunk index 0b10 (2), but they could also have tried 0b100 (4) or 0b1000 (8), or any other index with a single 1-bit set. Similarly, a tree with six chunks would have a rightmost chunk index of 0b101 (5), which could be ambiguous with 0b11 (3), 0b110 (6), or any larger number with two 1-bits. Disambiguating/decolliding these cases requires some node along the path to incorporate the total size of the tree in its CV. The chunk counter does this, and any Bao-like tree hash design without a chunk counter (for example, with the goal of allowing subtree caching) would need to incorporate the total size somewhere else, perhaps by having parent nodes include their own height in the compression function parameters.

Notably, the proof frameworks laid out by Sufficient conditions for sound tree and sequential hashing modes and Sound Hashing Modes of Arbitrary Functions, Permutations, and Block Ciphers, which we used in the BLAKE3 paper, aren't concerned with this property. For the purposes of those frameworks, the fact that parent can't be constructed to collide with chunk_a (i.e. "tree-decodability" or "radical-decodability") is the end of the story. The modified tree can never represent the hash of any input, so we don't need to consider it. But for Bao's purposes, we need something stronger. The victim might never even look at parent, but they still need to be certain that none of the chunks they do look at have been moved. I need to formalize the specific properties Bao is aiming for here and then (hopefully) prove that Bao achieves them.

[oconnor663]

A couple more observations: I'm pretty sure that this dependency on the chunk counter only applies to seeking. So if the recipient was streaming an entire Bao encoding from the front, I don't think they'd be vulnerable even without the chunk counter. The reason is that traversing the left face of any subtree always verifies the height of that subtree, and the attacks we're considering here are based on the attacker lying about the height of the subtrees you're skipping over.

So if BLAKE3 had not included the chunk counter, one option for fixing Bao would be to expand the "final chunk requirement" to include traversing the left face of some subtrees. Maybe something like "for each run of 1-bits in the final chunk index, you need to verify the height of the subtree represented by the first 1-bit in the run". That's substantially more complicated, though, and also O(log²(n)) work in general. Is it possible to do better?

[oconnor663]

On the subject of the chunk counter, here are all the properties I know of so far that depend on it:

• Solving the "ambiguous seeks along the right face" problem that this issue is all about. As I mentioned above, there could be other ways to solve this, like having each parent node assert its own height.
• Discouraging subtree caching. This was the original motivation for including chunk counters in the design, and section 7.5 of the paper goes into this.
• Protecting the privacy of hidden inputs in a keyed Bao tree. I don't think I've written about this anywhere else. Suppose you have a secret file, and you bao encode --outboard that file. If you publish that outboard encoding (that is, the whole Bao tree minus the chunks) what does that reveal about your file? Well, if an attacker can guess the whole file, or actually any chunk in the file, seeing the Bao encoding allows them to check their guess. Ok, so what if the encoding is keyed? (Bao only implements unkeyed BLAKE3 currently, but getting keying working would be relatively easy.) This is more interesting. An attacker who doesn't know the key can't check their guesses. However, they might try to learn whether two chunks in the tree are identical, by looking to see whether any CVs in the tree repeat. The chunk counter prevents this: chunk CVs will be different even if their contents are the same. This property could be useful for an application that wanted to publish Bao trees with secret inputs, though to be honest I don't know what that application would be. (Note that reusing the same key to encode two different files would reveal identical chunks in identical positions, so this hypothetical application would probably want some sort of nonce.)
• Using some sort of block counter or chunk counter defeats attacks like Second Preimages on n-bit Hash Functions for Much Less than 2ⁿ Work (Kelsey and Schneier 2004). These attacks start by assuming that you can find collisions, which means the hash function is already broken by most practical standards, and it's more of a question of "blast radius".
• Because Bao doesn't explicitly hash the input length, the only way to verify the length is to seek to the final chunk and verify it. This is a downside for protocols like Iroh, becasue it makes the "proof" of the length of a file relatively large (the final chunk plus O(log(n)) parents). But it has a security/correctness upside: The final chunk is the only "source of truth" for verifying the input length. (Assuming the implentation doesn't blindly trust the first 8 bytes of the stream without verifying anything.) This wouldn't be the case if e.g. the root note included the input length as a suffix, and in that alternate design we'd need to think carefully about what happens when the root and the final chunk disagree.