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

[Chelsea Holland Komlo]

There are a couple approaches to consider.

POW via hashing goes for a relatively simple to implement approach.
However, this incurs a high cost for all clients, and also environmental
damage, per previous email.

Another approach similar to the above (but more environmentally
friendly) can be Proof of Storage (or proof of space), as in
https://eprint.iacr.org/2013/796.pdf

With both of the above approaches, there will be a tradeoff to what the
cost is to deter a would-be attacker, versus the cost to real but
bandwidth/cpu limited clients, such as on mobile platforms.

More involved approaches include anonymous blacklists/whitelists,
blinded tokens, etc. Previous work has been done in this space, here is
one example:
https://crysp.uwaterloo.ca/courses/pet/F11/cache/www-users.cs.umn.edu/~hopper/faust-wpes.pdf

While designs using a token-based approach such as what Jeff mentions
below may require more design/thought up front, the benefit is that
clients won't be penalized every time they connect to an onion service.
Considering the goal of scaling of the Tor network and of "onions
everywhere", this seems like a good tradeoff. 


On 2019-06-16 18:03, Jeff Burdges wrote:
> As a rule, proof-of-work does not really deliver the security
> properties people envision.  We’ve no really canonical anti-sibel
> criteria in this case, but maybe some mixed approach works:
> 
> First, introduction points have a default mode in which they rate
> limit new connections and impose some artificial latency.  Second, an
> onion service can issue rerandomizable certificates, blind signature,
> or oblivious PRFs that provide faster and non-rate limited access
> through a specific introduction points.
> 
> Coconut would suffice for the rerandomizable certificates of course,
> but sounds like overkill.. and slow.
> 
> We should consider an oblivious PRF for this use case too:
> 
> It’s easy to make an oblivious PRF from the batched DLEQ proof
> implemented in
> https://github.com/w3f/schnorrkel/blob/master/src/vrf.rs  I suppose
> Tor might adapt this to not use Ristretto, or maybe choose an Ed25519
> to Ristretto map, but regardless the whole scheme is not too much more
> complex than a Schnorr signature.
> 
> We require the oblivious PRF secret key be known by both the
> introduction point for verification and the onion service for issuing.
>  In this, we do not share the oblivious PRF key among different
> introduction points because introduction points cannot share a common
> double redemption database anyways.
> 
> I’m worried about different oblivious PRF keys being used to tag
> different users though.  There are complex mechanisms to prevent this
> using curves created with Cocks-Pinch, but..
> 
> We could simply employ blind signatures however, which avoids sharing
> any secrets, and thus permits binding the key uniquely to the hidden
> service.  As a rule, blind signatures require either slow cryptography
> like pairings or RSA, or else issuing takes several round trips and
> have weak soundness.  I think weak soundness sounds workable here,
> although I’m no longer sure about all the issues with such scheme.
> 
> Best,
> Jeff
> 
> p.s.  We’re hiring in security
> https://web3.bamboohr.com/jobs/view.php?id=38 and several research
> areas like cryptography https://web3.bamboohr.com/jobs/view.php?id=29
> 
> 
> 
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev