up:: The Threat MOC

Multi-Target and Precomputation Attacks

Multi-target and precomputation attacks are the family of techniques where an attacker lowers the average cost of a break by spreading the work across many keys at once, or by doing the expensive part ahead of time and reusing it, rather than paying the full published cost to attack a single key in isolation. They matter because the security number quoted for an algorithm, its bit strength, usually describes the cost of attacking one target.

A real adversary rarely faces one target. They face a database of a million password hashes, or a fleet of a million devices sharing a key size, and if the cost of breaking one of the million is far below a million times the cost of breaking a specific one, the effective security is lower than the headline number suggests. This is the difference between a per-target cost and a batch cost, and quantum computing sharpens it because Grover’s algorithm has a multi-target form worth understanding precisely.

The short version:

• The bit strength quoted for an algorithm is usually the cost to break one target. Multi-target and precomputation attacks amortize work, so the cost to break one target out of many can be much lower, which is a different and often more realistic threat model.
• A precomputation attack pays a large cost once to build a table, then breaks any future target cheaply. Rainbow tables against unsalted password hashes are the classic case: build once, crack forever.
• The defense against precomputation is salting and domain separation. A per-user salt means every target needs its own table, which destroys the reuse that made the attack economical.
• Quantum multi-target search exists. Grover finding one preimage among t targets in a space of N costs about the square root of N over t, so batching genuinely helps an attacker, though the effect is bounded and defended by the same larger-margin logic that governs SHA-256 and AES-256.
• The practical takeaway is a design discipline: assume the attacker sees the whole population, salt and separate so work cannot be shared across targets, and size margins so that even amortized batch cost stays out of reach.

Picture a burglar facing an apartment building. Attacking one specific unit means picking that one lock, and the published “security” of the building is how long that takes. Now change the goal to getting into any one unit out of a thousand. If every unit uses an identical lock, the burglar files one master key once and every door opens, so the real security collapsed the moment the goal became any-one-of-many. If instead every unit has a lock keyed differently, the master-key trick fails and the burglar is back to picking locks one at a time. Salting is the building manager insisting on a different key for every unit. It does not make any single lock stronger, and it destroys the shortcut that made attacking the whole building cheap.

What is the difference between per-target and batch cost?

Per-target cost is the work to break one specific, named key. Batch cost is the work to break any one key out of a large set, and for many attacks the second number is dramatically smaller than the first multiplied by the set size. Conflating the two is the most common way a security estimate flatters itself, because the published bit strength of an algorithm almost always describes the per-target case.

Consider a concrete framing. If breaking one specific 60-bit-strength secret costs about 2^60 work, a naive reading says breaking one of a billion such secrets costs a billion times more. For a well-designed system that is roughly true, and the attacker gains little from the crowd. For a badly designed system it is wildly false: if the secrets were generated or stored so that one computation can test all of them at once, the cost of finding some victim among the billion can stay near 2^60, and the per-victim cost collapses by a factor close to a billion. The security of the population is only as good as the design that decides whether an attacker’s work can be shared across its members.

This is why a threat model has to state which cost it means. “128-bit security” is a reassuring phrase, but the honest question is whether it survives an adversary who is content to compromise any account, any device, or any session out of the whole fleet, rather than one you named in advance. That is the adversary who actually shows up.

Attack shape	Goal	What makes it cheap	The defense
Single target	Break one named key	Nothing shared, full published cost	Adequate key size
Precomputation	Break any future target	A table built once, reused forever	A unique per-target salt
Multi-target search	Break any one of many keys	Work shared across the whole set	Per-target randomness plus wider margins

How do precomputation and rainbow-table attacks work?

A precomputation attack front-loads the expensive part of a break into a one-time table that can then be reused against every future target for cheap, so the amortized cost per victim after the table exists is small. The canonical example is the rainbow table against password hashes, and it is worth walking because it makes the whole family concrete.

1. Build the table once. The attacker takes a hash function and a dictionary of candidate passwords, hashes an enormous set of them, and stores the results in a specially structured lookup (a rainbow table is a space-time-optimized form of this idea). This is expensive, but it happens a single time.
2. Crack every future target cheaply. When the attacker later steals a database of password hashes, they look each stolen hash up in the precomputed table. Any password that was in the original dictionary is recovered by a lookup rather than by fresh computation. A table built for one breach cracks the next breach, and the one after that, at nearly no marginal cost.
3. The economics is the point. The attack pays a huge fixed cost and a tiny per-target cost, so it becomes overwhelmingly worthwhile the moment the attacker has many targets. Against a database of millions of unsalted hashes, precomputation turns “crack a password” into “index a table.”

