Faster hash function

[itamarst]

Given pervasive use of dicts, Python's hash function gets used a lot. There are faster alternatives than SIP 2-4, e.g. ahash: https://github.com/tkaitchuck/aHash#comparison-with-other-hashers

ahash is still in need of cryptographic analysis to prove it has same protection as SIP 2-4, but (from using it in Rust) switching definitely has a meaningful performance improvement on hashmap lookups.

[gvanrossum]

The string hash doesn’t need to be cryptographically secure, doesn’t it? We use hash randomization with a cryptographically secure seed.

[itamarst]

My understanding (not an expert) is that there is cryptographically secure (e.g. SHA-512 or whatever), and that's definitely irrelevant to this use case.

But then there's denial-of-service proof, which is a much lower bar but still requires some of the same mathematical/cryptographic analysis to prove? And you do want DoS-proof. And that analysis has been done for SIP 2-4, which is why it's everyone's current default, but not for ahash (although the latter's author believes that it's DoS-proof: https://github.com/tkaitchuck/aHash/wiki/How-aHash-is-resists-DOS-attacks).

[itamarst]

So what I meant to say in initial issue was not so much "ahash is cryptographically insecure" (since that's fine) but rather "ahash needs more analysis to prove it's DoS-proof".

[gvanrossum]

How would an attacker DoS me with an "insecure" hash, given that hash randomization's seed is secure?

…

On Mon, Sep 27, 2021 at 8:25 AM Itamar Turner-Trauring < ***@***.***> wrote: So what I meant to say in initial issue was not so much "ahash is cryptographically insecure" (since that's fine) but rather "ahash needs more analysis to prove it's DoS-proof". — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#88 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAWCWMVRGR7WP3NKSH763Y3UECEFDANCNFSM5E2NXBDQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

-- --Guido van Rossum (python.org/~guido)

[itamarst]

https://www.python.org/dev/peps/pep-0456/ has a bunch of details; just learned from reading it that for a bad hash, the seed can be recovered by an attacker.

[gvanrossum]

In that case, we should probably table this improvement until the security folks have had time to look at this.

[markshannon]

String hashing is done once per string, when strings are created. It doesn't impact dict performance. The C-level mutability of strings has much more of an impact.

Reducing the time to hash strings will improve startup times, though. That is when much hashing occurs.

[gvanrossum]

String hashing is done once per string, when strings are created.

Correction: it's done lazily. So typically on the first time the string is looked up in any dict (including interning). A value of -1 indicates that the hash hasn't been computed yet.

I wouldn't want to change this, since most strings aren't used to look anything up in a dictionary (e.g. when reading lines from a file).

[pitrou]

I may be wrong, but the ahash benchmarks seem to have been run with Rust implementations of the hash algorithms.

My impression is that xxh3 (the third iteration of xxHash) is both widely used and extremely fast: https://cyan4973.github.io/xxHash/
The xxHash wiki also elaborates on small-string performance, which is certainly relevant for Python:
https://github.com/Cyan4973/xxHash/wiki/Performance-comparison#benchmarks-concentrating-on-small-data-

Note: xxHash APIs accept an optional seed, making it keyable. I have no idea whether it's DoS-resistant.

[itamarst]

That might be a good solution too, yes, the main point is that it is likely possible to switch to a faster hash than currently used one while still preserving anti-DoS guarantees.

[methane]

On Tue, Sep 28, 2021 at 1:02 AM Guido van Rossum ***@***.***> wrote: How would an attacker DoS me with an "insecure" hash, given that hash randomization's seed is secure?

Attackers may guess the key by sending many hashes and measuring timings. So having seed is not enough for anti-HashDoS. FYI, I had made an issue to change the hash algorithm from SipHash-2-4 to SipHash-1-3, as Ruby and Rust had moved already. https://bugs.python.org/issue29410 Microbemchmark result: https://gist.github.com/methane/33c7b01c45ce23b67246f5ddaff9c9e7 Regards,

…

-- Inada Naoki ***@***.***>

[tiran]

Please be careful when comparing hashing performance benchmark. Some benchmarks show off with impressive numbers like X GB/sec throughput. Dictionary keys are usually short. AFAIK majority of dict key strings are in the range of 5 to 25 characters. Good hashing algorithms perform extra steps to finalize a hash in order to archive good diffusion. The finalization step is a fixed cost and impact short strings. SipHash-1-3 is already faster for shorter strings than SipHash-2-4. It performs one finalization round less.

[itamarst]

In my experience, when hashing 64-bit integers (equivalent to <8 char ASCII strings) ahash is faster than Rust's default hasher, which I believe is SipHash 1-3. So it's possible to have faster hashes than SipHash 1-3 even on latency measures of small data. Pretty sure xxh3 also does well on latency, though it doesn't graph a comparison to SipHash 1-3.

[markshannon]

I think we should wait until ahash has been comprehensively analyzed in the same way as siphash has been before we adopt it. Hopefully that will happen sooner rather than later.