50

I recently read the Rust language documentation and saw this:

By default, HashMap uses a cryptographically secure hashing function that can provide resistance to Denial of Service (DoS) attacks. This is not the fastest hashing algorithm available, but the trade-off for better security that comes with the drop in performance is worth it.

As someone with no background in systems languages, I've never heard of in memory attacks based on the wrong hashing algorithm. So I got some questions:

How does the secure hashing algorithm prevent a DoS or any other attacks?

When should I opt for a more secure hash over a faster one?

47

Sometimes applications use untrusted data as the key in a hash map. A simple implementation can allow the untrusted data to cause a denial of service attack.

Hash maps are fast - O(1) - in the best case, but slow - O(n) - in the worst case. This is because keys are normally in separate buckets, but some values can result in the same hash - a collision - which are handled by a slower linked list. With random data, collisions will be uncommon. However, some implementation have a vulnerability where malicious data can cause many collisions, which makes the hash map slow. Some years ago there was a Linux kernel DoS due to this.

The root cause of the Linux vulnerability was that hashing was predictable. It was fixed by introducing a key into the hash function that a remote user would not know. I don't know exactly how Rust hash maps work, but I expect they use a similar kind of keyed hash.

You should opt for a more secure hash any time you're using untrusted data as a key.

  • 3
    It's worth mentioning that some hashmap implementations put binary trees instead of linked lists in the buckets, which ensures that the performance doesn't degrade too much even if there are lots of collisions. Then what hash you use matters less. – Ben Millwood Oct 5 '18 at 14:11
  • 14
    @BenMillwood: The downside of that approach is that you need not just a hashing function for your elements, but also an ordering function. – MSalters Oct 5 '18 at 14:27
  • 3
    Would it make sense for an implementation to start by using a fast and simple hash function, but buckets which exceed e.g. 25 elements using a hash table based on a better (but slower) hash function? If 90% of the items in your table end up well distributed through N-1 buckets, but the other 10% end up in the remaining bucket, such an approach would offer better retreival performance for 90% of the buckets than would using the better hash function, but offer the advantages of the slower hash function when processing the problematic 10%. – supercat Oct 5 '18 at 19:13
  • 3
    Details: the Rust HashMap implementation is generic over a "HashBuilder" argument, which defaults to a builder that is (1) seeded randomly and (2) uses SipHash (2-4?) to prevent the ability from an attacker to build collisions off-line. – Matthieu M. Oct 6 '18 at 17:42
  • 1
    @alephzero: Compute the cheap hash for the key, and find the appropriate bucket. If the bucket is an "ordinary" bucket, check each item in the bucket against the key. If the bucket is a reference to a second hash table, then compute the expensive hash for the key and use it to find the item in that table. – supercat Oct 6 '18 at 22:52
35

Insert, search, and remove operations on hash tables have O(n) worst case behavior. If an attacker can choose keys to be inserted into a hash table and they can compute the hash function themselves then that creates an opportunity for denial of service. All they need to do is choose keys that map to the same bucket.

The quote suggests that the use of a cryptographic hash algorithm (SHA, MD5, Blake, Skein, etc.) solves the problem. That interpretation is totally incorrect. The algorithm that Rust's HashMap uses is called SipHash. It is a hash algorithm. And it is a cryptographic algorithm. But it is not a cryptographic-hash-function. The correct term for SipHash in the world of cryptography is PRF.

The key difference is that (in cryptography) all the details of a hash function may be public knowledge. A PRF, on the other hand, requires a secret key. Without the secret information there is no way to anticipate, for any input, what the output will be. (All the other details are public.)

Something like SHA-2 will not prevent denial of service. It will be totally unbiased for non-adversarial inputs. (Because cryptographic hash functions can be modelled as random oracles.) However anyone can evaluate plain SHA-2, so someone can find hash table collisions by brute force.

