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?
What exactly is a rainbow attack? [closed]
Asked Answered
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.
Though not the popular choice, this is what I was looking for. I have a little experience with salts and password hashes, but for some reason I'd not heard of the rainbow table attack until today. All of these answers really helped clarify it. Thanks –
Adverb
What do you mean by "and you have hashed them just once"? I can understand the value of salting your passwords, but what gain do I have in recursively hashing them n-times (like I have seen at times)? –
Mukerji
@Mukerji - It makes it slower to brute-force check each password, and you'd need a Rainbow Table that was made with the exact number of recursive-hashings in mind. –
Paeon
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...
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.)
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).
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.
Late to the party but I was also aware of Rainbow Tables being a method of attack on hashed/unsalted passwords. However on Twitter recently http://codahale.com/how-to-safely-store-a-password/ was shared and depending on your needs and concerns.. you may not be able to salt your way to safe password storage.
I hope this is informative to you.
Wikipedia is your friend:
© 2022 - 2024 — McMap. All rights reserved.