Coding Horror: Rainbow Hash Cracking(codinghorror.com)

26 pointsby charzomvor 19 Jahren9 comments

http://www.codinghorror.com/blog/archives/000949.html

12 comments

ijoshuavor 19 Jahren

As stated in the last few paragraphs, the simplest way to guard against this sort of attack is to salt the data before hashing it. What he doesn't discuss is how to choose a salt value. In a good hash function, every bit should affect the output, so really only a couple of bytes are needed for a good salt. Additionally, the salt value can be random and may include unprintable ASCII characters. Furthermore, a new salt can be created for every password. Now, if two users have the same password, the ciphertext will be different for each.

I've used this technique to store sensitive personal data which must be recoverable (i.e. credit card numbers.) When a new number is obtained, a few bytes of salt are randomly generated. The data, plus the salt, are passed to a symetric cipher, and the ciphertext and salt are stored in a database.

[edit: there's some discussion of this in the article comments.]

thomasptacekvor 19 Jahren

Also: stunningly bad exposition on "salt" values. A salt is a public nonce. Each password hash should have a different salt. An attacker shouldn't be able to construct a "your-salt" rainbow table to crack all the passwords on your machine; she should have to constrct N rainbow tables, for each of the passwords.

dappelbaumvor 19 Jahren

I don't think rainbow tables would work for public key crypto - cracking md5 with a lookup table is nothing like cracking RSA - they are completely different algorithms....

How quick would this do SHA-1?

jsjenkins168vor 19 Jahren

It looks like he is only using rainbow tables suitable for NTLM hashes. For other algorithms you need different lookup tables. I would honestly be surprised if it was even feasible to do this for an SHA-1 hash. The rainbow table would need to be unreasonably large.

And SHA-2, forget about it. Secret salt or not, you're not going to crack any of those variants anytime in the next several years. Rainbow tables would be impossibly large and hash collisions are next to impossible. That is unless you have access to some super-secret multi-bit quantum computer or something..

[deleted]vor 19 Jahren

kirsevor 19 Jahren

A year or so ago I remember a couple private rainbow cracking sites that had tables of up to several terabytes in size. It was easy to just submit your hash and they'd queue it up to be cracked. I think one of them is now rainbowcrack.com, but it seems like a few have gone to paid services.

andreyfvor 19 Jahren

Does anyone know of Rainbow table-like pre-computation that could be used to crack any private/public key systems?

tempovor 19 Jahren

Store the prime factorization of all numbers up to, say, 2^128.

[deleted]vor 19 Jahren

almostvor 19 Jahren

I hear Bruce Schneier once calculated all those in his head over lunch.

thomasptacekvor 19 Jahren

Correction: passwords are routinely stored in plain text (or reversably encrypted); there are a variety of challenge-response protocols that you can't run if all you have is the hash. It's a tradeoff; what do you care more about, passwords at rest or passwords in motion?