I was reading about the TIK protocol for thwarting wormhole attacks on adhoc networks. It uses a Merkel Hash Tree to store keys. But since the number of keys can be large, the tree is optimized by only storing the upper levels.

As far as I understand, the $a$ node is the result of the hash of its two children. But what I do not understand is that hashing is irreversible. If it is theoretically not feasible for an adversary to construct the child nodes if the parent node is known, how does storing the upper layers help at all?

What am I missing here?


The usual way to do this is by using a CSPRNG to generate the leaf values, such as AES in counter mode. That way, once you have calculated the entire tree, you only need to store the upper layers, the secret AES key, and the initial counter value, and it is quite easy to recalculate very quickly any particular branch you need.

For example, let's say you generate a tree of depth 20 using AES in CTR mode to generate the values $v_0, v_1, v_2, ...v_n$ (in figure 1 on page 5 of the paper you linked), so there is a corresponding counter-value $c_i$ for each $v_i$, such that $v_i = E_K(c_i)$. Let's also say you only store the AES key, the first counter value, and the top 9 layers of the hash tree (so you only need to keep 511 hashes, and can discard the remaining 1 million or so hashes in the tree).

To recalculate the path from any one particular leaf, $v_i$, back to the top-most node, all you need to do is re-generate the leaf value for $v_i$ using AES and the counter value $c_i$ (which is easy if you know the initial counter value and the index $i$), plus 2047 of its immediate neighboring values, and then use the hash function $H$ to re-generate the branch of the tree from those 2048 values up to one of the 256 stored values in layer 9 (which takes much less time to calculate than the initial set-up because you are only doing one 256th of the tree rather than the whole tree).

| improve this answer | |
  • 1
    $\begingroup$ Thanks. However, if I am understanding your answer correctly, one cannot reconstruct the tree unless AES is used in CTRC or CTR$ mode, since no other mode provides any determinism. $\endgroup$ – ritratt Sep 29 '13 at 19:47
  • 1
    $\begingroup$ You could use AES in OFB mode, or a dedicated stream cipher. But those options are not as good as CTR mode because CTR mode has a 'random access' property, where you don't need to recalculate $v_0, v_1,$...$v_{i-1}$ in order to calculate $v_i$. Also, you could use Salsa20, which is a stream cipher, but it has that random access property. $\endgroup$ – J.D. Sep 29 '13 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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