Why Go Randomizes Map Iteration: The Attack It Prevents

TL;DR: Every map gets a random hash seed and every range starts at a random offset, both from the runtime’s per-M ChaCha8 generator. The seed stops an attacker who controls your keys from piling them into one bucket; the random start stops an attacker who has measured your map from predicting the order you will visit keys in.

Write this loop and run it twice:

text
for k, v := range m {
    fmt.Println(k, v)
}

You will get a different order every time. That is not a bug, it is not “undefined behaviour” in the C sense, and it is not there to make your life harder. It is the defence against a denial-of-service attack that has a name, a CVE number, and a history.

The spec’s promise

The Go specification is deliberately vague, and the vagueness is the point:

html
<!-- doc/go_spec.html:6843 -->
The iteration order over maps is not specified
and is not guaranteed to be the same from one iteration to the next.
If a map entry that has not yet been reached is removed during iteration,
the corresponding iteration value will not be produced. If a map entry is
created during iteration, that entry may be produced during the iteration or
may be skipped. The choice may vary for each entry created and from one
iteration to the next.
If the map is <code>nil</code>, the number of iterations is 0.

“not specified” plus “not guaranteed to be the same from one iteration to the next” is a promise that the implementation will deliberately vary the order. If it did not, code that happened to depend on insertion order would silently break, and — much more importantly — code that depended on it would be a security problem in someone else’s server.

The two random mechanisms

It is easy to conflate two separate mechanisms that both come from the runtime’s random number generator. They defend against different attacks.

Mechanism	Where it lives	What it defends against
Per-map hash seed	`Map.seed`, mixed into every key hash	Hash flooding: attacker picks keys that all land in one bucket
Random iteration start	`Iter.entryOffset`, `Iter.dirOffset`	Order prediction: attacker guesses which key you will process first

The first is about performance. The second is about disclosure.

The hash seed

Every Map gets a random seed when it is created:

