CRC functions are linear/affine. This means that they are trivial to construct collisions for and that it’s easy to accidentally write hashing constructs that have dangerous cancellation properties.
You can already do this. If you want to use a custom hash function with a given key type, then just wrap it in a HashKey type as I suggested above, use whatever hash function you want, and define isequal of your HashKey to any other type to be false.
I was just thinking of how to expose the built-in hash for people to use, where it doesn’t end up converting strings first to UTF-8.
I think that there are two separate issues there, one is about security, which, as we’ve discussed here, can’t really be solved just by changing the hashing function used, and the other one, do you have examples of that sort of thing occurring in practice?
I believe that for internal hash tables with string keys, CRC32C would be a very good choice, whereas it would be recommended to use a totally different hash table design and different hash algorithm for general hash tables that might be used for “external” data (and hence be open to attack).
Yes, this sort of thing has happened but I don’t have the examples on hand and it doesn’t warrant more than a few minutes of searching through issues.
We could certainly use a better hashing function than MurmurHash3, but the best choice is almost definitely not CRC32.
I tried something along those lines in WIP/RFC: Adding EgalDict{K,V} (aka ObjectIdDict{K,V}) by mauro3 · Pull Request #24932 · JuliaLang/julia · GitHub. I think an approach like that to dicts in Julia would be good (although that PR was lacking in other departments).
A lot of the discussion on Stack Overflow compared many different hashes, and a number of people did recommend CRC32C.
Until such a time as a better hash algorithm for Julia is decided upon (possibly FarmHash), do you think a PR to replace the current usage of MurmurHash3.c and replace it with the Julia version I have written would be well received? (You can look at the code in JuliaString/Strs.jl/src/murmurhash3.jl).
Besides simply translating the MurmurHash3 algorithm, I wrote code to hash generic AbstractString strings efficiently, by building up in registers a UTF-8 encoding on the fly, and also to more efficiently deal with unaligned strings. (I do have a little more work to do there, to write the unaligned version for 32-bit platforms, and to do some testing for 32-bit).
It’s nicely faster than the C version (the C version wasn’t really all that well written, it was doing things like XOR bytes into 64-bit values where it was known to be 0 already, just to pick up the trailing bytes, in a big switch, using falling through).
I also noticed something that I think might be a flaw in the design of MurmurHash3, but I’m not sure.
In the operation performed on each block, it is calculating h1, h2, h3, h4, but instead of doing it in such a way that the new values only depend on the previous round, h4 is calculated using the value of h1 from the current round, not the previous one. Not being a cryptographer, I’m not sure if that was the desired behavior or not, but it does have a performance effect, since it means that the 4 values cannot all be calculated in parallel (it might even cut in half the potential speed of the algorithm).
There are other “mixing” operations, where it does h1 += h2 ; h2 += h1, which don’t really seem to be the best way of mixing two 64-bit values, you really just end up with h1, h2 = h1 + h2, h1 + 2*h2, which seems to imply that h2 is not really that different from h1 after that step.
Although the specifics elude me at the moment, I know MurmurHash3 to be faulty in some way that matters us. I looked at this a few years ago and there are some non-cryptographic hashes that otherwise have good properties overall and in specific without found algorithmic clumsiness or sharper edges. And CRC-32 is not for this purpose.
While Julia may choose to embed a cryptographic protocol (hash + signature + a few others), it must provide a [preferably two, each with best features in nonoverlapping purpose] noncryptographic hash for more dynamic use where the question of crypto-strong is not key. When I hash the entries in a small dictionary – well go-ahead and reverse engineer it – I need fast and nonlikely collisions.
Going forward, we can apply the deeply elegant trait facility to allow data structures and packaged types some few choices in hashing.
Maybe Julia should switch to:
AHash is the fastest, DOS resistant hash currently available in Rust. AHash is intended exclusively for use in in-memory hashmaps.
Note, Python (and I believe Rust) use SipHash 1-3 since it’s cryptographic, but I understand that’s not really needed.
Note, regarding HashDoS Protection AI says “Strong (when hardware AES is available)”
and I suppose AES hardware is almost always available, or we could fallback to other for old CPUs.
This is always fastest according to their graph so no tradeoff.
It supports all our platforms:
nightly-arm-aes: To use AES instructions on 32-bit ARM, which requires nightly. This is not needed on AArch64.
I think the AES-NI instruction might be implemented here now:
AES-NI is now autodetected at runtime on i686/x86-64 platforms. If AES-NI is not present, the aes crate will fallback to a constant-time portable software implementation.
The string hash doesn’t need to be cryptographically secure, doesn’t it? We use hash randomization with a cryptographically secure seed.
[It doesn’t impact
dictperformance. 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.]
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).
Python switched from SipHash-2-4 to SipHash-1-3 in Python 3.11, which was released on October 24, 2022. And AI tells me Rust uses it too: Google Search
I’m quite skeptical of those benchmarks … they claim to be 10x faster than fxhash which is barely more than a multiply?
This gxhash might be even faster: See section 3 High ILP Construction in the paper: Reddit
Do they? No, or not my reading of the table (or the log plot, I think you must have misread).
It’s faster than fxhash, for all strings from 1-byte, but not for primitive types like u8 up to u64 (while faster for u128): aHash/FAQ.md at master · tkaitchuck/aHash · GitHub
Another is taking advantage of hardware instructions. When it is available aHash uses AES rounds using the AES-NI instruction. AES-NI is very fast (on an intel i7-6700 it is as fast as a 64 bit multiplication.) and handles 16 bytes of input at a time, while being a very strong permutation.
This is obviously much faster than most standard approaches to hashing, and does a better job of scrambling data than most non-secure hashes.
It’s however only 21% up to 2.17x faster for all lengths that already very fast fxhash, I see tested in this table except for the largest 1024 byte string, then 6.15x faster. Since the speed claim is central to this package, I doubt the timings are wrong.
I think this has to do with SIMD string handling. I only found the text “SIMD” in one place in the repo, so I suspect because less string related overhead because of this dependency it pointed to:
Fast, safe, compile error. Pick two.
In the code use zerocopy::transmute; and I suspect fxhash maybe doesn’t use such transmute (similar to our reinterpret; maybe more general, i.e. for strings too?) tricks (but could?). I hope I get an exception to post background from AI (that I believe is highly plausible, also not my place to prove what this code does or why it’s fast):
At its core,
zerocopy::transmuteis a compiler-safe wrapper for forcing a type-punning operation. It allows you to instantly convert a value of one type into another type of the exact same size by reinterpreting the raw memory bits—with zero runtime overhead, zero copying, and zerounsafeblocks.
How is it different from Rust’s built-in
std::mem::transmute?Rust has an official built-in function called
std::mem::transmute. However, the standard version is incredibly dangerous (unsafe).
I was going to suggest another, xxh3, but AI tells me, reminded me (so I guess nothing more to be done here), “In Julia v1.13, the language transitioned away from its legacy C-based MurmurHash3 algorithm for strings, replacing it with a far more modern design. .. Julia core contributors chose a modern approach heavily inspired by the design principles of rapidhash (a cutting-edge successor to wyhash, which is famously the default hash in ecosystems like Go, Zig, and Nim).”
“rapidhash is generally faster than xxHash (including XXH3)”