Hash chain
A hash chain is a linked sequence of hash-table entries stored in one bucket to handle multiple keys that produce the same hash value.
Hacking Cryptography
A hash chain is a sequence formed by alternately applying a hash function and a deterministic reduction function to messages and digests.
- How it is used
- Supports storage-efficient precomputation for dictionary attacks against password digests.
- How deep it goes
- Works through reduction, chain generation, endpoint lookup, verification, merging, and rainbow-table improvements in Go.
- Examples
- Traces a six-character SHA-256 chain and implements a 1,000-column rainbow-table cracker.
- What you can do after
- Build it from scratch by generating chains, storing endpoints, and verifying candidate password matches.
Grokking Data Structures
A hash chain is a linked list attached to a hash-table bucket that stores entries mapped to that bucket.
- How it is used
- Resolves hash-table collisions by storing multiple values in a bucket-linked list.
- How deep it goes
- Explains bucket operations, linked-list choices, customizable key extraction, and average versus worst-case running times.
- Examples
- Uses bucket collisions, singly linked-list operations, multiplication hashing, and a running-time table.
- What you can do after
- Build it from scratch using bucketed singly linked lists and configurable key extraction.
Related concepts
- linked listkind of · An ordered sequence of elements stored in separate nodes connected by links or references rather than in one contiguous storage region.
- rainbow tablealternative to · A rainbow table is a precomputed structure of chained password-hash values that accelerates recovery of plaintext passwords from unsalted hashes by trading storage for lookup time.
- Mappart of · A map is an associative data structure that stores key-value pairs and supports retrieving values by key.
- reduction functionhas part · A reduction function deterministically maps a hash digest to a candidate plaintext or password satisfying specified constraints without reversing the hash function.
- hash collisionaddresses · A hash collision occurs when distinct inputs to a hash function produce the same hash value or map to the same hash-table location.
- bucketpart of · A bucket is a grouping or storage unit to which data or items are assigned according to a criterion, range, hash, or partitioning scheme.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.