I'm digging through CONIKS papers and it seems that it is an absolute must to select new tree-wide constant for each update (and to rebuild the whole tree respectively) to prevent parallel attacks through past versions of the same tree structure (like parallel birthday attack for instance).

Can't understand why does it matter and what is the attack scenario?

How practical is this attack?

For instance, Google Trillian developers don't select new Tree Id for each update (for Map using CONIKS hasher).

Papers Im looking at:

1) https://eprint.iacr.org/2014/1004.pdf

2) https://eprint.iacr.org/2016/683.pdf

Many thanks!


1 Answer 1


As Gary Belvin from Trillian replied:

In Trillian we use a tree wide constant for computing hashes (See MapHasher) in order to achieve as close to l bit security as possibe and prevent attacks between trees and between different locations inside of a tree.

As you've noted, the map does not update the tree nonce for each revision of the map. Recomputing the entire map tree for each update would be prohibitively expensive and would prevent the Trillian Map from being a system that supports near-realtime updates. This tradeoff is described in the CONIKS paper, section 3.1

To attack multiple revisions of the same tree, an attacker searches for a collision, and then hopes that a future version of the tree contains a node that matches the collision. If every leaf node changed at every revision, this would be a lot of new nodes to hope for a match against. However, in the map, the number of new nodes is < tree depth * updates, which grows linearly, not exponentially.

Even if every node of the map changed at each revision, we should still be safe. If I'm reading Katz correctly, in order to maintain l bit security in a multi-instance setting we need l + log(N) bits in the hash function, where N is the total number of map revisions. 256 bits of hash output should be sufficient to maintain 128 bits of security for 2^128 revisions.


Your Answer

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

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