[tor-dev] Proposal 216: Improved circuit-creation key exchange

[Mike Perry]

Thus spake Watson Ladd (watsonbladd at gmail.com):

> On Thu, Nov 29, 2012 at 11:07 PM, Mike Perry <mikeperry at torproject.org> wrote:
> >
> > Thus spake Nick Mathewson (nickm at freehaven.net):
> >
> > > Title: Improved circuit-creation key exchange
> > > Author:  Nick Mathewson
> > >
> > > Summary:
> > >
> > >   This is an attempt to translate the proposed circuit handshake from
> > >   "Anonymity and one-way authentication in key-exchange protocols" by
> > >   Goldberg, Stebila, and Ustaoglu, into a Tor proposal format.
> > >
> > >   It assumes that proposal 200 is implemented, to provide an extended CREATE
> > >   cell format that can indicate what type of handshake is in use.
> > >
> > > Protocol:
> > >
> > >   Take a router with identity key digest ID.
> > >
> > >   As setup, the router generates a secret key b, and a public onion key
> > >   B with b, B = KEYGEN().  The router publishes B in its server descriptor.
> > >
> > >   To send a create cell, the client generates a keypair x,X = KEYGEN(), and
> > >   sends a CREATE cell with contents:
> > >
> > >     NODEID:     ID             -- H_LENGTH bytes
> > >     KEYID:      KEYID(B)       -- H_LENGTH bytes
> > >     CLIENT_PK:  X              -- G_LENGTH bytes
> >
> > I mentioned this on the ntor ticket (#7202), but it's probably worth
> > repeating here in case anyone has any suggestions or ideas:
> >
> > I think we really should consider a proof-of-work field on the client's
> > CREATE cell, so we have some form of response available in the event of
> > circuit-based CPU DoSes against Tor relays.
> 
> Not an issue: in 10 minutes a Core 2 Quad Intel machine can calculate
> 10 million ECC calculations.
> I think we'll be okay.

Hrmm.. If you used all 4 cores for this test, this is ~4000 ECC
calculations per second, per core. If I'm reading the proposal right,
the handshake requires two ECC calculations and three hashes per create
cell.. Let's just call this 1000 create cells per second per core for
now, but it's probably a bit lower than that.

This is substantially fast and worlds better than current onionskins,
but it still worries me that clients don't need to spend any CPU on this
attack, only bandwidth. This client-vs-server CPU asymmetry means that a
client with 512KBytes/sec of upstream could take down any single-core
relay instance it wanted. This is somewhat close to the upstream
capacity for residential cable modems.

This means a very small botnet could bring down the Tor network, even
with the new handshake. Worse, it will be very hard to rate limit such
clients by IP in the event of an attack, because they get to route their
CREATE cells through other hops first.


On the other hand, making the proof-of-work system not be buggy and
failure prone might be quite a bit of dev effort. So there is that to
consider.

I suppose a simpler solution might be to make it hard/impossible to
blast unlimited RELAY_EXTEND/CREATE cells through intermediate nodes
without waiting for any round trips/responses. Maybe this is already the
case, unless there are ways to re-use partially constructed/initial
portions of circuits to send RELAY_EXTENDs... Does the "leaky-circuit"
support code still exist, for example?



-- 
Mike Perry
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20121130/5ea9fbf4/attachment-0001.pgp>