Opened 7 years ago

Closed 3 years ago

Last modified 3 years ago

#5460 closed defect (implemented)

Write proposal(s) to implement improved relay/circuit crypto authentication

Reported by: mikeperry Owned by: nickm
Priority: High Milestone: Tor: 0.2.8.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: needs-proposal, tor-client, path-bias, 027-triaged-1-out, 028-triage, TorCoreTeam201512, 201511-deferred
Cc: nickm, rransom, yawning, isis Actual Points:
Parent ID: #5456 Points: medium
Reviewer: Sponsor: SponsorU?

Description

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:

  1. Self-authenticating crypto (BEAR/LION/LIONESS, others?)
  2. 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.

Child Tickets

Change History (30)

comment:1 in reply to:  description ; Changed 7 years ago by rransom

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:

  1. 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.

  1. 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.

comment:2 Changed 7 years ago by nickm

Owner: set to nickm
Status: newassigned

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.

comment:3 Changed 7 years ago by nickm

Milestone: Tor: 0.2.4.x-final

comment:4 Changed 7 years ago by 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.

comment:5 in reply to:  1 ; Changed 7 years ago by 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?

comment:6 in reply to:  4 Changed 7 years ago by arma

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

comment:7 in reply to:  5 Changed 7 years ago by nickm

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.

comment:8 in reply to:  4 Changed 7 years ago by nickm

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.)

comment:9 Changed 7 years ago by nickm

Keywords: needs-proposal added

comment:10 Changed 6 years ago by nickm

Keywords: tor-client added

comment:11 Changed 6 years ago by nickm

Component: Tor ClientTor

comment:12 Changed 6 years ago by nickm

Milestone: Tor: 0.2.4.x-finalTor: unspecified

comment:13 Changed 6 years ago by mikeperry

Keywords: path-bias added

comment:14 Changed 4 years ago by nickm

Milestone: Tor: unspecifiedTor: 0.2.7.x-final

These go in Tor 0.2.7

comment:15 Changed 4 years ago by nickm

Keywords: 027-triaged-1-out added

Marking triaged-out items from first round of 0.2.7 triage.

comment:16 Changed 4 years ago by nickm

Milestone: Tor: 0.2.7.x-finalTor: 0.2.???

Make all non-needs_review, non-needs_revision, 027-triaged-1-out items belong to 0.2.???

comment:17 Changed 4 years ago by nickm

Cc: yawning added

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.

comment:18 Changed 3 years ago by mikeperry

Keywords: 028-triage added

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.

comment:19 Changed 3 years ago by nickm

Milestone: Tor: 0.2.???Tor: 0.2.8.x-final

comment:20 Changed 3 years ago by nickm

Points: medium

comment:21 Changed 3 years ago by nickm

Sponsor: SponsorU?
Summary: Write proposal(s) to evaluate circuit crypto authenticationWrite proposal(s) to implement improved relay/circuit crypto authentication

Aiming to have another one done in November.

comment:23 Changed 3 years ago by nickm

Keywords: TorCoreTeam201511 added
Severity: Normal

comment:24 in reply to:  22 Changed 3 years ago by nickm

Replying to nickm:

https://lists.torproject.org/pipermail/tor-dev/2015-October/009684.html is a start.

I've started revising it a little, and emailed the AEZ authors for advice on the uncertain points.

comment:25 Changed 3 years ago by nickm

https://lists.torproject.org/pipermail/tor-dev/2015-November/010002.html is the latest draft here. Still hoping for feedback on the tricky parts. I need to get performance metrics on non-aesni platforms.

comment:26 Changed 3 years ago by nickm

Keywords: TorCoreTeam201512 201511-deferred added; TorCoreTeam201511 removed

Bulk-move uncompleted items to december. :/

comment:27 Changed 3 years ago by yawning

For posterity: https://eprint.iacr.org/2015/1193

It doesn't break the primitive and is in-line with the security proof, but I'd like to see the AEZ authors response.

comment:28 Changed 3 years ago by yawning

Ah nevermind(?). The paper is why they tweaked the primitive between v3 and v4, so the key recovery attack is no longer possible. Carry on. Still a interesting paper.

comment:29 Changed 3 years ago by nickm

Resolution: implemented
Status: assignedclosed

I've wrapped up writing the AEZ proposal as proposal 261 (which probably needs proposal 262 for rekeying).

I've also started on a draft proposal for HHFHFH .

Calling this one done; there is now a proposal. Decisions will be needed once we have alternatives and performance number.

comment:30 Changed 3 years ago by isis

Cc: isis added

If we want someone who should know AES better than anyone else, who is also willing to give us a statement saying we should not use AEZ… then Joan Daemen is happy to do so. (I've already explained to Joan the tagging attacks, and why we want AE/AEAD ASAP.)

Note: See TracTickets for help on using tickets.