Hi, all.
This is just the ntor proposal draft, as circulated last year, but with a proposal number assigned to it, and a closing section about how to make Tor actually work with it.
Filename: 216-ntor-handshake.txt Title: Improved circuit-creation key exchange Author: Nick Mathewson Created: 11-May-2011 Status: Open
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.
Notation:
Let a|b be the concatenation of a with b.
Let H(x,t) be a tweakable hash function of output width H_LENGTH bytes.
Let t_mac, t_key, and t_verify be a set of arbitrarily-chosen tweaks for the hash function.
Let EXP(a,b) be a^b in some appropriate group G where the appropriate DH parameters hold. Let's say elements of this group, when represented as byte strings, are all G_LENGTH bytes long. Let's say we are using a generator g for this group.
Let a,A=KEYGEN() yield a new private-public keypair in G, where a is the secret key and A = EXP(g,a). If additional checks are needed to insure a valid keypair, they should be performed.
Let PROTOID be a string designating this variant of the protocol.
Let KEYID be a collision-resistant (but not necessarily preimage-resistant) hash function on members of G, of output length H_LENGTH bytes.
Instantiation:
Let's call this PROTOID "ntor-curve25519-sha256-1" (We might want to make this shorter if it turns out to save us a block of hashing somewhere.)
Set H(x,t) == HMAC_SHA256 with message x and key t. So H_LENGTH == 32. Set t_mac == PROTOID | ":mac" t_key == PROTOID | ":key" t_verify == PROTOID | ":verify"
Set EXP(a,b) == curve25519(.,b,a), and g == 9 . Let KEYGEN() do the appropriate manipulations when generating the secret key (clearing the low bits, twiddling the high bits).
Set KEYID(B) == B. (We don't need to use a hash function here, since our keys are already very short. It is trivially collision-resistant, since KEYID(A)==KEYID(B) iff A==B.)
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
The server generates a keypair of y,Y = KEYGEN(), and computes
secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID KEY_SEED = H(secret_input, t_key) verify = H(secret_input, t_verify) auth_input = verify | ID | B | Y | X | PROTOID | "Server"
The server sends a CREATED cell containing:
SERVER_PK: Y -- G_LENGTH bytes AUTH: H(auth_input, t_mac) -- H_LENGTH byets
The client then checks Y is in G^* [see NOTE below], and computes
secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID KEY_SEED = H(secret_input, t_key) verify = H(secret_input, t_verify) auth_input = verify | ID | B | Y | X | PROTOID | "Server"
The client verifies that AUTH == H(auth_input, t_mac).
[NOTE: It may be adequate to check that EXP(Y,x) is not the point at infinity. See tor-dev thread.]
Both parties now have a shared value for KEY_SEED. They expand this into the keys needed for the Tor relay protocol.
Key expansion:
Currently, the key expansion formula used by Tor here is
K = SHA(K0 | [00]) | SHA(K0 | [01]) | SHA(K0 | [02]) | ...
where K0==g^xy, and K is divvied up into Df, Db, Kf, and Kb portions.
Instead, let's have it be
K = K_0 | K_1 | K_2 | K_3 | ...
Where K_0 = H(m_expand | INT8(i) , KEY_SEED ) and K_(i+1) = H(K_i | m_expand | INT8(i) , KEY_SEED ) and m_expend is an arbitrarily chosen value, and INT8(i) is a octet with the value "i".
Ian says this is due to a construction from Krawczyk at http://eprint.iacr.org/2010/264 .
Let m_expand be PROTOID | ":key_expand"
Performance notes:
In Tor's current circuit creation handshake, the client does: One RSA public-key encryption A full DH handshake in Z_p A short AES encryption Five SHA1s for key expansion And the server does: One RSA private-key decryption A full DH handshake in Z_p A short AES decryption Five SHA1s for key expansion
While in the revised handshake, the client does: A full DH handshake A public-half of a DH handshake 3 H operations for the handshake 3 H operations for the key expansion and the server does: A full DH handshake A private-half of a DH handshake 3 H operations for the handshake 3 H operations for the key expansion
Integrating with the rest of Tor:
Add a new optional entry to router descriptors and microdescriptors:
"onion-key-ntor" SP Base64Key NL
where Base64Key is a base-64 encoded 32-byte value, with padding omitted.
Add a new consensus method to tell servers to copy "onion-key-ntor" entries to from router descriptors to microdescriptors.
Add a "UseNTorHandshake" configuration option and a corresponding consensus parameter to control whether clients use the ntor handshake. If the configuration option is "auto", clients should obey the consensus parameter. Have the configuration default be "auto" and the consensus value initially be "0".
Reserve the handshake type [00 01] for this handshake in CREATE2 and EXTEND2 cells.
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 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?
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.
-- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin
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?
On Fri, Nov 30, 2012 at 12:07 AM, 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 responded on that ticket a little when you posted it. I think that a proof-of-work idea is interesting and worth analyzing, but probably out-of-scope for #7202 and ntor work in 0.2.4. Here's why:
1) The ntor handshake will the force multiplier worse for the attacker, not better. So this doesn't seem like a regression that should block ntor. 2) We have 10 days left before the implementation deadline for new features in 0.2.4, and negative 20 days left for the deadline for brand-new feature proposals in 0.2.4 [1]. 3) I am sure that we would design something better if we take the time to learn the literature better and write some proposals than we would if we scramble to get something into 0.2.4.
So unless there's something above that I'm getting wrong, this is a topic that I'd like to come back to in a week or two, once I'm dug out from under the stuff I want to get in before the Big Feature deadline [1]. Stuff I should expand on then includes: * "Replay caches can afford be fuzzy and imperfect " * "GPUs vs smartphones" * etc
[1] https://trac.torproject.org/projects/tor/wiki/org/roadmaps/Tor/024
Thus spake Nick Mathewson (nickm@freehaven.net):
On Fri, Nov 30, 2012 at 12:07 AM, 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 responded on that ticket a little when you posted it. I think that a proof-of-work idea is interesting and worth analyzing, but probably out-of-scope for #7202 and ntor work in 0.2.4. Here's why:
- The ntor handshake will the force multiplier worse for the
attacker, not better. So this doesn't seem like a regression that should block ntor. 2) We have 10 days left before the implementation deadline for new features in 0.2.4, and negative 20 days left for the deadline for brand-new feature proposals in 0.2.4 [1]. 3) I am sure that we would design something better if we take the time to learn the literature better and write some proposals than we would if we scramble to get something into 0.2.4.
You're right. I didn't mean to distract from finishing ntor on time for 0.2.4.x, I was just curious if anyone else had any ideas. Ntor is pretty darn important by itself, and is also an improvement against this attack, and it should also now be much easier to change the CREATE handshake than it used to be.
I also checked the source, and it does seem like there's no obvious way to send multiple RELAY_COMMAND_EXTENDs down the same circuit. circuit_extend() will tear down a circuit that has circ->n_chan set when it gets a new extend command, and it sets n_chan in the same codepath.
So if nothing else, the attack is somewhat hard to run at full link speed while still using intermediate nodes. You gotta do a lot of circuit parallelization, which would allow you to be fingerprinted at Guards more easily as an attacker than I initially thought.
-
Mike Perry -
Nick Mathewson -
Watson Ladd