Home » Technical Interview Questions » Rainbow Table

Rainbow Table


Reading Time - 10 mins

A rainbow table attack might bring in a myriad of pre-nominations and assumptions into the minds of my imaginative readers. Like everyone might know about me till now.

I am not someone fond of jumping to things right away so I would want to help my readers with a few cryptographic terms before I begin to blabber all about cyber attacks and bore my enthusiastic public.

We are all fond of browsing the internet and go through a variety of things over it daily.

What if you find one day that your roommate had secretly been snooping your data and sending it over to your girlfriend, dad and mom?

You would feel attacked and betrayed.

So is a Cyber Attack.

A deliberate attempt by someone is it an individual or an organization to snoop into your data for reasons that bring them to profit in any form be it financial or personal.

We log into a host of services on a daily basis starting from Gmail to our academic portals. Even I have logged into Tutorialcup to be able to deliver this article.

This makes all of us a possible prey or a source of data for a predator who might misuse us. There can be various types in which a hacker may try to break into passwords.

Terms Used in Cyber Attack field

Some of the most common ones are

  • Brute Force Attack
  • Dictionary Attack
  • Rainbow Table Attack
  • Phishing
  • Trojans, Viruses and Malware
  • Social Engineering
  • Port Scan Attack
READ  Happy Number

As we are getting into the know-how’s of a Rainbow Attack let us first discuss a few terms

A Hash Function

They are something that we have all heard of while trying to learn Data Structures and Algorithms. The expert hash functions can transform input data to a random output or rather say help us encode/encrypt our data. Examples of these include-SHA1, SHA256 and MD5.

Hash functions ensure that the output changes of the input string changes by even a single character. Making Plaintext and its hash un-differentiable.

This is something which we may call as one-way encryption.

Let us see some of the popular hash functions like SHA into action

Demonstrating how hash functions work

Now that we know what a hash function is let us build to the Rainbow table understanding a few other ways of attack along the way.

Brute Force Attacks

For understanding this attack method let us assume you have a bunch of infinite keys that you can use to open a lock. So is a brute force attack in which the attacker turns to different combinations generated with letters, numbers and characters to crack open a password.

But, we all hate brute force methods. Don’t we?

So do the hackers!which made them decide to move on to something faster.

Dictionary Attack

As the name suggests for a dictionary attack a table of common hashed passwords with their hash functions. In a brute force as the keys and as an attacker generates passwords they store them in a table to be put to later use for a dictionary attack.

Are we eating into a lot of storage?

READ  Palindrome Number

The answer is: YES

A Rainbow Table and Rainbow Table attack

A rainbow table tries to balance this tradeoff between the space and time taken to make the attack more efficient. In this process, we land on to a reduction function that does just the opposite of a hash function. Mapping hashes to plaintext.

However, the reduction function does not reverse the hash value and shall not be confused with a Blackbox yielding the original plaintext from a hash function.

How do these tables work?

In a rainbow table, a chain is formed the hashes are generated from the new text generated from a reduction function many times forming a chain. The hash we are trying to find is then taken and compared to each hash in the table. The hacker keeps repeating the process until they find the hash value at one of the endpoints.

This is something which shall not be confused with finding the final password. The hacker has deciphered the chain leading up to the hash value.

We thus start at the beginning of the chain and carry out the reductions and hashing one by one until the desired hash value and plaintext are not reached.

Example:

Input:12345

Hash Function: MD5

Output:827ccb0eea8a706c4c34a16891f84e7b

Let the reduction function be a function that takes the first four numbers letting us into the next cycle as

Input:8270

Hash Function: MD5

Output: ea2a5dbe60939dc09744a1c1447a07e8

And so on

Till when do we continue?

Till we hit a cycle i.e a previous input. We would then rush on to store the start and end of this chain.

READ  Seconds to Days
Picture Illustrating how chain is formed in a Rainbow Table
Picture Illustrating how the chain is formed in a Rainbow Table

Why are they called Rainbow tables?

The plaintext is encrypted multiple times before it is stored into a database. When someone tries to pry through the passwords they use multiple reduction functions in each step to provide better results.

We mark different reduction functions with colours making it a colourful rainbow.

Defence against a Rainbow Attack

 Salting and Peppering our data

Salt is a short random collection of characters added on to data whilst hashing to ensure security. Also, we have to make sure to use different salts for each and every piece of data in order to add to their usability.

Also, usernames as salt are a horrible idea as it causes serious issues with predictability.

I hope my post has brought some key information to the cryptography fanatics!

See you soon! 😀

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions