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.