Dictionary Attacks and Rainbow Tables

A dictionary attack does not try every possible combination; instead it tries a curated list of likely passwords. Real users choose passwords from a limited vocabulary: common words, names, dates, and phrases. Testing a wordlist of one million likely passwords is vastly faster than testing all possible 8-character strings (200 trillion combinations). Dictionary attacks succeed because human password choices are predictable.

In 2009, the social networking site RockYou suffered a breach that exposed 32 million user passwords in plaintext. The resulting list, now called rockyou.txt, contains approximately 14 million unique passwords and is the standard first wordlist used in password cracking. Examining rockyou.txt reveals that the most common passwords are 123456, password, and variations on first names followed by numbers.

A hybrid attack extends a base wordlist by applying transformation rules. A word like password becomes Password, P@ssword, p4ssword, password1, password123, and hundreds more variants. Hashcat's rule engine allows specifying exactly which transformations to apply: capitalise first letter, append two digits, substitute letters with symbols. This dramatically expands coverage without testing truly random strings.

Leet speak substitutions (replacing letters with numbers: e=3, a=4, i=1, o=0, s=5) were once thought to improve password security. Rule-based crackers include these substitutions as standard transformations. A password like s3cur1ty is trivially cracked from the base word security plus a leet substitution rule. Crackers also try common patterns: appending !, 123, or the current year to any dictionary word.

A rainbow table is a large precomputed database that maps hash values back to the original passwords. Instead of hashing a candidate and comparing, the attacker looks up the hash in the table. Building the table takes enormous time and storage but each lookup is instantaneous. Rainbow tables for MD5 of all 8-character alphanumeric passwords can fit in a few terabytes and crack any matching password in milliseconds.

Rainbow tables embody a time-memory trade-off: spend time computing the table once, then use memory to make future lookups fast. The table stores hash chains: each chain starts with a guess, hashes it, applies a reduction function to generate another guess, and repeats. Storing only chain endpoints allows recovering passwords from hashes through a chain reconstruction process that balances storage against computation.

A salt is a random value appended to the password before hashing. Because the salt is unique per user, two users with the same password produce different hash values. This means an attacker cannot precompute a rainbow table for the salted password; they would need to build a separate table for every possible salt value, which is computationally infeasible. Salting is mandatory for any secure password storage system.

Many early web applications stored passwords as unsalted MD5 hashes. MD5 of the string password is 5f4dcc3b5aa765d61d8327deb882cf99, a fixed value. Anyone who has seen this hash before, or who looks it up in a precomputed database, instantly knows the password. Sites like CrackStation maintain billions of precomputed MD5 and SHA-1 hashes. Unsalted common passwords are cracked in under a second.

Have I Been Pwned (HIBP), created by security researcher Troy Hunt, aggregates password hashes from major data breaches. Users can check if their email address or password has appeared in a breach. Developers can use the HIBP API to check candidate passwords against 850 million breached hashes using a k-anonymity model: the first 5 hex characters of the SHA-1 hash are sent to the API, which returns matching suffixes without the server learning the full hash.

Credential stuffing attacks take username-password pairs from one breach and test them against other services. Because many users reuse passwords across sites, a breach at a low-security site yields working credentials for high-value targets like banking and email. Automated tools submit thousands of login attempts per second across multiple services. Rate limiting and multi-factor authentication are the primary defences against credential stuffing.

Secure password storage combines salting with a slow, adaptive hash function. bcrypt, Argon2, and scrypt are designed to be computationally expensive, taking milliseconds per hash rather than microseconds. This limits attacker throughput from billions of attempts per second to thousands. The cost parameter can be increased as hardware gets faster, maintaining a consistent work requirement. These algorithms are the current standard for password storage.

Why does adding a unique random salt to each password before hashing defeat precomputed rainbow table attacks?

Dictionary attacks test likely passwords rather than all combinations. rockyou.txt provides 14 million real-world examples. Hybrid and rule-based attacks extend wordlists with transformations. Rainbow tables give instantaneous lookup for unsalted hashes. Salting defeats rainbow tables by making each hash unique. HIBP checks whether passwords appear in known breaches. Adaptive hash functions like bcrypt and Argon2 are required for secure storage.