bytes/hash: upper 32-bits of Hash result are independent of seed on 32-bit CPUs

[mdempsky]

Package bytes/hash claims:

// All bits of the Hash result are close to uniformly and
// independently distributed, so can be safely restricted to a range
// using bit masking, shifting, or modular arithmetic.

This is false on 32-bit CPUs:

package main

import "bytes/hash"

func main() {
	for i := 0; i < 10; i++ {
		h := hash.New()
		h.AddString("foo")
		println(h.Hash() >> 32)
	}
}

$ GOARCH=386 go run x.go
2561895305
2561895305
2561895305
2561895305
2561895305
2561895305
2561895305
2561895305
2561895305
2561895305

This is because hash.New() only generates 32 bits of entropy (all in the lower 32-bits of seed), so the "hi" computation in hash.rthash does not involve any entropy.

Mixing lo/hi like the TODO comment says would address this, but the simpler fix would be to generate 64-bits of entropy.

[mdempsky]

/cc @randall77 @alandonovan @FiloSottile

[randall77]

The"uniformly and independently distributed" is intended to apply to changing the key, not the seed. There is no claim of even distribution of bits when changing the seed. Perhaps that could be worded better. For use in a hash table, it is the distribution when varying the key that matters.

But yes, we want to have at least some result dependence on seed, to thwart collision attacks. It need not be as perfect as the key dependence.

[gopherbot]

Change https://golang.org/cl/202577 mentions this issue: bytes/hash: initialize all 64 bits of hash seed