Write proposal(s) to implement improved relay/circuit crypto authentication
We need to write a proposal to determine the best way to provide authentication to our circuit crypto, so that cells that have been tagged/tampered with/duplicated cause circuit failure at the 2nd hop, not the third.
As I understand it, there are two competing possibilities:
- Self-authenticating crypto (BEAR/LION/LIONESS, others?)
- Per-hop MAC
The main disadvantage of 1 is that it's likely slow and not very many people use it. The disadvantage of 2 is that it requires us to disclose path length count and position to nodes, as well as have MACs that either grow with increased path length, or become less secure with increased path length.
There are probably other issues. I believe the current plan is to produce both options in one or more proposals and compare and contrast them.
Activity
changed milestone to %Tor: 0.2.8.x-final
added 027-triaged-1-out 028-triage 201511-deferred TorCoreTeam201512 component::core tor/tor milestone::Tor: 0.2.8.x-final needs-proposal owner::nickm parent::5456 path-bias points::medium priority::high resolution::implemented severity::normal sponsor::U? status::closed tor-client type::defect labels
Replying to mikeperry:
We need to write a proposal to determine the best way to provide authentication to our circuit crypto, so that cells that have been tagged/tampered with/duplicated cause circuit failure at the 2nd hop, not the third.
The goal is to ensure that any attempt to tag a circuit destroys all further data sent on it, so that the attacker cannot tag a circuit's data in any way other than by destroying it. (These anti-tagging measures do nothing about timing-based ‘tagging’ techniques; they are motivated by the assumption that tagging a circuit's data is much easier or more effective than any timing attack.)
As I understand it, there are two competing possibilities:
- Self-authenticating crypto (BEAR/LION/LIONESS, others?)
BEAR/LION/LIONESS are not ‘self-authenticating crypto’. They are large-block block ciphers which ensure that any change to a block's data on one side of an honest relay completely scrambles the block's data on the other side. They would need to be accompanied by an end-to-end MAC.
- Per-hop MAC
The main disadvantage of 1 is that it's likely slow and not very many people use it.
LION can be made relatively fast (certainly faster than Tor's current crypto) by using an appropriate stream cipher and message-digest function in it. (Per-hop MACs can be made faster, but LION isn't slow.)
The disadvantage of 2 is that it requires us to disclose path length count and position to nodes, as well as have MACs that either grow with increased path length, or become less secure with increased path length.
These disadvantages are not required. Nick proposed these ideas because they may allow better security-versus-MAC-size tradeoffs.
There are probably other issues. I believe the current plan is to produce both options in one or more proposals and compare and contrast them.
I'm taking assignment on this, since i already started in the latter part of xxx-new-crypto-ops.txt. I'm going to split that into one or two "here's how the circuit protocol would work" things.
We can figure out the relative advantages and disadvantages of both designs once we have the proposals, I think. I'll also try to write up the #tor-dev IRC discussion we had about them about their relative impacts on cell tagging.
Trac:
Owner: N/A to nickm
Status: new to assigned
Replying to rransom:
BEAR/LION/LIONESS are not ‘self-authenticating crypto’. They are large-block block ciphers which ensure that any change to a block's data on one side of an honest relay completely scrambles the block's data on the other side. They would need to be accompanied by an end-to-end MAC.
Even if accompanied by an end-to-end mac, isn't that insufficient? If I can mangle a cell, and detect mangling, and it still gets to the other end, that sounds like a tagging attack to me. It's not as fine-grained a tagging attack sure, but if the goal is "cause circuit failure at the 2nd hop, not the third" then it's not going to do it, right?
-
Replying to mikeperry:
Ondrej pointed out that I2P's one-RTT circuit construction is very useful for avoiding disclosing the length of your circuit. It might also be useful for avoiding the per-hop MACs we'd need here.
There are a series of papers on one-RTT circuit construction for Tor. See e.g. http://freehaven.net/anonbib/#sphinx-onion-fc10
-
Replying to arma:
Replying to rransom:
BEAR/LION/LIONESS are not ‘self-authenticating crypto’. They are large-block block ciphers which ensure that any change to a block's data on one side of an honest relay completely scrambles the block's data on the other side. They would need to be accompanied by an end-to-end MAC.
Even if accompanied by an end-to-end mac, isn't that insufficient? If I can mangle a cell, and detect mangling, and it still gets to the other end, that sounds like a tagging attack to me. It's not as fine-grained a tagging attack sure, but if the goal is "cause circuit failure at the 2nd hop, not the third" then it's not going to do it, right?
"It Depends". The biggest problem with the current tagging attack is that a successfully tagged circuit (one where the attacker observes the tag) is recoverable by the attacker. Either a whole-cell encryption approach or a per-hop MAC approach would solve that. (As for the "it's still a tag" argument... it's not clear that "the whole circuit gets destroyed away suddenly" is much worse as a tag than "the whole circuit turns to junk suddenly.)
I wrote a draft draft draft today, and I'm showing it to as some naive-about-tor/smart-about-crypto people to try to make sure it's readable. I'll give it another editing pass after that, assign it a proposal number, and call this ticket closed.
-
Replying to mikeperry:
Ondrej pointed out that I2P's one-RTT circuit construction is very useful for avoiding disclosing the length of your circuit. It might also be useful for avoiding the per-hop MACs we'd need here.
Mike, Marsh, and I just discussed this a little on IRC. The tricky thing here is that there aren't a lot of ways to do one-RTT circuit construction and retain PFS--especially PFS for your path itself!-- unless you're getting your PFS from key rotation.
We should go through Kate and Goldberg's paper to see if it shows (or cites!) something we could use, but it's not obvious to me that it's a great idea right now.
(Also, circuit creation is not what this ticket is about: this ticket is about handling relay cells once circuits are established.)
-
See Yawning's experimental results at https://lists.torproject.org/pipermail/tor-dev/2015-March/008485.html : it seems that LIONESS is going to be a heck of a lot slower than we can accept.
Hope is on the way, perhaps: DJB and Rogaway both tell me that AEZ is probably fast enough and secure enough. (Especially if we're willing to depend on AESNI.) DJB says that he's got a more generic construction in the works that doesn't rely on the AES round function, and if that's done soon enough, we can consider that one too.
Trac:
Cc: nickm, rransom to nickm, rransom, yawning 
I wrote https://gitweb.torproject.org/torspec.git/tree/proposals/253-oob-hmac.txt as a potential stopgap that might be doable on the 0.2.8.x timescale.
Trac:
Keywords: N/A deleted, 028-triage added