On Thu, Feb 10, 2022 at 12:53:08AM +0000, Siarhei Siamashka via Digitalmars-d-learn wrote: > On Wednesday, 9 February 2022 at 21:05:47 UTC, Siarhei Siamashka wrote: > > Is the current implementation of associative arrays in D language > > resistant to Denial of Service hash collision attacks? > > Answering to myself. No, it isn't. Here's a simple example: [...] > ulong[] generate_bad_array(ulong n) > { > return iota(n).map!(x => (x << 46)).array; > } [...] > == adversarially constructed array == > n=100000, unique_elements=100000, assoc time: 22626 ms, rbtree time: 15 ms > ```
Nice investigation! This should be filed as a bug. I remember browsing through various hash functions in druntime before (built-in AA's use per-type hash functions), and many of them were trivial, which would imply that it's trivial to construct adversarial input that triggers a large number of collisions for various basic types. T -- Give me some fresh salted fish, please.