nodelist_add_microdesc: assign md to all appropriate nodes properly
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?
Activity
changed milestone to %Tor: unspecified
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.
Trac:
Priority: normal to major
Milestone: N/A to Tor: 0.2.5.x-final
Keywords: N/A deleted, tor-relay needs-proposal added-
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.
-
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)
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.
-
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.
changes file for bug11743
Without this fix, a hostile relay could selectively disable client use of target relaysDescription 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).
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.
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.
Trac:
Milestone: Tor: 0.2.6.x-final to Tor: 0.2.???Ed25519 identity keys are #12498 (moved) (prop 220); cross-certification is #12499 (moved) (prop 228).
mentioned in issue #12498 (moved)
moved to tpo/core/tor#11743 (closed)
