a companion discussion area for blog.codinghorror.com

Rainbow Hash Cracking


#81

So, having read all this, what is the BEST method for password encryption? I don’t think anything will be 100% secure, nothing ever is - you just make it as hard as possible.

Everyone’s got to agree on something…the BEST and HARDEST method.

Besides, you can salt and hash all day long, but without add_slashes to stop sql injection…anyone can get your hashes, regardless and use the methods mentioned.


#82

Would there be a point in using really long salts? Like 10k, 10m chars or worse? The time to authenticate a login request would not take that much longer, but generating a rainbow table would take a lot longer, wouldn’t it?


#83

one useful idea for non-us users is to use non-english alphabet characters that are on our keyboards, but not a USA one. Most of the online hash libraries do not include them.


#84

Ok…

The rainbow Attack is used to compare “a List” of hashed passwords against a known list of hashes.

Basically the rainbow-table is the solution to the function

MD5(secret) - Hash

Now you are able to look up a result and retrieve the secret needed to generate the result. It takes a “fair” amount of work to generate such a table.

If you change the function to include a salt, then you would be forced to generate a new table for each salt. That means a “plain old” brute force would be much more adequate, since it would stop once the password is retrieved, and no more CPU power would be wasted on generating new hashes…

The reason for a hash is to make those precomputed lists “invalid”. And its achieving that exactly.

Also the “insane” memory requirements for the rainbow table would be gone, and the whole problem would be raw cpu power.

The suggestion with the “public key, without a private counterpart” is a completely different aproach. It introduces a NEW FORMULA into the mix. There is no precomputed solution table for your public key. Its safe to hand it out, and without the private part, there is “no known” way to reverse it… Heck… you can even hash the password, and then one-way encrypt it symetrically…

Hope this makes sense… :slight_smile:


#85

Ok, enough of this sillyness

You keep the salt string in an encrypted file on the server.

In Windows you use the user key and machine key to encrypt it - so only this machine and the user IIS is running under can unencrypt it.

That way no user can unencrypt it, and if it is copied to another machine it cant unencrypt it.

Next step

Pick the salt such (I am using C#)

String salt = “Hey user {0} ThIs_is a pretty %@%^)() strong salt for the PaSsWoRd {1}”;
String Salted = String.Format(salt, UserId, Password);

You can also break the hash into parts - you decide how many, where and what lengths, then sprinkle those parts into the salt.

Remember this isn’t cryptography - it is hashing - you just need a secure way to store and verify passwords. The above is plenty secure.

Pick a salt based on the text of a book - use a whole page of text - a good page from The Amateur Emigrant by Robert Louis Stevenson with the hash sprinkled among the text will work nicely.

Store the SHA512 (space is cheap) value of that and it will NEVER be rainbowed.

Also you never hold the password pass that point - you store the SHA512 hash - you compare the SHA512 hash.

Never use unencrypted cookies. Bad, bad developer. Best is to store a hash on the users machine - use the hash to lookup the users session data. This hash can be based on time given out, users IP address, anything you want to lock it down, but use a nice salt for it too.

String salt = “This is a salt string for a cookie created at {0} for the user {1} at IP address {2}.”

Where {0} is date time and {1} is the user name and lastly {2} is the users IP address.

Again, it is best to use a large salt. (Larger than the example). IP addresses can be shared - so you need to think of other properties to add. Think of all the data you get from a browser.

This isn’t rocket science people, basic security 101.


#86

ICR - in relation to:

Anon - “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.”

If you know the salt, say ‘w4x’ … and the max length password is 3… you generate a length table of 6 with $hash(w4x[XXX]).


#87

The thing with Rainbow tables is that they are just a brute force attack with precomputed values but note if they have the hash value they can always produce the original input given enough time and resources.

So you have four ways of making your system more secure

  1. make the password more complex so that the dehashing takes longer (either by forcing users to use a more complex password, or by adding a site wide salt)
  2. add a salt so that the raw original value is useless (i.e. it’s not the password, it’s a value that the password can be computed from) , a simple non-random salt is obvious and can easily be removed
    but MD5(MD5(salt) + MD5(password)) is much more difficult to de-salt
    and a per-user salt very difficult to remove
  3. protect your hashes (and salts)!
  4. Use public key encryption, this makes calculating the password from the stored value practically impossible

