Rainbow Hash Cracking

The multi-platform password cracker Ophcrack is incredibly fast. How fast? It can crack the password "Fgpyyih804423" in 160 seconds. Most people would consider that password fairly secure. The Microsoft password strength checker rates it "strong". The Geekwisdom password strength meter rates it "mediocre".

This is a companion discussion topic for the original blog entry at: http://www.codinghorror.com/blog/2007/09/rainbow-hash-cracking.html

Am I missing something here, or would you also want your salt to contain special characters so that they wouldn’t even be able to get the salted password with the smaller rainbow hashes? In other words, use “[more salt?]” as the prefix and perhaps “{booya!}” as a suffix …

In case anyone is interested, here’s how long it takes to generate a basic Rainbow Table on a modern spec PC:

rtgen lm alpha-numeric 1 7 0 2400 40000000 all

hash: LM, 8 chars, [A-Z0-9] = space 80,603,140,212

I’m getting about 110 seconds per every 100,000 hash values generated. The table size is 40,000,000 so total generation time will be 400 * 110 sec = 12.2 hours.

rtgen is definitely not multithreaded, so you might be able to run two (or more) instances on multicore machine and increase throughput, also.

Jeff Says: 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.

Yes, that is exactly what you do. Having a salt with ENTIRELY RANDOM makes it infeasable that the rainbow table attack would work. A static salt like “bob” or the username I can’t see doing that.

If you read through the first Q/A of this there are more implementation details:

The code of figure 2 [the SaltedHash class] shows doing exactly what you said, storing the salt with the hash. Then to check that the password the user enters match

SHA1(stored salt, user entered password) == stored hash

When the user changes thieir password there isn’t much reason to avoid changing the salt too [darn, that’s another 20 bytes of writing sql server has to do…].

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?

gah, the above should’ve been:
SHA1(stored salt + user entered password) == stored hash

also I just ran across this, but it’s in the evil VB:

In response to Tom Moertel, using a generate random salt function is exactly what you do using encrpytion. However, you also need a way to log into the system.

Please remember that in order to log in, the user submits their password to your service, and it does the exact same thing it did before.

salt = generate_random_salt()
hash = md5(salt + password)

compare this hash to stored hash and if they are the same user is authentic.

Problem is, you need to use the same salt as before or no one will ever be able to log into your service.

Where generating this salt becomes very important is when setting up encrypted communications. Let say for example each time you set up your encryption, you use the same key, and encrypted communications always start with the same thing.

To make it simple we do an encrypt(‘helo other server, we’d like to establish encrypted communications’); which returns 4fc3d2. Now if everytime you set up this encryption, you do the same thing, the bytes you send over the network are also the same(4fc3d2). This is where your salting and IV (initialization vector) comes in. since then all you do first is encrypt(salt), then encrypt(handshake message), and the bytes sent over the line will always be different. This makes it much more difficult for a crypto-analyst to try and deduce what you are sending without decrypting any data.

This is why I proposed you use an actual encryption algorithm, and not just a hash. You want to take advantage of the fact that everytime you start encryption, with the same key, you always return the same result. Now you might want to pass your encryptor 128 or 256bytes to be more secure, this is where your hashes come in since you easily get a fixed length password from a mixed length password. So you simply do your md5/sha(password), then encrypt it against your private/public key pair with the pirvate key discarded. There is literally no way for your average attacker to decrypt these passwords.

The biggest worry from myself would be that with spammers and cracker’s getting increased computational power through botnets, cryptoanalysis could become alot more prominent. Which is why I would also recommend you rotate the key’s used ona yearly/monthly/daily basis, and force a password change yearly. (if you database is compromised, they have a copy of it, even if it takes 10 years to decrypt it.)

Check out the RSA Challenge: http://www.rsa.com/rsalabs/node.asp?id=2093 And see what using distributed computing can do to break these passwods.

@John Woodword +1 Same for me, I don’t get this salt thing :wink:

John Said: 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.

… You could, but I [as a hacker] would rather find which users have the same password, which would mean the same hash [but only if all users have the same salt].

[Though by the time I have the password hashes I could would probably have reasonable enough contact information to ask the users for thier passwords myself. I could offer them chocolate, or call in saying I was their IT guy and I need to do change a setting in their account or any number of other things. Jeff: You should get read “The Art of Deception: Controlling the Human Element of Security”]

