What Is a Rainbow Table Attack and How Salting Stops It

A rainbow table is a precomputed table of hash chains that lets an attacker reverse unsalted password hashes in seconds, trading disk space for cracking time. Salting defeats it: a unique random value is added to each password before hashing, so one table cannot match many hashes and each one must be cracked on its own.

If you met the term in a breach story or a security course, you probably know that a hash is a one-way fingerprint of a password, but not how a table of “chains” can run that one-way function backwards. This post walks through one small chain by hand, shows how an attacker uses it to crack a stolen hash, and then answers the question most glossary pages skip: do rainbow tables still matter today? Against a modern system they mostly do not, because salting and slow hashes made them useless, and the threats that replaced them (GPU guessing and credential stuffing) need different defenses. We finish with the storage settings OWASP and NIST recommend and what Keycloak does for you by default.

Key takeaways

• A rainbow table stores only the start and end of long chains of hash and “reduce” steps, which lets it cover billions of passwords in a few gigabytes. The original 2003 paper cracked 99.9% of alphanumeric Windows password hashes in 13.6 seconds with 1.4 GB of tables (Oechslin, CRYPTO 2003).
• A per-password random salt makes every hash unique, so a table built in advance matches nothing. OWASP says salts “protect against an attacker’s pre-computing hashes using rainbow tables or database-based lookups” (OWASP).
• Salting alone does not slow down guessing, which is why you also need a slow hash: OWASP’s minimum is Argon2id with 19 MiB of memory, 2 iterations and 1 degree of parallelism (OWASP).
• Keycloak hashes and salts the passwords in its own database (Keycloak Server Administration Guide), with Argon2 by default since version 25 and PBKDF2-SHA512 at 210,000 iterations in FIPS mode (Keycloak 25 release notes, Keycloak Server Administration Guide).

What is a rainbow table, in plain words?

When a site stores passwords as plain, unsalted hashes, the same password always produces the same hash. That makes a simple attack possible: hash every likely password once, keep the results, and then look up any stolen hash in your list. The catch is size. A full lookup table of every possible password and its hash grows huge very quickly, so for anything beyond short passwords it cannot be stored.

A rainbow table is a clever compromise between the two extremes of “compute everything at attack time” and “store everything in advance”. It does most of the hashing ahead of time, like a lookup table, but it stores only a tiny fraction of the results and recomputes the rest during the attack. Cryptographers call this a time-memory trade-off. Martin Hellman described the idea in 1980, and Philippe Oechslin’s 2003 paper made it faster and gave it the “rainbow” name (Oechslin, Making a Faster Cryptanalytic Time-Memory Trade-Off). His demonstration against Windows LAN Manager hashes cracked 99.9% of all alphanumeric password hashes in 13.6 seconds using 1.4 GB of data, against 101 seconds for the earlier method (Oechslin, CRYPTO 2003).

How does a rainbow table work? A worked chain example

Two functions do all the work. The first is the hash function, H, which turns a password into a digest. The second is a reduction function, R, which goes the other way in a very loose sense: it takes a digest and turns it into some other valid-looking password. R does not reverse the hash (nothing can), it just maps a digest onto the space of passwords the table is meant to cover, so the chain can keep going.

For a toy example, say the table covers four-letter lowercase passwords, the hash is MD5, and the reduction function takes the first four bytes of the digest and turns each into a letter (the byte’s value plus the step number, modulo 26, where 0 is “a”). Using a different reduction at each step is what makes the table a “rainbow”: each column of the chain uses its own colour of R, which stops chains from merging into each other as often. Here is one chain, worked out with the md5sum command, with the digests shortened to their first eight hex characters:

rain --H--> 23678db5 --R1--> kama --H--> 68944d7c --R2--> cubw --H--> ff3afc33 --R3--> yjvc

You can reproduce each digest with any MD5 tool, for example printf %s rain | md5sum on Linux, and check the first reduction yourself: 0x23 is 35, plus 1 is 36, and 36 modulo 26 is 10, which is “k”. The other three bytes give “a”, “m” and “a”, so the chain moves from “rain” to “kama”. A real table builds millions of chains, each thousands of steps long, and then throws away everything in the middle. For this chain it keeps exactly one row:

Now suppose the attacker steals the hash 68944d7c.... They do not know where in which chain it sits, so they try every position, starting from the end. If it were the last hash in a chain, applying R3 would give an endpoint, but R3 gives “dvcx”, which is not in the table. If it were the second-to-last hash, applying R2 gives “cubw”, hashing and applying R3 gives “yjvc”, and “yjvc” is in the table. The attacker now replays that one chain from its start, “rain”, hashing as they go, and finds that “kama” hashes to 68944d7c.... The password is “kama”.

