A hash chain is a space–time trade-off for precomputed dictionary attacks. Starting with a candidate password, it alternates a hash function with a deterministic reduction function: password → digest → possible password → digest. Rather than storing every password–digest pair, a table can retain a chain’s start and endpoint. section 6.4.2 section 6.5
Figure 6.10 Hash chains alternatively apply a hash function and a reduction Function.
The alternating steps matter: hashing produces a digest, while reduction maps that digest back into the allowed password space so another step can follow. section 6.4.2
A reduction function is not a hash-function inverse. It deterministically selects a valid candidate from a digest—for example, by using digest bytes to choose characters from a fixed six-character alphabet. Many digests can map to the same candidate, so reduction preserves neither the original password nor all digest information. section 6.4.2
To build and use a chain table:
- Choose the password length and character set, then define a deterministic reduction function compatible with that candidate space. section 6.4.2
- Generate a starting password and repeatedly hash it and reduce the resulting digest for a fixed chain length. section 6.4.2
- Store the starting password keyed by the final digest, instead of storing every intermediate guess and digest. section 6.4.2
- For a target digest, simulate possible remaining chain positions to find an endpoint; if an endpoint matches, rerun that chain from its start and verify whether it reaches the target. section 6.4.2
Six-character SHA-256 chain
Beginning with abcdef, hash it with SHA-256, reduce the digest to ilWrlG, hash again, and reduce again to kdhkjA. Repeating the same deterministic operations makes the chain reproducible from its start, while the endpoint table uses far less space than a full password–digest dictionary. section 6.4.2
Ordinary hash chains can merge when different paths reach the same reduced password; afterward, their remaining steps are identical, reducing coverage. Rainbow tables address this by changing the reduction function by column, which helps prevent chains from merging. Salts invalidate precomputed tables that were generated without the relevant salt. section 6.4.2 section 6.5
