Make Hasher portable? (mini RFC)

[scottmcm]

Note that Hash not being portable is a good thing – .Net even took a breaking change to make .GetHashCode non-portable for many core types as part of security improvements.

it should be documented

If the docs are insufficiently clear, I’m sure PRs would be welcome to state the nonportability directly.

[Ixrec]

.Net even took a breaking change to make .GetHashCode non-portable for many core types as part of security improvements.

Is there a link you could post about this? It sounds very interesting but Google is completely failing to find it for me.

[scottmcm]

I can’t find any blogs about the change, but you can see the intentional non-portability in the reference source around the FEATURE_RANDOMIZED_STRING_HASHING define: https://referencesource.microsoft.com/#mscorlib/system/string.cs,836

Was probably around the time of CVE-2011-3414, an instance of “Collisions in HashTable May Cause DoS Vulnerability” in ASP.Net.

The docs for GetHashCode current explicitly mention

You should never persist or use a hash code outside the application domain in which it was created, because the same object may hash across application domains, processes, and platforms.

(though the version picker is broken so I can’t check old ones.)

[dhardy]

There’s keyed hashing (as our HashMap already uses) and there’s portable hashing. I’m not sure that there’s actually a real use case for anything in between though? It sounds like what you’re talking about is using keyed hashing.

[michaelwoerister]

This is fine for HashMap but useless for anything needing portable output (cryptographic hashes, checksums, file systems, etc.

We are using the Hasher trait in the compiler for platform independent hashes for quite a while now: https://github.com/rust-lang/rust/blob/c0955a34bcb17f0b31d7b86522a520ebe7fa93ac/src/librustc_data_structures/stable_hasher.rs#L78-L166

[drXor]

While I understand that “the compiler does it” is often used as a standard for the “correct” way of doing things in Rust, presumably it’s only like this because this issue was never brought up? It’s already wide-spread to make Hasher platform independent by overriding default trait methods, as mentioned above, but I think the case can be made that this is a bad status-quo (where it’s not clear that a random impl Hasher does not guarantee platform-independence) that should at least be documented. Certainly, it would be nice to be able to say in the trait bound “I want this Hasher to be platform-independent” by saying H: Digest instead of H: Hasher or what-have-you.

After all, in the Before Time, the compiler was full of @Ts.

[michaelwoerister]

I was just giving a counter-example to the statement saying that the Hasher trait was “useless for anything needing portable output”. I’m not saying that the documentation should not mention any pitfalls. But unless you take care of using a platform-independent hash algorithm implementation too, converting input parameters to little-endian won’t be enough. It might even lead to people wrongly assuming that they can forgo thinking about platform-specific concerns.

[Eh2406]

In cargo we also try to use hash for run to run identification, and it is annoying. That is on the same computer, but still; I personally would love to see a split between hash/digest trates, so we can only do the slow “make it consistent” when we are making a digest and use the fast tricks when inserting in a hashmap.

[drXor]

Yeah, that makes sense!

It might even lead to people wrongly assuming that they can forgo thinking about platform-specific concerns.

This makes me think that Digest should be an unsafe trait, to express the contract that it’s a platform-specific hasher.

[Soni]

uh what about compile-time constant hashmaps? those need portable, or at least deterministic, hashes, no?

[dhardy]

hash / digest

I don’t like this terminology. There is for example password hashing, which definitely needs to be portable.

what about compile-time constant hashmaps?

Do we have such a thing in Rust? If we did, they would indeed need to be portable. But there’s another issue: HashMap uses a hasher with random key, so for compile time usage the key would need to be fixed. For constants maps that wouldn’t matter, but for mutable ones it might make them vulnerable to DoS via hash collisions.

I still think just making Hasher portable by default is the nicest option.

[Eh2406]

I don’t like this terminology. There is for example password hashing, which definitely needs to be portable.

Indeed there is strong precedent for using hash to mean both things, that is why the hash trait is expected to do all things for all needs. If we decide to be more specific we will be braking with the existing terminology.

[drXor]

but for mutable ones it might make them vulnerable to DoS via hash collisions.

A const constructor for HashMap doesn’t make a lot of sense anyways, since HashMap is a glorified Vec. What it sounds like you want is an analogue of [T; n] for HashMap, which, in a compile-time setting, would be immutable: const TABLE: ConstMap<K, V, n> = const_map! { .. };. The correct thing to use for the mutable case is a static mut and maybe a Once or whatever.

Indeed there is strong precedent for using hash to mean both things, that is why the hash trait is expected to do all things for all needs. If we decide to be more specific we will be braking with the existing terminology.

Java actually follows the convention I describe: hashCode produces an ephemeral hash, while somewhere deep in javax.crypto you can dig up the Digest class, which supports SHA1 and friends. I think “digest” is prevalent enough as “platform-safe hash” that no one should be confused. And, let’s be honest: if you’re doing something actually dangerous like dealing with passwords, you should be double-checking that your chosen hash does what you want.

[kornel]

Does the trait guarantee order in which struct fields are hashed? Is it the source order or optimized memory layout order?

[Soni]

I’m talking about the Rust equivalent of “string switches” (as seen in Java).

[drXor]

Does the trait guarantee order in which struct fields are hashed? Is it the source order or optimized memory layout order?

That’s entirely dependent on the struct’s Hash implmentation; I don’t think #[derive(Hash)] makes any such assurance.

I’m talking about the Rust equivalent of “string switches” (as seen in Java).

This already exists:

match foo {
    "foo" => ..
}

IIRC this just does the obvious O(n) comparison. Using a hashmap for such a purpose is a bad idea: hashing will usually be slower than checking by equality anyways, and if your match is so big that a hashmap actually nets you a performance gain… your match is too big. A const HashMap is a good idea, but it should definitely not be generated by a match.

IIRC Java doesn’t use a hashmap to switch on strings but compiles it to a sequence of invokevirtuals, ifeqs, and gotos to emulate fall-through. It does do this for switching on enums, because the ordinal (a.k.a discriminant) of an enum is not fixed at compile time, because Java is linked at runtime. (Mind, I just ran example code through a disassembler so I could be completely wrong!)

[Soni]

Java didn’t always specify the String hashCode. But then Java 7 happened.

Because Java’s switch (s) {} (where s is a String) is a hashtable.

[drXor]

Fair, I actually wasn’t aware of that. I still don’t think this an appropriate optimization for Rust; Java has the advantage that a lot of strings are interned, and that Java’s String is really a (&'gc [u16], i32), since the result of the hashcode is cached. It sounds to me like what you want is best accomplished by a macro.

[Centril]

A const constructor for HashMap doesn’t make a lot of sense anyways, since HashMap is a glorified Vec .

Aside: But being able to construct Vecs and push to them inside a const fn does make sense so that you can build more interesting algorithms and execute them at compile. By the same rationale, HashMaps made and used at compile time also is useful.

[drXor]

Oh yes, this is definitely something I spent a long time thinking about while walking home the other day. I was actually wondering if we can somehow make Box<T> and friends abstract over “owned pointer to heap OR data segment”, probably by using the pointers in an invalid memory page. I’d really like to be able to say const XS: Vec<i32> = vec![1, 2, 3]; or something like that.