Sufficient conditions for sound tree and sequential hashing modes

Hash functions are usually composed of a mode of operation on top of a concrete primitive with fixed input-length and fixed output-length, such as a block cipher or a permutation. In practice, the mode is often sequential, although parallel (or tree) hashing modes are also possible. The former requires less memory, while the latter has several advantages such as its inherent parallelism and a lower cost of hash value recomputation when only a small part of the input changes. In this paper, we consider the general case of (tree or sequential) hashing modes that make use of an underlying hash function, which may in turn be sequential. We formulate a set of three simple conditions for such a (tree or sequential) hashing mode to be sound. By sound, we mean that the advantage in differentiating a hash function obtained by applying a tree hashing mode to an ideal underlying hash function from an ideal monolithic hash function is upper bounded by \(q^2/2^{n+1}\) with \(q\) the number of queries to the underlying hash function and \(n\) the length of the chaining values. We provide a proof of soundness in the indifferentiability framework. The conditions we formulate are easy to implement and to verify and can be used by the practitioner to build a tree hashing mode on top of an existing hash function. We show how to apply tree hashing modes to sequential hash functions in an optimal way, demonstrate the applicability of our conditions with two efficient and simple tree hashing modes and provide a simple method to take the union of tree hashing modes that preserves soundness. It turns out that sequential hashing modes using a compression function (i.e., a hash function with fixed input-length) can be considered as particular cases and, as a by-product, our results also apply to them. We discuss the different techniques for satisfying the three conditions, thereby shedding a new light on several published modes.

Authors and Affiliations

1. STMicroelectronics, Agrate, Italy

   Guido Bertoni

2. STMicroelectronics, Diegem, Belgium

   Joan Daemen & Gilles Van Assche

3. NXP Semiconductors, Haasrode, Belgium

   Michaël Peeters

Corresponding author

Correspondence to Joan Daemen.

Appendix A: Illustrations

In this section, we illustrate two undesired properties of tree hashing modes explained in Sect. 4 to introduce two of the three conditions for sound tree hashing. We give some figures of templates generated by some mode of use. The way these templates have been generated by the mode of use are out of scope of this section. Note also that these templates illustrate undesired properties, and hence, the modes of use that would produce them are per definition not sound.

Example of an inner collision without a collision in \(\mathcal {F}\)

Full size image

We use the following conventions. Instead of depicting individual bits, we depict message-, chaining- or frame blocks, where a block is just a sequence of consecutive bits. Frame blocks are depicted by white rectangles with its value indicated, message blocks by light gray rectangles and their position in the message indicated, and chaining blocks by dark gray rectangles with an indication of their child. An output is depicted by a rounded rectangle. The nodes are identified with their indices and the relation between the nodes is additionally indicated by arrows, symbolizing the application of \(\mathcal {F}\) during template execution for a concrete input \(M\).

The first property is related to the existence of inner collisions in the absence of collisions in the output of \(\mathcal {F}\) and is illustrated in Fig. 4. The figure depicts two templates that are generated by a mode of use \(\mathcal {T}\) for two different message lengths. All nodes have as first two bits frame bits with value 01. The template on the left has four nodes: three leaf nodes of height 1 and a final node that takes an input block and the chaining values corresponding to the three leaf nodes. The template on the right has three nodes: two leaf nodes of height 1 and a final node that takes an input block and the chaining values corresponding to the two leaf nodes. Note that the final node of the right template has a message block (indicated by \(M'_0\)) in the place where the final node of the left template has the concatenation of a message block \(M_0\) and a chaining block \(CV_2\). We can exploit this fact to construct an inner collision from any message \(M\) with length matching the left template. As can be seen in the figure, it suffices to form \(M'\) by replacing in \(M\) the block \(M_1\) by \(\mathcal {F}(01|M_1)\).

Example of the generalization of length extension to tree hashing

Full size image

The second property, a generalization of length extension to tree hashing, is illustrated in Fig. 5. Given the output of \(h = \mathcal {T}[\mathcal {F}](M)\) of some message \(M\), length extension is the possibility to compute the output of \(\mathcal {T}[\mathcal {F}](M')\) with \(M\) a substring of \(M'\), only knowing the output \(h\) and not \(M\) itself. Figure 5 depicts two templates corresponding with two different message lengths. The templates have a binary tree structure. The template at the left has three nodes: two leaf nodes and a final node containing the chaining values corresponding to the two leaf nodes. The template at the right has seven nodes: four leaf nodes, two intermediate nodes each containing the chaining values corresponding to two leaf nodes and a final node containing the chaining values of the intermediate nodes. Note that the chaining block \(CV_0\) in the final node of the right template corresponds with the hashing output of the left template. As can be seen in the figure, given the hash output \(h\) of a message \(M\) with length matching the left template, one can compute the hash output of any message \(M' = M | M_2 | M_3\) with length matching the right template without knowledge of \(M\).

Appendix B: Remarks on the cost

The cost measure introduced in Sect. 5.2 aims at counting on an equal footing both queries to \(\mathcal {H}\) and queries to \(\mathcal {I}\). We wish to illustrate this by comparing two examples of distinguisher.

The first distinguisher uses only the \(\mathcal {I}\) interface to produce a collision in \(\mathcal {F}_n\) (or in the simulator). Assuming a collision is produced, two messages can be built, so as to turn this collision into an inner collision in \(\mathcal {T}\) but not in \(\mathcal {G}\). This attack takes about \(2^{n/2}\) queries. (If after \(2^{n/2}\) attempts no collision has been found, the distinguisher may suspect it is not querying \(\mathcal {F}\) but a simulator.)

The second distinguisher uses only the \(\mathcal {H}\) interface and attempts to exhibit an inner collision directly. When talking to \(\mathcal {T}\), such an inner collision can occur, but when talking to \(\mathcal {G}\), an inner collision does not even exist (with the requested output-length sufficiently large to detect such an inner collision with arbitrary certainty). More specifically, the distinguisher queries the \(\mathcal {H}\) interface with equal tree parameters \(A\) and messages \(M_i\) that vary only in one leaf, which is chosen to have the maximum height \(H\) in the tree. To obtain an inner collision, it is sufficient to get a collision at any of the \(H\) nodes on the way from the leaf to the final node. The distinguisher needs about \(2^{n/2}/H\) queries to hit an inner collision. Hence, in this context a query to \(\mathcal {H}\) appears to be a factor \(H\) more powerful than a query to \(\mathcal {I}\).

The cost function that counts calls to \(\mathcal {F}\) and discards duplicate queries as one brings the two distinguishers to a more equal footing. The first distinguisher succeeds at a cost of about \(2^{n/2}\). The queries of the second distinguisher could be performed at the level of the \(\mathcal {I}\) interface, the tree mode \(\mathcal {T}\) being simulated by the distinguisher. In this case, each query to \(\mathcal {H}\) translates into \(f_\mathcal {T}(|M|,A)\) queries to \(\mathcal {I}\). However, the strategy of the second distinguisher is such that only \(H\) \(Q_\mathcal {I}\) queries differ for each of the \(2^{n/2}/H\) \(Q_\mathcal {H}\) queries. Hence, the cost of \(Q_\mathcal {I}\) for the second distinguisher is also about \(2^{n/2}\).

Reprints and permissions