A time-space tradeoff exchanges storage for computation: storing fewer guesses saves space but requires more hashing during a dictionary attack. section 6.0 section 6.4.2
Hash chains apply a hash function and a deterministic reduction function repeatedly, retaining chain endpoints and reconstructing candidates when a target digest matches. section 6.4.2
The tradeoff appears in the attack workflow:
- Store complete password-to-digest mappings for immediate lookups, or store compact chain representations that require recomputation. section 6.4.2
- Generate chains from candidate passwords, alternating SHA-256 hashing with reduction; rainbow tables vary the reduction by column to limit collisions. section 6.4.2
- Search backward from the target digest, locate a matching endpoint, then traverse the chain to verify the recovered password. section 6.4.2
Rainbow-table attack
The Go implementation generates five million chains for six-character passwords, stores their endpoints, and tests the resulting table against 100 unsalted SHA-256 password digests.
Figure 6.10 Hash chains alternatively apply a hash function and a reduction Function.
Shows the alternating hash-and-reduction structure that makes chain storage smaller than complete guess tables. section 6.4.2
