Randomize hashes of strings (DoS vulnerability)

[oprypin]

Explanation, taken from Python

By default, the __hash__() values of str, bytes and datetime objects are “salted” with an unpredictable random value. Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python.

This is intended to provide protection against a denial-of-service caused by carefully-chosen inputs that exploit the worst case performance of a dict insertion, O(n^2) complexity. See http://www.ocert.org/advisories/ocert-2011-003.html for details.

See also PYTHONHASHSEED.

In the linked document, it can be seen that Ruby and many other programming languages had this vulnerability fixed.

$ echo '2.times { p "a".hash }' | ruby
2546372741366295617
2546372741366295617
$ echo '2.times { p "a".hash }' | ruby
-3656422326255655719
-3656422326255655719
$ echo '2.times { p "a".hash }' | crystal eval
97
97
$ echo '2.times { p "a".hash }' | crystal eval
97
97

A similar change should probably be introduced to Crystal.

[will]

An alternative is to use djb's crit-bit trees https://cr.yp.to/critbit.html

From the "Putting crit-bit trees to work" section:

A hash table supports insertion, deletion, and exact searches. A crit-bit tree supports insertion, deletion, exact searches, and ordered operations such as finding the minimum. Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data.

[faustinoaq]

@spalladino This issue Ain't better in topic:security since could be a vulnerability

[ysbaddaden]

Granted.

[akzhan]

Crystal String.hash uses algorithm that vulnerable to hashDoS.

Ruby and Rust uses Siphash.

Perl 5.26 just released with good improvement:

We have switched to a hybrid hash function to better balance performance for short and long keys.

For short keys, 16 bytes and under, we use an optimised variant of One At A Time Hard, and for longer keys we use Siphash 1-3. For very long keys this is a big improvement in performance. For shorter keys there is a modest improvement.

[vladfaust]

No 1.0 unless it's fixed?