Rainbow Hash Cracking

Obviously salt doesn’t protect you against rainbow tables (because rainbow tables are just memoized brute-forcing), but sufficient salting makes the attack infeasible. No-one has 100-character tables.

Kevin Nisbet:

Thanks for your response. Please let me respond to your claims.

Regarding: “I really must dispute the effectiveness of this technique. It is better than storing just the MD5, but I don’t think by much.”

First, my using MD5 is merely a continuation of Jeff’s examples from the original article. When you see MD5, please understand that it represents the hash function of your choice.

Second, the effectiveness of salting is not in dispute. It is a well-understood, well-studied method of making precomputed-dictionary attacks impractical. If you disagree on this point, please do some homework on salting before replying.

Third, salting does not make it impossible to mount offline attacks against a password database; rather, salting makes such attacks more costly because it forces each password to be attacked independently. That is, it raises the cost of a precomputed-dictionary attack on the entire database to the point where it exceeds a the cost of attempting to guess each password in the database individually.

Regarding: “It’s one of those, what happens when the cracker has the table, and the begining of every password just happens to begin with another column in your password table.”

What happens is that the cracker is forced to guess each password individually, and that’s if he can live with obtaining only some of the passwords in the database. If he wants to get them all, he must brute-force the ones he can’t guess, and that’s expensive.

You can’t do better than that. If the cracker has your database, he most likely has everything else of value from your severs as well: your “hidden” keys, your “secret” hashing methods, your executable code to examine, if not your actual source code. Any bit of information your code had access to, the cracker now has. So, the only question that matters is, Given that the cracker has all the information you have, how hard is it for him to recover passwords? If the answer is that he must guess or brute-force every single password he wants, that’s as good as it’s going to get (for any password-based authentication system). You simply can’t do better.

Regarding: “I would think that a highly improved version of this would be you atleast store the MD5(MD5(salt) + MD5(password)).”

I’m sorry, but your new hash function adds no protection. The resulting hashed value depends only upon the salt and the password, the same as before. Remember, attackers are not trying to reverse your hash function; rather, they are searching its input space, and you haven’t enlarged the input space.

Regarding: “I can only assume you have this method in production, …”

Yes. And so does everybody else who understands that you can’t do better than forcing the other guy to guess or brute-force every single password he wants to obtain.

Regarding: “And also, at what level are you satisfied that as a worst case, the hacker has a botnet of computers at his disposal to run against your technique?”

Like I said, if the attacker can afford to brute-force a password, it’s his. If he has the resources to brute-force the entire database, he can recover all of your passwords. That’s just the way it is. There’s nothing you or I can do about it.

Cheers. --Tom

Where do I download that desktop background?

^.^

Actually the way you demonstrated on your blog would be a rather bad way of salting your passwords. When the password is broken by the rainbow crack deliciously-salty-{x} will show up in every password. What was offered in an above comment is a much better and more discouraging way of the MD5(‘deliciously-salty-’ + MD5(password));

Now here’s the thing, the real pro’s don’t need your fancy CD’s and lots of memory to break an NTLM hash. That’s already available on an “advanced distributed cracking system”. Check out plain-text.info. And learn to crack an MD5 hash in under a second.

Now I would still consider your proposed method a bad way of storing password all together. Why should we store password hashed with common algorithm such as sha1, md5, and ntlm.

What I much prefer is using a modern asymetric encryption algorythm. Generate yourself a Public / Private Key, throw out the private key, and you’ve got yourself your very own encrypted password storage. Worried about password being the same, then you properly use the salt (or md5) of the users username against the password before encrypting.

Really really worried, then you generate a private key for each user, which get’s stored seperately. Imagine the computing power needed to break that system with solely one piece of the picture. Then again, if you spend so much time designing password systems… don’t forget to design suitable software that uses them :wink:

As others have mentioned, salts have essentially two functions: 1) See to it that two users with the same password do not have the same hash value, and 2) Make the keyspace larger, so that brute-force cracking becomes infeasible.

That being said, for weak passwords that are, for instance, a variant of the username, or “password”, “asdffdsa”, “asdf123”, or any common english dictionary word, the salts do not help much. For instance John the Ripper (a password cracker), is extremely fast when it comes to prepending the salt to dictionary words, hash them and comparing the result to the stored hash value. It will likely find many passwords that “normal people” use, in just a few seconds.

By the way, keeping the salting function as a secret is OK, as long as your security does not rely on it, i.e., if the attacker discovers the algorithm, your hashes should still be secure. Similarly, if an attacker discovers the algorithm, you may as well assume that all attackers have access to it from that point on.

Jeff: My 5 year old son wants your wallpaper! Where can I get it? q;-)

A quick google search turned up http://umbra.shmoo.com:6969/ as a bittorrent source for a 34GB (!) rainbow table. I’m sure you can find a lot of other tables for download within minutes.

Me again. I’ve just read that you can also use ophcrack to only extract the hashes and save/copy it for later (eg. more expensive cracking on your own machine at home?). There’s even a website where you can submit a hash and it’ll return the password within seconds (using a 1.1GB rainbow table): http://lasecwww.epfl.ch/~oechslin/projects/ophcrack/

