While I was working for Pyrofex, we ran into an interesting problem that could be solved with an Online Tree Hashing mode.
An online hashing mode is one where the data can be streamed into the function and a hash can be calculated without storing the data until the end is reached. Standard linear hashing is online. Except for the parallel implementations, most of the Blake2 tree modes are not online.
Tree modes are usually applied to break up a single piece of data into a hash tree so that updating the hash in response to changes in the data is fast.
In our case we were building the tree structure online. In parallel, new leaf nodes could be created and an arbitrary number of leaf messages could be merged. At any point we could take a node and ask for the final root hash associated with its subtree and any data processed at that node until now.
We wanted to guarantee that the new hashing mode that we were creating would be safe against collisions and extension attacks. For our application we only really needed to protect against collisions, but I wanted the mode to be general and usable in cases that needed protection against extension attacks.
The standard for safety of a hash mode is the paper “Sufficient conditions for sound tree and sequential hashing modes”, by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
Tree hash modes use an inner hash function Fn
The paper lists three criteria for a hash mode to be sound:
The mode is Tree-Decodable
This is technical, but the gist is that it should be impossible to construct identical inputs to Fn given two differently shaped trees.
The mode is Message-Complete
This is easy to grasp, as it means that all of the message bits are fed into Fn at some point. If they aren’t, it’s easy to construct a collision (change the bits that are never fed in)
The mode is Final-Node-Separable
The gist of this property is that the final output from the root of the tree cannot be re-used as a chaining value for a larger tree. This is a generalization of extension attacks. Extension attacks matter for keyed hashing like HMAC, but not for public hashing like SHA1. HMAC is a construction from a hash function specifically to prevent extension attacks.
At any point in time, we have a set N of nodes. For each of these nodes, its children if any have already been completely processed, and their chaining values have been processed as well. We have four operations we can do to the set of nodes.
A node is represented as a Blake2 Hash Context. Blake2 is initialized with tree parameters that we bend to fit our application.
Feeding data to a node is simply feeding data into the Hash Context.
To introduce a new leaf node, we simply create a new hash context with the following parameters:
Merging is similar to above, but we set the fanout parameter to the number of child hashes. For each of them, we extract an internal final hash and feed it into the new hash context. For simplicity, we 0 pad the child hashes to a full block, but this doesn’t affect security either way.
In the code that I wrote, with more than 255 children, we just create parents in a loop. I should have done this differently, as it is a security flaw. A simple solution would be to pad the last block with ones if we are merging for more than 255 children. This would make the padding a necessary part of security, but only for exactly 255 children.
To ask a node for its final state, we use Blake2 finalization, but we set both f0 and f1. This distinguishes an internal nodes final state and a root node’s final state. Note that to prevent extension attacks, no internal chaining value can be disclosed.
Message Completeness is easy. We hash all the data that we care about, so our mode is message complete.
Final Node Separability is pretty easy as well. By using the f1 flag only on the final root hash, we guarantee that it can’t be used as an internal node for some larger tree.
Tree Decodability is a little harder to see. Assuming we never merge more than 255 nodes, then the fanout parameter prevents someone from constructing a node that differs in tree structure. You can feed the same data, but the parameters, which form the first block of data, will be different for different tree structures.
I don’t know if there is an application for a mergeable and splittable random number generator outside of our particular application. It was useful in our particular application, and I’m proud of it. In our application, we were generating 256 bit strings to be used as identifiers. We didn’t need any more collision resistance than this, so we used 256 bit internal chaining values. If you are using this to actually hash a tree and not as a PRNG, then your internal chaining value size should match your result value size.