The fact that a cryptographic hash function is collision resistant (with at least 256-bit output) doesn't translate to a lack of collisions in the case of hash tables. Ultimately your hash function, for a table with n buckets, will be reduced to one of n possible values. By trial and error you can find an input that maps to a specific bucket about once every n tries. No hash tables use enough buckets to make this impossible.

Using an un-keyed hash function is inherently vulnerable to denial of service, no matter how good the hash function is. The fact that the attacker and server-with-a-hash-map both query the same oracle enables a DOSer to use specifically chosen inputs to tie up your CPU.

PRFs like SipHash don't have this vulnerability if used correctly. The server uses an oracle/function chosen from a pool of 2128 possible functions. To exploit a PRF based (hash-table-)hash-function the attacker either needs to guess which of the 2128 functions he should be using (a "key recovery") or to find a bias in the PRF independent of the key (a way to distinguish the PRF from a random oracle).

Finally, there exists more confusing nuances involving hash algorithms. But summarized simply:

  • Cryptographic hash functions are a subset of all ordinary hash functions
  • Under the classical definition of cryptographic hash function the randomness isn't required. However randomness is a feature of all big-name cryptographic hash functions anyway.
  • Not all PRFs are cryptographic hash functions
  • Not all cryptographic hash functions are PRFs
  • An algorithm can have the properties of a PRF and a cryptographic hash function.
    • Blake2, Skein, and KMAC have both sets of properties
    • The SHA-2 and SHA-3 families are examples of (unkeyed) cryptographic hash functions
    • SipHash is only a PRF (and an ordinary, but not cryptographic, hash function)
  • A PRF can be constructed using typical cryptographic hash functions, but the hash function itself is not necessarily a PRF.
  • "Randomized hashing" and "universal hashing" are similar to PRFs in some ways, but they don't have the same security requirements.
  • 2
    You got my upvote, even though you totally neglected Java's HashMap that uses a balanced tree instead of a linked list: openjdk.java.net/jeps/180 ...in fact, my opinion is that it's better to use as fast hash function as possible (i.e. MurmurHash3) and handle collisions using a balanced tree than it is to use a slow hash function (i.e. SipHash) and handle collisions using a linked list. – juhist Oct 6 '18 at 12:26
18

I agree that's a little vague and it's going to heavily depend on how the hashmaps are used.

Here's my guess: say you're taking some input from users, say [Firstname.Lastname] and using that as the lookup value in your hash table. Let's say you're building your hash table using the simple hash function that takes initials so that [Firstname.Lastname] --> FL then it would be easy for an attacker to submit loads of values that all hash to the same thing. That would essentially turn your hashtable into a list which negates all the performance gains of using a hashtable. Slow lookups = denial of service.

AA -> [ ]
AB -> [ ]
...
FK -> [ ]
FL -> [First.Last, F1.F2, F1.F2, Fanotheu.Lonteuh, ...]
FM -> [ ]
...
ZZ -> [ ]

Cryptographic hash functions are specifically designed to prevent this because it's very hard to construct two different inputs that have the same hash value (called collisions).


When should I opt for a more secure hash over a faster one?

The answer is simple: opt for a cryptographic hash any time the lookup value is supplied by users and could be maliciously crafted. If the lookup values are coming from some internal source that you trust to be non-malicious and evenly distributed, then you can use a faster hash.

  • I don't know who to accept for this very reason. Thank you to you both! The answers are both helpful. I go for paj28's answer, for the explanation with O(1) vs O(n) and the explicit statement that it becomes a linked list. In the end, I had to decide... – Greaka Oct 5 '18 at 13:12
  • HAHA! That's awesome. – Mike Ounsworth Oct 5 '18 at 13:13
  • 2
    F1.L1, F2.L2 maybe? – enkryptor Oct 5 '18 at 21:50
  • @enkryptor oh, oops. Not worth bumping it to the home page for a minor edit like that though. – Mike Ounsworth Oct 5 '18 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.