[tor-dev] [RFC] Proposal: A First Take at PoW Over Introduction Circuits
George Kadianakis
desnacked at riseup.net
Wed Jun 10 12:05:08 UTC 2020
Hello,
after reading all the excellent feedback on this thread, I did another
revision on this proposal:
https://github.com/asn-d6/torspec/tree/pow-over-intro
I'm inlining the full proposal in the end of this email.
Here is a changelog:
- Improve attack vector section
- Shrink nonce size on cells to 16 bytes
- Change effort definition to linear
Here is a few things I did not do and might need some help with:
- I did not decide on the PoW function. I think to do this we miss the
scheduler number crunching from dgoulet, and also I need to understand the
possible options a bit more. I removed most references to argon2 and replaced
them with XXX_POW.
Tevador, thanks a lot for your tailored work on equix. This is fantastic. I
have a question that I don't see addressed in your very well written
README. In your initial email, we discuss how Equihash does not have good GPU
resistance:
https://lists.torproject.org/pipermail/tor-dev/2020-May/014268.html
Since equix is using Equihash isn't this gonna be a problem here too? I'm not
too worried about ASIC resistance since I doubt someone is gonna build ASICs
for this problem just yet, but script kiddies with their CS:GO graphics cards
attacking equix is something I'm concerned about. I bet you have thought of
this, so I'm wondering what's your take here.
Right now I think the possible options are equix or the reduced Randomx
(again thanks tevador) or yespower. In theory we could do all three of them
and just support different versions; but that means more engineering.
In any case, we are also waiting for some Tor-specific numbers from dgoulet,
so we need those before we proceed here.
- In their initial mail, tevador points out an attack where the adversary games
the effort estimation logic, by pausing an attack a minute before descriptor
upload, so that the final descriptor has a very small target effort. They
suggest using the median effort over a long period of time to fix this. Mike,
can you check that out and see how we can adapt our logic to fix this?
- In tevador's initial mail, they point how the cell should include POW_EFFORT
and that we should specify a "minimum effort" value instead of just inserting
any effort in the pqueue. I can understand how this can have benefits (like
the June discussion between tevador and yoehoduv) but I'm also concerned that
this can make us more vulnerable to [ATTACK_BOTTOM_HALF] types of attacks, by
completely dropping introduction requests instead of queueing them for an
abstract future. I wouldn't be surprised if my concerns are invalid and
harmful here. Does anyone have intuition?
- tevador suggests we use two seeds, and always accept introductions with the
previous seed. I agree this is a good idea, and it's not as complex as I
originally thought (I have trauma from the v3 design where we try to support
multiple time periods at the same time). However, because this doubles the
vefication time, I decided to wait for dgoulet's scheduler numbers and until
the PoW function is finalized to understand if we can afford the verification
overhead.
- Solar Designer suggested we do Ethash's anti-DDoS trick to avoid instances of
[ATTACK_TOP_HALF]. This involves wrapping the final PoW token in a fast hash
with a really low difficulty, and having the verifier check that fast hash
POW first. This means that a target trying to flood us with invalid PoW would
need to do some work for every PoW instead of it being free. This is a
decision we should take at the end after we do some number crunching and see
where we are at in terms of verification time and attack models.
Thanks a lot! :)
---
Filename: xxx-pow-over-intro-v1
Title: A First Take at PoW Over Introduction Circuits
Author: George Kadianakis, Mike Perry, David Goulet
Created: 2 April 2020
Status: Draft
0. Abstract
This proposal aims to thwart introduction flooding DoS attacks by introducing
a dynamic Proof-Of-Work protocol that occurs over introduction circuits.
1. Motivation
So far our attempts at limiting the impact of introduction flooding DoS
attacks on onion services has been focused on horizontal scaling with
Onionbalance, optimizing the CPU usage of Tor and applying congestion control
using rate limiting. While these measures move the goalpost forward, a core
problem with onion service DoS is that building rendezvous circuits is a
costly procedure both for the service and for the network. For more
information on the limitations of rate-limiting when defending against DDoS,
see [REF_TLS_1].
If we ever hope to have truly reachable global onion services, we need to
make it harder for attackers to overload the service with introduction
requests. This proposal achieves this by allowing onion services to specify
an optional dynamic proof-of-work scheme that its clients need to participate
in if they want to get served.
With the right parameters, this proof-of-work scheme acts as a gatekeeper to
block amplification attacks by attackers while letting legitimate clients
through.
1.1. Related work
For a similar concept, see the three internet drafts that have been proposed
for defending against TLS-based DDoS attacks using client puzzles [REF_TLS].
1.2. Threat model [THREAT_MODEL]
1.2.1. Attacker profiles [ATTACKER_MODEL]
This proposal is written to thwart specific attackers. A simple PoW proposal
cannot defend against all and every DoS attack on the Internet, but there are
adverary models we can defend against.
Let's start with some adversary profiles:
"The script-kiddie"
The script-kiddie has a single computer and pushes it to its
limits. Perhaps it also has a VPS and a pwned server. We are talking about
an attacker with total access to 10 Ghz of CPU and 10 GBs of RAM. We
consider the total cost for this attacker to be zero $.
"The small botnet"
The small botnet is a bunch of computers lined up to do an introduction
flooding attack. Assuming 500 medium-range computers, we are talking about
an attacker with total access to 10 Thz of CPU and 10 TB of RAM. We consider
the upfront cost for this attacker to be about $400.
"The large botnet"
The large botnet is a serious operation with many thousands of computers
organized to do this attack. Assuming 100k medium-range computers, we are
talking about an attacker with total access to 200 Thz of CPU and 200 TB of
RAM. The upfront cost for this attacker is about $36k.
We hope that this proposal can help us defend against the script-kiddie
attacker and small botnets. To defend against a large botnet we would need
more tools in our disposal (see [FUTURE_DESIGNS]).
{XXX: Do the above make sense? What other attackers do we care about? What
other metrics do we care about? Network speed? I got the botnet costs
from here [REF_BOTNET] Back up our claims of defence.}
1.2.2. User profiles [USER_MODEL]
We have attackers and we have users. Here are a few user profiles:
"The standard web user"
This is a standard laptop/desktop user who is trying to browse the
web. They don't know how these defences work and they don't care to
configure or tweak them. They are gonna use the default values and if the
site doesn't load, they are gonna close their browser and be sad at Tor.
They run a 2Ghz computer with 4GB of RAM.
"The motivated user"
This is a user that really wants to reach their destination. They don't
care about the journey; they just want to get there. They know what's going
on; they are willing to tweak the default values and make their computer do
expensive multi-minute PoW computations to get where they want to be.
"The mobile user"
This is a motivated user on a mobile phone. Even tho they want to read the
news article, they don't have much leeway on stressing their machine to do
more computation.
We hope that this proposal will allow the motivated user to always connect
where they want to connect to, and also give more chances to the other user
groups to reach the destination.
1.2.3. The DoS Catch-22 [CATCH22]
This proposal is not perfect and it does not cover all the use cases. Still,
we think that by covering some use cases and giving reachability to the
people who really need it, we will severely demotivate the attackers from
continuing the DoS attacks and hence stop the DoS threat all
together. Furthermore, by increasing the cost to launch a DoS attack, a big
class of DoS attackers will disappear from the map, since the expected ROI
will decrease.
2. System Overview
2.1. Tor protocol overview
+----------------------------------+
| |
+-------+ INTRO1 +-----------+ INTRO2 +--------+ |
|Client |-------->|Intro Point|------->| PoW |-----------+ |
+-------+ +-----------+ |Verifier| | |
+--------+ | |
| | |
| | |
| +----------v---------+ |
| |Intro Priority Queue| |
+---------+--------------------+---+
| | |
Rendezvous | | |
circuits | | |
v v v
The proof-of-work scheme specified in this proposal takes place during the
introduction phase of the onion service protocol.
The system described in this proposal is not meant to be on all the time, and
should only be enabled by services when under duress. The percentage of
clients receiving puzzles can also be configured based on the load of the
service.
In summary, the following steps are taken for the protocol to complete:
1) Service encodes PoW parameters in descriptor [DESC_POW]
2) Client fetches descriptor and computes PoW [CLIENT_POW]
3) Client completes PoW and sends results in INTRO1 cell [INTRO1_POW]
4) Service verifies PoW and queues introduction based on PoW effort [SERVICE_VERIFY]
2.2. Proof-of-work overview
2.2.1. Primitives
For our proof-of-work scheme we want to minimize the spread of resources
between a motivated attacker and legitimate clients. This means that we are
looking to minimize any benefits that GPUs or ACICs can offer to an attacker.
For this reason we chose XXX_POW
2.2.2. Dynamic PoW
DoS is a dynamic problem where the attacker's capabilities constantly change,
and hence we want our proof-of-work system to be dynamic and not stuck with a
static difficulty setting. Hence, instead of forcing clients to go below a
static target like in Bitcoin to be successful, we ask clients to "bid" using
their PoW effort. Effectively, a client gets higher priority the higher
effort they put into their proof-of-work. This is similar to how
proof-of-stake works but instead of staking coins, you stake work.
The benefit here is that legitimate clients who really care about getting
access can spend a big amount of effort into their PoW computation, which
should guarantee access to the service given reasonable adversary models. See
[PARAM_TUNING] for more details about these guarantees and tradeoffs.
As a way to improve reachability and UX, the service tries to estimate the
effort needed for clients to get access at any given time and places it in
the descriptor. See [EFFORT_ESTIMATION] for more details.
2.2.3. PoW effort
For our dynamic PoW system to work, we will need to be able to compare PoW
tokens with each other. To do so we define a function:
unsigned effort(uint8_t *token)
which takes as its argument a hash output token, interprets it as a
bitstring, and returns the quotient of dividing a bitstring of 1s by it.
So for example:
effort(00000001100010101101) = 11111111111111111111 / 00000001100010101101
or the same in decimal:
effort(6317) = 1048575 / 6317 = 165.
This definition of effort has the advantage of directly expressing the
expected number of hashes that the client had to calculate to reach the
effort. This is in contrast to the (cheaper) exponential effort definition of
taking the number of leading zero bits.
3. Protocol specification
3.1. Service encodes PoW parameters in descriptor [DESC_POW]
This whole protocol starts with the service encoding the PoW parameters in
the 'encrypted' (inner) part of the v3 descriptor. As follows:
"pow-params" SP type SP seed-b64 SP expiration-time NL
[At most once]
type: The type of PoW system used. We call the one specified here "v1"
seed-b64: A random seed that should be used as the input to the PoW
hash function. Should be 32 random bytes encoded in base64
without trailing padding.
suggested-effort: An unsigned integer specifying an effort value that
clients should aim for when contacting the service. See
[EFFORT_ESTIMATION] for more details here.
expiration-time: A timestamp in "YYYY-MM-DD SP HH:MM:SS" format after
which the above seed expires and is no longer valid as
the input for PoW. It's needed so that the size of our
replay cache does not grow infinitely. It should be
set to three hours in the future (+- some randomness).
{TODO: PARAM_TUNING}
{XXX: Expiration time makes us even more susceptible to clock skews, but
it's needed so that our replay cache refreshes. How to fix this?
See [CLIENT_BEHAVIOR] for more details.}
3.2. Client fetches descriptor and computes PoW [CLIENT_POW]
If a client receives a descriptor with "pow-params", it should assume that
the service is expecting a PoW input as part of the introduction protocol.
The client parses the descriptor and extracts the PoW parameters. It makes
sure that the <expiration-time> has not expired and if it has, it needs to
fetch a new descriptor.
The client should then extract the <suggested-effort> field to configure its
PoW 'target' (see [REF_TARGET]). The client SHOULD NOT accept 'target' values
that will cause an infinite PoW computation. {XXX: How to enforce this?}
To complete the PoW the client follows the following logic:
a) Client generates 'nonce' as 16 random bytes.
b) Client derives 'seed' by decoding 'seed-b64'.
c) Client derives 'labeled_seed = seed + "TorV1PoW"'
d) Client computes hash_output = XXX_POW(labeled_seed, nonce)
e) Client checks if effort(hash_output) >= target.
e1) If yes, success! The client uses 'hash_output' as the puzzle
solution and 'nonce' and 'seed' as its inputs.
e2) If no, fail! The client interprets 'nonce' as a big-endian integer,
increments it by one, and goes back to step (d).
At the end of the above procedure, the client should have a triplet
(hash_output, seed, nonce) that can be used as the answer to the PoW
puzzle. How quickly this happens depends solely on the 'target' parameter.
3.3. Client sends PoW in INTRO1 cell [INTRO1_POW]
Now that the client has an answer to the puzzle it's time to encode it into
an INTRODUCE1 cell. To do so the client adds an extension to the encrypted
portion of the INTRODUCE1 cell by using the EXTENSIONS field (see
[PROCESS_INTRO2] section in rend-spec-v3.txt). The encrypted portion of the
INTRODUCE1 cell only gets read by the onion service and is ignored by the
introduction point.
We propose a new EXT_FIELD_TYPE value:
[01] -- PROOF_OF_WORK
The EXT_FIELD content format is:
POW_VERSION [1 byte]
POW_NONCE [16 bytes]
where:
POW_VERSION is 1 for the protocol specified in this proposal
POW_NONCE is 'nonce' from the section above
This will increase the INTRODUCE1 payload size by 19 bytes since the
extension type and length is 2 extra bytes, the N_EXTENSIONS field is always
present and currently set to 0 and the EXT_FIELD is 17 bytes. According to
ticket #33650, INTRODUCE1 cells currently have more than 200 bytes
available.
3.4. Service verifies PoW and handles the introduction [SERVICE_VERIFY]
When a service receives an INTRODUCE1 with the PROOF_OF_WORK extension, it
should check its configuration on whether proof-of-work is required to
complete the introduction. If it's not required, the extension SHOULD BE
ignored. If it is required, the service follows the procedure detailed in
this section.
If the service requires the PROOF_OF_WORK extension but received an
INTRODUCE1 cell without any embedded proof-of-work, the service SHOULD
consider this cell as a zero-effort introduction for the purposes of the
priority queue (see section [INTRO_QUEUE]).
3.4.1. PoW verification [POW_VERIFY]
To verify the client's proof-of-work the service extracts (hash_output,
seed, nonce) from the INTRODUCE1 cell and MUST do the following steps:
1) Make sure that the client's seed is identical to the active seed.
2) Check the client's nonce for replays (see [REPLAY_PROTECTION] section).
3) Verify that 'hash_output =?= XXX_POW(seed, nonce)
If any of these steps fail the service MUST ignore this introduction request
and abort the protocol.
In this proposal we call the above steps the "top half" of introduction
handling. If all the steps of the "top half" have passed, then the circuit
is added to the introduction queue as detailed in section [INTRO_QUEUE].
3.4.1.1. Replay protection [REPLAY_PROTECTION]
The service MUST NOT accept introduction requests with the same (seed, nonce)
tuple. For this reason a replay protection mechanism must be employed.
The simplest way is to use a simple hash table to check whether a (seed,
nonce) tuple has been used before for the actiev duration of a
seed. Depending on how long a seed stays active this might be a viable
solution with reasonable memory/time overhead.
If there is a worry that we might get too many introductions during the
lifetime of a seed, we can use a Bloom filter as our replay cache
mechanism. The probabilistic nature of Bloom filters means that sometimes we
will flag some connections as replays even if they are not; with this false
positive probability increasing as the number of entries increase. However,
with the right parameter tuning this probability should be negligible and
well handled by clients. {TODO: PARAM_TUNING}
3.4.2. The Introduction Queue [INTRO_QUEUE]
3.4.2.1. Adding introductions to the introduction queue [ADD_QUEUE]
When PoW is enabled and a verified introduction comes through, the service
instead of jumping straight into rendezvous, queues it and prioritizes it
based on how much effort was devoted by the client to PoW. This means that
introduction requests with high effort should be prioritized over those with
low effort.
To do so, the service maintains an "introduction priority queue" data
structure. Each element in that priority queue is an introduction request,
and its priority is the effort put into its PoW:
When a verified introduction comes through, the service uses the effort()
function with hash_output as its input, and uses the output to place requests
into the right position of the priority_queue: The bigger the effort, the
more priority it gets in the queue. If two elements have the same effort, the
older one has priority over the newer one.
{TODO: PARAM_TUNING: If the priority queue is only ordered based on the
effort what attacks can happen in various scenarios? Do we want to order on
time+effort? Which scenarios and attackers should we examine here?}
3.4.2.2. Handling introductions from the introduction queue [HANDLE_QUEUE]
The service should handle introductions by pulling from the introduction
queue. We call this part of introduction handling the "bottom half" because
most of the computation happens in this stage.
Similar to how our cell scheduler works, the onion service subsystem will
poll the priority queue every 100ms tick and process the first 20 cells from
the priority queue (if they exist). The service will perform the rendezvous
and the rest of the onion service protocol as normal.
With this tempo, we can process 200 introduction cells per second.
{XXX: Is this good?}
After the introduction request is handled from the queue, the service trims
the priority queue if the queue is too big.
{TODO: PARAM_TUNING: What's the max size of the queue? How do we trim it? Can
we use WRED usefully?}
{TODO: PARAM_TUNING: STRAWMAN: This needs hella tuning. Processing 20 cells
per 100ms is probably unmaintainable, since each cell is quite expensive:
doing so involving path selection, crypto and making circuits. We will need
to profile this procedure and see how we can do this scheduling better.}
3.4.3. PoW effort estimation [EFFORT_ESTIMATION]
During its operation the service continuously keeps track of the received PoW
cell efforts to inform its clients of the effort they should put in their
introduction to get service. The service informs the clients by using the
<suggested-effort> field in the descriptor.
In particular, the service starts with a default suggested-effort value of 5000.
Everytime the service handles an introduction request from the priority queue
in [HANDLE_QUEUE], the service compares the request's effort to the current
suggested-effort value. If the new request's effort is lower than the
suggested-effort, set the suggested-effort equal to the effort of the new
request.
{XXX tevador attack: see their email
https://lists.torproject.org/pipermail/tor-dev/2020-May/014268.html
where it says "Secondly, the proposed method of calculating..."
They suggest using the median here and their "pause-before-desc-publish"
attack seems legit.}
Everytime the service trims the priority queue in [HANDLE_QUEUE], the service
compares the request at the trim point against the current suggested-effort
value. If the trimmed request's effort is higher than the suggested-effort,
set the suggested-effort equal to the effort of the new request.
The above two operations are meant to balance the suggested effort based on
the requests currently waiting in the priority queue. If the priority queue
is filled with high-effort requests, make the suggested effort higher. And
when all the high-effort requests get handled and the priority queue is back
to normal operation, relax the suggested effort to lower levels.
The suggested-effort is not a hard limit to the efforts that are accepted by
the service, and it's only meant to serve as a guideline for clients to
reduce the number of unsuccessful requests that get to the service. The
service still adds requests with lower effort than suggested-effort to the
priority queue in [ADD_QUEUE].
{XXX: What attacks are possible here?}
3.4.3.1. Updating descriptor with new suggested effort
When a service changes its suggested-effort value, it SHOULD upload a new
descriptor with the new value.
The service should avoid uploading descriptors too often to avoid overwheming
the HSDirs. The service SHOULD NOT upload descriptors more often than
'hs-pow-desc-upload-rate-limit' seconds (which is controlled through a
consensus parameter and has a default value of 300 seconds).
{XXX: Is this too often? Or too rare? Perhaps we can set different limits
for when the difficulty goes up and different for when it goes down. It's
more important to update the descriptor when the difficulty goes up.}
{XXX: What attacks are possible here? Can the attacker intentionally hit this
rate-limit and then influence the suggested effort so that clients do not
learn about the new effort?}
4. Client behavior [CLIENT_BEHAVIOR]
This proposal introduces a bunch of new ways where a legitimate client can
fail to reach the onion service.
Furthermore, there is currently no end-to-end way for the onion service to
inform the client that the introduction failed. The INTRO_ACK cell is not
end-to-end (it's from the introduction point to the client) and hence it does
not allow the service to inform the client that the rendezvous is never gonna
occur.
For this reason we need to define some client behaviors to work around these
issues.
4.1. Clients handling timeouts [CLIENT_TIMEOUT]
Alice can fail to reach the onion service if her introduction request gets
trimmed off the priority queue in [HANDLE_QUEUE], or if the service does not
get through its priority queue in time and the connection times out.
{XXX: How should timeout values change here since the priority queue will
cause bigger delays than usual to rendezvous?}
This section presents a heuristic method for the client getting service even
in such scenarios.
If the rendezvous request times out, the client SHOULD fetch a new descriptor
for the service to make sure that it's using the right suggested-effort for
the PoW and the right PoW seed. The client SHOULD NOT fetch service
descriptors more often than every 'hs-pow-desc-fetch-rate-limit' seconds
(which is controlled through a consensus parameter and has a default value of
600 seconds).
{XXX: Is this too rare? Too often?}
When the client fetches a new descriptor, it should try connecting to the
service with the new suggested-effort and PoW seed. If that doesn't work, it
should double the effort and retry. The client should keep on
doubling-and-retrying until it manages to get service, or its able to fetch a
new descriptor again.
{XXX: This means that the client will keep on spinning and
doubling-and-retrying for a service under this situation. There will never be
a "Client connection timed out" page for the user. Is this good? Is this bad?
Should we stop doubling-and-retrying after some iterations? Or should we
throw a custom error page to the user, and ask the user to stop spinning
whenever they want?}
4.2. Seed expiration issues
As mentioned in [DESC_POW], the expiration timestamp on the PoW seed can
cause issues with clock skewed clients. Furthermore, even not clock skewed
clients can encounter TOCTOU-style race conditions here.
The client descriptor refetch logic of [CLIENT_TIMEOUT] should take care of
such seed-expiration issues, since the client will refetch the descriptor.
{XXX: Is this sufficient? Should we have multiple active seeds at the same
time similar to how we have overlapping descriptors and time periods in v3?
This would solve the problem but it grows the complexity of the system
substantially.}
4.3. Other descriptor issues
Another race condition here is if the service enables PoW, while a client has
a cached descriptor. How will the client notice that PoW is needed? Does it
need to fetch a new descriptor? Should there be another feedback mechanism?
{XXX}
5. Attacker strategies [ATTACK_META]
Now that we defined our protocol we need to start tweaking the various
knobs. But before we can do that, we first need to understand a few
high-level attacker strategies to see what we are fighting against.
5.1.1. Overwhelm PoW verification (aka "Overwhelm top half") [ATTACK_TOP_HALF]
A basic attack here is the adversary spamming with bogus INTRO cells so that
the service does not have computing capacity to even verify the
proof-of-work. This adversary tries to overwhelm the procedure in the
[POW_VERIFY] section.
That's why we need the PoW algorithm to have extremely cheap verification
time so that this attack is not possible.
5.1.2. Overwhelm rendezvous capacity (aka "Overwhelm bottom half") [ATTACK_BOTTOM_HALF]
Given the way the introduction queue works (see [HANDLE_QUEUE]), a very
effective strategy for the attacker is to totally overwhelm the queue
processing by sending more high-effort introductions than the onion service
can handle at any given tick. This adversary tries to overwhelm the procedure
in the [HANDLE_QUEUE] section.
To do so, the attacker would have to send at least 20 high-effort
introduction cells every 100ms, where high-effort is a PoW which is above the
estimated level of "the motivated user" (see [USER_MODEL]).
An easier attack for the adversary, is the same strategy but with
introduction cells that are all above the comfortable level of "the standard
user" (see [USER_MODEL]). This would block out all standard users and only
allow motivated users to pass.
5.1.3. Precomputed PoW attack
The attacker may precompute many valid PoW nonces and submit them all at once
before the current seed expires, overwhelming the service temporarily even
using a single computer. An attacker with this attack might be aiming to DoS
the service for a limited amount of time, or confuse the difficulty
estimation algorithm.
6. Parameter tuning [PARAM_TUNING]
There are various parameters in this system that need to be tuned.
We will first start by tuning the default difficulty of our PoW
system. That's gonna define an expected time for attackers and clients to
succeed.
We are then gonna tune the parameters of our proof-of-work function. That will
define the resources that an attacker needs to spend to overwhelm the onion
service, the resources that the service needs to spend to verify introduction
requests, and the resources that legitimate clients need to spend to get to
the onon service.
6.1. PoW Difficulty settings
The difficulty setting of our PoW basically dictates how difficult it should
be to get a success in our PoW system. In classic PoW systems, "success" is
defined as getting a hash output below the "target". However, since our
system is dynamic, we define "success" as an abstract high-effort computation.
Even tho our system is dynamic, we still need default difficulty settings
that will define the metagame. The client and attacker can still aim higher
or lower, but for UX purposes and for analysis purposes we do need to define
some difficulties.
We hence created the table (see [REF_TABLE]) below which shows how much time
a legitimate client with a single machine should expect to burn before they
get a single success. The x-axis is how many successes we want the attacker
to be able to do per second: the more successes we allow the adversary, the
more they can overwhelm our introduction queue. The y-axis is how many
machines the adversary has in her disposal, ranging from just 5 to 1000.
===============================================================
| Expected Time (in seconds) Per Success For One Machine |
===========================================================================
| |
| Attacker Succeses 1 5 10 20 30 50 |
| per second |
| |
| 5 5 1 0 0 0 0 |
| 50 50 10 5 2 1 1 |
| 100 100 20 10 5 3 2 |
| Attacker 200 200 40 20 10 6 4 |
| Boxes 300 300 60 30 15 10 6 |
| 400 400 80 40 20 13 8 |
| 500 500 100 50 25 16 10 |
| 1000 1000 200 100 50 33 20 |
| |
============================================================================
Here is how you can read the table above:
- If an adversary has a botnet with 1000 boxes, and we want to limit her to 1
success per second, then a legitimate client with a single box should be
expected to spend 1000 seconds getting a single success.
- If an adversary has a botnet with 1000 boxes, and we want to limit her to 5
successes per second, then a legitimate client with a single box should be
expected to spend 200 seconds getting a single success.
- If an adversary has a botnet with 500 boxes, and we want to limit her to 5
successes per second, then a legitimate client with a single box should be
expected to spend 100 seconds getting a single success.
- If an adversary has access to 50 boxes, and we want to limit her to 5
successes per second, then a legitimate client with a single box should be
expected to spend 10 seconds getting a single success.
- If an adversary has access to 5 boxes, and we want to limit her to 5
successes per second, then a legitimate client with a single box should be
expected to spend 1 seconds getting a single success.
With the above table we can create some profiles for default values of our
PoW difficulty. So for example, we can use the last case as the default
parameter for Tor Browser, and then create three more profiles for more
expensive cases, scaling up to the first case which could be hardest since
the client is expected to spend 15 minutes for a single introduction.
{TODO: PARAM_TUNING You can see that this section is completely CPU/memory
agnostic, and it does not take into account potential optimizations that can
come from GPU/ASICs. This is intentional so that we don't put more variables
into this equation right now, but as this proposal moves forward we will need
to put more concrete values here.}
6.2. XXX_POW parameters [ARGON_PARAMS]
XXX_POW
We now need to define the secondary argon2 parameters as defined in
[REF_ARGON2]. This includes the number of lanes 'h', the memory size 'm', the
number of iterations 't'. Section 9 of [REF_ARGON2] recommends an approach of
how to tune these parameters.
To tune these parameters we are looking to *minimize* the verification speed
of an onion service, while *maximizing* the sparse resources spent by an
adversary trying to overwhelm the service using [ATTACK_META].
When it comes to verification speed, to verify a single introduction cell the
service needs to do a single argon2 call: so the service will need to do
hundreds of those per second as INTRODUCE2 cells arrive. The service will
have to do this verification step even for very cheap zero-effort PoW
received, so this has to be a cheap procedure so that it doesn't become a DoS
vector of each own. Hence each individual argon2 call must be cheap enough to
be able to be done comfortably and plentifuly by an onion service with a
single host (or horizontally scaled with Onionbalance).
At the same time, the adversary will have to do thousands of these calls if
she wants to make high-effort PoW, so it's this assymetry that we are looking
to exploit here. Right now, the most expensive resource for adversaries is
the RAM size, and that's why we chose argon2 which is memory-hard.
To minmax this game we will need
{TODO: PARAM_TUNING: I've had a hard time minmaxing this game for
argon2. Even argon2 invocations with a small memory parameter will take
multiple milliseconds to run on my machine, and the parameters recommended in
section 8 of the paper all take many hundreds of milliseconds. This is just
not practical for our use case, since we want to process hundreds of such PoW
per second... I also did not manage to find a benchmark of argon2 calls for
different CPU/GPU/FPGA configurations.}
7. Discussion
7.1. UX
This proposal has user facing UX consequences.
Here is some UX improvements that don't need user-input:
- Primarily, there should be a way for Tor Browser to display to users that
additional time (and resources) will be needed to access a service that is
under attack. Depending on the design of the system, it might even be
possible to estimate how much time it will take.
And here are a few UX approaches that will need user-input and have an
increasing engineering difficulty. Ideally this proposal will not need
user-input and the default behavior should work for almost all cases.
a) Tor Browser needs a "range field" which the user can use to specify how
much effort they want to spend in PoW if this ever occurs while they are
browsing. The ranges could be from "Easy" to "Difficult", or we could try
to estimate time using an average computer. This setting is in the Tor
Browser settings and users need to find it.
b) We start with a default effort setting, and then we use the new onion
errors (see #19251) to estimate when an onion service connection has
failed because of DoS, and only then we present the user a "range field"
which they can set dynamically. Detecting when an onion service connection
has failed because of DoS can be hard because of the lack of feedback (see
[CLIENT_BEHAVIOR])
c) We start with a default effort setting, and if things fail we
automatically try to figure out an effort setting that will work for the
user by doing some trial-and-error connections with different effort
values. Until the connection succeeds we present a "Service is
overwhelmed, please wait" message to the user.
7.2. Future work [FUTURE_WORK]
7.2.1. Incremental improvements to this proposal
There are various improvements that can be done in this proposal, and while
we are trying to keep this v1 version simple, we need to keep the design
extensible so that we build more features into it. In particular:
- End-to-end introduction ACKs
This proposal suffers from various UX issues because there is no end-to-end
mechanism for an onion service to inform the client about its introduction
request. If we had end-to-end introduction ACKs many of the problems from
[CLIENT_BEHAVIOR] would be aleviated. The problem here is that end-to-end
ACKs require modifications on the introduction point code and a network
update which is a lengthy process.
- Multithreading scheduler
Our scheduler is pretty limited by the fact that Tor has a single-threaded
design. If we improve our multithreading support we could handle a much
greater amount of introduction requests per second.
7.2.2. Future designs [FUTURE_DESIGNS]
This is just the beginning in DoS defences for Tor and there are various
futured designs and schemes that we can investigate. Here is a brief summary
of these:
"More advanced PoW schemes" -- We could use more advanced memory-hard PoW
schemes like MTP-argon2 or Itsuku to make it even harder for
adversaries to create successful PoWs. Unfortunately these schemes
have much bigger proof sizes, and they won't fit in INTRODUCE1 cells.
See #31223 for more details.
"Third-party anonymous credentials" -- We can use anonymous credentials and a
third-party token issuance server on the clearnet to issue tokens
based on PoW or CAPTCHA and then use those tokens to get access to the
service. See [REF_CREDS] for more details.
"PoW + Anonymous Credentials" -- We can make a hybrid of the above ideas
where we present a hard puzzle to the user when connecting to the
onion service, and if they solve it we then give the user a bunch of
anonymous tokens that can be used in the future. This can all happen
between the client and the service without a need for a third party.
All of the above approaches are much more complicated than this proposal, and
hence we want to start easy before we get into more serious projects.
7.3. Environment
We love the environment! We are concerned of how PoW schemes can waste energy
by doing useless hash iterations. Here is a few reasons we still decided to
pursue a PoW approach here:
"We are not making things worse" -- DoS attacks are already happening and
attackers are already burning energy to carry them out both on the
attacker side, on the service side and on the network side. We think that
asking legitimate clients to carry out PoW computations is not gonna
affect the equation too much, since an attacker right now can very
quickly cause the same damage that hundreds of legitimate clients do a
whole day.
"We hope to make things better" -- The hope is that proposals like this will
make the DoS actors go away and hence the PoW system will not be used. As
long as DoS is happening there will be a waste of energy, but if we
manage to demotivate them with technical means, the network as a whole
will less wasteful. Also see [CATCH22] for a similar argument.
8. Acknowledgements
Thanks a lot to tevador for the various improvements to the proposal and for
helping us understand and tweak the RandomX scheme.
Thanks to Solar Designer for the help in understanding the current PoW
landscape, the various approaches we could take, and teaching us a few neat
tricks.
9. References
[REF_ARGON2]: https://github.com/P-H-C/phc-winner-argon2/blob/master/argon2-specs.pdf
https://password-hashing.net/#argon2
[REF_TABLE]: The table is based on the script below plus some manual editing for readability:
https://gist.github.com/asn-d6/99a936b0467b0cef88a677baaf0bbd04
[REF_BOTNET]: https://media.kasperskycontenthub.com/wp-content/uploads/sites/43/2009/07/01121538/ynam_botnets_0907_en.pdf
[REF_CREDS]: https://lists.torproject.org/pipermail/tor-dev/2020-March/014198.html
[REF_TARGET]: https://en.bitcoin.it/wiki/Target
[REF_TLS]: https://www.ietf.org/archive/id/draft-nygren-tls-client-puzzles-02.txt
https://tools.ietf.org/id/draft-nir-tls-puzzles-00.html
https://tools.ietf.org/html/draft-ietf-ipsecme-ddos-protection-10
[REF_TLS_1]: https://www.ietf.org/archive/id/draft-nygren-tls-client-puzzles-02.txt
More information about the tor-dev
mailing list