1
$\begingroup$

Let $H$ a cryptographic hash function of image length $n+1$ and $s_0$, $s_1$, ... , $s_k$ a finite sequence of bitstrings (length $>n+1$), such that $s_j$ contains a hash of $s_{j-1}$ for all $1\leq j \leq k$, that is $\langle s_j(0),...,s_j(n)\rangle = H(s_{j-1})$ (The first $n+1$ bit of each $s_j$ are the hash of $s_{j-1}$).

Is it possible and if yes how likely, that the sequence $s_0$, $s_1$, ... , $s_k$ is a loop? I.e. that $s_0=s_k$?

Edit: If important for the answer, $s_j$ must not necessarily begin with the hash of $s_{j-1}$ but contain it at least at a fixed position in the bitstring. The soley point of the question is to find Merkle DAGs/Trees which are not well defined due to the existence of those cycles.

If its infeasible, I would like to see a deduction from the axioms of a cryptographically secure hash function.

Edit: Relating the question to the title: If such a loop can be found as a path in a Merkle Dag (or in the extrem case a Merkle tree), then the resulting data structure is neither a tree nor a dag anymore.

Edit-2: From Fixed point of the SHA-256 compression function we know that fix points of cryptographic hash function can be found, so it might also be possible to come up with bitstrings $s_0$ of length $>n+1$ that contain their own hash in the first $n+1$ bits. So it is indeed possible to find those loops with $(s_0,s_0, \ldots, s_0)$ for arbitrary $k$'s. In fact the answer from Is there a string that's hash is equal to itself? estimates that this happens frequently (The answer assumes strings of length $n$, but can be extended to our case)

So it boils down to the question of the possibility to find strings strictly larger then their hash, that nevertheless contain their hash as a substring.

Improve this question
$\endgroup$
7
  • $\begingroup$ "such that $s_j$ contains a hash of $s_{j-1}$ for all $1\leq j \leq k$"; what else does $s_j$ contain? If it contains (say) the value of $j$, then obviously we'll never run into a case that $s_0 = s_k$ $\endgroup$
    – poncho
    May 27, 2019 at 16:19
  • $\begingroup$ I did not specify that. The question is, if we can come up with something, such that $a_0=a_k$.. Its an existence or possibility question. Of course there are case where it does not work. Thats easy. $\endgroup$
    – Bobby
    May 27, 2019 at 16:48
  • $\begingroup$ Then, what's $a_i$? I had assumed that $a_0 = a_k$ was a typo for $h_0 = h_k$... $\endgroup$
    – poncho
    May 27, 2019 at 18:31
  • $\begingroup$ Its all there. $a_i$ is a bitstring of length $>n$, such that the first $n$ bits are a hash of $a_{i-1}$... Thats all that is required from $a_i$ really, so the bits at positions $>n$ can be choose arbitrarily. The question is then if its possible to choose $k$ and the bits, such that $a_0=a_k$. Whats so complicated? $\endgroup$
    – Bobby
    May 27, 2019 at 20:13
  • $\begingroup$ If there is a solution, then data structures like Merkle Trees oder Merkle DAGs might not be trees or DAGs in any case, really. So its important, but I can't find an answer anywhere... $\endgroup$
    – Bobby
    May 27, 2019 at 20:16

1 Answer 1

Reset to default
1
$\begingroup$

It is certainly possible for a string to contain its own hash value, so it's even possible that $s_0 = s_1$.

And it's even possible to artificially construct functions that satisfy all the standard properties required of a cryptographic hash function (i.e. collision and first and second preimage resistance), but which hash an arbitrarily chosen string to a prefix of itself. All you need to do take any standard secure cryptographic hash function and redefine its output for that single arbitrarily chosen input, as in fgrieu's answer to this related question.

However, no examples of such strings are known for any cryptographic hash function that is widely used and currently believed to be secure, such as SHA-2 or SHA-3. Indeed, arguably, the ability to exhibit such a string would strongly suggest some kind of a weakness in the hash function, since finding such a string purely by brute force would be completely infeasible for any hash function with a reasonable output length (say, 256 bits or more).

Indeed, the same holds for longer cycles as well: as far as I know, for a random hash function $H$ with $n$-bit output, there's no way to find such cycles more efficiently than by using a generic cycle finding algorithm, all of which require at least $2^{n/2}$ evaluations of the hash function on average.

Finally, I should note that none of this necessarily has any relevance to whether or not Merkle DAGs or trees are well defined, as it's perfectly possible to define those structures in a way that allows two distinct nodes to have the same hash and/or the same children and/or content. For example, the definition of a Merkle tree currently given on Wikipedia reads:

[A] Merkle tree is a tree in which every leaf node is labelled with the hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes.

While this definition is rather terse, and glosses over some important details (some of which are addressed later on the page), the key point is that under this definition a Merkle tree would remain a tree even if all the nodes happened to have the same label, since the labels have no effect on the graph structure of the tree!

Of course, a secure implementation of a Merkle tree should not allow an attacker to feasibly construct two nodes with different children and/or contents but the same label, at least not on the same level of the tree, since swapping one such node for the other would then allow a forgery. But even an insecure implementation that did allow that would still be well defined.

Conversely, even if you defined a Merkle tree (or DAG) in such a way that the connectivity of the tree was determined by the labels (i.e. such that a node $A$ was defined to be a child of node $B$ if and only if $B$'s label contained the hash of $A$'s label) then, as noted above, as long as you used a secure hash function with no known ways to find cycles faster than by brute force, you could still be practically certain that the resulting structure would indeed be acyclic.

A more serious conceptual issue with such a definition, of course, is that most non-leaf nodes of such trees would have an infinite — or at least a very, very large — number of possible children, simply because hash functions are non-injective and most hash values have infinitely many possible preimages, or nearly so. Of course, for a secure hash function, finding most of those preimages should be computationally infeasible, but theoretically they still exist.

In practice, to put such a definition on a solid conceptual footing, you'd probably have to restrict the valid node labels to only those appearing in some kind of a global database of known strings indexed by their hash, and then explicitly require that it be infeasible for an attacker to find a string outside the database that shares a hash value with any string in the database. Fortunately, this is a direct corollary of collision resistance (even assuming that the attacker can add strings to the database; otherwise second preimage resistance would be sufficient), and thus already (presumably) satisfied by any (presumably) secure cryptographic hash function.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Ilmari Karonen. Thats a great answer. Unfortunately my 'Bobby' avatar is currently not able to publicly upvote this, which is unfortunate. I'll think about it and reply later in more detail. $\endgroup$
    – Bobby
    May 28, 2019 at 19:33
  • $\begingroup$ @Bobby: That's all right. If it answers your question, you can always mark it as accepted, at least. $\endgroup$
    – Ilmari Karonen
    May 28, 2019 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.