The attacker builds a chain from “rain” through “kama” and “cubw” to “yjvc” (1, 2), stores only “rain” and “yjvc” (3), walks forward from the stolen hash until “yjvc” turns up (4), and replays the chain from “rain” to find that “kama” is the password (5).

In this way the table stores two short strings for a chain that covers many passwords, and the attacker pays for the saving with a little extra hashing at lookup time, which for a fast hash like MD5 or NTLM is next to nothing.

Rainbow table vs dictionary attack vs brute force

All three attacks try to turn a stolen hash back into a password, but they spend their effort in different places. A dictionary attack hashes a list of likely passwords (leaked password lists, words and common variations) at attack time. A brute force attack hashes every possible combination up to some length. A rainbow table moves most of the brute-force work to before the attack and saves it to disk.

The last two rows are why the rest of this post focuses on salts and slow hashes rather than on the tables themselves.

How does salting stop a rainbow table?

A salt is a random value generated for each password when it is set, combined with the password before hashing and stored next to the hash. It is not a secret. Its job is to make the same password produce a different hash for every user, and that one change breaks the rainbow table completely.

Take the toy example again. MD5 of “kama” is 68944d7c..., the hash our table cracked. With a salt of “9f2c” in front, the stored hash becomes MD5 of “9f2ckama”, which md5sum gives as 820bf266..., and another user with the same password and the salt “b71e” gets 94894e21... (you can check both the same way). Our table was built for unsalted four-letter passwords, so it contains neither. To use a rainbow table now, the attacker would have to build a separate table for each salt, which costs more than simply guessing that one user’s password directly. OWASP puts it this way: salts “protect against an attacker’s pre-computing hashes using rainbow tables or database-based lookups”, and they also hide which users share a password (OWASP Password Storage Cheat Sheet).

The salt has to be unique and long enough that two users rarely share one. NIST’s current guidance says “the salt SHALL be at least 32 bits in length and chosen to minimize salt value collisions among stored hashes” (NIST SP 800-63B-4, 3.1.1.2), and the Argon2 specification says “a length of 128 bits is sufficient for all applications” (RFC 9106, section 4). We cover the salt itself in more depth, including where it is stored and what it cannot do, in password hashing and salting explained.

Are rainbow tables still a threat today?

Against a system built in the last decade or so, mostly not. Any password store that uses a per-user salt, which every modern password hashing function does as part of its design, is out of reach of a precomputed table. Rainbow tables still work against old systems that store unsalted fast hashes, such as legacy Windows LM and NTLM hashes or a homegrown table of plain MD5 or SHA-1 values, so they are a good reason to find and migrate anything like that.

The threat that replaced them is guessing on graphics cards. A salt forces the attacker to crack each hash separately, but it does nothing to slow each guess down, and GPUs make guesses very cheap. A published Hashcat v6.2.6 benchmark of a single RTX 4090 lists “164.1 GH/s” for MD5 (hash mode 0) and “288.5 GH/s” for NTLM (mode 1000), but only “184.0 kH/s” for bcrypt (mode 3200, run at a low cost of “Iterations: 32”) (Hashcat v6.2.6 RTX 4090 benchmark). With a fast hash, a salt only means the attacker cracks your users one at a time very quickly, and weak passwords still fall. With a slow hash, each guess costs real time, and that is what protects a stolen database now.

The other big threat never touches your hashes at all. OWASP defines credential stuffing as “testing username/password pairs obtained from the breach of another site” (OWASP Credential Stuffing Prevention Cheat Sheet), and it works whenever people reuse passwords. No storage setting stops it, so it needs defenses at login: multi-factor authentication, checking new passwords against breached lists, and limiting failed attempts. Our post on how to prevent password cracking in IAM covers those login-side controls.

Salt vs pepper vs key stretching: when does each matter?

These three terms often get mixed up, but each one answers a different attack, and a good password store uses salt and key stretching together, with a pepper as an optional extra.

OWASP describes a pepper as “shared between stored passwords” and says it “should not be stored along with the generated hash” but separately from the password database (OWASP). NIST makes the same suggestion in its own terms: “an additional iteration of a keyed hashing or encryption operation using a secret key known only to the verifier”, with that key “stored separately from the hashed passwords” (NIST SP 800-63B-4, 3.1.1.2). A pepper helps when an attacker copies your database but not your secrets store, so it is worth having, but it never replaces the salt or the slow hash.

