Opened 3 years ago

Last modified 25 hours ago

#11743 new defect

nodelist_add_microdesc: assign md to all appropriate nodes properly

Reported by: cypherpunks Owned by:
Priority: High Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-relay, needs-proposal, 2016-bug-retrospective
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

Auths can to create the same md for two different relays. Because hash collision or evil relay. Last one can to announce any onion keys and family, without needs any proofs. All parts of code designed with assumption one md per many nodes, except nodelist_add_microdesc.

nodelist_add_microdesc using router_get_consensus_status_by_descriptor_digest which cut off digest, digestmap_set using SHA1 while md's digest about SHA256.
nodelist_add_microdesc can't to assign md to all appropriate nodes, and only to first with id returned by router_get_consensus_status_by_descriptor_digest.

If evil relay will craft self id specifically then it will break usage of victim's relay for any freshly new clients till updated consensus (it's about several hours).

If to keep nodelist_add_microdesc with md per one node then md format need to be more unique generated. Unique md can be generated by adding ID of relay, it will stop crafted mds. Which way to choose? Need another ticket about it?

Child Tickets

Change History (25)

comment:1 follow-up: Changed 3 years ago by nickm

  • Keywords tor-relay needs-proposal added
  • Milestone set to Tor: 0.2.5.x-final
  • Priority changed from normal to major

Hm. There are a lot of options here. Let's find the best one we can do quickly, and then the best one to do long-term.

(A) Proposal 228 (cross-certify identity keys with onion keys) would help here somewhat, but in 0.2.5 we would still need a way for authorities to enforce uniqueness on microdescriptors, since proposal 228 isn't even implemented yet, much less deployed to all routers.

(B) Probably the best way to prevent md hash duplication would be to this would be to add a new consensus algorithm to add a distinguisher to any microdescriptors. Adding a short hash of the identity key to all microdescriptors (say, 128 bits, since we're worried about preimages and not collisions) would be adequate there.

(C) One thing that isn't easy to do would be adding the distinguisher only when two microdescriptors would collide. But that isn't easy, since we might not know that they will collide until all the votes are in. (Consider what happens if n/2+1 of the authorities vote for router A, and n/2+1 vote for router B, and both routers have the same microdescriptors, but .)

(D) We can also, as a stopgap, refuse to vote for two routers with the same onion key, if we have a reasonably good way to be sure that we are voting for the right router.

(E) Another way would be to reject any router that uses the same onion key as another router if we can't build circuits through it, though I don't know if the authorities' testing mechanisms currently try circuit building.

(F) A final fix here would be to fix all the client code to allow multiple nodes to share a microdescriptor. I don't think that's a great idea for 0.2.5, since the code there might be fragile. I'm not sure it's a good idea for 0.2.6 either, since nodes really shouldn't share microdescriptors.

So my inclination here is to do (B) and/or (D) in Tor 0.2.5, and (A) in Tor 0.2.6.

comment:2 Changed 3 years ago by nickm

Case (B) is so very simple to implement that I went ahead and did it. Untested code in branch bug1743_option_b.

comment:3 Changed 3 years ago by nickm

See also bug11743_option_b in my torspec repository for the corresponding spec change.

comment:4 follow-up: Changed 3 years ago by arma

Re E, the authority testing only does link handshakes currently.

Re B, how much size growth are we talking here?

comment:5 Changed 3 years ago by arma

Re D, what would be our way to know that we're picking the right relay? That one seems tough.

comment:6 in reply to: ↑ 4 ; follow-up: Changed 3 years ago by nickm

Replying to arma:

Re E, the authority testing only does link handshakes currently.

Re B, how much size growth are we talking here?

Uncompressed microdescriptors get 7% longer. Compressed microdescriptors get around 12% longer. This shouldn't matter even that much if we are right that microdescriptors change infrequently, and consensuses dominate the amount of stuff we download. We can get it back down to 0% later on when we implement proposal 228.

Replying to arma:

Re D, what would be our way to know that we're picking the right relay? That one seems tough.

I don't know what our way would be. I can try to make something up, but B seems like a much more solid solution to me.

comment:7 in reply to: ↑ 6 Changed 3 years ago by nickm

Replying to nickm:

Uncompressed microdescriptors get 7% longer. Compressed microdescriptors get around 12% longer. This shouldn't matter even that much if we are right that microdescriptors change infrequently, and consensuses dominate the amount of stuff we download. We can get it back down to 0% later on when we implement proposal 228.

Those numbers assume that we include 160-bit identity digests in microdescriptors. If we're feeling cheeky, and we decided to include a 128-bit truncated digest, the uncompressed and compressed overheads are 6.7% and 10% respectively. If we dropped to 80 bits, we'd add 5% and 7% respectively, but I should never pay attention to the "80 bits are enough" voice again.

(All these numbers were obtained by adding random id lines to all the microdescriptors in my cached-microdescriptors file)

comment:8 in reply to: ↑ 1 ; follow-up: Changed 3 years ago by cypherpunks

nodes really shouldn't share microdescriptors.

But auths could to generate md with the same hash for two different relays from consensus, just because hash collision nature. And no simple solution to fix that, it's tricky to drop consensus with such colliding md.
Client shouldn't crash if that happens at least.

comment:9 in reply to: ↑ 8 Changed 3 years ago by nickm

Replying to cypherpunks:

nodes really shouldn't share microdescriptors.

But auths could to generate md with the same hash for two different relays from consensus, just because hash collision nature.

Well, we're never going to see an *accidental* collision in SHA256. (That's about a P=2-128 event, and those are basically impossible.)