go
// src/internal/runtime/maps/map.go:283
func NewMap(mt *abi.MapType, hint uintptr, m *Map, maxAlloc uintptr) *Map {
	if m == nil {
		m = new(Map)
	}

	m.seed = uintptr(rand())

	if hint <= abi.MapGroupSlots {
		// A small map can fill all 8 slots, so no need to increase
		// target capacity.
		//
		// In fact, since an 8 slot group is what the first assignment
		// to an empty map would allocate anyway, it doesn't matter if
		// we allocate here or on the first assignment.
		//
		// Thus we just return without allocating. (We'll save the
		// allocation completely if no assignment comes.)

		// Note that the compiler may have initialized m.dirPtr with a
		// pointer to a stack-allocated group, in which case we already
		// have a group. The control word is already initialized.

		return m
	}

and the seed is stored alongside the map’s contents:

go
// src/internal/runtime/maps/map.go:214
type Map struct {
	// The number of filled slots (i.e. the number of elements in all
	// tables). Excludes deleted slots.
	// Must be first (known by the compiler, for len() builtin).
	used uint64

	// seed is the hash seed, computed as a unique random number per map.
	seed uintptr

The seed is then passed to the runtime’s hasher for every key operation:

go
// src/internal/runtime/maps/runtime.go:106
	hash := typ.Hasher(key, m.seed)

Without the seed, the hash of a key is a pure function of the key’s bytes. An attacker who can submit keys — a username, a URL path, a product code — can compute their hashes offline and find a set that all collide into one bucket. Then a map with a thousand of those keys degrades from O(1) lookups to a thousand-element linear scan per lookup, and the server’s CPU melts. That is the algorithmic complexity attack, and it is the class of bug that Kubernetes tracked as CVE-2019-11253.

With the seed, the attacker cannot predict which bucket a key will land in, because the whole hash function’s output is shifted by a per-process, per-map random value. The collision-finding attack has to be performed against the live map, at full cost per attempt, instead of offline.

The seed is also refreshed in a couple of interesting places — Delete and Clear both roll a new one:

go
// src/internal/runtime/maps/map.go:786
	m.seed = uintptr(rand())

so an attacker cannot accumulate knowledge of one map’s layout across a long-lived process.

The random iteration start

Now the second mechanism. The iterator is a struct that carries two random offsets:

go
// src/internal/runtime/maps/table.go:704
type Iter struct {
	key  unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
	elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
	typ  *abi.MapType
	m    *Map

	// Randomize iteration order by starting iteration at a random slot
	// offset. The offset into the directory uses a separate offset, as it
	// must adjust when the directory grows.
	entryOffset uint64
	dirOffset   uint64

	// Snapshot of Map.clearSeq at iteration initialization time. Used to
	// detect clear during iteration.
	clearSeq uint64

	// Value of Map.globalDepth during the last call to Next. Used to
	// detect directory grow during iteration.
	globalDepth uint8

	// dirIdx is the current directory index, prior to adjustment by
	// dirOffset.
	dirIdx int

	// tab is the table at dirIdx during the previous call to Next.
	tab *table

	// group is the group at entryIdx during the previous call to Next.
	group groupReference

	// entryIdx is the current entry index, prior to adjustment by entryOffset.
	// The lower 3 bits of the index are the slot index, and the upper bits
	// are the group index.
	entryIdx uint64
}

Two offsets, for two different index spaces. entryOffset randomises where inside the slot space you start; dirOffset randomises which table in the directory you start with. They have to be separate because the directory can grow during iteration, and a single offset would then be ambiguous.

Both are rolled once, at iterator initialisation:

go
// src/internal/runtime/maps/table.go:740
// Init initializes Iter for iteration.
func (it *Iter) Init(typ *abi.MapType, m *Map) {
	it.typ = typ

	if m == nil || m.used == 0 {
		return
	}

	dirIdx := 0
	var groupSmall groupReference
	if m.dirLen <= 0 {
		// Use dirIdx == -1 as sentinel for small maps.
		dirIdx = -1
		groupSmall.data = m.dirPtr
	}

	it.m = m
	it.entryOffset = rand()
	it.dirOffset = rand()
	it.globalDepth = m.globalDepth
	it.dirIdx = dirIdx
	it.group = groupSmall
	it.clearSeq = m.clearSeq
}

Two rand() calls, one for each offset. Nothing else about the iteration is random: once the offsets are fixed, the walk is completely deterministic.

Where the offsets get used

The directory offset picks the first table:

go
// src/internal/runtime/maps/table.go:979
	// Continue iteration until we find a full slot.
	for ; it.dirIdx < it.m.dirLen; it.nextDirIdx() {
		// Resolve the table.
		if it.tab == nil {
			dirIdx := int((uint64(it.dirIdx) + it.dirOffset) & uint64(it.m.dirLen-1))
			newTab := it.m.directoryAt(uintptr(dirIdx))
			if newTab.index != dirIdx {
				// Normally we skip past all duplicates of the
				// same entry in the table (see updates to
				// it.dirIdx at the end of the loop below), so
				// this case wouldn't occur.
				//
				// But on the very first call, we have a
				// completely randomized dirIdx that may refer
				// to a middle of a run of tables in the
				// directory. Do a one-time adjustment of the
				// offset to ensure we start at first index for
				// newTable.
				diff := dirIdx - newTab.index
				it.dirOffset -= uint64(diff)
				dirIdx = newTab.index
			}
			it.tab = newTab
		}

Note the & uint64(it.m.dirLen-1) — a mask, not a modulo, because dirLen is a power of two. And note the comment: the first table is chosen completely at random, and then the offset is adjusted so the walk does not visit the same logical table twice.

The entry offset picks the first slot within a table:

go
// src/internal/runtime/maps/table.go:1025
		entryIdx := (it.entryIdx + it.entryOffset) & entryMask
		slotIdx := uintptr(entryIdx & (abi.MapGroupSlots - 1))
		if slotIdx == 0 || it.group.data == nil {
			// Only compute the group (a) when we switch
			// groups (slotIdx rolls over) and (b) on the
			// first iteration in this table (slotIdx may
			// not be zero due to entryOffset).
			groupIdx := entryIdx >> abi.MapGroupSlotsBits
			it.group = it.tab.groups.group(it.typ, groupIdx)
		}

Again a mask, because the table capacity is a power of two. And note slotIdx == 0 || it.group.data == nil — the group is only recomputed when the slot index rolls over or on the very first iteration, which is where entryOffset makes the group index start somewhere unexpected.

Small maps — those that fit in a single group — take a simpler path, but still use the offset:

go
// src/internal/runtime/maps/table.go:886
	if it.dirIdx < 0 {
		// Map was small at Init.
		for ; it.entryIdx < abi.MapGroupSlots; it.entryIdx++ {
			k := uintptr(it.entryIdx+it.entryOffset) % abi.MapGroupSlots

			if (it.group.ctrls().get(k) & ctrlEmpty) == ctrlEmpty {
				// Empty or deleted.
				continue
			}

(entryIdx + entryOffset) % MapGroupSlots — a rotation of the eight slots of the group. So even a three-element map comes out in a random order.

The runtime’s random numbers

rand() here is the runtime’s own generator, linked in by linkname:

go
// src/internal/runtime/maps/runtime.go:22
//go:linknamestd bootstrapRand runtime.bootstrapRand
func bootstrapRand() uint64

//go:linkname rand
func rand() uint64

and it is the per-M ChaCha8 stream, not math/rand:

go
// src/runtime/rand.go:156
// rand returns a random uint64 from the per-m chacha8 state.
// This is called from compiler-generated code.
//
// Do not change signature: used via linkname from other packages.
//
//go:nosplit
//go:linkname rand
func rand() uint64 {
	// Note: We avoid acquirem here so that in the fast path
	// there is just a getg, an inlined c.Next, and a return.
	// The performance difference on a 16-core AMD is
	// 3.7ns/call this way versus 4.3ns/call with acquirem (+16%).
	mp := getg().m
	c := &mp.chacha8
	for {
		// Note: c.Next is marked nosplit,
		// so we don't need to use mp.locks
		// on the fast path, which is that the
		// first attempt succeeds.
		x, ok := c.Next()
		if ok {
			return x
		}
		mp.locks++ // hold m even though c.Refill may do stack split checks
		c.Refill()
		mp.locks--
	}
}

Each OS thread (m) has its own ChaCha8 state, so two goroutines on different threads never contend for a lock to get a random number, and the numbers are not correlated in a way an attacker could exploit. The runtime even keeps a separate, cheaper generator for the places where quality does not matter:

go
// src/runtime/rand.go:212
// cheaprand is a non-cryptographic-quality 32-bit random generator
// suitable for calling at very high frequency (such as during scheduling decisions)
// and at sensitive moments in the runtime (such as during stack unwinding).
// it is "cheap" in the sense of both expense and quality.
//
// cheaprand must not be exported to other packages:
// the rule is that other packages using runtime-provided
// randomness must always use rand.
//
// cheaprand should be an internal detail,
// but widely used packages access it using linkname.
// Notable members of the hall of shame include:
//   - github.com/bytedance/gopkg
//
// Do not remove or change the type signature.
// See go.dev/issue/67401.
//
//go:linkname cheaprand
//go:nosplit
func cheaprand() uint32 {

Map iteration does not use cheaprand. It uses rand, the good one.

The compiler’s entry point

The compiler-generated code for range goes through the runtime:

go
// src/runtime/map.go:142
// mapIterStart initializes the Iter struct used for ranging over maps and
// performs the first step of iteration. The Iter struct pointed to by 'it' is
// allocated on the stack by the compilers order pass or on the heap by
// reflect. Both need to have zeroed it since the struct contains pointers.
func mapIterStart(t *abi.MapType, m *maps.Map, it *maps.Iter) {
	if raceenabled && m != nil {
		callerpc := sys.GetCallerPC()
		racereadpc(unsafe.Pointer(m), callerpc, abi.FuncPCABIInternal(mapIterStart))
	}

	it.Init(t, m)
	it.Next()
}

Init rolls the offsets, Next takes the first step. reflect uses the same entry points, so reflect.Value.MapRange is randomised too.

The `maps` package inherits it

The generic maps package does not reimplement anything — it just ranges:

go
// src/maps/iter.go:9
// All returns an iterator over key-value pairs from m.
// The iteration order is not specified and is not guaranteed
// to be the same from one call to the next.
func All[Map ~map[K]V, K comparable, V any](m Map) iter.Seq2[K, V] {
	return func(yield func(K, V) bool) {
		for k, v := range m {
			if !yield(k, v) {
				return
			}
		}
	}
}

The doc comment states the contract; the mechanism is the runtime’s. maps.Keys, maps.Values, maps.Collect and maps.Insert all inherit the same randomisation for free.

Trade-offs

What the randomness buys:

Hash-flooding resistance. An attacker cannot precompute colliding keys, so a map keyed on untrusted input cannot be forced into O(n) behaviour.
Unpredictable ordering. Code that iterates a map to pick “the first” element, or to pick a random victim, does not accidentally become deterministic in a way an attacker can exploit. This is why map iteration order being stable was treated as a security bug every time it leaked.
No cost on the hot path. The offsets are computed once per range, not once per element. A million-element map costs two rand() calls plus two masked adds per table.

What it costs:

Tests that depend on order break. A test that asserts “the first key is a” is testing something the spec never promised. It will pass locally and fail in CI, or pass in CI and fail in production.
Snapshot-like reasoning is impossible. Two iterations of the same unmodified map give different orders, so you cannot zip them.
A tiny cost per range. Two rand() calls — a few nanoseconds — on every loop, including loops over three-element maps.

Caveats

The randomness is per iteration, not per map. Two range loops over the same map get different orders, but they are both drawn from the same per-map hash seed. The seed protects the layout; the offsets protect the order.

It is not cryptographic. The offsets come from the runtime’s ChaCha8 stream, which is a good generator but not a secrets API. If you need a cryptographically random choice of element, use crypto/rand, not map iteration order.

Small maps are randomised too. A map with one element has one order. A map with two has two. A map with three has six possible orders, all reachable.

maps.All and friends do not snapshot. An iterator over a map that is being mutated concurrently will not crash (the runtime detects concurrent map write and map iteration and throws), but a map mutated between two iterations can yield different sets.

Do not rely on “sorted-ish” behaviour. Some maps happen to iterate in a quasi-sorted order when the keys are small integers, because the hash of a small integer is roughly the integer. That is an artefact of the hasher, not a guarantee, and it disappears with strings, structs, or large integers.

The old implementation randomised differently. Before the Swiss-table rewrite, the runtime picked one random bucket and one random offset within that bucket. The current implementation picks a random directory index and a random slot offset. The guarantee is the same; the mechanism changed with the data structure.

Hash-flooding defence does not extend to your own data structures. The per-map seed protects Go maps. If you wrote your own hash table keyed by untrusted input, you have to randomise the hash yourself.

Wrapping up

The one thing to remember: two independent random mechanisms — a per-map hash seed that defeats hash flooding, and a per-iteration random offset that defeats order prediction — both fed by the runtime’s per-M ChaCha8 generator.

The part people get wrong: assuming the random order is a quirk of the old bucket implementation. It is a stated guarantee of the specification (“not guaranteed to be the same from one iteration to the next”), and it survived the complete rewrite of Go’s map internals.

What to go do about it: grep your tests for assertions that depend on map order and fix them — sort the keys first. Then, if you accept untrusted input as map keys, make sure you are on a Go version with per-map hash seeds (Go 1.14 and later), because that is the mechanism that actually stops the CPU-burning attack.