#88

md5_encrypt($plain_text, $password_e, $iv_len = 16)
{
$plain_text .= “\x13”;
$n = strlen($plain_text);
if ($n % 16) $plain_text .= str_repeat("\0", 16 - ($n % 16));
$i = 0;
$enc_text = get_rnd_iv($iv_len);
$iv = substr($password_e ^ $enc_text, 0, 512);
while ($i $n) {
$block = substr($plain_text, $i, 16) ^ pack(‘H*’, md5($iv));
$enc_text .= $block;
$iv = substr($block . $iv, 0, 512) ^ $password_e;
$i += 16;
}
return base64_encode($enc_text);
}

/*


#89

This article was featured over at slashdot, nice one Jeff.

I’d like a quick question answered…
If the salt is generated completely randomly for each password, how is the user supposed to log in if the system can’t recreate the same salt at logon? It’d need to be a static function that changes based on user input.


#90

“If the salt is generated completely randomly for each password, how is the user supposed to log in if the system can’t recreate the same salt at logon?”

The salt is stored plaintext. Usually just prepended to the beginning of the resulting hash.

The salt doesn’t need to be secret at all.


#91

For individual users, it is simple to protect yourself - use a password or pass phrase 15 characters or longer. Such a password cannot be stored in NTLM - you will receive a warning when changing to it that ‘the password may not be compatible with older software such as Windows 98.’ NTLMv2 passwords, which do not share this vulnerability, can be up to 128 characters in length.

So oddly, enough, “12 monkees type Shakespeare!” is more secure than “#hG0(;mjH3$=ZZ”. And easier to remember.


#92

after having read some of this, in particular PES’s suggestion (“Would there be a point in using really long salts? Like 10k, 10m chars or worse? The time to authenticate a login request would not take that much longer, but generating a rainbow table would take a lot longer, wouldn’t it?”) and thinking a bit about some of the other issues, here’s my suggestion for how to do it:

the string to be hashed:

faily-long-static-salt + username + username + username + … + username + password + password + … + password

and this is the good bit (possibly – looking to see if it is in fact a good idea): use more than one hash algorithm, two or three different hash algorithms, and store each of the hash results. using several different hash algorithms will stop pretty much entirely any possibility of a collision string working for the attacker – so they must find the actual string which was used rather than one which results in the same hash value (which is the problem, I think, with PES’s suggestion possibly).

i don’t know. this is all most head jarring. maybe a long input string like the one i’ve described above doesn’t make much difference?; that information is in the code, and once known, doesn’t help. generating a 100 hash values from input strings of 10,000 characters long costs much the same as generating a 100 hash values from input strings of 5 characters long. making the input string long in the way i and PES was suggesting doesn’t increase the number of possible input strings really – it shifts them but doesn’t increase them. yup, so my post was a complete waste of time i think.


#93

And crack xls files? :stuck_out_tongue:

Ernest Schuetz


#94

brian:

“If the attacker has multiple hashes a prefix/suffix salt does no good. Because after the attacke cracks two hashes:
abc$12Password
abc$123IlikePoneys”

This is where you are wrong. There are other reasons to have a per-password seed (which doesn’t depend on the password), but this is not one of them. What you’ll get when you crack the hash is not “abc$12Password”, but “()#$!@# D@#$” that just happens to hash to the same value.

Again: HASHES ARE BY DESIGN NOT REVERSIBLE. Multiple password+salt combinations will lead to the same hash. This is, in fact, why rainbow hashes work: you don’t need to map each and every possible password of each and every possible length to its stored hash, you just need one of the possible passwords for each possible stored hash, which is many orders of magnitude smaller in scope!

If you reverse-hash 1000 passwords which all share the same seed, it is still unlikely that the seed will be “obvious”. Depending on the specific hash algorithm, there could be a million possible “solutions” to each particular hash, and so chances are you won’t even hit the salt in those 1,000 solutions!

Consider the simple ASCII checksum hash (which of course wouldn’t be used in a security setting I’d hope, but which illustrates the point): “abc” and “cab” and “aad” and “daa” all have the same hash value. In that particular hashing algorithm, “saltpassword” might be the original salted password, and “passsaltword” might be the solution for one of the hashes, or even “psassbwolsd” (the two words intermingled and the “a” and “t” shifted to “b” and “s”). It’s unlikely you’d be able to deduce that putting “pawwsord” into the algorithm will validate your login there.


#95

Why not interleave the salt with the password …

so salted_password = (salt_character_1 + password_character_1 … + salt_character_n + password_character_n)

When length(salt) length(password), repeat the characters of either the salt or the password (whichever is shorter) until length(salt) == length(password).

It seems like this approach would make it impossible to discern patterns in the hashes, and thereby determining what the salt is.

Oh well, probably is very naive, and won’t work; but just my $0.02.


#96

I agree with Aaron G,

I always salt the password with something more than a default salt or a salt based off of the username or password, (as someone suggested).

You need to base your salts off of something that is NOT also stored with the password data. Such as the users Browser + the current time in India. OR even better, make a salt formula that changes over time AND uses random stuff like the time.


#97

Personally, I use a custom encryption/decryption algorithm which spits out a base_64 encoded string that was created by applying an internal key. After which it is hashed with a salt taken from a piece of data found in all user rows, (ie first 3 letters of their username) but doesn’t by itself indicate it is to be used as a the salt.

Even if the bad guys are able to figure out the salting method used and rainbow crack a users password, they end up with a base64 encoded string wrapping an extensive encryption algorithm. Forcing them to have to figure out how to reverse engineer my custom encryption algorithm before they have a usable password.

The source of the class I wrote to handle this process is also encrypted so that will need to be deciphered before they could use it to help reverse engineer the encryption. The method used to encrypt the source is completely different.

Basically, it is going to take someone a really long time, per each password, to crack my users passwords, even if they are sitting on my terminal logged in as root.

Layers of security, that’s what it is all about.


#98

How to make passwords (more) secure:

  1. Use two different hashing algorithms, this renders collision attacks useless. For example, use MD5 and SHA1 and make sure both hashes match the user’s input for a successful login.
  2. Generate two random salts containing at least one special character of at least eight characters long for each user. Apply one to the MD5 and one to the SHA1. It’s okay to store these in the database.
  3. Apply a static, site-wide salt to the password, make this at least 8 characters long. Store this password in a protected directory in the application, not the database.
  4. Run the password through their respective algorithms many times, at least 1000. This makes the act of generating a rainbow table extremely expensive on the attacker.

If you follow these steps you will have a password system that:

  • Is immune to collisions
  • Requires the attacker to get your database and your application code. At this point you probably have more to worry about than passwords being discovered.
  • Forces the attacker to spend considerable resources cracking the password. Each user’s password will be at least 16 + minimum password length (suggested at least 6) characters long. Generating a rainbow table going 22 characters with special symbols included will take forever. On top of this, the attacker spends 1000 times as long as it takes normally to generate this rainbow table because of your iterations. 1000 times a 22 character length rainbow table is not a quick process.
  • Needs a new table for each user.

#99

I love people. They whinge about the “sillyness” and then propose convoluted techniques for generating a 512-bit salt which are guaranteed to be less random (and thus less useful) than simply grabbing 512 bits out of your nearest cryptographically acceptable random number generator. (Building a cryptographically acceptable random number generator is hard, but no amount of hashing text and mucking around with XOR will do the job.)

FYI if you’re using C, then rand() does not count. If you’re using a web framework, consider carefully checking how it generates its random numbers.

Encryption - the only topic that beats religion and politics for inspiring the ignorant to claim to be geniuses. :wink:


#100

so what if you were to both salt the password (before and after) and pick, say, 15 letters that get replaced by different symbols?

so, username hotch, password 46hh78iuan would enter into the database (pre-hash) with password “hot-46%%78i*)@-ch”

so, h is replaced by %, u by *, a by ), n by @, first 3 letters of username are put before pass, remainder of username is put after… this seems like it would be nearly impossible to crack, especially if the hacker doesn’t know the scheme. for even more security you could have the replacement characters determined by some function of the username, or even a function of, say 3 characters of the username, so that your chosen characters are replaced by 3 different characters based on a cypher which would make my 9-char alphanumeric pass into a 25 char extended pass BEFORE including the prefix/suffix salt, with that included we’re up to 32char.

or, why not build your own hash from scratch?

the real question is, what kind of impact would these security schemes have on your server?