The reason this works is that every user who chose the same password produced the same hash, so a single stored answer serves all of them and serves every future database too. The attack is not a weakness in the hash function’s math. It is a consequence of using the hash in a way that lets one computation answer for many targets across all time.

How does salting and domain separation defeat it?

Salting defeats precomputation by making every target’s computation unique, so a table built for one target is worthless against any other and the reuse that made the attack economical disappears. A salt is a distinct random value, stored alongside each hash, that is mixed into the input before hashing, so two users with the identical password produce different stored values because their salts differ.

The effect on the attacker’s economics is total. A precomputed table is only useful if the same input maps to the same stored output for everyone, and a per-user salt breaks that correspondence: to use a rainbow table against a salted database, the attacker would have to build a separate table for every distinct salt, which multiplies the one-time cost by the number of targets and destroys the amortization. The expensive part stops being a one-time cost that everyone shares, so the attack collapses back toward attacking each target individually, which is exactly the per-target cost the defender wanted to force.

Domain separation is the same principle generalized past passwords. When a construction feeds a distinguishing label, a context string, a protocol identifier, into a hash or key-derivation step, it ensures that the same secret used in two different contexts produces two unrelated outputs, so an attacker cannot build one body of precomputed work or one captured value that transfers between contexts. Salting is domain separation across users; a protocol’s context labels are domain separation across uses. Both exist to guarantee that an attacker’s effort against one instance buys nothing against another, and both are why modern password storage combines a salt with a deliberately slow, memory-hard function rather than a bare fast hash.

Source: NIST, “Digital Identity Guidelines: Authentication and Lifecycle Management,” SP 800-63B (memorized-secret verifiers shall use salting and a suitable one-way key-derivation function for stored secrets), pages.nist.gov/800-63-3/sp800-63b.html.

Does Grover’s algorithm help an attacker batch targets?

Yes, and the multi-target form of Grover’s algorithm is the quantum version of this whole family, so it is worth stating with precision because it is easy to over- or under-claim. Grover’s algorithm searches an unstructured space of N possibilities in about the square root of N steps, and its multi-target variant, searching for any one of t marked items instead of one specific item, runs in about the square root of N divided by t steps. Batching the targets genuinely lowers the search cost, and the more targets, the cheaper finding some victim among them becomes.

That is a real effect, and it is also a bounded one. The speedup is still only quadratic in the underlying search, the same square-root advantage Grover gives on any unstructured search, so it dents rather than breaks. For a 256-bit symmetric key like AES-256, single-target Grover brings the effective strength to about 128 bits, and multi-target batching across a realistic fleet lowers it by a further modest factor, leaving a margin that no foreseeable machine threatens. NIST’s general read on Grover is that its speedup on unstructured search “does not render cryptographic technologies obsolete,” but “can have the effect of requiring larger key sizes, even in the symmetric key case,” and the multi-target sharpening is one more reason the remedy is a wider margin rather than a new algorithm.

Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, csrc.nist.gov/pubs/ir/8105/final.

The defense mirrors the classical one. Where salting stops classical precomputation from sharing work across targets, adequate key sizes and per-target randomness keep the batched quantum cost above reach, so a fleet standardized on 256-bit symmetric keys and properly separated per-target material stays safe even against an adversary who attacks the whole population at once with a quantum search.

Why is multi-target the more realistic threat model?

Because a real adversary is almost never handed one predetermined target and told to break exactly that one. They compromise a database, tap a network, or seize a device population, and their goal is to get into some account, read some session, or forge some token out of a large set, so the any-one-of-many cost is the cost that describes their actual situation. Designing to the single-target number quietly assumes the adversary’s problem is harder than it is.

The pattern shows up across the stack. A stolen password database is a multi-target problem the instant it lands, and it is exactly why salting is non-negotiable for stored secrets. A fleet of devices that shared a weak random number generator is a multi-target problem, because one flaw in the generator lets an attacker’s work against one device transfer to all of them, which is how large-scale key-collision studies have recovered private keys from real internet-facing hosts. A protocol that reuses a nonce or fails to separate contexts turns many independent sessions into one linked target. In every case the defense is the same architectural instinct: make sure the attacker’s effort against one instance is worthless against the next, so the population’s security is the per-target strength rather than something far weaker.

Source: Heninger, Durumeric, Wustrow, Halderman, “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices,” USENIX Security 2012 (shared and low-entropy randomness across many devices enabled batch recovery of private keys), factorable.net.