What should you use to store passwords now?

Use a modern password hashing function with the parameters the standards bodies publish, and let it handle the salt. These are the current figures:

NIST’s 2017 revision 3 asked for PBKDF2 with “typically at least 10,000 iterations” (NIST SP 800-63B, revision 3), but that page now carries the notice “This revision of NIST SP 800-63 has been superseded by NIST SP 800-63-4 as of August 1, 2025”, and the current revision gives no iteration count, so treat OWASP’s figures as the target. If you are weighing bcrypt specifically, our bcrypt explainer goes through its work factor and the 72-byte limit. Storage is also only half of the job: NIST says verifiers “SHALL compare the prospective secret against a blocklist that contains known commonly used, expected, or compromised passwords” (NIST SP 800-63B-4, 3.1.1.2), because a slow hash of “password123” is still cracked on the first guess.

How does Keycloak store passwords?

If your users sign in through an identity provider such as Keycloak, your application never sees or stores a password hash, so none of the code above is yours to write. For passwords in its built-in database, Keycloak “hashes and salts the password before sending it to the database” (Keycloak Server Administration Guide), and the defaults follow the current guidance:

• Argon2 by default. Since Keycloak 25, “Argon2 is now the default password hashing algorithm used by Keycloak in a non-FIPS environment” (Keycloak 25 release notes). The administration guide lists argon2 as “default for non-FIPS deployments” (Keycloak Server Administration Guide), and its table of default hash iterations gives 5 for argon2 (Keycloak Server Administration Guide).
• PBKDF2-SHA512 in FIPS mode. The guide lists pbkdf2-sha512 as “PBKDF2 with SHA512 (default for FIPS deployments)” (Keycloak Server Administration Guide), its table of default hash iterations gives 210,000 for pbkdf2-sha512, and it says “Lower values for iterations provide insufficient security” (Keycloak Server Administration Guide). Keycloak 24 had already raised the PBKDF2 default from 27,500 to 210,000 iterations (Keycloak 25 release notes).
• Re-hashing at login. When you change the hashing algorithm in a realm’s password policy, “password hashes in storage will not change until the user logs in” (Keycloak Server Administration Guide).
• A breached password list. The “Password blacklist” policy means “Password must not be in a blacklist file”, and “Keycloak compares passwords in a case-insensitive manner” (Keycloak Server Administration Guide).

For the login-side threats, Keycloak “has brute force detection capabilities and can permanently or temporarily disable a user account if the number of login failures exceeds a specified threshold”, but “Brute force detection is disabled by default” (Keycloak Server Administration Guide). It has limits worth knowing about, which we cover in Keycloak’s brute force protection blind spot, and our Keycloak password policy best practices shows which policies to turn on. The surest way to take password cracking off the table is to stop relying on passwords alone, and our Keycloak passkeys and WebAuthn guide walks through adding passkeys to a realm.

FAQ

What is a rainbow table in simple terms?

It is a precomputed file that lets an attacker turn an unsalted password hash back into the password quickly. It stores the start and end of long chains of hashing and reducing steps instead of every hash, which keeps it small enough to fit on disk.

Do rainbow tables work on salted passwords?

No. A salt changes every stored hash, so a table built in advance for unsalted passwords matches none of them, and building a table per salt costs more than guessing directly (OWASP).

Is salting enough to protect passwords?

No. A salt stops precomputed tables, but it does not slow down guessing. You also need a slow, memory-hard hash such as Argon2id, plus login-side defenses like multi-factor authentication and a breached password check.

What is the difference between a salt and a pepper?

A salt is unique per password and stored next to the hash, so it is not secret. A pepper is one secret value for all passwords, kept outside the database, so a stolen database alone is not enough to crack them (OWASP).

Why is it called a rainbow table?

Each column of the chains uses a different reduction function, and when each function is drawn in its own colour, “a rainbow appears in the rainbow table”. Wikipedia notes that “the term rainbow tables was first used in Oechslin’s initial paper” and that for his Crypto 2003 presentation “Oechslin added color to the graphic in order to make the rainbow association more clear” (Wikipedia, Rainbow table).

What to do next

Check how your own application stores passwords today against the table of OWASP settings above. If you find unsalted MD5, SHA-1 or SHA-256, or a homegrown salt with a fast hash, plan a move to Argon2id and re-hash each password at the user’s next login. If you would rather not own password storage at all, Keycloak 25 and later hash with Argon2 and a per-password salt by default, and you can read about managed Keycloak hosting on Skycloak.