[tor-dev] A Proposal for a hidden service revocation system

[Adrien Johnson]

Filename: xxx-rend-revoke.txt
Title: Hidden Service Revocation
Author: Adrien Johnson
Created: 2015-03-04
Status: Draft

Hidden service operators need to be able to revoke trust in their hidden 
service
if they know or suspect their hidden service secret key has been 
compromised.

1. Motivation

     A Hidden service operator can determine that the hidden service 
secret key
     is compromised in several ways today. Forensic traces of intrusion 
may be
     detected on the hidden service server, or valid signed descriptors 
for the
     service may be published by someone other than the legitimate 
operator in a
     traffic hijacking attack. It is impossible for a compromised hidden 
service
     secret key to be used to hijack traffic in a way that is not 
detectable by
     the latter method.

     Even though it is easy for the operator to detect a hidden service 
key is
     compromised, there is no satisfactory way for a hidden service 
operator to
     notify its users of this fact. The hidden service may display
     a message to its users warning of the compromise and directing them 
to a new
     supposedly uncompromised .onion domain, but a user has no way to know
     whether such a message was posted by the legitimate hidden service 
operator
     or a hijacker.

     A revocation system where anyone possessing the hidden service 
secret key
     can revoke trust in the key solves this problem.

2. Overview

     This revocation system is built on the hidden service directory 
system. A
     revocation takes the form of a hidden service descriptor which 
provides no
     way to contact the hidden service (i.e. zero introductory points).

     A hidden service directory which receives a revocation descriptor and
     verifies its signature should discard any non-revocation descriptors it
     possesses for that hidden service, and should propagate the revocation
     through the hidden service directory system as normal.

     Crucially, a hidden service directory which possesses a revocation
     descriptor for a hidden service and receives a newer, valid 
descriptor for
     that hidden service which is not a revocation descriptor MUST 
retain the
     revocation descriptor and MUST discard the newer non-revocation 
descriptor.
     This is the only change needed to support this revocation system at a
     basic level today.

3. Design considerations

     3.1 Revocation lifetime

         Ideally, a revocation should be permanent. The Tor network would
         ideally remember forever that a hidden service has been 
revoked, and
         this would provide the maximum possible protection to the users 
of the
         hidden service against imposter services.

         Indeed, any tor node which becomes aware a hidden service has been
         revoked should remember this information forever, and should 
refuse to
         connect to any hidden service which it knows was revoked in the 
past
         (unless the user disables this protection).

         However, a permanent (or even just long-lived) revocation in 
the hidden
         service directories present problems:

         1) Increased memory and bandwidth requirements on the Tor network
         compared to a normal hidden service descriptor. For 
non-malicious use,
         this may not really be a problem, since once a service is 
revoked, there
         would be only a trickle of requests for updated information 
about it
         (from visitors who have not already found out it was revoked). 
However
         for a malicious user who attacks the Tor network by flooding it 
with
         hidden service descriptors for fake hidden services, any increased
         lifetime of a revocation descriptor over a normal descriptor 
represents
         a multiplication of their attack power.

         2) For next generation hidden services as described in
         224-rend-spec-ng.txt, a revocation which lasts longer than one 
blinded
         signing key validity period weakens the privacy protection against
         correlation which is provided by rotating blinded signing keys. 
If a
         revocation were - for any amount of time - not expected to be
         signed by the current normal blinded signing key for that 
service, but
         instead a separate 'blinded revocation signing key', then users 
seeking
         to check the revocation status of that service before visiting 
would
         have to make two requests for a hidden service descriptor: one 
to see if
         there is a revocation descriptor published by that service, and 
one to
         see if there is a normal descriptor published by that service.
         A malicious hidden service directory (or group of directories) 
could use
         this correlation to determine which hidden service descriptors 
belong to
         the same hidden service between blinded signing key rotations.

         [NOTE: Not sure how easy correlation based on request volume 
already
         makes this attack if the attacker controls enough hidden server
         directories to reliably monitor request volume between blinded 
signing
         key rotations. I suspect the real danger of long-lived revocations
         compared to attacks based purely on request volume is that it lets
         attackers easily "pick up a lost trail" if they managed to link a
         revocation signing key and a normal blinded signing key at any time
         in the past, whereas attacks based purely on request volume are 
likely
         to lose track of a service permanently when its descriptors 
shift to
         a directory the attacker does not control]

         For these reasons, revocations which last no longer than
         a normal hidden service descriptor, and which the operator must
         therefore constantly broadcast, are the safest option for 
implementing
         hidden service revocations using hidden service descriptors.

         Short lived revocations have the advantage that the Tor network 
does not
         need to make any hard-and-fast judgement about how long it is 
worthwhile
         to remember a hidden service has been revoked, the hidden service
         operator can make that judgement for themselves and broadcast the
         revocation for as long the operator feels hijacking and 
impersonation
         is a concern.

         If the operator is unable to maintain (or fears they will be 
unable to
         maintain) a revocation broadcast for an appropriate amount of time,
         they can disclose their private key to a 3rd party service who will
         broadcast the revocation on the operator's behalf. An operator 
would
         want to employ several of these services, since if only one 
service had
         the private key, and if they were malicious, they could cease
         broadcasting the revocation and instead use the key to set up an
         impostor service.

         Despite these minor difficulties that short-lived revocations 
impose,
         they are still a major improvement to the security of the Tor 
network.

     3.2 Digression on the shape of a 3rd party Revocation Broadcast Service

         Though it is outside the scope of this proposal,
         I envision these 3rd party key revocation services being simple 
