Rainbow Hash Cracking

QUOTE::: I’m afraid I somewhat missed the point. Wouldn’t the rainbow table include also the hash of “deliciously-salty-password”? Sure, in this case you come up with a password that is not the actual password, but recovering the correct one should prove pretty easy: just try and remove some of the leading or trailing characters.
And, if you use a per-server salt, you could just find the salted passwords for two users and compare them to recover the salt.
Am I wrong?
John Woodword on September 9, 2007 01:20 AM
lets say you add “THIS_IS_REALLY_LONG_ASFASD#$%$$%^ASDAS#$%$^^$%734%F” To the beginning of the password. The hash table only does up to say 14 characters… The table size to store the hash of even the salt would be so large it would be easier to manually remove data from the HDD than to get the pwd.

@Eam

I think Andreas Krey had a very good sugestion… You overelooked that he suggested to throw the private part of the key away!

This will give you a good one way function, since there is no way to recover the original without the (deleted) private key.

Also, storing the hash with the password does not make it insecure. It will shut down rainbow attacks on your passwords in quite an effective way. So the attacker has to rely on a brute force.

Alex, the rainbow tables can be constructed for ANY hash. But it has to be predefined. The pre-packaged tables described in the actual article are for the LMNT hash function. But you can generate a table using any hash you wish. Jeff, in one of his comments, found that it’d take approximately 22 hours to generate a table of only alphanumerical values.

There’s software freely available “rainbowcrack” that let’s you generate these tables, AND… if you want to google around… you could download one constructed for the hash of your choice.

Mike H - Yes, adding the salt changes the resulting hash. They are talking about after it has been reversed.

“Password” might hash to “fghky” and “SaltPassword” might hash to “forkf”.
If you reverse the hash for “fghky” you will get “Password” and for “forkf” “SaltPassword”. If you don’t know the salt, you don’t know where the password begins. It could be that the salt is actually “SaltPass” and the password is “word”.
But if you also have the hash “porkf” and you reverse that to “SaltPassfish” then you know that the salt is “SaltPass” and the actual passwords are “word” and “fish” respectively.

Someone feel free to correct me if I am wrong.

Anon - unless the cracker knew the salt in advance. If the maximum password length was only say, 10 chars long, then all the cracker would need to do is generate a table to a max of 10 chars, and just prefix each one with the salt. This would open up every single password to the cracker. Hence, why people are saying that each salt should be different. A new table would need to be generated for EACH password, assuming the cracker knew the salt of EACH user.

Storing the salt in each users record however, would give the cracker all the information he’d need. It’d be time costly to crack each one, but would you need more than one?

How would you go about generating a random salt for each user, yet allowing the system to recover the salt on logon, without having it available to a possible cracker if your database was exposed?

Nice Wikipedia article about this topic:
http://en.wikipedia.org/wiki/Key_strengthening
It’s about hashing the password and the salt multiple times to make it harder to do a “simple” rainbow-table attack.

I still like the idea of hiding the salt “formula” in code rather than putting it in plain sight next to the hashed password – that way, the attacker can’t generate any rainbow tables at all unless they’ve managed to obtain both the user/hashpass table and the code itself.

They don’t necessarily need the code: if they can inject their own trial passwords into the system (they can log on as a user, and then later get the hash of their own password back) they may be well on their way to reverse engineering your “salt forumla”, especially if it’s trivial. The two suggestions above (Prepending a fixed string, or a username) are not particularly non-trivial. :slight_smile:

eam: surely the only difference there is that instead of having to prepend dictionary words when generating the rainbow tables, you prepend the hash of dictionary words? The size of the table will be the same.

"I think Andreas Krey had a very good sugestion… You overelooked that he suggested to throw the private part of the key away!

This will give you a good one way function, since there is no way to recover the original without the (deleted) private key."

I don’t think that using public-key encryption here (which is de facto precisely reversible) instead of hash-based encryption (which is essentially one-way) is the answer.

Consider the simple case of just adding a little “salt” to a password. Say, I start with password ABC, add “~!” to the start of it (like I said, simple!), and hash “~!ABC”.

