CC @golang/runtime @randall77

There are a bunch of discussions in #9365 about this. TL;DR we're not really providing a hash-flooding DoS guarantee, but we should probably mitigate easy seed-independent collisions (like this one is).

I also said:

I intend to add some startup randomness to the new hash functions once they are in. It should only require a judicious xor or two to add that in.

Which I haven't done. Maybe we should do that.

Which I haven't done. Maybe we should do that.

Maybe I did do that? And then it was undone by https://go-review.googlesource.com/c/go/+/279612

I did, it was https://go-review.googlesource.com/c/go/+/2344

@mengzhuo

Change https://go.dev/cl/579115 mentions this issue: runtime: make it harder to find collisions in the 64-bit fallback hash

Good finding!
Since original wyhash isn't crypto-safed hash algorithm, I think process-wide seeding is good enough to resolve hashmap collision attack as Keith's CL do.

@randall77 Thank you for the quick CL, but I'm wondering if this is a proper fix to this issue (I'm assuming it's OK to ping, do tell me otherwise).
I downloaded your patch and it definitely prevents the exact snippet I posted, but I believe there is a workaround. For example consider this example.

package main

import (
	"encoding/binary"
	"math/rand"
	"testing"
)

const (
	width = 1 << 10
)

var (
	sink bool
)

func BenchmarkMap(b *testing.B) {
	tab := make(map[string]bool, width)
	var keys [width]string
	for n := range width {
		var buf [48 + 16]byte
		// Must use this random 8 bytes on both buf[24:] and buf[40:].
		random := rand.Uint64()
		binary.LittleEndian.PutUint64(buf[16:], 0x8ebc6af09c88c6e3) // constant m3.
		binary.LittleEndian.PutUint64(buf[24:], random)
		binary.LittleEndian.PutUint64(buf[32:], 0x589965cc75374cc3) // constant m4.
		binary.LittleEndian.PutUint64(buf[40:], random)
		key := string(buf[:])
		keys[n] = key
		tab[key] = true
	}
	b.ResetTimer()
	b.ReportAllocs()
	for n := range b.N {
		sink = sink != tab[keys[n%width]]
	}
}

(Note: I didn't realize there was a GODEBUG env variable, so to reproduce, use a command like GODEBUG="cpu.aes=off" go test -bench . -count 10 instead.)
This will still report ~2000 ns/op, again. The cause is this part:

	seed1 := seed
	seed2 := seed
	for ; l > 48; l -= 48 {
		seed = mix(r8(p)^m2, r8(add(p, 8))^seed)
		seed1 = mix(r8(add(p, 16))^m3, r8(add(p, 24))^seed1)
		seed2 = mix(r8(add(p, 32))^m4, r8(add(p, 40))^seed2)
		p = add(p, 48)
	}
	seed ^= seed1 ^ seed2

Since it's doing seed1 ^ seed2, it's possible to collide the result, as long as seed1 and seed2 evaluates to the same value, without knowing secrets like seeds or hashkeys.
In this program, I made it so that the m3/m4 at the left side cancels, leaving the value just hashkey[1], and the r8(add(p, 24))^seed1 and r8(add(p, 40))^seed2 at the right side become the same value.

FYI it is based on

https://github.com/wangyi-fudan/wyhash/blob/408620b6d12b7d667b3dd6ae39b7929a39e8fa05/wyhash.h#L128-L135

      uint64_t see1=seed, see2=seed;
      do{
        seed=_wymix(_wyr8(p)^secret[1],_wyr8(p+8)^seed);
        see1=_wymix(_wyr8(p+16)^secret[2],_wyr8(p+24)^see1);
        see2=_wymix(_wyr8(p+32)^secret[3],_wyr8(p+40)^see2);
        p+=48; i-=48;
      }while(_likely_(i>=48));
      seed^=see1^see2;

Maybe we should replace hard-wired secret(primes) XORed process-wide seed?

	seed1 := seed
	seed2 := seed
	for ; l > 48; l -= 48 {
		seed = mix(r8(p)^m2^hashkey[1], r8(add(p, 8))^seed)
		seed1 = mix(r8(add(p, 16))^m3^hashkey[2], r8(add(p, 24))^seed1)
		seed2 = mix(r8(add(p, 32))^m4^hashkey[3], r8(add(p, 40))^seed2)
		p = add(p, 48)
	}
	seed ^= seed1 ^ seed2

Yeah, the long-key case can still get key-independent collisions.
Your fix sounds fine to me, xoring different process seeds into the different streams.
At that point, not sure what the point of ^mX even is. a ^ c ^ secret is completely equivalent to a ^ secret.