5 ms·

Note that if you have untrusted input, you may want to use a defensive option for hashing involving a private key, such as SipHash[1]. Otherwise, an attacker wh

Note that if you have untrusted input, you may want to use a defensive option for hashing involving a private key, such as SipHash[1]. Otherwise, an attacker who knows your hash functions can just pre-generate a large number of colliding elements and reduce your hash function to a linked list; given enough attacker-controlled elements, this can effectively amount to a DoS attack[2]. [1] https://github.com/veorq/SipHash https://github.com/veorq/SipHash [2] https://www.aumasson.jp/siphash/siphashdos_29c3_slides.pdf https://www.aumasson.jp/siphash/siphashdos_29c3_slides.pdf

pansa2 5y ago
SipHash is considerably slower than an unkeyed hash function, isn’t it? One idea I had to avoid its overhead is to use double hashing, with a fast primary hash and SipHash as the secondary hash. Naïvely this feels as though it should provide good performance in the common case and also good security - even if there are many primary hash collisions, they won’t also be secondary hash collisions. Does anyone know if there is an analysis of this approach anywhere?
veltas 5y ago
Another alternative is not using a hash table, and instead using a sorted binary tree or similar, which tends to be slower on average but has worst case O(log n) lookup, O(log n) insertion. Depends on your criteria.
- dhosek 5y ago
  That depends on the implementation. If it's a simple binary tree, the worst case is O(n), not O(log n) since if you insert data in sorted order everything will always be in the left branch. O(log n) is average lookup time. If you have a specialized tree structure like a red-black tree which will automatically balance, this will improve, but sorted input is still a viable attack method. That said, a lot depends on the application and one should pick a hash function wisely. A binary tree–mapped hash table works best when you want to be able to iterate on keys in sort order or find an entry that's just before or just after a non-existent key in sort order. It's not really a good defense against hash attacks. On the flip side, the default hasher in Rust is hardened against hash attacks, but it's overkill for most applications and can cause severe performance degradation (although at least the library documentation is clear on this and points at alternative hash implementations for such cases). Unfortunately, the Rust resizing algorithm is flawed and won't resize until the hash capacity is completely full¹ making hash collisions much more likely. I had a doubling of performance in benchmarking some code that I was writing just by increasing the initial capacity of the map. ⸻⸻⸻ 1. A common mistake I see Java developers make is, when they know they'll be inserting n items into a HashSet or HashMap is to initialize the structure with a capacity of n. This guarantees that Java will end up re-allocating the index since the default load factor in Java is 0.55 meaning that once you have 0.55×capacity elements in your collection it will resize.
  - veltas 5y ago
    I said 'sorted' but I meant balanced as well. And even if you can 'attack' still, there is a limit to how slow it can get. Worst case O(log n) is not bad. As for security, I can't speak to its efficacy, but I know it's appropriate for real-time applications.
  - a1369209993 5y ago
    > inserting n items into a HashSet or HashMap is to initialize the structure with a capacity of n. That's actually a bug in HashMap (either the implementation or the spec). If you ask a structure to reserve space for n elements, that means it should should reserve enough space to actually store n elements (so n/0.55 in this case). If the method actually does mean to set the internal, implementation-detail capacity rather than the real capacity, then the specification is buggy, because that's largely useless unless you're relying on implementation details (as demonstrated).
    - tialaramex 5y ago
      Here's what Oracle says for JDK8: "When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets." and it explicitly tells you that HashMap will default to 0.75 load factor, therefore the documentation is telling you that HashMap(400) is not a suitable container for 400 items but only up to 300 items. Now, it's true that e.g. Rust's HashMap::with_capacity(400) is actually a container which promises it's suitable for 400 items‡ and that's more ergonomic, but I don't think we can call Java's choice here a mistake, it's just harder to use correctly. ‡"The hash map will be able to hold at least capacity elements without reallocating".
      - dhosek 5y ago
        Based on some benchmarking details¹ for my application, it appears that Rust is willing to completely fill its hashmap. It may be that my use case is somewhat unusual in that I'm expecting most requests to not return a value,² but I found that just specifying a larger initial capacity dramatically sped up the application (I got a bigger speed boost from that than I did from switching from SipHash to FNV). 1. https://www.finl.xyz/2021/09/30/building-a-trie-in-rust-optimizations/ https://www.finl.xyz/2021/09/30/building-a-trie-in-rust-opti... 2. And since this won't be the only char-indexed map in the application, I will have to revisit this.
kgeist 5y ago
Can't you simply salt the output of your simple hash function with a randomly-pregenerated salt value? (can be unique for each hashtable, a simple integer to be xored) That way the attacker can't predict the collision and you have same performance as before.
- haberman 5y ago
  A key result of the SipHash paper is that the SipHash authors broke common hash functions so completely that they can generate seed-independent multicollisions. That means that certain inputs will collide regardless of what the seed is. Seeding the hash function is no defense against such an attack.
- wongarsu 5y ago
  If you salt the output, wouldn't anything that collided before salting also collide after salting? Surely you would salt the input of the hash function? The effectiveness of that kind of depends on your hash function. SipHash tries to give you guarantees that your salt is effective and stays secret even if hashes (along with unhashed values) ever get exposed to the attacker
