a companion discussion area for blog.codinghorror.com

Rainbow Hash Cracking


#101

OMG PONIES!
No seriously, where do I get that desktop wallpaper? :slight_smile:


#102

Hi all, when referring to NTLM hashes, there’s no need to crack the hash to obtain the cleartext password if you want to use those hashes to connect to services using NTLM authentication.

You can use this tool:

http://oss.coresecurity.com/projects/pshtoolkit.htm

and use the hashes directly on your windows machine, impersonating
the user whose hashes you’ve stolen. Then, outbound network connections will be authenticated using the hashes you just changed in memory using the tool mentioned above.
There’s no need to install a 4GB table, or crack the password if you have the hash(es) of the password and want to connect to a service that uses NTLM authentication.

More info an attack scenarios possible with the tools are detailed here:

http://oss.coresecurity.com/pshtoolkit/doc/index.html


#103

“Forcing them to have to figure out how to reverse engineer my custom encryption algorithm before they have a usable password.”

99% of all custom encryption systems are worthlessly insecure. Until it’s peer-reviewed, it’s a very, very bad idea to trust it. How do you know, for example, that your algorithm doesn’t /decrease/ password entropy? Are you sure it’s reversible?


#104

I think the concept of a “salt” is being extended and over used from its original intended purpose.

Salts were originaly created so that a user couldn’t make their password say “password” and then compare their hashed password against EVERYBODY elses and see how many folks used that same one.

Thats all it should do.

Now a by product of the Salt is that the password is a little longer, but you can accomplish this much easier by making the original password longer.

Precomputed lookups can be very easily foiled by simply making the password longer. For every extra digit added you are increasing the number of permutations by 100X and it doesn’t take that many digits to render Rainbow redundant. Jeff’s mentioned passphrases and that will be the next evolution in passwords.

In the end we are going to be carrying our ID’s on a physical device such as a mag card or USB drive or just forgo that entirely and use a biometric method such as a thumbprint reader. Public/Private keys will be the future and Rainbow cracker will be obsolete.


#105

The simple prefixing or sufixing of the real password with a salt relitivly pointless. The only function it serves is to increase the character length of the password.

In the scenario where this type of attack can occur the attacker A: has access to your live DB or B: attacker has a many stolen hashes C: attacker has only one stolen hash.

In A you are already screwed.
In B and C you have a bigger problem and are only trying to delay the attacker long enough that the hashes they have are not valuable.

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

it is clear what the salt was. It is what is common between them: abc$123.