When the rainbow hash algorithm comes up against this as an unsalted password, it might come up with “~!ABC”, but it more probably will come up with something wholly unresembling that original salt+password combination, like “XYZ$”. If he knew that the “salt” was in the first two letters, he’d use “Z$” as the password, which wouldn’t work (because the hash of ~!Z$ is not the same as the hash of ~!ABC). If he knew that the “salt” was “~!”, then he’d still be nowhere unless he made a custom rainbow hash with the constraint of every passcode starting with “~!” (then he might come out the other side with “($” as the password, but only if “~!($” and “~!ABC” hashed out the same).

Now, IF WE HAD PUBLIC KEY ENCRYPTION, the above would not be true at all. Rainbow hash brute forcing would still work, although the stored length would be longer and so the hash would be significantly larger. But, it would ALWAYS come up with “~!ABC”. So, if he de-hashes 10 passwords, the pattern of “~!” as a prefix will be blatantly obvious, and the “salt” completely useless. For every password yanked out of the algorithm, he’d just chop the “~!” and use that password for authentication.

Now, of course, the problem with the simple prefix (or simple algorithm creating the prefix) is that when it is known the hacker can just create a new rainbow hash with that prefix or algorithm as a constraint. The random salts make that more difficult. For instance, even if he knew that “~!” was the salt for this particular password and created his rainbow tables based on that, he wouldn’t gain anything because the next row’s salt is “#$” and so he’d need a new rainbow table, etc.

Personally, I am not a security professional, but I’d think that a combination of tactics would be the best. Start with a random seed (stored alongside the hash in the logins table). Add to that an algorithmic seed (an MD5 hash of the second, third, and fifth letters of the user id or something similar), which doesn’t get stored in the database (so, to find this second salt the hacker would need access to the code in addition to the database). Then add on the password the user passed in.

As for the guy saying any such solution is insecure because you send it over to the user’s browser as javascript … why on earth would you send it over to the user’s browser as javascript? Is there a reason why the single user’s password shouldn’t be sent (over SSL obviously) to the server for hashing in a controlled environment? Remember: IANASP, so treat me like a semi-retarded kindergartner in your answer :slight_smile:

Of course, if they happen to have physical access to your machine, no password could protect you from someone taking your HDD. I guess that’s why you put servers under lock and key, huh?

Jeff:

You must use a new, random salt for each password. If you don’t, you’re not salting; you’re just creating a single, one-off hash function and using it across all of your passwords. An attacker need only pre-compute one dictionary to efficiently attack your entire password database.

For example, consider your proposed implementation:

hash = md5('deliciously-salty-' + password)
# store hash in user record; throw out password

Note that the only variable upon which the hash value is dependent is the password itself; the salt is constant. There is a one-to-one correspondence between password and hash. Thus the brute-force search space is still the space of passwords. Adding the one “salt” value has not expanded the search space at all.

Now consider true salting:

salt = generate_random_salt()
hash = md5(salt + password)
# store salt and hash in user record; throw out password

Now the hash value is dependent upon two variables: the random salt and the password. The brute-force search space has just been massively expanded (multiplicatively) by the size of the salt space, and (for large salt spaces) that’s what makes precomputed-dictionary attacks infeasible.

In sum, if the size of your salt space is 1, you’re not salting. To get significant benefits, you must use a large, randomly selected salt for each and every password.

Cheers. --Tom

OMG PONIES!

Just to resolve a couple of assumptions about the way md5 works, here are a few example usages of it.

password : 5f4dcc3b5aa765d61d8327deb882cf99
delicious-salty- : 1db9d25f47d9991dd6967d6c45077f9b
delicious-salty-password : f28e176a45f8b8f4b88eaf8f3152b057
passworddelicious-salty- : d7b27446c952e6b047ec895b90cab3b0
v3ryS3cur3p455w0rd : c6ddb34fd61e967c9821adee12240f26
delicious-salty-v3ryS3cur3p455w0rd : 76cc7274212ba88ce098842bfa734f4e
v3ryS3cur3p455w0rddelicious-salty- : 162e492cbb3f4dbc1f1bd8e6d28f79e5

If you compare these hashes, they will have very little in common.

Actually, the salt should depend on the user, like the hash being md5(password,md5(username)), so that a separate table is needed for each user.

/etc/passwd used a random salt (of just 12 bits) stored along with the hash, but that was primarily to avoid people with the same cleartext password have the same hash. /etc/passwd was world-readable (and still is, but it doesn’t contain password hashed anymore).

Tom, that’s true. The letter “a” would be a bad salt. the salt should be somewhat long and full of unusual characters for best effect.

It’s also possible to use random per-row salts, as mentioned in the wikipedia article on Salt…

http://en.wikipedia.org/wiki/Salt_(cryptography)

I’m unclear how you can use a “random” salt for each password without storing it in the very same table row as the resulting hashed value, which seems to render the benefit of a salt moot to me… I always thought of salt as a per-server secret.

Just getting the password stored as non-reversable hash is hard enough. The powers that be of software projects often want to be able to retrieve forgotten user passwords, security be damned.

Actually, all you need is the password hashes. You don’t even need to crack the password.

Example:
When you go to login to your server, you type your username and password into your machine and click ‘submit’. Your machine sends a request to the server to login (no credentials are sent). The server responds with a nonce, (nonsense data/random garbage). Your PC takes the password you typed in and hashes it, then it uses the hash to encrypt the nonce it received from the server. It combines the encrypted nonce with the username and transmits it back to the server. The server does a lookup on the username, takes its private copy of your hashed password stored on the computer and uses that hash to decrypt the nonce it sent you, then compares the decrypted nonce to the nonce it sent out to you. If it matches, you typed in the correct password and your actual password is never sent across the network.

The weak spot is the hash. If I have gathered the hashes from the server, I do not need to go through the trouble of cracking them. I have written a custom login tool that all you do is type in the username. The program looks up the hashed password associated with the username and uses the hashed value to encrypt the nonce.

At this point, it doesn’t matter if your password is 1 character or 14 random characters, if I have your hashes, you’re toast. Cracking the passwords is simply an academic exercise at that point.

:slight_smile:

Regards,
JRHelgeson

Wow, I’ve never seen so many people who don’t understand salt talk about it.

Salt is random. It won’t be the same between two different users.

It is effective against a rainbow hash because a rainbow hash cannot possibly include every combination.

Let’s assume the windows password is limited to A-Z 0-9. No lowercase, no special characters. Let’s also assume the password is 7 characters long. This is a pretty poor password by anyone’s reckoning.

But there are 36^7 different passwords encoded by this. That would take a 1.2 terabyte rainbow file to store all combinations. Now we add a measly 2 character salt that is completely random, and you now need a 16 petabyte rainbow file.

With the 2 character salt, even a password of “password” would need 1296 different entries in the rainbow file to handle all the possible hashes of “password” plus salt. You can see how the salt increases the size of the required rainbow file exponentially.

Is the geekwisdom meter meant to be taken seriously? head -c 8 /dev/urandom | uuenview -b produces a rating of “mediocre” and that’s from 64 bits of pure entropy (well, PRNG entropy).

The number of clueless partly-clueless posts is smirk inducing. The number of people who don’t realize that there is no character-per character correspondence between the input and output to a cryptographically strong hash is way too high.