[tor-dev] Proposal for PoW DoS defenses during introduction (was Re: Proposal 305: ESTABLISH_INTRO Cell DoS Defense Extension)

[George Kadianakis]

juanjo <juanjo at avanix.es> writes:

> On 13/6/19 12:21, George Kadianakis wrote:
>> Is this a new cell? What's the format? Are these really keys or are they
>> just nonces?
>
> Yes sorry, they are nonces.
>
>
> This was only a proposal for a proposal.
>
>> Is this a new cell? What's the format? Are these really keys or are they
>> just nonces?
>>
>> IMO we should not do this through a new cell because that increases the
>> round-trip by one. Instead we should just embed the PoW parameters in
>> the onion service descriptor and clients find them there.
> Yes, this is a new cell triggered only when DoS limit is reached.
>
> We can't embed it on the onion service descriptor because the attacker 
> could precompute the PoW and make a dictionary attack. The IPKey (will 
> be a nonce) should unique for each new connecting client that wants to 
> send the INTRODUCE2.
>
> What we want this way is increasing the cost of an attacker by many 
> times vs only a little overhead to the I.P.
>

I see. So you were going for an interactive PoW protocol. I wonder what
else we can get if we admit we want interactive. Can we get a CAPTCHA?
What else?

Still, I think the above protocol can be optimized to not require an
extra round trip (extra round trips are bad for the network and for the
intro point): For example, in place of an IPKey nonce that the IP
explicitly sends to the client, we could use some sort of unpredictable
crypto object from the circuit setup (e.g. ntor) between the client and
intro point.

>> That looks like a naive PoW scheme. It would perhaps be preferable to
>> try to find a GPU/ASIC-resistant or memory-hard PoW scheme here, to
>> minimize the advantage of adversaries with GPUs etc.?  Are there any
>> good such schemes?
>>
>> Also services should definitely be able to configure the difficulty of
>> the PoW, and IMO this should again happen through the descriptor.
> That PoW scheme was just a simple example. We should find the right 
> choice. Something hard to find but easy to check.
>

Yep. We should indeed find the right choice here. I have briefly tried
and failed to find papers that compare PoW schemes in a useful way for
this project.