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".
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
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:
http://msdn.microsoft.com/msdnmag/issues/03/08/SecurityBriefs/
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:
http://channel9.msdn.com/wiki/default.aspx/SecurityWiki.SaltedHashCode2
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)
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 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.
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? 
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.
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.â