- wyager 5y ago
  If you scramble the output of the hash function, it has to be in a way that does not commute with the mapping from hash to bucket index. Xor won’t cut it for power of two sized hash tables. Should probably just use a keyed hash function like siphash - the security analysis is straightforward and these hash functions are quite well developed.
  - deleted 5y ago
    [deleted]

pansa2 5y ago

SipHash is considerably slower than an unkeyed hash function, isn’t it? One idea I had to avoid its overhead is to use double hashing, with a fast primary hash and SipHash as the secondary hash. Naïvely this feels as though it should provide good performance in the common case and also good security - even if there are many primary hash collisions, they won’t also be secondary hash collisions. Does anyone know if there is an analysis of this approach anywhere?

veltas 5y ago

Another alternative is not using a hash table, and instead using a sorted binary tree or similar, which tends to be slower on average but has worst case O(log n) lookup, O(log n) insertion. Depends on your criteria.

dhosek 5y ago
That depends on the implementation. If it's a simple binary tree, the worst case is O(n), not O(log n) since if you insert data in sorted order everything will always be in the left branch. O(log n) is average lookup time. If you have a specialized tree structure like a red-black tree which will automatically balance, this will improve, but sorted input is still a viable attack method. That said, a lot depends on the application and one should pick a hash function wisely. A binary tree–mapped hash table works best when you want to be able to iterate on keys in sort order or find an entry that's just before or just after a non-existent key in sort order. It's not really a good defense against hash attacks. On the flip side, the default hasher in Rust is hardened against hash attacks, but it's overkill for most applications and can cause severe performance degradation (although at least the library documentation is clear on this and points at alternative hash implementations for such cases). Unfortunately, the Rust resizing algorithm is flawed and won't resize until the hash capacity is completely full¹ making hash collisions much more likely. I had a doubling of performance in benchmarking some code that I was writing just by increasing the initial capacity of the map. ⸻⸻⸻ 1. A common mistake I see Java developers make is, when they know they'll be inserting n items into a HashSet or HashMap is to initialize the structure with a capacity of n. This guarantees that Java will end up re-allocating the index since the default load factor in Java is 0.55 meaning that once you have 0.55×capacity elements in your collection it will resize.
- veltas 5y ago
  I said 'sorted' but I meant balanced as well. And even if you can 'attack' still, there is a limit to how slow it can get. Worst case O(log n) is not bad. As for security, I can't speak to its efficacy, but I know it's appropriate for real-time applications.
- a1369209993 5y ago
  > inserting n items into a HashSet or HashMap is to initialize the structure with a capacity of n. That's actually a bug in HashMap (either the implementation or the spec). If you ask a structure to reserve space for n elements, that means it should should reserve enough space to actually store n elements (so n/0.55 in this case). If the method actually does mean to set the internal, implementation-detail capacity rather than the real capacity, then the specification is buggy, because that's largely useless unless you're relying on implementation details (as demonstrated).
  - tialaramex 5y ago
    Here's what Oracle says for JDK8: "When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets." and it explicitly tells you that HashMap will default to 0.75 load factor, therefore the documentation is telling you that HashMap(400) is not a suitable container for 400 items but only up to 300 items. Now, it's true that e.g. Rust's HashMap::with_capacity(400) is actually a container which promises it's suitable for 400 items‡ and that's more ergonomic, but I don't think we can call Java's choice here a mistake, it's just harder to use correctly. ‡"The hash map will be able to hold at least capacity elements without reallocating".
    - dhosek 5y ago
      Based on some benchmarking details¹ for my application, it appears that Rust is willing to completely fill its hashmap. It may be that my use case is somewhat unusual in that I'm expecting most requests to not return a value,² but I found that just specifying a larger initial capacity dramatically sped up the application (I got a bigger speed boost from that than I did from switching from SipHash to FNV). 1. https://www.finl.xyz/2021/09/30/building-a-trie-in-rust-optimizations/ https://www.finl.xyz/2021/09/30/building-a-trie-in-rust-opti... 2. And since this won't be the only char-indexed map in the application, I will have to revisit this.

kgeist 5y ago

Can't you simply salt the output of your simple hash function with a randomly-pregenerated salt value? (can be unique for each hashtable, a simple integer to be xored) That way the attacker can't predict the collision and you have same performance as before.

haberman 5y ago
A key result of the SipHash paper is that the SipHash authors broke common hash functions so completely that they can generate seed-independent multicollisions. That means that certain inputs will collide regardless of what the seed is. Seeding the hash function is no defense against such an attack.
wongarsu 5y ago
If you salt the output, wouldn't anything that collided before salting also collide after salting? Surely you would salt the input of the hash function? The effectiveness of that kind of depends on your hash function. SipHash tries to give you guarantees that your salt is effective and stays secret even if hashes (along with unhashed values) ever get exposed to the attacker
wyager 5y ago
If you scramble the output of the hash function, it has to be in a way that does not commute with the mapping from hash to bucket index. Xor won’t cut it for power of two sized hash tables. Should probably just use a keyed hash function like siphash - the security analysis is straightforward and these hash functions are quite well developed.
- deleted 5y ago
  [deleted]