[tor-dev] Key revocation in Next Generation Hidden Services

[Nicholas Hopper]

On Wed, Jan 29, 2014 at 11:04 AM, George Kadianakis
<desnacked at 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.

-- 
------------------------------------------------------------------------
Nicholas Hopper
Associate Professor, Computer Science & Engineering, University of Minnesota
Visiting Research Director, The Tor Project
------------------------------------------------------------------------