What exactly is a rainbow attack?

Question

I was reading a few articles on salts and password hashes and a few people were mentioning rainbow attacks. What exactly is a rainbow attack and what are the best methods to prevent it?

Answer 1

It's when somebody uses a Rainbow table to crack passwords.

If you are worried about this, you should use Salt. There is also a Stack Overlow question that might help you understand salt a little better than Wikipedia...

Answer 2

Wikipedia is your friend:

http://en.wikipedia.org/wiki/Rainbow_table

Answer 3

This is a useful article on Rainbow Tables for the lay person. (Not suggesting you are a layperson, but it's well written and concise.)

Answer 4

The wikipedia article is a bit difficult to understand. In a nutshell, you can think of a Rainbow Table as a large dictionary with pre-calculated hashes and the passwords from which they were calculated.

The difference between Rainbow Tables and other dictionaries is simply in the method how the entries are stored. The Rainbow table is optimized for hashes and passwords, and thus achieves great space optimization while still maintaining good look-up speed. But in essence, it's just a dictionary.

When an attacker steals a long list of password hashes from you, he can quickly check if any of them are in the Rainbow Table. For those that are, the Rainbow Table will also contain what string they were hashed from.

Of course, there are just too many hashes to store them all in a Rainbow Table. So if a hash is not in the particular table, the hacker is out of luck. But if your users use simple english words and you have hashed them just once, there is a large possibility that a good Rainbow Table will contain the password.

Answer 5

Broadly speaking, you encrypt a vast number of possible short plaintext strings (i.e. for passwords), and store the encrypted values alongside the plaintext. This makes it (relatively) straightforward to simply lookup the plaintext when you have the encrypted value.

This is most useful for weak and/or unsalted password hashes. A popular example is the LAN Manager hash, used by versions of Windows up to XP to store user passwords.

Note that a pre-computed rainbow table for even something as simple as the LM hash takes a lot of CPU time to generate and occupies a fair amount of space (on the order of 10s of gigabytes IIRC).

Answer 6

Rainbow Tables basically allow someone to store a large number of precomputed hashes feasibly.

This makes it easy to crack your hashed passwords, since instead of performing a whole heap of hashing functions, the work has already been done and they virtually just have to do a database lookup.

The best protection against this kind of attack is to use a salt (random characters) in your password. i.e. instead of storing md5(password), store md5(password + salt), or even better md5(salt + md5(password)).

Since even with rainbow tables, it is going to be near impossible to store all possible salted hashes.

BTW, obviously you have to store your salt with your hash so that you can authenticate the user.