1 More on Hashing

Your remarks on hashing passwords are incomplete.

First, you should use a different salt value for each user. If you use the same salt each time, then an attacker can discover users who have the same password, which probably means that it’s a common one and they should concentrate on cracking that one.

Second, you have to assume that an attacker who has compromised your system and has got your user database has also got your salt values, so they can use them to try a dictionary attack against your users’ passwords. To help to prevent this, you should use a hashing algorithm that has been deliberately designed to be slow and inefficient, such as bcrypt.

posted at 07:02 am on February 22, 2011 by drplokta

2 Collisions

I’m no expert, but doesn’t “This means that multiple inputs could theoretically produce the same result…” contradict the idea of collision resistance?

posted at 07:07 am on February 22, 2011 by Stephen Hampshire

3 collision

No. Collision-resistance merely means that there’s no way of producing a collision that is simpler than just trying different inputs until by accident two hash to the same value.

Since the output, the hash, is generally shorter than the input. (typically the input can be any length while the output is fixed-length), there must be collisions.

Consider it with a theorethical (too small!) hash that is fixed-length at one hex-character.

There’s only 16 possible hash-values, so you MUST get a collision if you hash 17 different strings, and likely you’ll get one much sooner.

The same thing applies if the hash is larger, it’s just that you need to hash more stuff before you get a collision – and if the hash is large enough, then “more stuff” becomes “unreasonably much stuff”

For example, if the hash is 128 bit, and truly collision-resistant, then you’d expect to have to try to hash aproximately 2^64 different strings before you’d get the first collision. (on the average, offcourse you could get lucky and get a collision after the first 2)

Since 2^64 is equivalent to hashing a billion strings every second for slightly more than 200.000 years, this is unlikely to happen in practice. (and by the time computers are fast enough that it could be provoked, we’d need a bigger hash)

posted at 07:28 am on February 22, 2011 by agrajag

4 Raising awareness = good, advice = bad

It’s great that ALA decided to publish an article about security and password storage, because generally the awareness among web developers is rather low.

However, the advice about salting is a little short and doesn’t really explain in-depth how to go about storing the salt. In that, I agree with commenter #1. But the real problem with this article is that it’s giving bad advice! There have been several incidents in recent news of sites that were using simple hashing mechanisms to store passwords where people stole the databases and retrieved a lot of passwords.

Nowadays hashes can be calculated at amazing speeds and there are tools that make this very easy to do. Combined with a dictionary-based attack, this allows attackers to retrieve a password rather quickly. There are standardised functions for safely storing passwords like the UNIX crpyt() function that every web developer should know about.

Why use crypt() and not roll your own? Well, crypt() has many advantages:

• It is easy to make mistakes in rolling your own. Smart people have put a lot of thought into these functions. and they are more likely to be secure than whatever you might come up with, unless you’re an experienced security researcher.
• Crypt() bindings are available in almost every programming language. This makes it a portable way to store passwords, and will allow you to easily share your database with programs written in different languages.

• The crypt() format is forwards-compatible; you can upgrade to a stronger mechanism transparently and passwords encrypted with an older encryption algorithm continue to work. As people log in, you can rehash their password using the new mechanism.

posted at 08:09 am on February 22, 2011 by Peter Bex

6

Lyle, thanks for your reply.

The original DES implementation of crypt() is weak and broken indeed and it needs to be stressed that people shouldn’t rely on that algorithm anymore. However, all modern systems implement either OpenBSD’s blowfish-based algorithm or RedHat/Ulrich Drepper’s SHA-2-based algorithms, both of which are quite strong.

I think avoiding crypt() just because an older implementation is broken is unneccessary. In fact, exactly because algorithms become weaker as time passes it’s a good idea to use crypt(), because of its modular design. Just upgrade the system’s crypt and voila, all your applications suddenly have stronger hashing capabilities, with complete backward compatibility for existing passwords.

You mention that these password crackers are specifically for crypt() output. Indeed, John the Ripper is by default targeted at OS-specific algorithms, but it can be easily modified to target custom salted SHA-1 hashes

The above link shows that this person was able to get 2,900 guesses per second from their modified JtR on a plain salted SHA1.

So, yes, JtR and other crackers are aimed specifically at standard operating system algorithms, but that just proves my point: these standard algorithms are constantly under close scrutiny. This means that their secure status is well-known and you can safely rely on using them. When they are broken it will be pretty widely known and new algorithms will be replaced, which you can easily upgrade to because modern crypt() is inherently modular.

Upgrading your own system will be much harder unless you’ve given this serious thought. And once you’ve given it serious thought, you’ll probably end up with a similar design, so why not save you the hassle and just use crypt()?

Finally, you advocate storing a global salt value, but that’s dangerous advice. If the database can be stolen, it’s very likely that your configuration files are compromised as well, and any global salt can easily be extracted from the configuration files.

In fact, if you were to use only a global hash value, you can immediately see from your database when two people are using the same password (because the same salt is concatenated to the same password this will yield an identical hash value). Generating a custom “Rainbow Table” given a known salt is also pretty easily done, and the passwords in your database can be cracked in parallel. If the salt is custom per hash, like with crypt(), each password must be cracked separately.

posted at 10:38 am on February 22, 2011 by Peter Bex

8

“I think we can all agree that hashing is better than not hashing, and salted hashing is better than straight hashing.”

Definitely agreed. That said, if the salt is unknown as the password is, that also makes hacking significantly more difficult. For example, simply salting a password with a user’s name is a fairly standard protocol, even if it’s not the best; at least it makes the salt unique per user.

A lot of people advocate using random salts, which generally fall into 2 categories. First is those that are completely random, and thus must be stored along with the password. This approach is very difficult to beat, provided the method of salting isn’t known to the database, but only to the application (for example, if the attacker sees the salt in the database, he will probably try something like simply concatenating the random salt and the password first).

Another option is to use a salt generated in such a way that it’s unique per user, but isn’t the user name, and isn’t stored in the database. One example I’ve seen involves creating a random variable seeded based on something (like, say, the length of the user name) that always returns the same value, and concatenating that with the user name.

All of these, though, are predicated on the hacker not being able to access the application code. If he can, then it doesn’t matter how you hash and salt.

Good article. I think a lot of people will find it useful.

posted at 11:38 am on February 22, 2011 by Othersider

9

Lyle,

I agree that storing a separate global salt is a good additional layer of security if you’re concerned about SQL injection or when the database server is reachable through the internet, since those two scenarios are about the only ways someone could get to the database without also having access to the webserver’s files.

You mention that if this happens, we should slow down the attacker as much as possible. This ties in to the very first comment here by drplokta; systems like crypt() (or bcrypt as drplotka mentions) don’t just salt the passwords, they also stretch them. This effectively lengthens the password in such a way that cracking one password takes longer. You can do this through applying the hashing function for thousands of iterations or more. This could reduce the JtR example above from 2,300 attempts per second to several seconds per attempt, if you want! I’m sure you agree this is preferable to hashing just once.

In fact, that’s what crypt() does. The modern implementations I mentioned in fact even allow you to tweak how many iterations it should use. This allows a system administrator to compensate for Moore’s law; as CPUs get faster, the administrator can just tune the number of iterations. The cool thing is that the modular syntax of crypt() hashes allow you to do this also without having to rehash existing passwords. This allows you to implement your own policy for expiring passwords hashed with older algorithms and upgrade to a more secure system at your own pace.

posted at 11:40 am on February 22, 2011 by Peter Bex