[tor-bugs] #33712 [Core Tor/Tor]: Design a PoW/credential scheme for HS DoS defence

[Tor Bug Tracker & Wiki]

#33712: Design a PoW/credential scheme for HS DoS defence
-------------------------------------------------+-------------------------
 Reporter:  asn                                  |          Owner:  (none)
     Type:  defect                               |         Status:  new
 Priority:  Medium                               |      Milestone:  Tor:
                                                 |  unspecified
Component:  Core Tor/Tor                         |        Version:
 Severity:  Normal                               |     Resolution:
 Keywords:  tor-hs, tor-dos, network-team-       |  Actual Points:
  roadmap-2020Q1, network-health, research       |
Parent ID:  #31223                               |         Points:
 Reviewer:                                       |        Sponsor:
-------------------------------------------------+-------------------------

Comment (by mikeperry):

 Replying to [comment:2 asn]:
 > The strawman proposal of a basic PoW-over-INTRO scheme is:
 >
 > 1) Client sends INTRO1 with a special PoW extension
 > 2) Intro sends back INTRO_CHALLENGE to client with a nonce
 > 3) Client crafts PoW with that nonce and sends it back to client
 > 4) Intro validates PoW difficulty and either forwards intro to service
 or rejects.
 >
 > This can come with various variants like the service encoding the nonce
 and parameters [https://lists.torproject.org/pipermail/tor-
 dev/2019-June/013882.html in the descriptor] in an attempt to cut the
 challenge round trip (with extra complexity coming from replay detection
 etc.), or with clients doing PoW bidding (or "staking") as proposed in the
 recent call.

 The above protocol sketch requires that the service only choose
 intropoints that have upgraded to fully support the protocol. This is
 risky, and still will require requires at least several months to deploy.
 Possibly much longer, if we are nervous about only a few IPs being
 available for use at a time by services under attack.

 I think it is most important that we separate our protocols by how much
 network upgrade (and/or external infra) is required before they can be
 used.

 To this end, here are some variants that we should keep in mind that
 require no network upgrades, or less extensive ones.

 Service-as-validator (requires no IP upgrades):

 0. Descriptor lists a challenge input seed, updated every X minutes or
 every Y intros
 1. Client generates its own GUID challenge to combine with descriptor seed
 2. Client sends INTRO1 with PoW extension in **encrypted extension
 section**, in 253 bytes
 3. Service verifies client's GUID is unique since its last descriptor seed
 update
 4. Service itself verifies PoW (which is supposed to be fast)
 5. Service then builds rend if PoW passes (and drops otherwise)

 Now, at 253 bytes, we lose most or all memory hardness guarantees of the
 PoW, but it can still be computationally expensive and possibly also GPU-
 resistant.

 One minor variant that also requires no network upgrades is to use an
 external credential server that accepts a full memory-hard 11KB Itsuku PoW
 and gives out smaller privacy pass credentials that can be sent directly
 to service in the encrypted extension, which verifies the privacy pass
 credential. This also requires no network upgrades, but the external
 credential server must be built and deployed, and will be subject to DoS
 attack too.

 If we expand scope slightly to allow intropoint upgrades that are minimal
 enough to backport to all releases, we can remove the "1 intro1 cell per
 circuit" limit at the intropoint if rate limits are requested by the
 service (this is roughly a 3 line diff). Then, schemes like the following
 become possible:

 0. Descriptor lists a challenge input seed, updated every X minutes or
 every Y intros
 1. Client generates its own GUID challenge to combine with descriptor seed
 2. Client sends INTRO1 with "multi-cell" extension in **encrypted
 extension section**
 3. Client sends Itsuku proof (<11KB, since we don't need that much) over
 subsequent cells
 4. Service combines these chained INTROs to reassemble PoW
 5. Service verifies client's GUID is unique since its last descriptor seed
 update
 6. Service itself verifies PoW (which is supposed to be fast)
 7. Service then builds rend if PoW passes (and drops otherwise)

 Because the change to allow protocols like this is small, hopefully we can
 backport it and deploy it to the network much, much faster than a full
 release cycle. If we can't do that, we should rule out this class of
 protocol.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/33712#comment:3>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online