websites
         where anyone can upload a hidden service private key and the 
website
         will broadcast the revocation indefinitely. They could employ 
simple
         abuse-mitigation like CAPCHAs or IP ratelimiting over the 
clearnet to
         prevent mass-upload of keys. This should keeps costs low enough 
that
         these revocations services could operate for free.

         Alternatively (or additionally), a distributed 3rd party revocation
         service could be built into the Tor network by enclosing the 
private
         key in the revocation descriptor. This would allow anyone who 
retrieves
         the revocation descriptor (and knows which .onion it's for) to
         broadcast updated 'echo' revocation descriptors of their own. 
This could
         be built to avoid the problems with static long-lived revocations.
         [TODO: Expand in another document later]

4. Implementation

     4.1 Basic Support

         For the Tor network to support hidden service revocations at a 
basic
         level, a large proportion of hidden service directories must 
recognize
         that a hidden service descriptor with zero introductory points 
has the
         special meaning of being a revocation. These hidden service 
directories
         must not allow a current unexpired revocation descriptor to be 
replaced
         by a non-revocation descriptor (so called 'un-revocation'). In 
all other
         ways, treatment of a revocation descriptor is identical to 
treatment of
         a non-revocation descriptor for a hidden service.

         [NOTE: Maybe we want a more explicitly requested revocation? 
Using a
         zero introductory point descriptor as a revocation has the
         advantage of being backward-compatible with older directory 
software,
         which will be able to accept and propagate the revocation to 
other more
         up-to-date directories, even though the older directories will not
         provide protection against un-revoking a hidden service if the 
attacker
         delivers an un-revocation descriptor to them directly.

         Is there a need for zero introductory point descriptors in any 
other
         case? If a hidden service previously published introductory points
         and it now no longer can be contacted at those points, and it does
         not have any new introductory points, it is unreachable. 
Publishing a
         descriptor announcing all zero of its introductory points will not
         change its reachability, though it may slightly reduce wasted 
effort by
         tor nodes attempting to reach it.]

         4.1.1 Steps required to add support

             1) If current code results in hidden services publishing zero-
             introductory point descriptors, this is blocked to prevent
             accidental revocation. I would love to get this in 0.2.6.

             2) If a modification is needed in step 1, then a grace period
             is given for hidden service operators to update their
             software. This grace period does not have to be long, we 
can move
             onto step 3 relatively fast, since the only penalty for 
accidental
             revocation step 3 would create is forcing the hidden service to
             upgrade their software, and the hidden service being 
unreachable for
             a maximum of 25 hours (lifetime of a descriptor) after the
             hidden service upgrades.

             3) Hidden service directories are modified to not allow a
             current unexpired revocation descriptor to be replaced by an
             un-revocation descriptor. Basic support for revocation is 
achieved!

             4) A long upgrade grace period is now given. The vast majority
             of hidden services should be using software which includes the
             modifications made in step 1

             5) Expanded revocation capabilities may be added, as described
             below.

     4.2 Expanded Capabilities

         4.2.1 Cache of revoked services

             A Tor node which tried to connect to a hidden service in 
the past
             and discovered that the service was revoked should remember 
that
             revocation and refuse to connect indefinitely, even if the
             revocation ceases to be broadcast in the future.

         4.2.2 Presentation to the user

             If an onion proxy that detects the user tried to visit a 
revoked
             service, this information should be presented to the user
             out-of-band. I.E not in a way that could be mistaken for a 
hidden
             service which is only temporarily unreachable, or as 
information
             sent by the service. This could be done via a system level 
popup, or
             a taskbar notification. The presentation should be strongly
             distinguished from a hidden service which is simple 
unreachable.

         4.2.3 Automatic hijacking detection/revocation

             Tor hidden service software could have a mode to detect if 
another
             party is using the hidden service private key to publish 
descriptors
             for that service. If the hidden service operator configures it,
             the Tor hidden service software could immediately begin to 
broadcast
             the revocation for that service.

5. Future Compatibility with Next Generation Hidden Services

     Next generation Tor hidden services require a modified
     revocation system because the hidden service master secret key is 
better
     protected, and does not need to live online on the hidden service 
tor node.
     The day-to-day operation of the service is carried out by a 
pre-loaded set
     of changing subordinate descriptor signing keys, which expire after 
a set
     time (25 hours by default). If descriptor signing keys are compromised,
     they can be used to hijack traffic and impersonate the hidden service,
     but only until the descriptor signing keys expire. So there is a need
     for a way to revoke descriptor signing keys and provide new ones, 
but not to
     permanently revoke trust in the hidden service.

     Also, theft of descriptor signing keys should not allow an attacker to
     revoke the master secret key.

     The revocation permissions would looks something like the following.
     (Blinded signing keys are equivalent to the master secret key for
     revocation purposes because an attacker which obtains any blinded 
signing
     secret key can easily derive the master secret key.)

     1) Current descriptor signing key can revoke current descriptor 
signing key.

     2) Master secret key can revoke any descriptor signing key and 
provide a new
     descriptor signing key for that time-period.

     3) Master secret key is the only one that can revoke master secret key.

     5.1 Descriptor Signing Keys Revoking Themselves

         [TODO: Finish later]

     5.1 Master Secret Key Revoking and Replacing Descriptor Signing Keys

         [TODO: Finish later]

     5.2 Master Secret Key Revoking Itself

         [TODO: Finish later]