And no simple solution to fix that, it's tricky to drop consensus with such colliding md.
Client shouldn't crash if that happens at least.

Right.

For now, what do you think of "bug11743_option_b" to prevent collisions from duplicate onion keys? It should make md collisions as hard as SHA256 collisions, which should be out of reach for a while.

comment:10 Changed 3 years ago by cypherpunks

bug11743_option_b

Seems ok.

comment:11 Changed 3 years ago by nickm

Works for me under chutney; code still looks okay to me. Added a changes file. Merging this one tonight unless there are objections.

comment:12 Changed 3 years ago by andrea

Code review: I think this should work and is the easiest fix, but go change that comment on '#define MIN_METHOD_FOR_ID_HASH_IN_MD 18' in dirvote.h.

comment:13 Changed 3 years ago by nickm

Fixed that, and a future-compatibility issue with proposal 220. Have another look?

comment:14 Changed 3 years ago by nickm

(The future-compatibility issue is that proposal 220 specified an "id" line of the form id ed25519 <base64>. So the format for these lines needs to be id rsa1024 <base64> to avoid conflict. The 8 additional bytes won't matter when microdescriptors are sent compressed.)

comment:15 Changed 3 years ago by nickm

okay, cleaned that up, and added a unit test for good measure. Merged it to master.

comment:16 Changed 3 years ago by nickm

  • Milestone changed from Tor: 0.2.5.x-final to Tor: 0.2.6.x-final

other fixes here are in-scope for 0.2.6

comment:17 Changed 3 years ago by cypherpunks

changes file for bug11743

Without this fix, a hostile relay could selectively disable client use of target relays

Description looks too depressive.
Just for clarity. nodelist_set_consensus updates all nodes properly with need md, if md was in memory already. This bug affects (for example) users of Tails on cold boot, but if to use Tor longer or to start Tor with cached documents then bug of nodelist_add_microdesc should be automagically fixed.
And this bug can't to block usage of guards (client still able to use create_fast without onion key).

comment:18 Changed 3 years ago by nickm

I've tried to correct the message in c948bdaa2859bb4d92b8af526bf1363a854919e8 by adding the word "some". People who are interested in a complete list of when the attack works can find it here at this ticket. :)

comment:19 Changed 3 years ago by cypherpunks

And this bug can't to block usage of guards (client still able to use create_fast without onion key).

It seems was wrong statement. choose_good_entry_server() doesn't count nodes without md and choose_random_entry_impl() can't to choose node without descriptor for guard purpose. Doubly blocked.

People who are interested in a complete list of when the attack works can find it here at this ticket. :)

OK.

Last edited 3 years ago by cypherpunks (previous) (diff)

comment:20 Changed 3 years ago by andrea

  • Milestone changed from Tor: 0.2.6.x-final to Tor: 0.2.???

Per nickm, the solution is ed25519 identity keys in microdescriptors and onion key cross-signing. Then this can only happen in the sha256 collision case; there's still a bug but it isn't exploitable under reasonable assumptions, so kicking this to 0.2.???, but those other ones should happen in 0.2.6.

comment:21 Changed 3 years ago by andrea

Ed25519 identity keys are #12498 (prop 220); cross-certification is #12499 (prop 228).

comment:22 Changed 13 months ago by nickm

  • Keywords 2016-bug-retrospective added
  • Severity set to Normal

comment:23 Changed 6 months ago by teor

  • Milestone changed from Tor: 0.2.??? to Tor: 0.3.???

Milestone renamed

comment:24 Changed 5 months ago by nickm

  • Keywords tor-03-unspecified-201612 added
  • Milestone changed from Tor: 0.3.??? to Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:25 Changed 25 hours ago by nickm

  • Keywords tor-03-unspecified-201612 removed

Remove an old triaging keyword.

Note: See TracTickets for help on using tickets.