Opened 5 years ago

Closed 3 years ago

Last modified 14 months ago

#4900 closed enhancement (implemented)

Use a more randomized hash function for our hash tables

Reported by: nickm Owned by:
Priority: High Milestone: Tor: 0.2.5.x-final
Component: Core Tor/Tor Version:
Severity: Keywords: security, tor-relay, tor-dos, 2016-bug-retrospective
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

(This is NOT about using a new cryptographic hashing algorithm.)

There's been some good work recently [1] about the class of DOS attacks where you know the hash algorithm that's going to be used for putting data into a hash table, so you provide a whole bunch of known-to-collide inputs so that the hashtable operations will become O(N) rather than O(1).

To avoid this class of attacks, we ought to have some sort of a per-run random tweak on the data-hashing functions we use for our hash tables.

[1] http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html

Child Tickets

Change History (19)

comment:1 Changed 5 years ago by nickm

I've got the start of a proof-of-concept in bug4900 in my public repo. Trouble is, it crashes Tor on startup, because we need to set a global seed before we put anything into a hash table, but we can't get a good seed until we've initialized openssl. More hacking needed.

The good news here is that this change doesn't seem to slow stuff down much. ./src/test/bench reports about a 4-5% slowdown in digestmap operations on my 32-bit laptop.

comment:2 Changed 5 years ago by rransom

How many hashmaps does Tor create? Can we keep a global list of them until a good RNG is available, then generate our randomization ‘seed’, rehash the hashmaps, and free the list?

comment:3 Changed 5 years ago by nickm

That might work. Alternatively, we could initialize the seed using the logic from crypto_seed_rng(), which does not require that openssl be initialized. It's overkill to use strong entropy for this, but we only need a few bytes.

comment:4 Changed 5 years ago by asn

  • Milestone changed from Tor: 0.2.3.x-final to Tor: 0.2.4.x-final

The implementation of this seems more complicated than originally thought. We should probably do this in 0.2.4.x, except if we find a nice and clean way of doing it.

comment:5 Changed 5 years ago by nickm

  • Keywords tor-relay added

comment:6 Changed 5 years ago by nickm

  • Component changed from Tor Relay to Tor

comment:7 Changed 4 years ago by asn

We should see if the attacks of
http://events.ccc.de/congress/2012/Fahrplan/events/5152.en.html
apply to our hash table function. We should also seriously consider using siphash as our hash table function.

comment:8 Changed 4 years ago by nickm

I favor moving to siphash on general principle. Could be in 0.2.4 if the impact is small and the portability is obviously good; could be in 0.2.5 otherwise.

comment:9 Changed 4 years ago by arma

I spoke to Linus very briefly about the topic, and from what I understand, I think siphash is a fine plan too.

comment:10 Changed 4 years ago by nickm

  • Milestone changed from Tor: 0.2.4.x-final to Tor: 0.2.5.x-final
  • Priority changed from normal to major
  • Type changed from defect to enhancement

Let's move to siphash early in 0.2.5. It's a QOI issue at this point, since this is not the best or only way to DOS.

comment:11 Changed 3 years ago by nickm

bug4900_siphash in my public repository has an incomplete siphash-based implementation for initial poking-at. Initially, it looks a little costly, but I didn't use a screamingly optimized implementation or anything. It doesn't randomize its keys yet, so it's not ready for prime-time.

Possibly, we should also consider crit-bit trees, though those have potential timing issues that we would need to consider hard. And whatever else about them I forgot. I wonder where I put my incomplete critbit-based HT_* replacement code, and whether it's worth finishing.

comment:12 Changed 3 years ago by nickm

Okay, I tried using https://github.com/majek/csiphash/ instead, and got much better performance. Time to make a new branch using that.

comment:13 Changed 3 years ago by nickm

  • Status changed from new to needs_review

My branch bug4900_siphash_v2 is where it's at. Please review.

Before this branch:

digestmap_set: 43.14 ns per element
digestmap_get: 32.29 ns per element

preliminary performance results with this branch:

digestmap_set: 64.79 ns per element
digestmap_get: 54.71 ns per element

IMO, that's not a terrible price to pay for acceptable DoS resistance here. If we find some place where it actually matters for Tor performance, we can optimize that or look at other data structures.

comment:14 Changed 3 years ago by andrea

These patches all look good to me; agree about the performance tradeoff. Thumbs up if you want to go ahead and merge this.

comment:15 Changed 3 years ago by nickm

  • Resolution set to implemented
  • Status changed from needs_review to closed

Okay, I've merged it. It seems okay to me. Thanks for the review!

comment:16 Changed 14 months ago by mikeperry

  • Keywords tor-dos added; dos removed

Canonicalize dos tag to tor-dos

comment:17 Changed 14 months ago by nickm

  • Keywords 2016-bug-retrospective added

Mark bugs for 2016 bug retrospective based on hand-examination of changelogs for 0.2.5 onwards.

comment:18 Changed 14 months ago by nickm

Mark bugs for 2016 bug retrospective based on hand-examination of changelogs for 0.2.5 onwards.

comment:19 Changed 14 months ago by nickm

Mark bugs for 2016 bug retrospective based on hand-examination of changelogs for 0.2.5 onwards.

Note: See TracTickets for help on using tickets.