3 ms·
A hash table is vulnerable to collision attacks, if keys are derived from any kind of untrusted external input. Trees might be slow, but they're consistently sl
by int_19h 7y ago
A hash table is vulnerable to collision attacks, if keys are derived from any kind of untrusted external input. Trees might be slow, but they're consistently slow.
- deckard1 7y agonon sequitur. No one mentioned security, nor do any elementary data structures concern themselves with such higher level things. If you're allowing unlimited untrusted data to control internal data structures, you're going to have a bad time regardless of which data structure you're using.
- eximius 7y agoAnd rusts default hashing implementation is hardened against these attacks
- dlubarov 7y ago> nor do any elementary data structures concern themselves with such higher level things Not explicitly, but they concern themselves with worst-case performance, and tolerable worst-case performance implies security against a certain class of attacks (like HashDoS).
- int_19h 7y agoSecurity is a thing that is implicitly pervasive. If it doesn't apply, that should be explicit. And yes, elementary data structures concern themselves with such things all the time - because, regardless of how they "must" be used, in practice they do get used on untrusted inputs on the time, simply because it's the easiest thing. Have you noticed how many languages and standard libraries have switched to random seeds for their hash tables lately? And no, it's not true that you're going to "have a bad time regardless of the data structure". You're not going to have a bad time with an RB tree, regardless of where your inputs for keys come from - because it is a data structure that doesn't have a quirk of extremely bad perf on pathological inputs.
- viraptor 7y agoThis has been mitigated in almost every language already by starting the hash calculation with a random per-process seed. It's a theoretical issue of hash tables, but we've got known practical solutions.