This has turned into a really interesting discussion on encryption. I do realize this is largely employed (and use to be what I did), but there is no reason to simply follow the status quo.

The only reason I suggested the MD5(MD5(salt) + MD5(password)) was to use a 64 character key as input to the hash stored in the database, based on the examples floating around. But you’re right in that just using a salt that matches or exceeds this total input would be just as good. And even better is a salt unique to each user, this was just a cheap way to get a long key off the top of my head. I’m moving towards using actual encryption algorithms for my own usage.

Regarding: “You can’t do better than that. If the cracker has your database, he most likely has everything else of value from your severs as well”

This is an increidbly bad assumption, because this represents a complete failure of your system as a whole. There are many examples where solely the database is lost (SQL Injection, lost backups, incorrect access rights, etc) which do not neccassarily compromise the code used by these systems. If your database and services are operating on seperate servers, each server needs to be compromised individually, which depending on your architecture could be extremely easy or quite difficult. Now of course, when designing said system always assume the worst from a security standpoint.

The more the attacker knows about your system, the easier it’ll be for him to break it en mass, don’t leave any windows of opportunity open. I’m tired of hearing about security breaches en mass in the news.

LM hashes are enabled on my company’s servers. They’re set to completely random unrelated passwords, though. :tpg: It’s no real deterrent, but it’s cute. =D

Hi,
To the hello kitty fans
http://www.lexode.com/galerie/galerie/p/t/ptiteclo/113308897248.jpg

@Heiko:
What you’re describing, assuming the private key is completely unrecoverable, is functionally equivalent to a one-way hash. This is the solution I am suggesting (though a weird way of going about it). If the private key is somehow recoverable, you still have the same problem I am trying to address.

Also, I think you’re confusing “hash” with “salt”.

@Thom:
Indeed, but you have to do that for each individual user’s salt. That makes the attack no better than a simple brute force against every user.

We’re talking about avoiding quick large-scale attacks with pre-computed, conveniently-packaged tables.

Hey Now Jeff,
I enjoyed reading another very interesting informative post by you. You really surprised me when you stated the time it took to crack the passphrase.
Thx,
Catto

A lot of commenters are saying something along the lines of “with a salt, you can just remove the first N characters, why is that secure?” I’m not positive on this, but I believe that, when you hash an N letter word, it’s not a letter to letter mapping. If the hash of ABC is XYZ, the hash of ZZZABC won’t be 3 letters and then XYZ. Adding letters to the password changes the entire hash. That’s why you can store the salt with the hashed password.

I had an interesting thought, when I read your line

“Passwords are never stored in plaintext. At least they shouldn’t be, unless you’re building the world’s most insecure system using the world’s most nave programmers.”

What would be more insecure: A system that uses name and password authentification but is easy to trick or a system that uses no authentification at all?

Kevin Nisbet:

Regarding my comment that, “If the cracker has your database, he most likely has everything else of value from your severs as well,” you wrote: “This is an increidbly bad assumption, because this represents a complete failure of your system as a whole.”

What other assumption can you reasonably have? That, if you system is compromised, the attacker will get the database but not the secret key? Or that, he’ll get the secret key but not the database? Or that he’ll get the database and the key but not the code that tells him how to use the key to unlock the passwords in the database? These are the “bad assumptions.” The only good assumption, the only assumption that lets you sleep soundly, is that the bad guys will be able to get any information that your system has access to. (Remember: a lot of bad guys are insiders.)

To look at it another way, if you can design your system so that your users’ secrets are safe even under the assumption that the bad guys have all of the information your system does, you win – and so do your users.

To go back to our running example, if (via salting) you can force an attacker who steals your user database to guess or brute-force each password he wants to discover – and you can – and if you can use a suitably expensive hash function (e.g., bcrypt) to prevent him from extracting all but the most-easily guessed passwords – and you can – and if you can offer this degree of security even when the attacker has all of the information that you do – and you can – why would you aim for anything less? What is the benefit to assuming that, if your system is broken, the bad guys aren’t insiders or won’t get everything they could?

Cheers. --Tom

@Andreas Krey:
No, that is a bad idea. Either the attacker will get your private key (more likely scenario), or you should have secured the database in the same way you secured the key.

There’s just no good reason not to use a hash.

Every time some article about encryption comes up on The Daily Worse Than Fuck or some computer blog, I am always horrified by the responses from software professionals. You guys need to stop underestimating the cost of a compromised password, and start reading Bruce Schneier’s work.

@LOL:
Pull your head out of your ass. How large do you think the rainbow tables need to be when a SHA256 hash is used as the salt?

Heh, what’s with the screenie? Did you lose a bet or something?

@Hinek:
A very interesting question, and one I have some experience with.

You’d think removing authentication would lower the bar for impersonation attacks, but also make people more suspicious of it happening. Unfortunately, in most cases you’d be overestimating the acuity of the users.

Seriously… people are dumb.

These rainbow tables, are they pretty much just for MD5 hashes? I know a lot of people moved over to SHA hashes a long time ago (myself included for my projects), and last I heard such a table had not been constructed for it yet. Is that still the case?