How do you design against amortization?

Designing against multi-target and precomputation attacks is a small set of disciplines that all enforce the same rule: the attacker’s work against one target must not carry over to another. Applied consistently, they turn a batch problem back into a per-target problem the algorithm’s published strength was meant to cover.

1. Salt every stored secret with a unique per-target value. This is the direct defense against precomputation for password and credential storage, and it is why a bare fast hash of a password is a serious flaw regardless of the hash’s strength.
2. Use a slow, memory-hard derivation for secrets people choose. Salting stops table reuse, and a deliberately expensive function raises the per-guess cost so that even a per-target attack on a weak human password is slow, which pairs with salting rather than replacing it.
3. Separate domains explicitly. Feed context labels and protocol identifiers into hashes and key-derivation steps so the same secret in two settings yields unrelated outputs, and an attacker cannot transfer captured or precomputed work between them.
4. Source per-target randomness from a strong generator. Shared or low-entropy randomness across a fleet is the root cause that turns many devices into one target, so a properly seeded CSPRNG on each device is what keeps their keys independent.
5. Size symmetric margins for the batched case. Because multi-target Grover lowers the effective search cost across a population, standardizing on 256-bit symmetric keys and 384-bit-or-larger hashes for high-assurance work leaves headroom for the amortized attack, not merely the single-target one.

Source: NIST, “Digital Identity Guidelines,” SP 800-63B (salted, slow key-derivation storage of memorized secrets), pages.nist.gov/800-63-3/sp800-63b.html; NISTIR 8105 (larger key sizes as the Grover remedy), csrc.nist.gov/pubs/ir/8105/final.

Common misconceptions

• “An algorithm’s bit strength is the cost to break it.” The quoted strength is usually the cost to break one target. An adversary content to break any target out of many can pay far less when the design lets work be shared, so the batch cost is the number that describes the real threat.
• “Rainbow tables are a weakness in the hash function.” They are a consequence of using a hash so that identical inputs give identical stored outputs for everyone. The math is fine, and a per-user salt removes the reuse that makes the table economical.
• “Grover does not care how many targets there are.” Multi-target Grover finds one of t marked items in about the square root of N over t steps, so more targets means a cheaper search. The effect is real but bounded by the same quadratic limit, so a wider key margin absorbs it.
• “Salting makes each hash stronger.” Salting does not change the strength of any single hash. It makes every target’s computation unique, which defeats precomputation by forcing the attacker to redo work per target rather than reuse one table across all of them.
• “Long random keys make salting unnecessary.” Salting is about human-chosen and low-entropy secrets, where a small guess space plus reuse is the whole attack. For those, a unique salt and a slow derivation matter regardless of the underlying hash’s length.

Questions people ask

What is a multi-target attack in plain terms? It is an attack whose goal is to break any one key out of a large set rather than one specific key, and it matters because the cost of succeeding against some member of the set is often far below the cost of breaking a named one, so the population is weaker than its per-key strength suggests.

Why is salting so important for passwords? Because without it, everyone who chose the same password has the same stored hash, so an attacker precomputes one table and cracks every current and future database cheaply. A unique per-user salt makes each stored value distinct, which forces the attacker to redo the expensive work for every target and destroys the table’s reuse.

Does a quantum computer make multi-target attacks worse? It sharpens them modestly. Multi-target Grover lowers the search cost as the number of targets grows, but only within the same quadratic speedup Grover gives on any search, so the fix is the same larger key margin that answers single-target Grover, not a new class of algorithm.

Is precomputation the same as a rainbow table? A rainbow table is the best-known precomputation attack, a space-optimized way to store precomputed hashes so future targets are cracked by lookup. Precomputation is the general idea of paying a one-time cost to make every later break cheap, and rainbow tables are one instance of it.

What is domain separation and how does it relate? Domain separation is feeding a distinguishing label into a hash or key-derivation step so the same secret used in different contexts produces unrelated outputs. It is the generalization of salting past passwords, and it exists to guarantee an attacker’s captured or precomputed work in one context is worthless in another.

How do I know if my system is exposed to this? Look for shared work an attacker could reuse: unsalted or fast-hashed stored secrets, a random number generator seeded identically across a device fleet, reused nonces, or missing context labels in key derivation. Each of those lets one computation serve many targets, which is the exact condition multi-target and precomputation attacks exploit.

---

Everything here is the map, given freely. When your team needs its own credential storage, key generation, and protocol contexts audited for the shared-work weaknesses that turn a fleet into a single target, that’s what an alignment briefing is for.

Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.