Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

password
hashing
reduce
encryption
authentication

What are rainbow tables?

Anusheh Zohair Mustafeez

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code

Background

In today’s digital world, if a hacker gets access to your account password, a frightening amount of your sensitive data will be at their disposal. To achieve their malicious goals, attackers often use password cracking. However, traditional password cracking techniques can be extremely time-consuming, so attackers quickly realized that with rainbow tables, they could leverage the space-time trade-off to gain authentication more efficiently.

What are rainbow tables?

Rainbow tables are lists of hashes of a large set of strings or plaintext passwords that have already been computed and stored. Since authentication is done based on password hashes, and not the plaintext passwords themselves, rainbow tables enable hackers to gain access without knowing the original password. All they need to do is crack the password hash. Storing hashes of permutations of a large set of strings means that rainbow tables often require storage at the scale of terabytes. However, rainbow table attacks are far more efficient than traditional password cracking as hashes are checked against a stored database. This removes the need for repeated hashing.

svg viewer

How do rainbow tables work?

Rainbow tables are constructed using chains of hashing and reduction operations. A plaintext password is passed through a series of these operations and then stored in the table alongside the output hash as shown in Figure 1.
For password cracking, the password hash is passed through the chain, link by link, and checked against the stored hashes. If there is a match, rainbow tables retrieve the plaintext that produced the hash. Now, the attacker can successfully authenticate.

svg viewer
Figure 1

How to protect against rainbow table attacks

The best-known way of defending against rainbow table attacks is to make them too difficult to execute. Pseudorandom salt techniques serve as an excellent remedy to these attacks. They ensure that a randomly generated piece of data is passed into the hash function alongside the plain text to ensure that no two passwords share the same hash. Doing so increases the possible number of hashes a set of passwords could have, which makes the resulting rainbow table too difficult to construct; thus, preventing the attack.

RELATED TAGS

password
hashing
reduce
encryption
authentication

CONTRIBUTOR

Anusheh Zohair Mustafeez
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code
Keep Exploring