Thus spake Watson Ladd (watsonbladd@gmail.com):
On Thu, Nov 29, 2012 at 11:07 PM, Mike Perry mikeperry@torproject.org wrote:
Thus spake Nick Mathewson (nickm@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 bytesI 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?