Wouldn’t the salt just be a human-readable post-fix on every single entry? Then all you’d need to do is compare 2 strings from the right until string[length-n] != string2[length-n], remove n chars from each hash, then compare with the rainbow table?

Seems like a once off cost of computing the post-fix, and a per-hash cost of removing the post-fix.

Or am I wrong?

Jeff, as far as I know, per-user salting would result in hacker’s need to generate different rainbow tables for every user, as opposed to generating one rainbow table for database with known salt.

John: salt adds its length to the password, so if you make 14 characters long salt and hacker doesn’t know it, those 64GB rainbow tables wouldn’t decipher even one letter password.
If he does, he needs to generate rainbow tables tailored to the salt (a minor annoyance, I guess).

Jeff, what would be your solution to this problem?

I’m unclear as to how an 8.5 gig table contains 7 trillion hashes. Wouldn’t it have to be at least 7 terabytes?

If a hacker manager to get a chunk of my database passwords hashes, how hard would it be for him to get the salt password (function)?
the function have to be static, that’s the whole point.

  1. if it’s hard coded, just putting the hand on the code is enough (and secret code is not my idea about good security).
  2. if it’s somehow “dynamic” (per application instance), the application itself need to be able to figure it out - so it will be available somehow to the running code. again - not very strong.

I think if a hacker got his/her hands on the passwords hashes we are already in deep shit.

From the wikipedia article (http://en.wikipedia.org/wiki/Salt_%28cryptography%29):

“Salts also help protect against rainbow tables as they, in effect, extend the length and potentially the complexity of the password. If the rainbow tables do not have passwords matching the length (e.g. 8 bytes password, and 2 bytes salt, is effectively a 10 byte password) and complexity (non-alphanumeric salt increases the complexity of strictly alphanumeric passwords) of the salted password, then the password will not be found. If found, one will have to remove the salt from the password before it can be used.”

In the context of extending the length of the stored hash and preventing the obviousness of two identical passwords using a unique hash for each password can be done simply, as previously suggested, by appending the hash of the username or other such related constant.

For anyone else not too familiar with public key encryption who is struggling to grasp Kevin Nisbet’s ideas, I think it might be helpful to consider he’s talking more about the digital signature concept rather than the traditional public key encryption. I think. Please correct me if I’m wrong.

as previously suggested, by appending the hash of the username or other such related constant

You want hashes to be a prefix, not a suffix.

This makes sense. If an attacker obtained our passwords table, s/he would have no way of knowing that the salt “formula” is to hash the username and use that as a prefix for the password. Nor would s/he know the hash function we used for the username, either.

Those salting secrets are kept in the code, as Omry noted above. So the hacker would need the user/hashpass table and the code to attack the hashes with any hope of success.

Jeff, as far as I know, per-user salting would result in hacker’s need to generate different rainbow tables for every user.

Oh, right. The fact that the salt and the hash are plainly visible isn’t a problem, because the attacker still has to generate (# of users) rainbow tables instead of a single rainbow table for the entire lot.

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.

Makes sense, thanks for adding that. I’m relatively new to cryptography.

I don’t think you need a different rainbow table just because of a salt. Assuming you have a rainbow table that can recover [password] and [salted password] a rainbow attack will sort of work; the attacker would have to guess what salt has been added to your password.

If you’re using a salt like aywa%@ADWw^ysjrmpod!npmgs then it becomes very difficult to generate a generalized rainbow table that can crack your password hashes…which now that I think about it is what people have meant.

So a salt is for making a password stronger. If everyone had passwords like aywa%@ADWw^ysjrmpod!npmgs then who would care about salt? :slight_smile:

On a related note, if your attacker knows your salt (or how it’s generated) then it’s not very effective. One could sort of alleviate this by basing the salt on privileged information which would only be available to processes with elevated credentials (I don’t know off the top of my head whether there’s anything per-user that only admin/root accounts can access.) I think that if your attacker has the ability to start admin/root processes you may as well give up. :slight_smile:

Apparently only you can get away with having Hello Kitty on a freaking pony jumping over a freaking rainbow and super-geeky password intricacies in the same post! “Most impressive.”