If the attacker only has one hash it only delays for a while. If the cracked hash is (*%6ILikePoneys76

The attacker has it’s safe to assume that ILikePoneys is part of the password. Leaving less then 7! likely combinations.

Salting by rehashing the original hash will increase the time to crack, but only by double. If the hashes are cracked and they look like giberish, it’s safe to assume they were rehashed. So rerun the cracking tool and if the subsiquent cracked hashes are things like:
Admin0%$IlikePoneys
frankzappa%$YellowSnow

you immediatly know the formula is username + ‘%$’ + password.


#106

Correction:
If you rehash the attacker may see this after the first run:
Admin0%$987sgdsdfsd
frankzappa%$08hadsghhd6

Then will just need to strip the part that is different to crack.


#107

The algorithm is located and executed by my brain. God creates the best encryption.


#108

Is the password database on Windows open for reading by everyone?

What are the scenarios that Rainbow Hash Cracking is relevant for – just insiders with admin privilege? I know, you want to prevent that as well – I’m just missing context for this discussion.

PS I haven’t dealt with this topic since giving up Alpha/VMS admin back in 1992, so forgive me if this is a really dumb question…
(I’m mostly reading Jeff’s blog for the excellent UI topics).


#109

In the interest of password security and salting, I’ll add my own form of locking down passwords. Might be hackable still, but it’s gotta be a pain.

pw = md5(password)
add salt by either shuffling the result of the hash or taking some of the characters and adding them to the front and back
then for more salt do
if pw.length X
loop that takes the odd characters and appends them to the end of the hash till it’s X characters long, if it hits the end of the hashed string before getting to X length go again using the even characters
stored pw = md5(md5(user name)+md5(looped pw))

X is however long you want it to be, obviously the higher X is, the bigger the password is going to be, and the more difficult it is to use something like the rainbow tables.

I would personally love to see the work it’d take to reverse the hash into its password, especially if the hacker doesn’t have the prior knowledge about the special double-salting. About the only hope to break it in a reasonable amount of time is a lucky brute force attack.

Then again, maybe I’m crazy :stuck_out_tongue:


#110

When you push a cookie with a random MD5 hash on a client after verifying username and password with the database, clients can securely identify with that hash until expiry. The hash and IP address are checked on every request, the hash can not be generated again, or guessed, or ripped thru a hack and used from another client.

Any system with algorythms will be cracked, and sooner than we expect. Security must be brought back to the physical location of the client. Even using a plaintext password (sentence) of 12 or 15 characters in your system is allready much better than average, and not to difficult for the users, who are always right and always know best. We (specialists) are here to make their lives easy.


#111

Isn’t the definition of a hash an algorithm that produces a standard-length output from variable length inputs, making it essentially irreversible in the standard sense of plugging in the output and getting back the input?
The advantage of rainbow tables, it sounds like, is that because the hashes have been pre-calculated, I could look up a given output and get a list of all the possible inputs that would yield that combination. If I were using this as a password cracking tool, I’d still have to try each of those combinations (which might be many or few).
So adding salt to my inputs would significantly complicate (and/or slow down) rainbow table computations, but doesn’t increase the security of the hashing algorithm itself.
Nested hashes according to some secret algorithm/plan/pattern can make hash outputs useless to a would-be cracker only as long as they don’t know the pattern and hashing algorithsms that you’ve used.


#112

I already have the alpha-numeric-symbol14 rainbow tables and they work a treat :slight_smile: Cracked our old domain with 70 users in 40 mins. Nice :wink:


#113

That’s an interesting point about collisions Tom.
I’m still thoroughly confused over the proposed advantage of encryption over hashing.

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

That’s not how the hashing works. If the maximum password length was, for simplicity, 3, and I have a password of “die” and “pin” on their own they hash to “dp2” and “w2P” respectively. However, prepend a salt of “fi-” and they now hash to “pe3D34” and “lrZP2d”. The salt is added before the hashing, meaning you can’t just lop off the first x characters and then reverse that. “D34” doesn’t reverse to “die” and “P2d” to “pin” but instead something completely different.


#114

I have run into an several apps that “pre-salt” their password. It is fairly obvious that this has been done when you look at the list of passwords and see the same “X11C13E” or whatever at the beginning of the password.

The one app I had lost the password and was able to get into the app by just updating the table to X11C13E and drop the other 15 characters. I now had a blank password.

I would suggest a pre-salt based off something else in the table such as create date or the user id.


#115

Justin:

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

Isn’t this functionally identical to just doubling the length of your MD5 hash? I mean, either way the number of theoretical collisions goes down by about the same amount, right? Why complicate things further?


#116

If you store my hashed but non-salted password in your system and a cracker gets hold of the hash, they can now log in as me in other systems that also forgets to salt, using custom login tools that send the hash directly (without asking for the password to turn into that hash), under the (very good) assumption that I am using the same password elsewhere.

That’s why you should please not forget to salt.

/Mats


#117

Re: Tom Dibble

I suppose you could use md5 twice as long as they had different salts, or differed somewhere along the process of encrypting them. I prefer MD5 and SHA1, but your mileage may vary.

Another trick an admin could use to obfuscate a password in a database is to create two hashes and combine them in a way that looks like a single md5 hash. The only way to know the hashing function is to get the application code.

I think the moral of the story is simply do not use just a straight hash for protection. A salt and a few iterations is enough to deter all but the most persistent attackers as long as your application code doesn’t become known.


#118

(appending)

…also assuming that it is the same hashing algorithm in use on those other systems of course.

Also, if the cracker gets my unsalted hash from some sloppy system, they can brute-force/dictionry attack it to find an input that gives the correct hash (as noted by other commenters, the chances that hit will in fact be my password are small) and then just use that password to log into other sloppy (unsalted) systems where sloppy old I have used the same password - without even using a custom login tool.

This is the reason why a salt can’t be replaced by a longer password - even with a longer password you still need the salt to prevent the cracker from impersonating the (sloppy) user on other systems.

/Mats

/Mats


#119

Haven’t read all the comments, someone may have already pointed this out… If I am remembering correctly, the purpose of the salt is to combat a dictionary attack checking the stored pw hash against a list of hashes for commonly used passwords.


#120

Tom
You miss the point. The cases that an attacker would use this method, are cases where the attacker has access to the hashed passwords. Having a list opens up the ability to compare various ‘reversed’ or ‘cracked’ or whatever passwords to each other. If a salt is not random, then i would think it would become apparent.