Design a PoW scheme for HS DoS defence

Some initial research has been done on comment:13:ticket:31223 to sketch out a PoW/credential scheme that works for HS DoS defence.

This ticket is to continue scheming and working on this design.

See https://lists.torproject.org/pipermail/tor-dev/2020-April/014215.html for initial proposal.

changed milestone to %Tor: unspecified in legacy/trac

Trac:
Parent Ticket: legacy/trac#31223 (moved)
Child Ticket(s): legacy/trac#33650 (moved), legacy/trac#33843 (moved), legacy/trac#33844 (moved)

added component::core tor/tor in Legacy / Trac milestone::Tor: unspecified in Legacy / Trac network-health in Legacy / Trac network-team-roadmap-2020Q2 in Legacy / Trac parent::31223 in Legacy / Trac points::96 in Legacy / Trac priority::medium in Legacy / Trac research in Legacy / Trac severity::normal in Legacy / Trac status::new in Legacy / Trac tor-dos in Legacy / Trac tor-hs in Legacy / Trac type::defect in Legacy / Trac labels

Trac:
Description: Some initial research has been done on legacy/trac#31223 (moved) to sketch out a PoW/credential scheme that works for HS DoS defence.

This ticket is to continue scheming and working on this design.

Also see legacy/trac#33650 (moved) for an analysis on whether we can use v3 descriptors and INTRO cells as an end-to-end channel for passing parameters and tokens.

Also see this thread for an initial exploration of anon credential schemes.

to

Some initial research has been done on comment:13:ticket:31223 to sketch out a PoW/credential scheme that works for HS DoS defence.

This ticket is to continue scheming and working on this design.

Also see legacy/trac#33650 (moved) for an analysis on whether we can use v3 descriptors and INTRO cells as an end-to-end channel for passing parameters and tokens.

Also see this thread for an initial exploration of anon credential schemes.

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 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.

---

I wanted to mention this strawman proposal as a basic building block after reading that mtp-argon2 type of protocols require way too much space for proving. I was wondering if the above strawman approach but using argon2 as the hash function for memory-hardness would work for us, but then I understood that the space requirement is caused by using a merkle tree as part of enforcing the memory-hardness; as in that argon2 itself is not sufficient to enforce full memory-hardness.

So how do we go from a simple PoW scheme like the above, to something that works for us? Is it just the memory-hardness that we are losing by using the strawman approach over a more hardcore mtp-argon2 approach?

Replying to 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 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.

TL;DR of above is that there are multiple classes of protocol changes, and I think we should decide our high-level preference for what order we want to attempt them.

Here's a strawman ordering of the combination of (degree of network upgrade required, external infra required) pairs:

1. No network upgrade required; no external infra deployment (ie: client and service only)
2. Backportable network upgrade required; no external infra deployment.
3. No network upgrade required; external infra deployment is required.
4. Backportable network upgrade required, external infra deployment is required.
5. Non-backportable IP upgrade required; no external infra deployment.
6. Non-backportable IP upgrade required; external infra deployment is required
7. Non-backportable full network upgrade; no external infra deployment.
8. Non-backportable full network upgrade; external infra deployment is required

Quick example of 1: Smuggle PoW inside a single INTRO1 cell Quick example of 8: New wide-cell larger than 512 bytes to send a big anonymous credential provided by a captcha server.

Important questions to answer:

• Does this ordering sound right in terms of what we should prefer/attempt to build first?
• Does anyone want to propose a different ordering?
• What sorts of changes are backportable for this problem?

I think I arrive at the same conclusions as Mike, but for different reasons.

To me, the reason to focus on the "client to service" defense is that I believe whatever design we pick is going to need to have a "client to service" component, i.e. I don't think we can solve this problem solely with a "client to intro point" component. So if we need client-to-service, let's try to construct a system where that is sufficient.

I'm not much worried about time-to-upgrade. Let's think about the eventual result we want, and then get ourselves there. A few months for upgrades will pass before we know it, and if we have an important update that needs more relays to upgrade, we can ask them to do it.

Or, to rephrase: I currently think that client-to-service is the right area to focus on, because we're going to need it for the eventual solution, not because we have to constrain ourselves to solutions we can deploy this week. If we have a solution we like that involves parts of the network upgrading, let's be sure to keep it on the table so we don't accidentally rule out our best future just because it would be more logistics work to get there.

Trac:
Keywords: network-team-roadmap-2020Q1 deleted, network-team-roadmap-2020Q2 added

Trac:
Points: N/A to 96

First iteration of proposal: https://lists.torproject.org/pipermail/tor-dev/2020-April/014215.html

Trac:
Description: Some initial research has been done on comment:13:ticket:31223 to sketch out a PoW/credential scheme that works for HS DoS defence.

This ticket is to continue scheming and working on this design.

Also see legacy/trac#33650 (moved) for an analysis on whether we can use v3 descriptors and INTRO cells as an end-to-end channel for passing parameters and tokens.

Also see this thread for an initial exploration of anon credential schemes.

to

Some initial research has been done on comment:13:ticket:31223 to sketch out a PoW/credential scheme that works for HS DoS defence.

This ticket is to continue scheming and working on this design.

See https://lists.torproject.org/pipermail/tor-dev/2020-April/014215.html for initial proposal.
Summary: Design a PoW/credential scheme for HS DoS defence to Design a PoW scheme for HS DoS defence

changed time estimate to 768h

mentioned in issue legacy/trac#31223 (moved)

mentioned in issue legacy/trac#33650 (moved)

mentioned in issue legacy/trac#33844 (moved)

mentioned in issue legacy/trac#33843 (moved)

moved from legacy/trac#33712 (moved)

added Backlog label

removed 1 deleted label

added Bug label and removed 1 deleted label

added Research + 1 deleted label and removed 1 deleted label

mentioned in issue #40016 (closed)

added Doing label

assigned to @asn

added Next label and removed Backlog label

removed Next label

removed Bug label

removed milestone

on using tickets/tokens as a form of PoW, is it not feasible for torproject.org itself to run hcaptcha, issue/sign tokens blindly using BLS12-381, then allow relays under load to ask clients for tokens @ INTRO?

with the amount of space you have in the INTRO cell you could surely store a BLS12-381 signature and given the fancy properties mentioned here, onion servers could validate signatures signed by the torproject.org captcha service (if one existed).

Yep it should be feasible indeed. Also see https://blog.torproject.org/stop-the-onion-denial Thanks for your comment!

added Network health label and removed 1 deleted label

removed Doing label

added Icebox label

Some notes from last call:

• Figure out how client retries should work in the little-t-tor codebase.
• Should blake2b actually be used, or can we swap it with something else?

unassigned @asn

added Onion Services label and removed 1 deleted label

added Triage2022 label

closed

moved to torspec#134 (closed)

added DoS label and removed 1 deleted label