[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:

> Hello, this is my view of things, please be gentle as this is my first 
> proposal draft :)
>

Hello,

thanks for working on this. IMO any proof-of-work introduction proposal
can be seen as orthogonal to David's prop305 which is a rate-limiting
proposal (even tho it's not named as such) and hence deserves its own
thread.

> _ADAPTIVE POW PROPOSAL:_
>
> Client sends the INTRODUCE1 as normal.
>
> Introduction Point checks the Current Requests Rate and checks the DoS 
> settings.
>
> -DoS check is OK: send INTRODUCE2 to Hidden Service etc...
>

So far so good (even tho this is not our usual proposal format).

> -DoS settings/rate limit reached: then
>
>      1.Introduction Point generates a random 8 bytes key (IPKey) and 
> associates it with the client circuit. Then send INTRODUCE_POW to the 
> Client with the IPKey.

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. 

>      2.Client computes POW.
>      Do{
> Generates random 8 bytes key (ClientKey).
> Generates hash(sha512/256 or sha3??) of
> hash(IPKey + ClientKey)
> } while (hash does not start with "abcde")
>

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.

>      3. Client sends INTRODUCE_POWR to the I.P. with the generated POW 
> and the ClientKey.

IMO this should happen as part of the INTRODUCE1 cell.

>      4. I.P. checks the POW:
>
>          -POW is correct: send INTRODUCE2 to HS.
>          -POW is not correct: send INTRODUCE_POW_ERROR to client with 
> new IPKey.
>
> *I say 8 bytes for the Keys just for example.
>
> PROS AND CONS, who needs to update Tor version?:
> --------------
>
> Only rate limit: Introduction Point and Hidden Service. No breakage.
>
> POW: Client, Introduction Point and Hidden Service. POW will break 
> compatibility with other v3 Hidden Services clients, if we implement a 
> way to bypass POW for old clients then this feature won't work as intended.
>
> A forgotten guy here: Authenticated Rends cell: where we make sure the 
> Client established a connection to the Rend Point before requesting the 
> INTRODUCE1.
>

Yep, that's yet another proposal (ticket #25066).