Rainbow table

As explained in Hacking Cryptography

A rainbow table is a precomputed structure of chained password-hash values that trades storage space for lookup time when recovering likely plaintext passwords.

A rainbow table is a precomputed reverse-lookup structure for likely password inputs. It does not reverse a hash function; it repeatedly hashes candidate passwords and retains enough information to later recover a candidate that produces a target digest. It trades expensive upfront computation for fast lookup against leaked, unsalted password hashes. section 6.4.2 section 6.0

A plain dictionary attack stores every candidate password beside its digest, making a matching digest nearly instantaneous to look up but requiring substantial storage. Rainbow tables compress this dictionary: a hash chain alternates hashing with a reduction function that maps a digest back into a password-shaped candidate. Rather than retain every chain entry, the table stores a chain start keyed by its final digest. section 6.4.2 section 6.4.2

Figure 6.8 Hash digests are the keys. Passwords that resulted in those digests are stored as values.

A full dictionary stores digests as keys and the passwords that produced them as values; rainbow tables reduce that storage burden by retaining chain endpoints instead. section 6.4.2

Chains can merge when different paths reach the same value, reducing coverage. Rainbow tables address this by varying the reduction function by column, so the same digest is reduced differently at different chain positions. This improves resistance to chain collisions, but no reduction function can eliminate the limits of a finite candidate password space. section 6.4.2 section 6.4.2

SHA-256 password demo

A Go implementation restricts passwords to six characters from a 52-letter alphabet, hashes them with SHA-256, and builds chains of length 1,000. A test generates or loads millions of stored chain endpoints, registers 100 users with random passwords, then attempts to recover passwords from their stored hashes and authenticate each recovered result. section 6.4.2 section 6.4.2 section 6.4.2

The attack depends on attacker-controlled precomputation over a predictable candidate space and reusable hash outputs. Long, complex passwords enlarge that space. Salts add stored plaintext values that make hash output less predictable, preventing a single precomputed table from serving all stored password hashes in the same way. section 6.4.2 section 6.4.2

How Hacking Cryptography covers it

How deep it goes

Implements chain generation, column-specific reductions, endpoint lookup, and replay verification, while noting chain merging and false alarms.

Examples

Uses a six-character SHA-256 password space, 1,000-step chains, millions of rows, and a 100-user cracking test.

What it assumes

Assumes familiarity with hash digests and password storage while explaining dictionary attacks and chained reductions concretely.

What you can do after

Build it from scratch by generating chains, storing endpoints, locating candidate chains, and verifying recovered passwords.

How it connects

Connects hash functions with dictionary attacks, SHA-256, reduction functions, hash chains, salts, and preimage resistance.

liveBookmanning.com

Read Hacking Cryptography on liveBook Get the book at manning.com

Related concepts

• hash chainalternative to · 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.
• hash functionuses · A hash function deterministically maps input data to a value in a bounded output range, commonly for indexing, lookup, comparison, or integrity checking.
• dictionary attackkind of · A dictionary attack is a credential-guessing technique that tests candidate passwords or values drawn from a prepared list of common or likely choices.
• cryptographic saltaddressed by · A cryptographic salt is an additional typically random value combined with input before hashing to distinguish identical inputs and hinder precomputed attacks.
• password authenticationaddresses · Password authentication is an authentication method that verifies a claimed identity or access by checking a supplied secret password or passphrase.

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.