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

[Mike Perry]

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.

The first thing that came to my mind was a hash of the entire cell
contents plus timestamp and a nonce field. The nonce would be repeatedly
altered until the hash prefix matched a value specified by the
consensus.

Then, if a relay receives a cell with either a stale timestamp or an
invalid hash+hash prefix, that cell can be discarded. If the relay's
onionskin queue is full, it can do some additional accounting such as
ensuring that the hash values it sees are unique within the valid
timestamp window. Or perhaps it only needs to inspect this portion of
the cell at all if the onionskin queue is full.

As I see it, there are two serious hurdles to this approach:

1. The timesource of the timestamp needs to not be fingerprintable, yet
still current enough to allow us to feasibly track a list of these
hashes if we want. The client's consensus timestamp is the most readily
available source of such a timestamp, but it would have to be fuzzed to
account for the fact that only 1/4 of all clients will posses a
consensus for that hour.

Do we have other timesources? I seem to recall seeing some tickets about
dirport timesources fly by... Did we ever figure out a way forward for
those?

2. If we're not careful, the hash prefix consensus parameter would cause
most clients to be unable to build circuits until they download the new
consensus instructing them to do the proof of work. Relays would have to
wait several consensus periods before enforcing the hash prefix.


Or, alternatively, are there other proof-of-work mechanisms we could use
instead?



-- 
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/20121129/d864026d/attachment.pgp>