On Wed, Jan 29, 2014 at 11:04 AM, George Kadianakis desnacked@riseup.net wrote:
On the other hand, if we wanted to use the HSDirs, we could imagine the HS sending some sort of revocation message to the responsible HSDirs so that they stop serving descriptors with compromised keys. Unfortunately, this scheme treats HSDirs as trusted parties, since they can simply ignore the revocation and continue passing the evil descriptor to clients. We could decrease the chance of this happening by implementing #8244 and also having the clients use multiple HSDirs to fetch descriptors. This will force the attacker to corrupt multiple HSDirs for the attack to succeed. Still the solution is not very elegant.
What else should we consider?
Another approach could be similar to what is done for membership maintenance in ShadowWalker[1] and Torsk[2], and have the adjacent nodes (in the hash ring) periodically (every 10 minutes, say) cross-certify the list of "unrevoked" descriptors for each HSDir node. So the protocol would look something like:
1.) Each HSDir keeps a list of all of the valid descriptors for each of its $hsdir_spread_store predecessors in the hash ring. (This is done currently, although I don't think the implementation of the HSDir code segregates descriptors by the responsible neighbor)
2.hs) when the HS revokes a descriptor, it sends a signed REVOKE message to all of the replicas/spread nodes for its descriptor. 2.hsdir) Every $revoke_window seconds, each HSDir composes a list of still-valid descriptors for each hash ring neighbor N, signs the list, and sends the list/signature to all $hsdir_spread_store successors of N. (the signature should be explicitly bound to a revocation window. For privacy purposes it might make sense to sign the list as a cryptographic accumulator [3] or Merkle tree so that an HSDir can prove a descriptor is in the list without revealing the entire list)
3.) When a client performs a lookup for a descriptor, the HSDir includes the (proof that the descriptor is on the) current unrevoked list and any signatures from its neighbors. The client accepts that the descriptor has not been revoked if at least some threshold t of hash ring neighbors have signed the / a (current) list.
This requires threshold trust of the HSDirs (but you need it anyway for availability) and probably a larger value for $hsdir_spread_* than the currently specified defaults, but the crypto/communication overhead should be pretty small (e.g. accumulator witnesses are between 256 and 2048 bits depending on the accumulator) and it avoids adding another trusted party / set of duties for the directory authorities...
[1] http://freehaven.net/anonbib/bibtex.html#ccs09-shadowwalker [2] http://freehaven.net/anonbib/bibtex.html#ccs09-torsk [3] http://freehaven.net/anonbib/bibtex.html#camenisch2002da for example.