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

[Watson Ladd]

On Tue, Jun 18, 2019 at 6:29 PM Chelsea Holland Komlo
<me at chelseakomlo.com> wrote:
>
> 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

Privacy Pass has already been integrated into Tor Browser. Perhaps
work could be done to use it here?
>
> 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
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.